The A* algorithm is probably the most-used technique for path finding, given its implementation simplicity, and efficiency, and because it has room for optimization. It's no coincidence that there are several algorithms based on it. At the same time, A* shares some roots with the Dijkstra algorithm, so you'll find similarities in their implementations.
Just like Dijkstra's algorithm, this recipe uses the binary heap extracted from the GPWiki. Also, it is important to understand what delegates are and how they work for. Finally, we are entering into the world of informed search; that means that we need to understand what a heuristic is and what it is for.
In a nutshell, for the purpose of this recipe, a heuristic is a function for calculating the approximate cost between two vertices in order to compare them to other alternatives and take the minimum-cost choice.
We need to add small changes to the Graph class:
- Define a member variable as delegate:
public delegate float Heuristic(Vertex a, Vertex b);
- Implement Euclidean distance member function to use it as default heuristic:
public float EuclidDist(Vertex a, Vertex b) { Vector3 posA = a.transform.position; Vector3 posB = b.transform.position; return Vector3.Distance(posA, posB); } - Implement Manhattan distance function to use as a different heuristic. It will help us in comparing results using different heuristics:
public float ManhattanDist(Vertex a, Vertex b) { Vector3 posA = a.transform.position; Vector3 posB = b.transform.position; return Mathf.Abs(posA.x - posB.x) + Mathf.Abs(posA.y - posB.y); }
Even though this recipe covers defining a function, please take into consideration the comments in the code to understand the indentation and code flow more effectively:
- Define the
GetPathAstarfunction along with its member variables:public List<Vertex> GetPathAstar(GameObject srcObj, GameObject dstObj, Heuristic h = null) { if (srcObj == null || dstObj == null) return new List<Vertex>(); if (ReferenceEquals(h, null)) h = EuclidDist; Vertex src = GetNearestVertex(srcObj.transform.position); Vertex dst = GetNearestVertex(dstObj.transform.position); GPWiki.BinaryHeap<Edge> frontier = new GPWiki.BinaryHeap<Edge>(); Edge[] edges; Edge node, child; int size = vertices.Count; float[] distValue = new float[size]; int[] previous = new int[size]; // next steps } - Add the source node to the heap (working as a priority queue) and assign a distance value of infinity to all of them but the source node:
node = new Edge(src, 0); frontier.Add(node); distValue[src.id] = 0; previous[src.id] = src.id; for (int i = 0; i < size; i++) { if (i == src.id) continue; distValue[i] = Mathf.Infinity; previous[i] = -1; } - Declare the loop for traversing the graph:
while (frontier.Count != 0) { // next steps } return new List<Vertex>(); - Implement the conditions for returning a path when necessary:
node = frontier.Remove(); int nodeId = node.vertex.id; if (ReferenceEquals(node.vertex, dst)) { return BuildPath(src.id, node.vertex.id, ref previous); } - Get the vertex's neighbors (also called
successorsin some text books):edges = GetEdges(node.vertex);
- Traverse the neighbors for computing the
costfunction:foreach (Edge e in edges) { int eId = e.vertex.id; if (previous[eId] != -1) continue; float cost = distValue[nodeId] + e.cost; // key point cost += h(node.vertex, e.vertex); // next step } - Expand the list of explored nodes (frontier) and updating costs, if necessary:
if (cost < distValue[e.vertex.id]) { distValue[eId] = cost; previous[eId] = nodeId; frontier.Remove(e); child = new Edge(e.vertex, cost); frontier.Add(child); }
A* works in a similar fashion to Dijkstra's algorithm. However, instead of choosing the real lowest-cost node from all the possible options, it chooses the most-promising one based on a given heuristic, and goes on from there. In our case, the default heuristic is based solely on the Euclidian distance between two vertices with the option of using Manhattan distance.
You are welcome to play with different heuristic functions depending on the game and context, and the following is an example of how to do so:
- Define a heuristic function in the
Graphclass:public float Heuristic(Vertex a, Vertex b) { float estimation = 0f; // your logic here return estimation; }
The important thing here is that the heuristic we develop is both admissible and consistent. For more theoretical insights about these topics, please refer to Artificial Intelligence: A Modern Approach by Russel and Norvig.
In case you haven't noticed, we didn't implement the method BuildPath. This is because we talked about it at the end of the Depth-First Search recipe.
- The Finding the shortest path with Dijkstra recipe
- The Finding your way out of a maze with DFS recipe
For further information about Delegates, please refer to the official documentation available online at: