Jump to content
  • Advertisement
Sign in to follow this  

quad tree, path finding and object sizes

This topic is 3287 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 have been implementing a path finding system broadly along the lines demonstrated here: http://copperbit.com/?tag=actionscript So basically I start with a set of static level geometry which I use to create a quad tree and visibility graph. I've also made an A* searcher which seemes to be working well when it comes to solving the abstract problem of finding paths through the visibility graph. Two things I've having trouble with, both kind of to do with the fact that in practice we don't just want a path through a set of connected nodes but an actual physical path through the space. So for example when calculating the distance between nodes which you need to compute the G value for the node when using A*. At first I used just the distance between the rectangle mid points, but this can produce big overestimates when you would only need to travel over the corner of a very large node. So I changed this so that each node stores a path point which depends on the node the object is arriving from, basically when the objects G value and it's previous node is updated it finds the closest point on it's rectangle to the path point for the previous node. (Where the path point for the first node is just the starting position.) Does this sound reasonable? A more serious problem is how to use this system to handle objects of varying sizes. The visibility graph I'm using now just checks that nodes share a common edge, it doesn't actually guarantee that an object can get from one to the other. But this depends on the size and shape of the object. So I could either pass the object shape as a parameter to the search and adjust the visibility graph at each step to rule out nodes the object is too big to get too. But this sounds like it could be quite expensive and complicated. I'm not really sure how you'd do it, even the basic problem of taking a quad tree, two connected nodes and an objects bounding box and determining whether it's passable. But I also wondered whether this was necessary, since instead you could use the maximum level parameter when creating the quad tree to limit how small the passable nodes are allowed to be based on the object size. This would mean having a number of different quad trees for a set of stock object sizes, e.g humanoid, monster, dragon etc and make sure all your objects stick to them. I'm not really sure though whether limiting the node size kind of automatically solves this problem though.

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!