framed quadtrees

So it seems to me that framed quad-trees are used in this paper because the cells of the quad-tree itself are the nodes that are used for pathfinding in their experiment. Typically quad-trees in games are a way of optimizing rendering. Pathfinding is generally done either on the actual world polygons or on a tile-based representation of the map. Searching by either of those methods doesn't result in the non-optimal paths that they generated by using the quadtree cells as search nodes.

Remember that the problems being solved in that example are for robotic pathfinding through regions that it doesn't fully know about. AI agents in a game almost always have full knowledge of the world when they are planning paths.

-me

On the game I work on (should be out in Q4, yay!) we investigated the use of quadtrees to save some space compared to a top view grid, but we got way better result using nothing but convex polygons. They are way more precise and can cover narrow areas without generating a crazy amount of nodes.

Hope this helps

Eric

The naive application of any technique will lead to suboptimal solutions in most cases. Quadtrees (or any other tree structure) and convex polygons are both just tessalation methods, with pathfinding performed on the tesselated surface. If you simply used the quadtree depicted above, without first optimising its tessaltion of the space, then certainly you would expect a suboptimal path when you applied pathfinding. A hand-crafted tesselation is certainly going to perform better. However, if you merged neighbouring leaf nodes in the quadtree to form a minimal set of convex polygons (or just used a k-d tree to start with with convex leaf constraints), then you could automate the tessalation process and achieve comparable results to hand-crafted tesselations, with less construction time.

Timkin