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