[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /feed.php on line 173: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /feed.php on line 174: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums Falls 2011, sponsored by Google 2010-02-26T04:49:31+00:00 http://forums.aichallenge.org/feed.php?f=8&t=334 2010-02-26T04:49:31+00:00 2010-02-26T04:49:31+00:00 http://forums.aichallenge.org/viewtopic.php?t=334&p=1727#p1727 <![CDATA[Re: Chambers, dead ends, and graphs with cycles]]> Statistics: Posted by grogers — Fri Feb 26, 2010 4:49 am


]]>
2010-02-25T13:26:35+00:00 2010-02-25T13:26:35+00:00 http://forums.aichallenge.org/viewtopic.php?t=334&p=1684#p1684 <![CDATA[Re: Chambers, dead ends, and graphs with cycles]]> Statistics: Posted by Maxime81 — Thu Feb 25, 2010 1:26 pm


]]>
2010-02-25T07:38:20+00:00 2010-02-25T07:38:20+00:00 http://forums.aichallenge.org/viewtopic.php?t=334&p=1672#p1672 <![CDATA[Re: Chambers, dead ends, and graphs with cycles]]> Statistics: Posted by analyst74 — Thu Feb 25, 2010 7:38 am


]]>
2010-02-24T04:19:07+00:00 2010-02-24T04:19:07+00:00 http://forums.aichallenge.org/viewtopic.php?t=334&p=1619#p1619 <![CDATA[Re: Chambers, dead ends, and graphs with cycles]]> Statistics: Posted by Maxime81 — Wed Feb 24, 2010 4:19 am


]]>
2010-02-24T00:52:15+00:00 2010-02-24T00:52:15+00:00 http://forums.aichallenge.org/viewtopic.php?t=334&p=1614#p1614 <![CDATA[Re: Chambers, dead ends, and graphs with cycles]]>
The scenario I've described above (the very inaccurate tree-based calculation) is exactly the reason I decided not to forgo chamber mergers. The mergers are done by finding the lowest common parent chamber and relabeling all the cells as belonging to that chamber (this is where the square in O(n^2) comes from - may have to visit every cell an extra time per merger). To decrease number of chambers one has to merge (or keep track of), I try to recognize each corridor as a single chamber.

Anyway, since the mention of 'articulation vertexes' in the same thread I realized that my approach was actually rather naive. There's an algorithm () with O(n) runtime for finding articulation squares (squares that would disconnect the reacheable area), and then one needs just one more breadth-first pass (again, O(n)) to find all chambers (create a new chamber each time you step on an articulation vertex). Then iterate over the leaf chambers to find the longest path to the root.

On the whole, I find because of extra work my search ends up going 1-2 steps shallower in open spaces. But then, as montanalow mentioned, I find that this algorithm finds things that simple area calculation would recognize only 20 steps later, so on the whole I decided to stick with it.

Statistics: Posted by iouri_ — Wed Feb 24, 2010 12:52 am


]]>
2010-02-24T00:04:11+00:00 2010-02-24T00:04:11+00:00 http://forums.aichallenge.org/viewtopic.php?t=334&p=1612#p1612 <![CDATA[Chambers, dead ends, and graphs with cycles]]> Statistics: Posted by montanalow — Wed Feb 24, 2010 12:04 am


]]>