koobas.hobune.stream
Hep with binary heap poll
Hey everyone. Actually, after putting my A* to work with some Array.Sort to get the Node list adapted by F score, I'm trying to reach some better performance and finded out that the way to do this would be implementing Binary Heap into my pathfinding.
When I add an element to the list everything goes fine. It's added in his proper position. The problem is when I want to remove an item, sometimes it seems to work, but sometimes not, and the lower F cost node still in some other position in the array which is not actually 0.
This is the code I did to do the poll from the binary heap:
void binaryHeapPoll(int Index) {
if(openList.Count == 0) { return; }
openList[Index] = openList[openList.Count - 1];
openList.RemoveAt(openList.Count - 1);
int current = Index;
while(current < openList.Count) {
int leftChild = leftChildOf(current);
int rightChild = rightChildOf(current);
if(rightChild < openList.Count) {
if((openList[leftChild].F < openList[current].F) && (openList[leftChild].F < openList[rightChild].F)) {
current = binaryHeapSwap(current, leftChild, false); // this just swap the two items and return me the highest index between current and leftChild
} else if ((openList[rightChild].F < openList[current].F) && (openList[rightChild].F < openList[leftChild].F)) {
current = binaryHeapSwap(current, rightChild, false);
} else { return; }
} else if (leftChild < openList.Count) {
if(openList[leftChild].F < openList[current].F) {
current = binaryHeapSwap(current, leftChild, false);
return;
} else { return; }
} else { return; }
}
}
The Add method and some other methods I'm using in the binary heap you can see below:
int binaryHeapSwap(int indexOne, int indexTwo, bool returnMinimumIndex) {
int iOne = indexOne;
int iTwo = indexTwo;
int iMinimum = Mathf.Min(indexOne, indexTwo);
int iMaximum = Mathf.Max(indexOne, indexTwo);
Node indexOneNode = openList[iOne];
openList[iOne] = openList[iTwo];
openList[iTwo] = indexOneNode;
if(returnMinimumIndex) {return iMinimum;}
else {return iMaximum;}
}
void binaryHeapOffer(Node nodeToInsert) {
Node node = nodeToInsert;
openList.Add(node);
int currentIndex = openList.Count - 1;
while(currentIndex > 0) {
int parentIndex = parentOf(currentIndex);
if(openList[currentIndex].F < openList[parentIndex].F) {
currentIndex = binaryHeapSwap(currentIndex, parentIndex, true);
} else { break; }
}
}
int leftChildOf(int index) {
return ((index << 1) + 1);
}
int rightChildOf(int index) {
return ((index << 1) + 2);
}
int parentOf(int index) {
return((index - 1) >> 1);
}
Really hope someone can help me with this. I spent like 3 hours last night and didn't get any different result, but just with the poll.
Any help would be appreciated, from code to just logic tips. =)
Thanks from now!
Cheers!
The following code solve the problems!
void binaryHeapPoll(int Index) {
if(openList.Count == 0) { return; }
openList[Index] = openList[openList.Count - 1];
openList.RemoveAt(openList.Count - 1);
int current = Index;
while(current < openList.Count) {
int leftChild = leftChildOf(current);
int rightChild = rightChildOf(current);
if(rightChild < openList.Count) {
if((openList[leftChild].F < openList[rightChild].F)) {
if(openList[leftChild].F < openList[current].F) {
current = binaryHeapSwap(leftChild, current, false);
} else { return; }
} else {
if(openList[rightChild].F < openList[current].F) {
current = binaryHeapSwap(rightChild, current, false);
} else { return; }
}
} else if (leftChild < openList.Count) {
if(openList[leftChild].F < openList[current].F) {
current = binaryHeapSwap(current, leftChild, false);
return;
} else { return; }
} else { return; }
}
}
