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