Menge::AStarMinHeap Class Reference

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>

Public Member Functions
	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...

Protected Member Functions
void	initialize (size_t N)
	Resets the heap and all data. More...

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

Detailed Description

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.

Constructor & Destructor Documentation

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.

Member Function Documentation

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