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 gvalue for the given node. More...


float  g (unsigned int node) const 
 Retrieve the gvalue for the given node. More...


void  h (unsigned int node, float value) 
 Set the hvalue for the given node. More...


float  h (unsigned int node) const 
 Retrieve the hvalue for the given node. More...


void  f (unsigned int node, float value) 
 Set the fvalue for the given node. More...


float  f (unsigned int node) const 
 Retrieve the fvalue for the given node. More...


void  changeF (unsigned int node, float value) 
 Change the fvalue 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 fvalues 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 gvalues 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 hvalues 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 fvalue for the given node in the heap.
 Parameters

node  The node whose fvalue is to change. 
value  The new fvalue. 
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 fvalue for the given node.
 Parameters

node  The nav mesh node index for which the fvalue is to be set. 
value  The fvalue for the given node. 
float Menge::AStarMinHeap::f 
( 
unsigned int 
node  ) 
const 

inline 
Retrieve the fvalue for the given node.
 Parameters

node  The nav mesh node index whose fvalue is to be retrieved. 
 Returns
 The fvalue of the indexed node.
void Menge::AStarMinHeap::g 
( 
unsigned int 
node, 


float 
value 

) 
 

inline 
Set the gvalue for the given node.
 Parameters

node  The nav mesh node index for which the gvalue is to be set. 
value  The gvalue for the given node. 
float Menge::AStarMinHeap::g 
( 
unsigned int 
node  ) 
const 

inline 
Retrieve the gvalue for the given node.
 Parameters

node  The nav mesh node index whose gvalue is to be retrieved. 
 Returns
 The gvalue 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 hvalue for the given node.
 Parameters

node  The nav mesh node index for which the hvalue is to be set. 
value  The hvalue for the given node. 
float Menge::AStarMinHeap::h 
( 
unsigned int 
node  ) 
const 

inline 
Retrieve the hvalue for the given node.
 Parameters

node  The nav mesh node index whose hvalue is to be retrieved. 
 Returns
 The hvalue 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