This class implements an A* search algorithm for finding paths across terrain in 2-D. More...

Public Member Functions
	DtPathPlanner ()
virtual	~DtPathPlanner ()
virtual void	setPathMetric (DtPathMetric *metric)
	Sets the path metric class to be used to calculate the path.
virtual void	setNodeSpacing (double space)
	Set the spacing between grid nodes.
virtual void	setSegmentNodeSpacing (double space)
	Set the spacing between nodes on searchable vector features. (i.e. roads)
virtual void	setSearchAreaWidth (double width)
	Set the with of the area which will be searched for a path.
virtual void	setSearchAreaExtraLength (double length)
	Set the additional length (beyond the distance from the start to the goal) of the area which will be searched for a path.
virtual void	initPreferredSegmentMetrics (const DtRwVectorObstructionTypeList &segmentTypes)
	Creates a new set of DtRangeNetworkSegmentMetrics based on the preferred vector types specified in the list passed in and the node spacing.
virtual void	initImpassableSegmentMetrics (const DtRwVectorObstructionTypeList &segmentTypes)
	Creates a new set of DtNetworkSegmentMetrics based on the impassable vector types specified in the list passed in.
virtual void	setCrossCountryPenalty (double penalty)
	Set the penalty (in percent: i.e.
virtual void	setPhysicalWorld (const DtPhysicalWorld *physWorld)
	Sets the local physical world pointer.
virtual bool	makePath (const DtVector &start, const DtVector &goal)
	Generates a new path between the start and end vectors (in local coordinates).
virtual DtList *	path ()
	Returns the last generated path as a list of DtVectors in geocentric coordinates.
virtual void	interrupt ()
	Causes the path planner to be interrupted on its next call of checkInterrupt().
virtual bool	nodeVisited (const DtPoint &point)
	Returns true if the node is marked as visited.
virtual void	markNodeVisited (const DtPoint &point)
	Marks the node as visited.
virtual bool	nodeVisited (const DtNetworkSegment *segment, int position)
	Returns true if the vector node it marked as visited.
virtual void	markNodeVisited (const DtNetworkSegment *segment, int position)
	Marks the vector node as visited.
virtual bool	nodeSearchable (const DtPoint &point)
	Returns true if this node falls within the searchable extent.
virtual double	nodeSpacing ()
	Returns the node spacing.
virtual const DtPathMetric *	pathMetric () const
	Returns a pointer to the current path metric being used.
virtual const std::list < DtRangeNetworkSegmentMetric > &	preferredSegmentMetrics () const
	Returns a list of metrics which will return preferred segments.
virtual const std::list < DtIntersectNetworkSegmentMetric > &	impassableSegmentMetrics () const
	Returns a list of metrics which will return impassable segments.
virtual double	crossCountryPenalty ()
	Returns the cross country penalty.
virtual const DtVectorNetwork *	vectorNetwork ()
virtual int	findNumberOfNodesOnSegment (const DtNetworkSegment *segment)
	Determines the number of nodes that should be places along the specified vector segment.
virtual int	findSegmentPositionAndPoint (const DtNetworkSegment *segment, DtPoint &point)
	Returns the segment position of the point along the segment.
virtual DtPoint	findPointForSegmentPosition (const DtNetworkSegment *segment, int segPos)
	Returns the location of a node along the segment.
virtual DtPoint	findAdjacentGridPoint (const DtPoint &point, int xOffset, int yOffset)
	Returns the grid point the is <xOffset, yOffset> grid positions from the specified point.
virtual DtPoint	findNearbyGridPoint (const DtPoint &point, int corner)
	Returns the grid point position near the specified point.
virtual bool	checkNoGoVectorIntersection (const DtPoint &start, const DtPoint &end)
	Returns true if the segment from start to end intersects any no-go designated vector segments.
virtual double	calculateCost (const DtPoint &startPoint, const DtPoint &endPoint, bool checkVectorNetwork=true)
	Calculates the cost to move between these two points.
virtual double	estimateCostToGoal (const DtPoint &point)
	Calculates the estimated optimistic cost from this point to the goal.
virtual bool	isGoal (const DtPoint &point)
	Returns true if this point meets the goal criteria.
virtual bool	nearGoal (const DtPoint &point)
	Returns true if this point is within one grid square of the goal.
virtual const DtPoint &	goalPoint ()
	The goal point.
virtual void	addSolutionPoint (const DtPoint &point)
	Adds this point to the beginning of the solution route.
virtual void	clearStats ()
	Clears all the internal status variables.
virtual void	printStats ()
	Prints the status of the last calculation to the console.
virtual void	checkInterrupt ()
	Checks to see if the path planning should be interrupted, and throws DtPathPlannerInterruptedException if it should.

virtual void	nodeCreated ()
virtual void	nodeDeleted ()
virtual void	nodeExpanded ()
Static Public Member Functions
static int	round (double val)
	Utility function which takes a floating point number and does a standard rounding on it to get an integer.
Protected Member Functions
void	clearPath ()
	Deletes the current path.
virtual void	initNodeTable ()
	Initializes the table which tracks whether each grid node is visited or not.
virtual void	initTransforms (const DtVector &startPoint, const DtVector &endPoint)
	Sets up the transforms that go from local coordinates to the topographic projection we are using to do the planning.
virtual void	initGridExtent (const DtVector &startPoint, const DtVector &endPoint, double extraX, double extraY)
	Sets up the extent of the search area.
void	clearVisitedSegmentList ()
	Clears the visited segment list.
virtual void	optimizePath ()
	Modifies the current path by taking out redundant way points which will not change the layout of the path.
virtual void	setPathToTerrainHeight ()
	Modifies the current path by changing the altitude of each point to be the height of the terrain at that location.
virtual void	correctPathForTurningRadius (double turningRadius)
	Modifies the current path by moving points in the route so that the specified turning radius will take an entity moving along the path along the intended path, instead of overshooting the turns.
virtual void	printVisitedSegments ()
	For debugging.
virtual DtPoint	terrainPointToGrid (const DtPoint &terrainPoint)
	Translates a point in the local (aka terrain) coordinate system to the coordinates of the path planning grid.
virtual DtPoint	gridPointToTerrain (const DtPoint &gridPoint)
	Translates a point from the path planning grid coordinate system to the local (aka terrain) coordinate system.
virtual DtVector	setToZeroAltitudeTopo (const DtVector &localPos)
	Converts localPos to topo using the current localToTopoTransform, sets its Z value to 0, then converts in back to local and returns it.
Protected Attributes
const DtPhysicalWorld *	myPhysicalWorld
	Pointer to the terrain database.
DtList *	myPath
	List of DtVector objects which represent the calculated path.
bool *	myNodeTable
	Array that gets marked when a node is visited.
int	myNodeTableXSize
int	myNodeTableYSize
double	myNodeSpacing
double	mySegmentNodeSpacing
double	mySearchAreaWidth
double	mySearchAreaExtraLength
double	myCrossCountryPenalty
DtExtent	mySearchableExtent
	Percent penalty (0.0 ...) to penalize non-road travel.
DtPoint	myGoalPoint
DtPathMetric *	myPathMetric
std::list < DtRangeNetworkSegmentMetric >	myPreferredSegmentMetrics
std::list < DtIntersectNetworkSegmentMetric >	myImpassableSegmentMetrics
bool	myInterruptFlag
DtHashList	myVisitedSegmentList
DtCoordTransform	myTopoToGridTransform
DtCoordTransform	myGridToTopoTransform
DtCoordTransform	myLocalToTopoTransform
DtCoordTransform	myTopoToLocalTransform
unsigned int	myNumberOfCostsCalculated
	Local statistics.
unsigned int	myTotalNodesExpanded
unsigned int	myTotalNodesCreated
unsigned int	myTotalNodesPruned
unsigned int	myMaxConcurrentNodes
unsigned int	myTotalNodesInMemory
Private Member Functions
	DtPathPlanner (const DtPathPlanner &orig)
	Not Implemented.
DtPathPlanner &	operator= (const DtPathPlanner &orig)
	Not Implemented.

Detailed Description

This class implements an A* search algorithm for finding paths across terrain in 2-D.

It is used by the DtPathMovementController. The DtPathMovementController spawns a separate thread for the DtPathPlanner to calculate the best path.

Note:: The entity will remain in place while it is planning a path. If the terrain is complex, the distance to the destination is large, or there is not much available processor this may be a lengthy process.; Because this controller spawns a separate thread, the use of this controller breaks repeatability. See the repeatability section of the manual for more information.

Basic use of this class involves: 1) Calling setPhysicalWorld with the current DtPhysicalWorld from DtCgf 2) Creating and initializing a DtPathMetric by calling DtPathMetric::createPathMetric. The init() function should then be called on the metric. 3) Setting the parameters for the search using their respective member functions, including: -Node and Segment Node Spacing -Search area width and length -Preferred vector types -Impassable vector types 4) Calling makePath() with the start and end points of the path 5) Retrieving the resulting path as a DtList of vectors by calling path()

The characteristics of the path that is found depends on the parameters and the path metric. See the DtPathMetric class for information on path metrics. Different path metrics are used for different entities. The configurable parameters for a path metric are found in the entity's movement sysdef file under the path-movement enty.

Operational Description To find a path across arbitrary terrain, this class sets up a set of potential paths that are then searched for the best path. Potential paths are a combination of grid path sections and preferred path sections. Evenly spaced nodes are placed on a grid oriented from the start point to the end point with the width specified in the parameter, and a length of the distance between the start and end points plus the extra length parameter. The grid points are all nodeSpacing distance apart from orthogonal grid points. Grid paths are considered both orthogonally and diagonally from each point to each adjacent point. Thus there are 8 possible grid paths leaving each point.

Additionally, vector features in the terrain which match the preferred route types that are provided are considered as possible routes. Each segment of a preferred route is broken down further into path segments approximately segmentNodeSpacing long. (Each endpoint of a vector segment is guaranteed to be a considered node.) Paths along each segment are considered possible paths, as well as paths connecting each segment node to nearby grid nodes. Segment nodes are also connected to other nearby segment nodes on other segments.

The path planner runs a standard A* algorithm over all these considered paths. Each path segment is checked to see if it is crossed by a vector feature matching the impassable vector types specified. Any path which is crossed is immediately discarded, unless is also is a preferred route type. (Bridges will trump rivers, for example, allowing the vehicle to cross.) Each path segment is evaluated by passing the start and end point of the path segment to the DtPathMetric that was provided. Turning cost for each node in the path is also found though the metric. The optimistic heuristic for cost to the goal from each point is another return from the metric. As in any A* algorithm, it is important that the heuristic return value always be the least possible cost from the node to the goal. See the DtPathMetric class for more information on customizing the metrics.

Once a path is found, the optimizePath method is called, which removes unnecessary vertices of the path without significantly changing its shape.

See also:: DtAStarNode

Constructor & Destructor Documentation

DtPathPlanner::DtPathPlanner ( const DtPathPlanner & orig ) [private]

Not Implemented.

DtPathPlanner::DtPathPlanner ( )

virtual DtPathPlanner::~DtPathPlanner ( ) [virtual]

Member Function Documentation

DtPathPlanner& DtPathPlanner::operator= ( const DtPathPlanner & orig ) [private]

Not Implemented.

virtual void DtPathPlanner::setPathMetric ( DtPathMetric * metric ) [virtual]

Sets the path metric class to be used to calculate the path.

You must set a path metric before calling makePath().

virtual void DtPathPlanner::setNodeSpacing ( double space ) [virtual]

Set the spacing between grid nodes.

virtual void DtPathPlanner::setSegmentNodeSpacing ( double space ) [virtual]

Set the spacing between nodes on searchable vector features. (i.e. roads)

virtual void DtPathPlanner::setSearchAreaWidth ( double width ) [virtual]

Set the with of the area which will be searched for a path.

virtual void DtPathPlanner::setSearchAreaExtraLength ( double length ) [virtual]

Set the additional length (beyond the distance from the start to the goal) of the area which will be searched for a path.

virtual void DtPathPlanner::initPreferredSegmentMetrics ( const DtRwVectorObstructionTypeList & segmentTypes ) [virtual]

Creates a new set of DtRangeNetworkSegmentMetrics based on the preferred vector types specified in the list passed in and the node spacing.

virtual void DtPathPlanner::initImpassableSegmentMetrics ( const DtRwVectorObstructionTypeList & segmentTypes ) [virtual]

Creates a new set of DtNetworkSegmentMetrics based on the impassable vector types specified in the list passed in.

virtual void DtPathPlanner::setCrossCountryPenalty ( double penalty ) [virtual]

Set the penalty (in percent: i.e.

0.1) which will be applied to all paths that are not designated as preferred vector routes. This allows for cars to favor staying on a road even when in might be slightly faster to cut a direct path by going off-road.

virtual void DtPathPlanner::setPhysicalWorld ( const DtPhysicalWorld * physWorld ) [virtual]

Sets the local physical world pointer.

Call this before calling makePath with the world to be planned over.

virtual bool DtPathPlanner::makePath	(	const DtVector &	start,
		const DtVector &	goal
	)		`[virtual]`

Generates a new path between the start and end vectors (in local coordinates).

This method will keep the execution thread for as long as it needs to calculate an entire path. Returns true if a path was found. Will interrupt planning and return false if the interrupt() function is called while this is executing (from another thread).

virtual DtList* DtPathPlanner::path ( ) [virtual]

Returns the last generated path as a list of DtVectors in geocentric coordinates.

virtual void DtPathPlanner::interrupt ( ) [virtual]

Causes the path planner to be interrupted on its next call of checkInterrupt().

virtual bool DtPathPlanner::nodeVisited ( const DtPoint & point ) [virtual]

Returns true if the node is marked as visited.

virtual void DtPathPlanner::markNodeVisited ( const DtPoint & point ) [virtual]

Marks the node as visited.

virtual bool DtPathPlanner::nodeVisited	(	const DtNetworkSegment *	segment,
		int	position
	)		`[virtual]`

Returns true if the vector node it marked as visited.

virtual void DtPathPlanner::markNodeVisited	(	const DtNetworkSegment *	segment,
		int	position
	)		`[virtual]`

Marks the vector node as visited.

virtual bool DtPathPlanner::nodeSearchable ( const DtPoint & point ) [virtual]

Returns true if this node falls within the searchable extent.

virtual double DtPathPlanner::nodeSpacing ( ) [virtual]

Returns the node spacing.

virtual const DtPathMetric* DtPathPlanner::pathMetric ( ) const [virtual]

Returns a pointer to the current path metric being used.

virtual const std::list<DtRangeNetworkSegmentMetric>& DtPathPlanner::preferredSegmentMetrics ( ) const [virtual]

Returns a list of metrics which will return preferred segments.

virtual const std::list<DtIntersectNetworkSegmentMetric>& DtPathPlanner::impassableSegmentMetrics ( ) const [virtual]

Returns a list of metrics which will return impassable segments.

virtual double DtPathPlanner::crossCountryPenalty ( ) [virtual]

Returns the cross country penalty.

virtual const DtVectorNetwork* DtPathPlanner::vectorNetwork ( ) [virtual]

virtual int DtPathPlanner::findNumberOfNodesOnSegment ( const DtNetworkSegment * segment ) [virtual]

Determines the number of nodes that should be places along the specified vector segment.

Both ends are always nodes, and then nodes are evenly spaced between to approximate the segmentNodeSpacing parameter provided.

virtual int DtPathPlanner::findSegmentPositionAndPoint	(	const DtNetworkSegment *	segment,
		DtPoint &	point
	)		`[virtual]`

Returns the segment position of the point along the segment.

The point must be somewhere on the segment. No checks are done for this internally. This will modify the input point.

virtual DtPoint DtPathPlanner::findPointForSegmentPosition	(	const DtNetworkSegment *	segment,
		int	segPos
	)		`[virtual]`

Returns the location of a node along the segment.

virtual DtPoint DtPathPlanner::findAdjacentGridPoint	(	const DtPoint &	point,
		int	xOffset,
		int	yOffset
	)		`[virtual]`

Returns the grid point the is <xOffset, yOffset> grid positions from the specified point.

(remember that x and y are in the grid coord system, and not the terrain coordinates.

virtual DtPoint DtPathPlanner::findNearbyGridPoint	(	const DtPoint &	point,
		int	corner
	)		`[virtual]`

Returns the grid point position near the specified point.

corner is which corner of the grid: 0 - southwest, 1 - northwest, 2-northeast, 3-southeast

virtual bool DtPathPlanner::checkNoGoVectorIntersection	(	const DtPoint &	start,
		const DtPoint &	end
	)		`[virtual]`

Returns true if the segment from start to end intersects any no-go designated vector segments.

virtual double DtPathPlanner::calculateCost	(	const DtPoint &	startPoint,
		const DtPoint &	endPoint,
		bool	checkVectorNetwork = `true`
	)		`[virtual]`

Calculates the cost to move between these two points.

This is the expensive function in all of this calculation. If checkVectorNetwork is true, checkNoGoVectorInterection will be called before any terrain intersections are done. Cost calculation is done by call DtPathMetric::transitionCost

virtual double DtPathPlanner::estimateCostToGoal ( const DtPoint & point ) [virtual]

Calculates the estimated optimistic cost from this point to the goal.

This should be a relative cheap, and not less than the optimal cost. (the h(n) in A*)

virtual bool DtPathPlanner::isGoal ( const DtPoint & point ) [virtual]

Returns true if this point meets the goal criteria.

virtual bool DtPathPlanner::nearGoal ( const DtPoint & point ) [virtual]

Returns true if this point is within one grid square of the goal.

IE: A direct path from here to the goal (if possible) should be the next and final move.

virtual const DtPoint& DtPathPlanner::goalPoint ( ) [virtual]

The goal point.

virtual void DtPathPlanner::addSolutionPoint ( const DtPoint & point ) [virtual]

Adds this point to the beginning of the solution route.

virtual void DtPathPlanner::clearStats ( ) [virtual]

Clears all the internal status variables.

virtual void DtPathPlanner::printStats ( ) [virtual]

Prints the status of the last calculation to the console.

virtual void DtPathPlanner::nodeCreated ( ) [virtual]

These functions are called from inside the algorithms and update the statistics while the path is being planned.

virtual void DtPathPlanner::nodeDeleted ( ) [virtual]

These functions are called from inside the algorithms and update the statistics while the path is being planned.

virtual void DtPathPlanner::nodeExpanded ( ) [virtual]

These functions are called from inside the algorithms and update the statistics while the path is being planned.

virtual void DtPathPlanner::checkInterrupt ( ) [virtual]

Checks to see if the path planning should be interrupted, and throws DtPathPlannerInterruptedException if it should.

static int DtPathPlanner::round ( double val ) [static]

Utility function which takes a floating point number and does a standard rounding on it to get an integer.

(1.4999 -> 1, 1.5000 -> 2)

void DtPathPlanner::clearPath ( ) [protected]

Deletes the current path.

virtual void DtPathPlanner::initNodeTable ( ) [protected, virtual]

Initializes the table which tracks whether each grid node is visited or not.

virtual void DtPathPlanner::initTransforms	(	const DtVector &	startPoint,
		const DtVector &	endPoint
	)		`[protected, virtual]`

Sets up the transforms that go from local coordinates to the topographic projection we are using to do the planning.

virtual void DtPathPlanner::initGridExtent	(	const DtVector &	startPoint,
		const DtVector &	endPoint,
		double	extraX,
		double	extraY
	)		`[protected, virtual]`

Sets up the extent of the search area.

void DtPathPlanner::clearVisitedSegmentList ( ) [protected]

Clears the visited segment list.

virtual void DtPathPlanner::optimizePath ( ) [protected, virtual]

Modifies the current path by taking out redundant way points which will not change the layout of the path.

virtual void DtPathPlanner::setPathToTerrainHeight ( ) [protected, virtual]

Modifies the current path by changing the altitude of each point to be the height of the terrain at that location.

Note: this function makes a blocking terrain call to insure the required data is paged in. It also sets overrideBlockingAssert on its call to DtPhysicalWorld::groundClamp to prevent an assertion. This is safe because this function is not called from the main simulation thread.

virtual void DtPathPlanner::correctPathForTurningRadius ( double turningRadius ) [protected, virtual]

Modifies the current path by moving points in the route so that the specified turning radius will take an entity moving along the path along the intended path, instead of overshooting the turns.