This topic is 4853 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I discovered the framed quadtree idea the other day and was wondering why I had never heard it mentioned in relation to games, like on this forum etc. Didn't even show up in searches of gdnet. Is it not suited to games for some reason I can't think of? http://www.frc.ri.cmu.edu/~ssingh/pubs/icra98FQD.pdf

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
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

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633301
• Total Posts
3011268
• ### Who's Online (See full list)

There are no registered users currently online

×