Can someone please tell me why this code gives me an error,
NativeList<int> openList = new NativeList<int>(Allocator.Temp);
openList.Add(startNode.index);
while(openList.Length > 0) {
int currentNodeIndex = GetLowestCostFNodeIndex(openList);
PathNode currentNode = pathNodeArray[currentNodeIndex];
for(int i = 0; i < openList.Length; i++) {
if(openList[i] == currentNodeIndex) {
openList.RemoveAtSwapBack(currentNodeIndex);
break;
}
}
but not this code?
NativeList<int> openList = new NativeList<int>(Allocator.Temp);
openList.Add(startNode.index);
while(openList.Length > 0) {
int currentNodeIndex = GetLowestCostFNodeIndex(openList);
PathNode currentNode = pathNodeArray[currentNodeIndex];
for(int i = 0; i < openList.Length; i++) {
if(openList[i] == currentNodeIndex) {
openList.RemoveAtSwapBack(i);
break;
}
}
The only difference is that in the second one, I replace “currentNodeIndex” with i from the forloop. They’re the same number. And yet the first one gives me this error:
Like DreamingImLatios said, what makes you think they should be the same number? Your currentNodeIndex is an index into the pathNodeArray while i is the current index into your openList. The openList contains indices into the pathNodeArray. So using an index into a completely different array on the wrong array of course would result in all sorts of random issues.
First of all you would either removing completely unrelated items from the open list or you would run into out of bounds errors like you did. For example, your open list could contain the elements (3, 8, 20, 2, 0) If your currentNodeIndex is 3, your if statement in your loop would hit a match at i == 0 since the first element in the open list is the index 3. However removing index 3 out of the openList would mean you would remove the number 2 from the openList (the number at index 3 which has no relation to that element). So the new openList would be. Now imagine your currentNodeIndex is 20. Your loop would find a match at i == 2 since the number at index 2 is 20. Trying to remove index 20 from the openList would result in an index out of bounds since the openList only has 5 elements so there is no index 20.
So in short, your first code snippet is just wrong and doesn’t make sense and your second one is actually correct and does the thing it’s supposed to do
When I once implemented an A* algorithm in lua, I implemented the openlist implicitly has a linked list between the nodes itself. The list was always sorted based on the f score. So when adding an element to the open list it was inserted at the right spot in the linked list by iterating through the nodes. That way the lowest node was always at the top of the list and removing an element from a linked list is an O(1) operation. Yes, linked lists can be slower, however when they are directly implemented in the actual node instance, you don’t really have to worry about cache misses since you work with the nodes anyways. Removing nodes from the open list is the most frequent operation. When the open list gets large, performance of getting the best next node can be crucial. I created an A* search in lua for a computer craft turtle in minecraft. Since it was a 3d search space, the open list can get really large very quickly. So keeping the open list sorted is usually a good thing. Other implementations use a priority queue, though it depends on the specifics of the implementation. The closed list was actually just a flag in the node instance as well. The linked list pointers can also be used to implement the backtracking. The only disadvantage of integrating the open and closed list into the nodes itself is that you can not multithread several searches at the same time over the same nodes because you would have shared data of course.
I did a Debug.Log(), they reach the same number each time.
Changing openList[i] to i did fix it, and thank you Bunny for the illustration.
The reason I’m wondering is because I’m trying a new optimization for my pathfinding which involves changing an open variable to true each time a PathNode is added to the open list, instead of going through each node to see if it belongs to the open list or not.
