- Home /
A* Implementation broken?
I tried implementing [Wikipedia's version][1] of the A* pathfinding algorithm, but when I run it in Unity the object which the script is applied to does nothing and Unity ends up taking 15% of my CPU. I feel like this is a stack overflow error, but I can't tell where it breaks down. Here's the entirety of the script:
public class Walker : MonoBehaviour {
public int x { get; set; }
public int y { get; set; }
public MapView core { get; set; }
public Node goal { get; set; }
public float DistanceBetween(Node a, Node b) {
return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}
public List<Vector3> FindPath(Node goal) {
Node start = new Node(x, y);
List<Node> open = new List<Node>();
open.Add(start);
List<Node> closed = new List<Node>();
Dictionary<Node, Node> cameFrom = new Dictionary<Node, Node>();
Dictionary<Node, float> gScore = new Dictionary<Node, float>();
gScore[start] = 0;
Dictionary<Node, float> fScore = new Dictionary<Node, float>();
fScore[start] = DistanceBetween(start, goal);
while (open.Count != 0) {
Node current = open[0];
foreach (Node n in fScore.Keys)
if (fScore[n] < fScore[current])
current = n;
if (current == goal)
return ReconstructPath(cameFrom, current);
open.Remove(current);
closed.Add(current);
foreach (Node neighbor in Neighbors(current)) {
if (closed.Contains(neighbor))
continue;
float tempGScore = gScore[current] + DistanceBetween(current, neighbor);
if (!open.Contains(neighbor))
open.Add(neighbor);
else if (tempGScore >= gScore[neighbor])
continue;
cameFrom[neighbor] = current;
gScore[neighbor] = tempGScore;
fScore[neighbor] = gScore[neighbor] + DistanceBetween(neighbor, goal);
}
}
return new List<Vector3>();
}
public List<Vector3> ReconstructPath(Dictionary<Node, Node> cameFrom, Node current) {
List<Vector3> path = new List<Vector3>();
path.Add(current.GetVector());
while (cameFrom.ContainsKey(current)) {
current = cameFrom[current];
path.Add(current.GetVector());
}
return path;
}
public List<Node> Neighbors(Node current) {
int currx = current.x;
int curry = current.y;
List<Node> neighbors = new List<Node>();
neighbors.Add(new Node(currx, curry - 1));
neighbors.Add(new Node(currx, curry + 1));
neighbors.Add(new Node(currx - 1, curry));
neighbors.Add(new Node(currx + 1, curry));
return neighbors;
}
public virtual void SetStartCoords() {
x = (int)transform.position.x;
y = (int)transform.position.z;
}
}
public class Node {
public int x;
public int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public Vector3 GetVector() {
return new Vector3(x, 0, y);
}
}
Could I be misusing the DistanceBetween() function incorrectly, since I'm using it to calculate both the gScore and fScore of each node? [1]: https://en.wikipedia.org/wiki/A*_search_algorithm
I suspect you need to override Equals() (so that instances of node that share the same coordinates are equal to eachother) since you create new nodes when adding neighbours they will never previously exist in the closed-list (for every neighbour open/closed.Contains() will always return false). (EDIT: Clarification. The default Equals()-implementation will compare references, this is not the behaviour you're after.)
In addition you should consider using other datastructures. Like a HashSet for the closed-list (O(1) Contains() ins$$anonymous$$d of O(n) Contains()), a PriorityQueue for the open-list (so looking up the node with best score isn't a O(n) operation).
Your answer
Follow this Question
Related Questions
Unity 3.5: What is the definition of PLE algorithm? 1 Answer
A* optimization and path help 0 Answers
Preventing lines from overlapping 1 Answer
Help with A* algorithm 0 Answers