Class for computing paths through a navigation mesh.
More...
#include <PathPlanner.h>

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...



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.


Class for computing paths through a navigation mesh.
Constructor.
 Parameters

ptr  A resource pointer to the nav mesh the planner uses. 
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 hvalue.
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