Class BinaryHeap

void Add (

PathNode

node

)

Adds a node to the heap.

BinaryHeap (

int

capacity

)

Create a new heap with the specified initial capacity.

void Clear ()

Removes all elements from the heap.

void Rebuild ()

Rebuilds the heap by trickeling down all items.

Usually called after the hTarget on a path has been changed

PathNode Remove ()

Returns the node with the lowest F score from the heap.

float growthFactor = 2

The tree will grow by at least this factor every time it is expanded.

bool isEmpty

True if the heap does not contain any elements.

const ushort NotInHeap = 0xFFFF

int numberOfItems

Number of items in the tree.

const int D = 4

Number of children of each node in the tree.

Different values have been tested and 4 has been empirically found to perform the best.

void DecreaseKey (

Tuple	node
ushort	index

)

void Expand ()

Expands to a larger backing array when the current one is too small.

PathNode GetNode (

int

i

)

Tuple[] heap

Internal backing array for the heap.

int RoundUpToNextMultipleMod1 (

int

v

)

Rounds up v so that it has remainder 1 when divided by D.

I.e it is of the form n*D + 1 where n is any non-negative integer.

void SetF (

int	i
uint	f

)

const bool SortGScores = true

Sort nodes by G score if there is a tie when comparing the F score.

Disabling this will improve pathfinding performance with around 2.5% but may break ties between paths that have the same length in a less desirable manner (only relevant for grid graphs).

void Validate ()