 |
| Spatial Thinking |
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.
