Jump to content
• What is your GameDev Story?

• Advertisement

framed quadtrees

This topic is 4916 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

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

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

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

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

Share on other sites

• Advertisement
• Advertisement
• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• Popular Now

• 12
• 15
• 14
• 46
• 22
• Advertisement
• Forum Statistics

• Total Topics
634054
• Total Posts
3015275
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!