Class for computing paths through a navigation mesh. More...

#include <PathPlanner.h>

Public Member Functions
	PathPlanner (NavMeshPtr ptr)
	Constructor. More...

	~PathPlanner ()
	Destrutor.

PortalRoute *	getRoute (unsigned int startID, unsigned int endID, float minWidth)
	Returns a route between the two specified nodes. More...

Protected Member Functions
PortalRoute *	computeRoute (unsigned int startID, unsigned int endID, float minWidth)
	Computes a route (and adds it to the cache) between start and end with the minimum clearance given. More...

float	computeH (unsigned int node, const Vector2 &goal)
	Compute's "h" for the A* algorithm. H is the estimate of the cost of a node to a goal point. In this case, simply Euclidian distance. More...

PortalRoute *	cacheRoute (unsigned int startID, unsigned int endID, PortalRoute *route)
	Cache the given route going from start to goal. More...

void	initHeapMemory (size_t nodeCount)
	Initializes the heap memory. More...

Protected Attributes
PRouteMap	_routes
	A mapping from RouteKeys (a size_t) to to a list of routes. The list consists of routes between the points in the route key in INCREASING maximum width. (i.e. narrowest route to widest route.)

ReadersWriterLock	_routeLock
	Lock for securing _routes;.

NavMeshPtr	_navMesh
	The navigation mesh for planning on.

size_t	DATA_SIZE
	The size of a block of data used for COST in the A* algorithm (3N, N = number of nodes)

size_t	STATE_SIZE
	The size of a block of data used for STATE in the A* algorithm (2N, N = number of nodes)

unsigned int *	_HEAP
	The full set of data to serve as the heap There are N entries in a single heap and one heap per thread.

unsigned int *	_PATH
	The full set of data for reconstructing the path. For any given entry i, the value at i is the index of the node from which i was reached. There is one block per thread.

float *	_DATA
	The block of data for tracking the f, g, and h data for nodes. (This is where DATA_SIZE = 3N comes from.) One block for each active thread. The first N values in a block are the f values, the next N are the g values, and the last set of N values are the h values.

bool *	_STATE
	Block of data for reportin node state (if its in a heap or if its no longer used for calculation. First N booleans are "in heap", second N are "finished". One block of 2N booleans per thread.

Detailed Description

Class for computing paths through a navigation mesh.

Constructor & Destructor Documentation

Menge::PathPlanner::PathPlanner ( NavMeshPtr ptr )

Constructor.

Parameters

ptr	A resource pointer to the nav mesh the planner uses.

Member Function Documentation

PortalRoute * Menge::PathPlanner::cacheRoute	(	unsigned int	startID,
		unsigned int	endID,
		PortalRoute *	route
	)

protected

Cache the given route going from start to goal.

Caching the route saves the solution for an agent from startID to endID with the provided minimum width. This route may be identical to a route that was found for a larger agent. If the previous agent was sufficiently large, a recomputation was triggered in case there was a better path. However, it may be that this new path is the same as the old path. In this case, the two routes are merged and a pointer to the merged route is returned. If this route is uniquely superior, then pointer provided as input will be returned.

Parameters

startID	The index of the start node.
endID	The index of the end node.
route	The route between them.

Returns: The equivalent route.

float Menge::PathPlanner::computeH	(	unsigned int	node,
		const Vector2 &	goal
	)

protected

Compute's "h" for the A* algorithm. H is the estimate of the cost of a node to a goal point. In this case, simply Euclidian distance.

Parameters

node	The estimated cost from the given node to the goal point.
goal	The goal point.

Returns: The h-value.

PortalRoute * Menge::PathPlanner::computeRoute	(	unsigned int	startID,
		unsigned int	endID,
		float	minWidth
	)

protected

Computes a route (and adds it to the cache) between start and end with the minimum clearance given.

Parameters

startID	The index of the navigation mesh node at which the route starts.
endID	The index of the navigation mesh node at which the route ends.
minWidth	The minimum passable width required for the route.

Returns: A pointer to a PortalRoute from startID to endID with the required clearance.

PortalRoute * Menge::PathPlanner::getRoute	(	unsigned int	startID,
		unsigned int	endID,
		float	minWidth
	)

Returns a route between the two specified nodes.

Parameters

startID	The index of the navigation mesh node at which the route starts.
endID	The index of the navigation mesh node at which the route ends.
minWidth	The minimum passable width required for the route.

Returns: A pointer to a PortalRoute from startID to endID with the required clearance.

void Menge::PathPlanner::initHeapMemory ( size_t nodeCount )

protected

Initializes the heap memory.

Parameters

nodeCount The number of nodes for which to initialize memory.

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

src/menge/MengeCore/resources/PathPlanner.h
src/menge/MengeCore/resources/PathPlanner.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation