An implementation of a min heap for A* algorithm. The heap needs to be able to restructure itself because the values of nodes IN the heap can change due to the A* algorithm.
More...
#include <MinHeap.h>
|
| AStarMinHeap (unsigned int *heap, float *data, bool *state, unsigned int *path, size_t N) |
| Constructor. More...
|
|
bool | empty () const |
| Reports if the heap is empty. More...
|
|
unsigned int | pop () |
| Extract the minimum keyed value. More...
|
|
void | push (unsigned int x) |
| Insert a new value into the heap. More...
|
|
void | g (unsigned int node, float value) |
| Set the g-value for the given node. More...
|
|
float | g (unsigned int node) const |
| Retrieve the g-value for the given node. More...
|
|
void | h (unsigned int node, float value) |
| Set the h-value for the given node. More...
|
|
float | h (unsigned int node) const |
| Retrieve the h-value for the given node. More...
|
|
void | f (unsigned int node, float value) |
| Set the f-value for the given node. More...
|
|
float | f (unsigned int node) const |
| Retrieve the f-value for the given node. More...
|
|
void | changeF (unsigned int node, float value) |
| Change the f-value for the given node in the heap. More...
|
|
bool | isVisited (unsigned int node) const |
| Reports if the node has been visited. More...
|
|
bool | isInHeap (unsigned int node) const |
| Reports if the node is currently in the heap. More...
|
|
void | setReachedFrom (unsigned int dst, unsigned int src) |
| Sets the node from which this node was reached. More...
|
|
unsigned int | getReachedFrom (unsigned int dst) const |
| Report the node from which this node was reached. More...
|
|
|
float | _minKey |
| The VALUE of the minimum keyed heap member.
|
|
unsigned int | _minIdx |
| The location of the minimum keyed heap member.
|
|
unsigned int | _nextFree |
| The location of the next free slot on the heap.
|
|
float * | _f |
| An array of f-values for each node in the navigation mesh. This is a value used in the A* algorithm. The memory is supplied upon construction.
|
|
float * | _g |
| An array of g-values for each node in the navigation mesh. This is a value used in the A* algorithm. The memory is supplied upon construction.
|
|
float * | _h |
| An array of h-values for each node in the navigation mesh. This is a value used in the A* algorithm. The memory is supplied upon construction.
|
|
bool * | _inHeap |
| An array of booleans reporting if the given node is in the heap. The memory is supplied upon construction.
|
|
bool * | _visited |
| An array of booleans reporting if the given node has been visited. The memory is supplied upon construction.
|
|
unsigned int * | _heap |
| An array of node indices of the nodes in the heap. The memory is supplied upon construction.
|
|
unsigned int * | _cameFrom |
| An array of node indices which indicate how a node was reached. The memory is supplied upon construction.
|
|
An implementation of a min heap for A* algorithm. The heap needs to be able to restructure itself because the values of nodes IN the heap can change due to the A* algorithm.
Also tracks all of the A* data.
Menge::AStarMinHeap::AStarMinHeap |
( |
unsigned int * |
heap, |
|
|
float * |
data, |
|
|
bool * |
state, |
|
|
unsigned int * |
path, |
|
|
size_t |
N |
|
) |
| |
Constructor.
- Parameters
-
heap | A pointer to a block of memory to be used for the heap for N nav mesh nodes. |
data | A pointer to a block of memory to be used for the A* data (f, g, & h) for N nav mesh nodes. |
state | A pointer to a block of memory to be used for the heap state (in heap & finished) for N nav mesh nodes. |
path | A pointer to a block of memory to be used for recording the path taken. |
N | The number of nodes. |
void Menge::AStarMinHeap::changeF |
( |
unsigned int |
node, |
|
|
float |
value |
|
) |
| |
Change the f-value for the given node in the heap.
- Parameters
-
node | The node whose f-value is to change. |
value | The new f-value. |
bool Menge::AStarMinHeap::empty |
( |
| ) |
const |
|
inline |
Reports if the heap is empty.
- Returns
- True if the heap is empty, false if it is not.
void Menge::AStarMinHeap::f |
( |
unsigned int |
node, |
|
|
float |
value |
|
) |
| |
|
inline |
Set the f-value for the given node.
- Parameters
-
node | The nav mesh node index for which the f-value is to be set. |
value | The f-value for the given node. |
float Menge::AStarMinHeap::f |
( |
unsigned int |
node | ) |
const |
|
inline |
Retrieve the f-value for the given node.
- Parameters
-
node | The nav mesh node index whose f-value is to be retrieved. |
- Returns
- The f-value of the indexed node.
void Menge::AStarMinHeap::g |
( |
unsigned int |
node, |
|
|
float |
value |
|
) |
| |
|
inline |
Set the g-value for the given node.
- Parameters
-
node | The nav mesh node index for which the g-value is to be set. |
value | The g-value for the given node. |
float Menge::AStarMinHeap::g |
( |
unsigned int |
node | ) |
const |
|
inline |
Retrieve the g-value for the given node.
- Parameters
-
node | The nav mesh node index whose g-value is to be retrieved. |
- Returns
- The g-value of the indexed node.
unsigned int Menge::AStarMinHeap::getReachedFrom |
( |
unsigned int |
dst | ) |
const |
|
inline |
Report the node from which this node was reached.
- Parameters
-
dst | The index of the nav mesh node reached. |
- Returns
- The index of the nav mesh node from which dst was reached.
void Menge::AStarMinHeap::h |
( |
unsigned int |
node, |
|
|
float |
value |
|
) |
| |
|
inline |
Set the h-value for the given node.
- Parameters
-
node | The nav mesh node index for which the h-value is to be set. |
value | The h-value for the given node. |
float Menge::AStarMinHeap::h |
( |
unsigned int |
node | ) |
const |
|
inline |
Retrieve the h-value for the given node.
- Parameters
-
node | The nav mesh node index whose h-value is to be retrieved. |
- Returns
- The h-value of the indexed node.
void Menge::AStarMinHeap::initialize |
( |
size_t |
N | ) |
|
|
protected |
Resets the heap and all data.
- Parameters
-
N | The number of nodes in the nav mesh. |
bool Menge::AStarMinHeap::isInHeap |
( |
unsigned int |
node | ) |
const |
|
inline |
Reports if the node is currently in the heap.
- Parameters
-
node | The index of the nav mesh node to test. |
- Returns
- True if the node is in the heap, false otherwise.
bool Menge::AStarMinHeap::isVisited |
( |
unsigned int |
node | ) |
const |
|
inline |
Reports if the node has been visited.
- Parameters
-
node | The index of the nav mesh node to test. |
- Returns
- True if the node has been visited, false otherwise.
unsigned int Menge::AStarMinHeap::pop |
( |
| ) |
|
Extract the minimum keyed value.
- Returns
- The index of the nav mesh node with the minimum keyed value.
void Menge::AStarMinHeap::push |
( |
unsigned int |
x | ) |
|
Insert a new value into the heap.
- Parameters
-
x | The index of the node to insert. |
void Menge::AStarMinHeap::setReachedFrom |
( |
unsigned int |
dst, |
|
|
unsigned int |
src |
|
) |
| |
|
inline |
Sets the node from which this node was reached.
- Parameters
-
dst | The index of the nav mesh node reached. |
src | The index of the nav mesh node from which dst was reached. |
The documentation for this class was generated from the following files:
- src/menge/MengeCore/resources/MinHeap.h
- src/menge/MengeCore/resources/MinHeap.cpp