Jump to content
  • Advertisement
Sign in to follow this  
zppz

framed quadtrees

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!