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

Public Member Functions
	DtRailPathPlanner ()
virtual	~DtRailPathPlanner ()
virtual void	setPathMetric (DtRailPathMetric *metric)
	Sets the path metric class to be used to calculate the path.
virtual void	initPreferredSegmentMetrics (const DtRwVectorObstructionTypeList &segmentTypes)
	Set the rail network to seach in.
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	setPhysicalWorld (const DtPhysicalWorld *physWorld)
	Reads list of preferred route object types that can be used to generate the path.
virtual bool	makePath (const DtVector &start, const DtVector &goal)
	Generates a new path between the start and end vectors (in local coordinates).
virtual void	clear ()
	clear any leftover lists.
virtual DtRailSegmentList *	path ()
	Returns the last generated path as a list of DtRailSegment in geocentric coordinates.
virtual void	interrupt ()
	Causes the path planner to be interrupted on its next call of checkInterrupt().
virtual const DtNetworkEdge *	findTerminatingEdge (const DtPoint &point, const DtNetworkSegment *&segmentContainingPoint)
	! Methods used internally by the path planning system /////////////////////////! This finds the entry and exit edges to get onto and off of the network.
virtual void	appendEntryEdge ()
	Once the path is found thru the network, append the entry edge to the beginning of the path.
virtual void	appendExitEdge ()
	Same as above but appends exit edge to the end of the path.
virtual void	createPathFromEntryEdge ()
	In the instance that your entry and exit edge are the same just simple traverse the entry edge for the path.
virtual bool	nodeVisited (DtNetworkEdge *edge)
	Returns true if the segment is marked as visited.
virtual void	markNodeVisited (DtNetworkEdge *edge)
	Marks the segment as visited.
virtual const DtRailPathMetric *	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 const DtVectorNetwork *	vectorNetwork ()
virtual bool	atEntryPoint ()
	Keep track of when entity gets to the entry point.
virtual void	setAtEntryPoint (bool entering)
virtual void	setSearchAreaRadius (double radius)
virtual void	setSearchAreaExtraLength (double extra)
virtual double	calculateCost (const DtPoint &startPoint, DtNetworkEdge *edge)
	Returns true if the segment from start to end intersects any no-go designated vector segments.
virtual bool	accessableEdge (DtNetworkEdge *edge)
	Is this edge accessible to us? We check it's feature type against the impassable feature types.
virtual double	estimateCostToGoal (const DtPoint &point)
	Calculates the estimated optimistic cost from this point to the goal.
virtual bool	isPointInsideNetwork (const DtPoint &point, double distanceOffset=0)
	Returns true if the included point is inside your vector network, false otherwise.
virtual bool	isGoal (const DtPoint &point)
	Returns true if this point meets the goal criteria.
double	projectedDistanceSqXY (const DtPoint &start, const DtPoint &end)
	Finds the projected distance between start and end.
virtual bool	segmentContainsPointXY (const DtPoint &start, const DtPoint &end, const DtPoint &testPt, const DtNetworkSegment *conditionSeg)
	First checks if the start/end points match those of our conditional segment, else finds if the test point is containted by the chord defined by start-end in XY only.
virtual const DtPoint &	goalPoint ()
	The goal point.
virtual void	addSolutionEdge (DtNetworkEdge *edge, DtNetworkEdge::DtTraversalDirection direction)
	Iterator over edge in desired direction creating the solution segments list.
virtual bool	isEntryEdge (DtNetworkEdge *edge)
virtual bool	isExitEdge (DtNetworkEdge *edge)
virtual const DtNetworkSegment *	entrySegment ()
virtual const DtNetworkSegment *	exitSegment ()
virtual const DtPoint &	entryPoint () const
virtual const DtPoint &	exitPoint () const
DtVrfObject *	publishDebugPath (DtSimManager *simManager)
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.
static DtNetworkEdge::DtTraversalDirection	findTraversalDirection (const DtPoint &firstPoint, const DtPoint &secondPoint, const DtNetworkEdge edge, const Coordinate_System coordSys)
Protected Member Functions
void	clearPath ()
	Deletes the current path.
void	clearVisitedSegmentList ()
	Clears the visited segment list.
virtual DtRailSegment *	createNewRailSegment (const DtVector &start, const DtVector &end, const DtNetworkSegment *seg)
Protected Attributes
const DtPhysicalWorld *	myPhysicalWorld
	Pointer to the terrain database.
double	mySearchAreaRadius
	Radius around which to search;.
double	mySearchAreaExtraLength
	This will be added to the above.
bool	mySearchAreaSpecified
	If true user has specified a desired search area, other wise the radius will be the distance between the start and end points.
DtRailSegmentList	myPath
	List of DtVector objects which represent the calculated path.
const DtNetworkEdge *	myEntryEdge
const DtNetworkSegment *	myEntrySegment
const DtNetworkEdge *	myExitEdge
const DtNetworkSegment *	myExitSegment
DtPoint	myStartPoint
	These can be off the grid.
DtPoint	myGoalPoint
DtPoint	myEntryPoint
	These are on the grid These are our entry and exit points to/from the grid.
DtPoint	myExitPoint
DtRailPathMetric *	myPathMetric
std::list < DtRangeNetworkSegmentMetric >	myPreferredSegmentMetrics
std::list< DtString >	myPreferredSegmentTypes
std::list < DtIntersectNetworkSegmentMetric >	myImpassableSegmentMetrics
std::list< DtString >	myImpassableSegmentTypes
bool	myInterruptFlag
bool	myAtEntryPoint
std::list< DtNetworkEdge * >	myVisitedSegmentList
int	myNumberOfCostsCalculated
Private Types
enum	SegmentConnectionMode { ConnectNewRailMode = 0, ConnectToEndMode, ConnectToStartMode, ConnectExtendRailMode }
Private Member Functions
	DtRailPathPlanner (const DtRailPathPlanner &orig)
	Not Implemented.
DtRailPathPlanner &	operator= (const DtRailPathPlanner &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 DtRailPathController.

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: -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 std::list of DtRailSegments by calling path()

The characteristics of the path that is found depends on the parameters and the path metric. Currently this just uses the railPathMetric.

Operational Description To find a path across the vector Network and route objects, this class sets up a set of potential paths that are then searched for the best path. It searches all the segments of vector feature data and routes of the preferred types. Each segment's cost is evaluated to find the optimum path.

The path planner runs a standard A* algorithm over all these considered paths. Optionally each path segment can be checked to see if it is crossed by a vector feature matching the impassable vector types specified. This is more expensive. 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.

See also:: DtRailAStarNode

Member Enumeration Documentation

enum DtRailPathPlanner::SegmentConnectionMode [private]

Enumerator:

ConnectNewRailMode
ConnectToEndMode
ConnectToStartMode
ConnectExtendRailMode

Constructor & Destructor Documentation

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

Not Implemented.

DtRailPathPlanner::DtRailPathPlanner ( )

virtual DtRailPathPlanner::~DtRailPathPlanner ( ) [virtual]

Member Function Documentation

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

Not Implemented.

virtual void DtRailPathPlanner::setPathMetric ( DtRailPathMetric * 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 DtRailPathPlanner::initPreferredSegmentMetrics ( const DtRwVectorObstructionTypeList & segmentTypes ) [virtual]

Set the rail network to seach in.

Uses our preferred segment Metrics to create the searchable list of segments. If useRouteObjects is true, will include route objects of the preferred route types list. Creates a new set of DtRangeNetworkSegmentMetrics based on the preferred vector types specified in the list passed in and the node spacing.

virtual void DtRailPathPlanner::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 DtRailPathPlanner::setPhysicalWorld ( const DtPhysicalWorld * physWorld ) [virtual]

Reads list of preferred route object types that can be used to generate the path.

Sets the local physical world pointer. Call this before calling makePath with the world to be planned over.

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

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

Returns true if a path was found.

virtual void DtRailPathPlanner::clear ( ) [virtual]

clear any leftover lists.

Clears out the old path, the visited segments list, and the entry and exit edges.

virtual DtRailSegmentList* DtRailPathPlanner::path ( ) [virtual]

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

virtual void DtRailPathPlanner::interrupt ( ) [virtual]

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

virtual const DtNetworkEdge* DtRailPathPlanner::findTerminatingEdge	(	const DtPoint &	point,
		const DtNetworkSegment *&	segmentContainingPoint
	)		`[virtual]`

! Methods used internally by the path planning system /////////////////////////! This finds the entry and exit edges to get onto and off of the network.

virtual void DtRailPathPlanner::appendEntryEdge ( ) [virtual]

Once the path is found thru the network, append the entry edge to the beginning of the path.

virtual void DtRailPathPlanner::appendExitEdge ( ) [virtual]

Same as above but appends exit edge to the end of the path.

virtual void DtRailPathPlanner::createPathFromEntryEdge ( ) [virtual]

In the instance that your entry and exit edge are the same just simple traverse the entry edge for the path.

virtual bool DtRailPathPlanner::nodeVisited ( DtNetworkEdge * edge ) [virtual]

Returns true if the segment is marked as visited.

virtual bool segmentVisited(const DtRailSegment* segment);

virtual void DtRailPathPlanner::markNodeVisited ( DtNetworkEdge * edge ) [virtual]

Marks the segment as visited.

virtual const DtRailPathMetric* DtRailPathPlanner::pathMetric ( ) const [virtual]

Returns a pointer to the current path metric being used.

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

Returns a list of metrics which will return preferred segments.

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

Returns a list of metrics which will return impassable segments.

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

virtual bool DtRailPathPlanner::atEntryPoint ( ) [virtual]

Keep track of when entity gets to the entry point.

virtual void DtRailPathPlanner::setAtEntryPoint ( bool entering ) [virtual]

virtual void DtRailPathPlanner::setSearchAreaRadius ( double radius ) [virtual]

virtual void DtRailPathPlanner::setSearchAreaExtraLength ( double extra ) [virtual]

virtual double DtRailPathPlanner::calculateCost	(	const DtPoint &	startPoint,
		DtNetworkEdge *	edge
	)		`[virtual]`

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

Calculates the cost to move between these two points. This is the expensive function in all of this calculation. If checkBlockingSegments is true, checkNoGoVectorInterection will be called to see if there is any blocking features across the path. Cost calculation is done by call DtPathMetric::transitionCost

virtual bool DtRailPathPlanner::accessableEdge ( DtNetworkEdge * edge ) [virtual]

Is this edge accessible to us? We check it's feature type against the impassable feature types.

Return false if it is one of the impassable feature types.

virtual double DtRailPathPlanner::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 DtRailPathPlanner::isPointInsideNetwork	(	const DtPoint &	point,
		double	distanceOffset = `0`
	)		`[virtual]`

Returns true if the included point is inside your vector network, false otherwise.

This function is used by B-HAVE to attach to determine when the PathPlanner should be used.

Parameters:

point	The Point to verify.
distanceOffset	Return true if your point is within this many meters from the road.

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

Returns true if this point meets the goal criteria.

double DtRailPathPlanner::projectedDistanceSqXY	(	const DtPoint &	start,
		const DtPoint &	end
	)

Finds the projected distance between start and end.

virtual bool DtRailPathPlanner::segmentContainsPointXY	(	const DtPoint &	start,
		const DtPoint &	end,
		const DtPoint &	testPt,
		const DtNetworkSegment *	conditionSeg
	)		`[virtual]`

First checks if the start/end points match those of our conditional segment, else finds if the test point is containted by the chord defined by start-end in XY only.

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

The goal point.

virtual void DtRailPathPlanner::addSolutionEdge	(	DtNetworkEdge *	edge,
		DtNetworkEdge::DtTraversalDirection	direction
	)		`[virtual]`

Iterator over edge in desired direction creating the solution segments list.

static int DtRailPathPlanner::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)

virtual bool DtRailPathPlanner::isEntryEdge ( DtNetworkEdge * edge ) [virtual]

virtual bool DtRailPathPlanner::isExitEdge ( DtNetworkEdge * edge ) [virtual]

virtual const DtNetworkSegment* DtRailPathPlanner::entrySegment ( ) [virtual]

virtual const DtNetworkSegment* DtRailPathPlanner::exitSegment ( ) [virtual]

virtual const DtPoint& DtRailPathPlanner::entryPoint ( ) const [virtual]

virtual const DtPoint& DtRailPathPlanner::exitPoint ( ) const [virtual]

DtVrfObject* DtRailPathPlanner::publishDebugPath ( DtSimManager * simManager )

static DtNetworkEdge::DtTraversalDirection DtRailPathPlanner::findTraversalDirection	(	const DtPoint &	firstPoint,
		const DtPoint &	secondPoint,
		const DtNetworkEdge *	edge,
		const Coordinate_System *	coordSys
	)		`[static]`

Returns:: The traversal direction along edge required to get from firstPoint to secondPoint.

void DtRailPathPlanner::clearPath ( ) [protected]

Deletes the current path.

void DtRailPathPlanner::clearVisitedSegmentList ( ) [protected]

Clears the visited segment list.

virtual DtRailSegment* DtRailPathPlanner::createNewRailSegment	(	const DtVector &	start,
		const DtVector &	end,
		const DtNetworkSegment *	seg
	)		`[protected, virtual]`