Sign in to follow this  

Spatial Partioning Schemes For Path Graphs

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

First, if this topic would be better placed in the Artificial Intelligence section I apologize. I figured since it would focus on spatial partitioning it would be more appropriately placed in this sub forum.

Anyways, I recently wrote a simple path graph that used A* to provide efficient navigation through my world. It is currently a bit unoptimized for a few reasons, the biggest being a lack of spatial partitioning. There are some support functions which are vital in determining new paths based on game events/behaviors. At the moment, these functions basically just determine the closest node, or most appropriate path given a position in world coordinates, such as the following.

Node FindClosestNode(Vector3 pt);
NodePath FindPath(Vector3 pt, Node goal);
NodePath FindPath(Vector3 start, Vector3 end);

Now obviously, calculating the squared distance in a brute force loop isn't an economical way to do this. Unfortunately, when thinking of schemes I've used in the past, nothing really jumped out at me.
There are two major concerns that differentiate path nodes from typical objects thrown into a broad phase. One is that path nodes don't have any volume, they are merely points in space. In addition, they are more or less static, and there is never any need to determine collisions between the path nodes themselves.

We can rule out a Sort and Sweep, since the path nodes are basically static and we aren't concerned with intersections between them.
A bounding volume hierarchy would be an interesting experiment, since the arcs could form a merged AABB that is recursively split. However, this seems like it might result in very deep traversals for large paths.

Currently I'm leaning towards a finite sized grid, using fat objects or forcibly checking all the surrounding cells. The idea is to cast sphere with a sufficient radius at the passed in position into the grid. If no overlaps are found, search the neighboring cells until an occupied cell is met.

So...to anyone who has written a broadphase for a path graph before, what spatial partitioning scheme would you recommend?

Share this post


Link to post
Share on other sites
First off, the nodes in your pathfinding graph need not be points in space; they can be regions of a navmesh. Then your problem is not to determine the closest point, but to determine what region you're in. Presumably you have infrastructure for this; if not, a BVH or quadtree should be reasonable. Second, adjacency lists should be precomputed, so you shouldn't have to do these sorts of queries within your A* search.

Share this post


Link to post
Share on other sites

This topic is 2341 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.

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