Part of the OpenSkyNet project - http://openskynet.sourceforge.net/
Copyright (C) 2004-2012 Dylan
Blair
email: dblair@alumni.cs.utexas.edu
This library is
free software; you can redistribute it and/or
modify it under the
terms of the GNU Lesser General Public
License as published by the
Free Software Foundation; either
version 2.1 of the License, or
(at your option) any later version.
This library is
distributed in the hope that it will be useful,
but WITHOUT ANY
WARRANTY; without even the implied warranty of
MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General
Public License for more details.
You should have received a
copy of the GNU Lesser General Public
License along with this
library; if not, write to the Free Software
Foundation, Inc., 59
Temple Place, Suite 330, Boston, MA 02111-1307 USA
Notes on building:
The unit tests were compiled and tested on
Ubuntu 10.04 (Lucid Lynx) using GCC 4.4.3 and Windows 7 64-bit using
Microsoft Visual Studio 8.0. The libs were built on Android using the
NDK, revision 6b, but I have not yet run the unit tests on Android.
Dependencies for the PF library (only
needed if WPCs are used):
TinyXML
2.5.3 (http://www.grinninglizard.com/tinyxml/)
Dependencies
for the unit tests:
CppUnit 1.12.1
(http://cppunit.sourceforge.net/cppunit-wiki)
Linux:
Run
make from the PF_API-v0.52 directory:
make CFG=[debug|release]
[PF_USES_WPC=1]
You must specify the configuration (CFG) when
running make. PF_USES_WPC is not required.
Windows:
A Microsoft Visual Studio
8.0 solution is provided.
Android:
An Android-friendly
folder hierarchy and makefile can be found under the Android folder.
Build using
ndk-build.
--------------------------------------------------------------
Notes on the library:
Version 0.52 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.52:
1) Verified libs build on Android
using
NDK
--------------------------------------------------------------
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.
--------------------------------------------------------------
Dylan Blair
(agn0stic3000)
agn0stic3000@users.sourceforge.net