A pathfinder has to be very fast, but when we take a look at the performance we notice that working with the open-list is the bottleneck.

There are several possible data structures to store the open-list. We could use an ArrayList to store the values and keep it sorted using an IComparable interface. With this solution we end up with too much overhead keeping the entire list sorted. After all, the only thing our pathfinder is interested in, is the node with the lowest F-score, it doesn’t care about the other nodes.

A better solution is using a binary heap. In a binary heap, each item has two children with a value higher or equal to itself. Which means in the end the lowest item is at the top of the heap, easily accessible.



One of the nice things of a binary heap is the fact that it can be stored in a 1-dimensional array, making sorting of the heap a very quick operation.

The top of the heap is always stored at index 1. We don’t use the 0-index when working with zero-based arrays.



The children of any given item are always stored at the item’s location * 2 and the item’s location * 2 + 1. For example, in the image given above, the item with value 20 is stored at index 3 and its two children can be found at index 6 (3 * 2) and index 7 (3 * 2 + 1).

Adding an item to a binary heap can be achieved by adding the new item at the end of the array and then letting the new item bubble its way up.

This is achieved by comparing the item with its parent, swapping them when the item is smaller then its parent and repeating this until the parent is smaller.

[csharp]
public void Add(Int32 fCost) {
this.binaryHeap[this.numberOfItems] = fCost;

Int32 bubbleIndex = this.numberOfItems;
while (bubbleIndex != 1) {
Int32 parentIndex = bubbleIndex / 2;
if (this.binaryHeap[bubbleIndex] <= this.binaryHeap[parentIndex]) {
Int32 tmpValue = this.binaryHeap[parentIndex];
this.binaryHeap[parentIndex] = this.binaryHeap[bubbleIndex];
this.binaryHeap[bubbleIndex] = tmpValue;
bubbleIndex = parentIndex;
} else {
break;
}
}
this.numberOfItems++;
} /* Add */
[/csharp]

To remove an item from a binary heap, we simply take the item at index 1. But now we have to repair our heap, because there is a gap at the top. To fix this we take the last item and place it at the top, after which we let it sink downwards. This is done by comparing the value with its two children, replacing it with the smallest child and repeating this until the parent is smaller than both children.

[csharp]
public BinaryHeapItem Remove() {
this.numberOfItems--;
Int32 returnItem = this.binaryHeap[1];

this.binaryHeap[1] = this.binaryHeap[this.numberOfItems];

Int32 swapItem = 1, parent = 1;
do {
parent = swapItem;
if ((2 * parent + 1) <= this.numberOfItems) {
// Both children exist
if (this.binaryHeap[parent] >= this.binaryHeap[2 * parent]) {
swapItem = 2 * parent;
}
if (this.binaryHeap[swapItem] >= this.binaryHeap[2 * parent + 1]) {
swapItem = 2 * parent + 1;
}
} else if ((2 * parent) <= this.numberOfItems) {
// Only one child exists
if (this.binaryHeap[parent] >= this.binaryHeap[2 * parent]) {
swapItem = 2 * parent;
}
}
// One if the parent's children are smaller or equal, swap them
if (parent != swapItem) {
Int32 tmpIndex = this.binaryHeap[parent];
this.binaryHeap[parent] = this.binaryHeap[swapItem];
this.binaryHeap[swapItem] = tmpIndex;
}
} while (parent != swapItem);
return returnItem;
} /* Remove */
[/csharp]

A small comparison between an ArrayList and this binary heap implementation gives the following results:

[code]
Binary Heap: added 4000 items.
Time needed: 00:00:00
Lowest F-score: 1
Sorted ArrayList: added 4000 items.
Time needed: 00:00:07.2968750
Lowest F-score: 1

Binary Heap: added 10000 items.
Time needed: 00:00:00.0156250
Lowest F-score: 1
Sorted ArrayList: added 10000 items.
Time needed: 00:00:56.1250000
Lowest F-score: 1
[/code]

Inspiration and some images used from Patrick Lester.