Sign in to follow this  
Somnia

quad tree, path finding and object sizes

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this