Binary heap implementation.
More...
Binary heap implementation.
Binary heaps are really fast for ordering nodes in a way that makes it possible to get the node with the lowest F score. Also known as a priority queue.
This has actually been rewritten as a 4ary heap for performance, but it's the same principle.
 See also
 http://en.wikipedia.org/wiki/Binary_heap

https://en.wikipedia.org/wiki/Dary_heap

bool  isEmpty [get] 
 True if the heap does not contain any elements. More...



const int  D = 4 
 Number of children of each node in the tree. More...


Tuple []  heap 
 Internal backing array for the heap. More...


const bool  SortGScores = true 
 Sort nodes by G score if there is a tie when comparing the F score. More...


◆ BinaryHeap()
Create a new heap with the specified initial capacity.
◆ Add()
◆ Clear()
Removes all elements from the heap.
◆ DecreaseKey()
void DecreaseKey 
( 
Tuple 
node, 


ushort 
index 

) 
 

private 
◆ Expand()
Expands to a larger backing array when the current one is too small.
◆ GetNode()
◆ Rebuild()
Rebuilds the heap by trickeling down all items.
Usually called after the hTarget on a path has been changed
◆ Remove()
Returns the node with the lowest F score from the heap.
◆ RoundUpToNextMultipleMod1()
static int RoundUpToNextMultipleMod1 
( 
int 
v  ) 


staticprivate 
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 nonnegative integer.
◆ SetF()
void SetF 
( 
int 
i, 


uint 
f 

) 
 

package 
◆ Validate()
◆ growthFactor
The tree will grow by at least this factor every time it is expanded.
◆ heap
Internal backing array for the heap.
◆ NotInHeap
const ushort NotInHeap = 0xFFFF 
◆ numberOfItems
Number of items in the tree.
◆ SortGScores
const bool SortGScores = true 

private 
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).
◆ isEmpty
True if the heap does not contain any elements.
The documentation for this class was generated from the following file:
 /Users/arong/Unity/apathfindingproject/Assets/AstarPathfindingProject/Core/Misc/BinaryHeap.cs