OpenSkyNet::PF::Manager Class Reference

#include <PFManager.h>

List of all members.

Public Types
enum	ALGORITHM { BFS, A_STAR, BFS, A_STAR }
enum	ALGORITHM { BFS, A_STAR, BFS, A_STAR }
Public Member Functions
	Manager ()
virtual	~Manager ()
virtual RESULT	calcDriverAndTargetBins (std::vector< Math::Point< int > > &drivBins_, std::vector< Math::Point< int > > &targBins_, bool calcPositions_=false, bool useInitialGrid_=false)
RESULT	calcDriverAndTargetBins (bool calcPositions_=false, bool useInitialGrid_=false)
const std::vector< Math::Point < int > > &	getDriverBins () const
const std::vector< Math::Point < int > > &	getTargetBins () const
const Math::Point *	getDriver () const
const Math::Point *	getTarget () const
const CD::Grid *	getGrid () const
void	controlDriverPath (Math::Path *&drivPath_)
bool	controlDriverPath ()
void	releaseDriverPath ()
bool	isDriverPathControlled () const
Math::Path &	getFoundPath ()
virtual bool	isStuck ()
virtual RESULT	findPath (Manager::ALGORITHM algo_=Manager::A_STAR, bool doUpdateMaxCorner_=true, double secsAllotted_=-1.0)
void	resetPathfindingVars ()
bool	isDriverBinOutsideGrid () const
bool	isTargetBinOutsideGrid () const
	Manager ()
virtual	~Manager ()
virtual RESULT	calcDriverAndTargetBins (std::vector< Math::Point< int > > &drivBins_, std::vector< Math::Point< int > > &targBins_, bool calcPositions_=false, bool useInitialGrid_=false)
RESULT	calcDriverAndTargetBins (bool calcPositions_=false, bool useInitialGrid_=false)
const std::vector< Math::Point < int > > &	getDriverBins () const
const std::vector< Math::Point < int > > &	getTargetBins () const
const Math::Point *	getDriver () const
const Math::Point *	getTarget () const
const CD::Grid *	getGrid () const
void	controlDriverPath (Math::Path *&drivPath_)
bool	controlDriverPath ()
void	releaseDriverPath ()
bool	isDriverPathControlled () const
Math::Path &	getFoundPath ()
virtual bool	isStuck ()
virtual RESULT	findPath (Manager::ALGORITHM algo_=Manager::A_STAR, bool doUpdateMaxCorner_=true, double secsAllotted_=-1.0)
void	resetPathfindingVars ()
bool	isDriverBinOutsideGrid () const
bool	isTargetBinOutsideGrid () const
Setup Operations
void	setDriver (const Math::Point<> *driver_, const CD::Volume *drivBoundingVolume_)
void	setTarget (const Math::Point<> *target_, const CD::Volume *targBoundingVolume_, float targetRadius_=-1.0f)
void	setDriver (const Math::Point<> *driver_, const CD::Volume *drivBoundingVolume_)
void	setTarget (const Math::Point<> *target_, const CD::Volume *targBoundingVolume_, float targetRadius_=-1.0f)

---

Detailed Description

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.

--------------------------------------------------------------

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.

--------------------------------------------------------------

---

Member Enumeration Documentation

enum OpenSkyNet::PF::Manager::ALGORITHM

Only breadth first search and A* are currently available.

Enumerator:

BFS
A_STAR
BFS
A_STAR

enum OpenSkyNet::PF::Manager::ALGORITHM

Only breadth first search and A* are currently available.

Enumerator:

BFS
A_STAR
BFS
A_STAR

---

Constructor & Destructor Documentation

OpenSkyNet::PF::Manager::Manager

(

)

END: algorithmic specific data members and functions

virtual OpenSkyNet::PF::Manager::~Manager

(

)

[virtual]

Manager::Manager

(

)

END: algorithmic specific data members and functions

Manager::~Manager

(

)

[virtual]

---

Member Function Documentation

virtual RESULT OpenSkyNet::PF::Manager::calcDriverAndTargetBins	(	std::vector< Math::Point< int > > &	drivBins_,
		std::vector< Math::Point< int > > &	targBins_,
		bool	calcPositions_ = false,
		bool	useInitialGrid_ = false
	)		[virtual]

RESULT OpenSkyNet::PF::Manager::calcDriverAndTargetBins	(	bool	calcPositions_ = false,
		bool	useInitialGrid_ = false
	)		[inline]

virtual RESULT OpenSkyNet::PF::Manager::calcDriverAndTargetBins	(	std::vector< Math::Point< int > > &	drivBins_,
		std::vector< Math::Point< int > > &	targBins_,
		bool	calcPositions_ = false,
		bool	useInitialGrid_ = false
	)		[virtual]

RESULT OpenSkyNet::PF::Manager::calcDriverAndTargetBins	(	bool	calcPositions_ = false,
		bool	useInitialGrid_ = false
	)		[inline]

bool OpenSkyNet::PF::Manager::controlDriverPath

(

)

[inline]

void OpenSkyNet::PF::Manager::controlDriverPath

(

Math::Path *&

drivPath_

)

[inline]

In this version, controlDriverPath() only tells the manager what path the driver is currently using (or 0 if none). It makes the isStuck() method return true if the driver is using the last found path as its own and the target has changed bins. In essence, this says that the path is no longer assured to reach the target. It does not "control" or modify any aspect of the driver's path in this iteration of the library.

void OpenSkyNet::PF::Manager::controlDriverPath

(

Math::Path *&

drivPath_

)

[inline]

In this version, controlDriverPath() only tells the manager what path the driver is currently using (or 0 if none). It makes the isStuck() method return true if the driver is using the last found path as its own and the target has changed bins. In essence, this says that the path is no longer assured to reach the target. It does not "control" or modify any aspect of the driver's path in this iteration of the library.

bool OpenSkyNet::PF::Manager::controlDriverPath

(

)

[inline]

virtual RESULT OpenSkyNet::PF::Manager::findPath	(	Manager::ALGORITHM	algo_ = Manager::A_STAR,
		bool	doUpdateMaxCorner_ = true,
		double	secsAllotted_ = -1.0
	)		[virtual]

Returns TARGET_NOT_IN_RANGE or DRIVER_NOT_IN_RANGE if the target or driver are not in world aabb range and PF_UNFINISHED if piecemeal pathfinding has not completed. Set doUpdateMaxCorner_ to true if the aabb has been translated but not otherwise modified. If the aabb HAS been modified in some other way (scaled, etc.), then Grid::setCorners() must be recalled first. The parameter secsAllotted_ specifies the number of seconds to allow for piecemeal pathfinding this call (< 0 means there is no time limit). This method is NOT guaranteed to return within secsAllotted_, but it will be close to that. If a call to this method is made, and pathfinding did not complete in the allotted time previously, then the first two parameters do nothing, and the previous pathfinding algorithm continues with the previous aabb.

virtual RESULT OpenSkyNet::PF::Manager::findPath	(	Manager::ALGORITHM	algo_ = Manager::A_STAR,
		bool	doUpdateMaxCorner_ = true,
		double	secsAllotted_ = -1.0
	)		[virtual]

Returns TARGET_NOT_IN_RANGE or DRIVER_NOT_IN_RANGE if the target or driver are not in world aabb range and PF_UNFINISHED if piecemeal pathfinding has not completed. Set doUpdateMaxCorner_ to true if the aabb has been translated but not otherwise modified. If the aabb HAS been modified in some other way (scaled, etc.), then Grid::setCorners() must be recalled first. The parameter secsAllotted_ specifies the number of seconds to allow for piecemeal pathfinding this call (< 0 means there is no time limit). This method is NOT guaranteed to return within secsAllotted_, but it will be close to that. If a call to this method is made, and pathfinding did not complete in the allotted time previously, then the first two parameters do nothing, and the previous pathfinding algorithm continues with the previous aabb.

const Math::Point* OpenSkyNet::PF::Manager::getDriver

(

)

const [inline]

Gets a pointer to the position that paths start from.

const Math::Point* OpenSkyNet::PF::Manager::getDriver

(

)

const [inline]

Gets a pointer to the position that paths start from.

const std::vector<Math::Point<int> >& OpenSkyNet::PF::Manager::getDriverBins

(

)

const [inline]

const std::vector<Math::Point<int> >& OpenSkyNet::PF::Manager::getDriverBins

(

)

const [inline]

Math::Path& OpenSkyNet::PF::Manager::getFoundPath

(

)

[inline]

Returns the last path found or a path with zero steps if none found.

Math::Path& OpenSkyNet::PF::Manager::getFoundPath

(

)

[inline]

Returns the last path found or a path with zero steps if none found.

const CD::Grid* OpenSkyNet::PF::Manager::getGrid

(

)

const [inline]

const CD::Grid* OpenSkyNet::PF::Manager::getGrid

(

)

const [inline]

const Math::Point* OpenSkyNet::PF::Manager::getTarget

(

)

const [inline]

Gets a pointer to the position that paths try to end near.

const Math::Point* OpenSkyNet::PF::Manager::getTarget

(

)

const [inline]

Gets a pointer to the position that paths try to end near.

const std::vector<Math::Point<int> >& OpenSkyNet::PF::Manager::getTargetBins

(

)

const [inline]

const std::vector<Math::Point<int> >& OpenSkyNet::PF::Manager::getTargetBins

(

)

const [inline]

bool OpenSkyNet::PF::Manager::isDriverBinOutsideGrid

(

)

const

bool OpenSkyNet::PF::Manager::isDriverBinOutsideGrid

(

)

const

bool OpenSkyNet::PF::Manager::isDriverPathControlled

(

)

const [inline]

bool OpenSkyNet::PF::Manager::isDriverPathControlled

(

)

const [inline]

bool Manager::isStuck

(

)

[virtual]

If using other means to reach a target, like steering behaviors, this method could identify when those means have failed, and pathfinding is needed.

virtual bool OpenSkyNet::PF::Manager::isStuck

(

)

[virtual]

If using other means to reach a target, like steering behaviors, this method could identify when those means have failed, and pathfinding is needed.

bool OpenSkyNet::PF::Manager::isTargetBinOutsideGrid

(

)

const

bool OpenSkyNet::PF::Manager::isTargetBinOutsideGrid

(

)

const

void OpenSkyNet::PF::Manager::releaseDriverPath

(

)

[inline]

void OpenSkyNet::PF::Manager::releaseDriverPath

(

)

[inline]

void OpenSkyNet::PF::Manager::resetPathfindingVars

(

)

Without resetting, the manager will remember the initial directions of paths found previously, consider them to have failed, and may try subdividing the world aabb (implemented) or

Todo:

attempting paths with different initial directions (not implemented). This method also stops any unfinished piecemeal pathfinding.

void Manager::resetPathfindingVars

(

)

Without resetting, the manager will remember the initial directions of paths found previously, consider them to have failed, and may try subdividing the world aabb (implemented) or

Todo:

attempting paths with different initial directions (not implemented). This method also stops any unfinished piecemeal pathfinding.

void OpenSkyNet::PF::Manager::setDriver	(	const Math::Point<> *	driver_,
		const CD::Volume *	drivBoundingVolume_
	)		[inline]

Sets the object that paths start from.

void OpenSkyNet::PF::Manager::setDriver	(	const Math::Point<> *	driver_,
		const CD::Volume *	drivBoundingVolume_
	)		[inline]

Sets the object that paths start from.

void OpenSkyNet::PF::Manager::setTarget	(	const Math::Point<> *	target_,
		const CD::Volume *	targBoundingVolume_,
		float	targetRadius_ = -1.0f
	)		[inline]

Sets the object that paths try to end at.

Parameters:

targetRadius_

if < 0, then the bounding radius is used. If the target bin is found first, then a path is considered found, regardless if the target lies within the radius. The radius acts only as an "early out."

void OpenSkyNet::PF::Manager::setTarget	(	const Math::Point<> *	target_,
		const CD::Volume *	targBoundingVolume_,
		float	targetRadius_ = -1.0f
	)		[inline]

Sets the object that paths try to end at.

Parameters:

targetRadius_

if < 0, then the bounding radius is used. If the target bin is found first, then a path is considered found, regardless if the target lies within the radius. The radius acts only as an "early out."

---

The documentation for this class was generated from the following files:

• Android/jni/Libs/PF_LIB/PFManager.h
• Code/Libs/PF_LIB/PFManager.h
• Android/jni/Libs/PF_LIB/PFManager.cpp
• Code/Libs/PF_LIB/PFManager.cpp