Version 0.51 of a pathfinding library for guiding objects in 3D space. It allows a "driver" to reach a "target" while avoiding "obstacles." Drivers, targets, and obstacles are defined by position and bounding volume.
New changes in 0.51:
1) Bugfix to handle unneeded assert introduced by waypoint collections in 0.5.
Major features:
1) Piecemeal pathfinding - It is a user-settable option to determine the number of seconds alloted for pathfinding each call.
2) Batch pathfinding calls - Multiple drivers are often pathfinding w/ the same subdivision of the grid at any given time. Huge performance savings can be had in both speed and memory by sharing occupied bin data.
3) Transformable waypoint collections (WPCs) - WPCs can be stored offline per obstacle in *.wpc.xml files, allowing quickly calculated avoidance of complex translating (
- Todo:
- and rotating) obstacles.
Brief description of how the pathfinding algorithms work: A driver, target, and obstacles are hashed to bins representing divisions of an axis aligned bounding box (aabb), which is set up by the user. With the pathfinding area divided into bins (graph nodes), various graph algorithms can be used. The spatial representations of the bins are boxes, and movement from a node is limited to its 26 neighbors (boxes adjacent to the 6 faces, 12 edges, and 8 corners). Movement can be limited further by disallowing movement through an edge or corner shared by an obstacle-occupied bin, or by eliminating diagonal movement altogether. A spline curve can also be created from the path's points. This spline is NOT guaranteed to avoid all the occupied bins that the regular found path did.
The smaller the bin size, the greater the likelihood of finding any existing paths from the driver to the target. Smaller bin sizes also mean using both more CPU time and memory. If a path is not found, the aabb can be subdivided to a finer granularity. The max # of subdivisions is set by MAX_SUBDIVISIONS.
- Todo:
- Obstacles can occupy multiple bins. The driver and target, however, are only hashed to one bin, regardless of their volumes. This can result in the driver not reaching its goal since the space it occupies may extend into bins outside the found path and where obstacles lie. Another result is that a path is only searched for to the bin containing the center of the target's bounding volume.
What this library can be used for: Turn-based games like Final Fantasy Tactics and
games where movement is limited and discrete.
What this library should probably NOT be used for heavily: Real time games with
multiple degrees of continous motional freedom. A pathfinding algorithm should
never be a programmer's first line of attack for finding a target in a real time
game. Steering behavious should be used first and can usually get the driver
"close enough." See http://www.red3d.com/cwr/steer/. Pathfinding should be used
when a driver is stuck (which can be determined by using or overloading the
isStuck() method in this class), or needs a foolproof path that a graph algorithm
can provide. With this library, however, if the bins (graph nodes) do not divy
the space small enough, a path is not guaranteed, even if one exists, because
obstacles could be hashed to bins that may actually have enough room for the
driver to get through.
--------------------------------------------------------------
Below is one correct order of operations to find paths from a driver to a
target with potential obstacles in the way in 3D space (see method descriptions
below for more detailed dependencies):
Grid::init()
g_initialGrid->setCorners()
g_initialGrid->setNodes()
Grid::resetAllGlobalGrids()
add obstacles to the set of volumes passed into setNodes() g_initialGrid->calcOccupiedBins(); //also call for any subdivisions setDriver() setTarget() calcDriverAndTargetBins() findPath() resetPathfindingVars() findPath() ... Grid::shutDown()
Upcoming in 0.6
Allowing triangle meshes as a search space, instead of just grids.
1.8.6