- Home /
Help with pathfinding function!
Hey everyone. Can someone help me poiting some errors in this Pathfinding function?
This is just breaking Unity.
void AStar (Node initialNode, Node finalNode) {
openList = closedList = new List<Node>();
initialNode.G = 0;
initialNode.H = initialNode.GetH( finalNode );
openList.Add(initialNode);
Node current = null;
while(openList.Count != 0) {
current = openList[0];
closedList.Add(current);
if(current == finalNode) {
reconstructPath(openList);
return;
}
foreach(Node neighbor in current.Neighbors) {
if(closedList.Contains(neighbor)) {
continue;
} else {
if(!openList.Contains(neighbor)) {
neighbor.defineParentNode(current);
neighbor.GetF(current, finalNode);
openList.Add(neighbor);
} else {
int neighborG = neighbor.GetG(current);
if(neighborG < neighbor.G) {
neighbor.defineParentNode(current);
neighbor.G = neighborG;
}
}
}
}
openList.Sort(delegate(Node x, Node y) {
return x.F.CompareTo(y.F);
});
}
}
And here's the Node class :
public class Node {
public Vector3 position;
public List<Node> Neighbors; // these are defined with a function that I omitted, but I'm sure that it doesn't return a empty list
public Node parentNode;
public int F, G, H;
public Node (Vector3 Position, bool DefineNeighbors) {
position = Position;
}
public int GetF (Node currentNode, Node finalNode) {
this.G = GetG(currentNode);
this.H = GetH(finalNode);
this.F = this.G + this.H;
return this.F;
}
public int GetH (Node finalNode) {
H = (int)(Mathf.Abs(this.position.x - finalNode.position.x) + Mathf.Abs(this.position.z + finalNode.position.z));
return H;
}
public int GetG (Node currentNode) {
int distanceToCurrent = (int)(Mathf.Abs(this.position.x - currentNode.position.x) + Mathf.Abs(this.position.z + currentNode.position.z));
G = currentNode.G + distanceToCurrent;
return G;
}
public void defineParentNode(Node parent) {
this.parentNode = parent;
}
}
If someone have the time to read the code and point something that could be make me get stuck in the loop, I'll appreciate!
Thanks from now!
I'd recommend putting in some Debug.Log's in the loops and just see which one is getting called over and over again and not leaving?
The problem is that Unity's breaking and I can't take a look at the console.
By breaking, do you mean it just crashes completely and won't let you stop? Could then put counters and if the counter goes about (Huge number here), then you auto-close it. Then you can find the infinite that way too?
I can't stop. I need to close Unity from task manager.
Ins$$anonymous$$d of while(...) I did a for(int i=0;i<1000;i++) {... and after some seconds Unity continue the execution normally.
Answer by hathol · May 14, 2012 at 10:59 PM
You're never removing nodes from your open list. I think it should be
current = openList[0];
openList.removeAt(0);
closedList.Add(current);
I think that's not necessary because of the :
if(current == finalNode) {
reconstructPath(openList);
return;
}
The open list is necessary to build the path after the current node is equal do the final one.
Correct me if I'm wrong.
In addition, for reconstructing the path you don't need either of the lists, just the last node. Then you can just walk backwards by recursively looking at the nodes respective parent until you reach your start.
Nice point hathol! I studied a lot of the theory and forget about this.
You are wrong ;)
a) You might not have a valid path -> infinite loop
b) It could happen that your current node is still the one with the lowest F cost (there might be an obstacle for example) after the loop, so it will always end up on top of the list -> infinite loop
I tried with the line you suggest me but I didn't get any results. Is there some other logical error in the function or any other idea?
Answer by Justin Warner · May 14, 2012 at 11:39 PM
Going through your code, I'll agree with Alex. You're never removing a node from the list, because of this, your count in the list is never reaching 0, therefore, never ending. Unity will always freeze/crash if an infinite loop happens, and in this case, it never once will leave the while loop, also shown by the example code you gave me.
Upon looking at the code you're using, assuming [this][1], you can see that the method current == finalNode, may be true, and may run that reconstructPath, but this does nothing to openList, which is ultimately the problem.
Some work arounds, that I don't know if it'll work, but may strike an idea from you:
Make multi-[thread][2], so this works along with the main [thread][3] (Don't know if Unity does this, I assume it's possible though).
Have another list, something similiar to backedUpOpenList, and put all the openList in it, then remove the header and do the while it's not null, then return so said list when done with w/e you need to be done with.
Write your own A* program ;). You'll have more control, but no seriously, I think option 2 will work.
Hope this helps a bit, but yes, ultimately I believe Alex was right. =). Good luck! [1]: http://unifycommunity.com/wiki/index.php?title=AStarHelper [2]: http://answers.unity3d.com/questions/47732/about-multiple-thread.html [3]: https://www.google.com/search?client=opera&rls=en&q=unity3d+threads&sourceid=opera&ie=utf-8&oe=utf-8&channel=suggest#sclient=psy-ab&hl=en&client=opera&hs=IgQ&rls=en&channel=suggest&q=unity3d++multiple+threads&oq=unity3d++multiple+threads&aq=f&aqi=&aql=&gs_l=serp.3...4436.6972.0.7129.17.15.0.2.2.0.187.1617.9j6.15.0...0.0.gYeLB1SESyw&pbx=1&bav=on.2,or.r_gc.r_pw.,cf.osb&fp=59aa6895a8e2ed70&biw=1718&bih=990