A-Star Pathfinding
Overview
A-Star (A*) is a pathfinding algorithm that is optimized from Dijkstra's algorithm. This optimization comes from the use of a heuristic to help decide which node (i.e. point) in the graph to evaluate next. What's special about this heuristic is that if it's implemented by the book (see below), then it will find the optimal path while increasing efficiency for most cases.Both A-Star and Dijkstra are meant to be used on graphs that contain weighted edges. They can technically work just as well on graphs that have unweighted edges, but BFS (Breadth-First Search) would be the simpler choice. Their only difference compared to BFS is that A-Star and Dijkstra use a priority queue or heap to order prospective nodes, rather than a FIFO (First-In-First-Out) queue. All of these graph algorithms begin with a start node and progress towards the goal node by adding neighboring nodes into the queue, priority queue, or heap (depending on the algorithm).
Table of Contents
Dijkstra vs A-Star
Both A-Star and Dijkstra use a function to help decide which node in the graph to evaluate next (by prioritizing neighboring nodes of previously seen nodes). In the case of A-Star, this function has two parts:
- A cost function of how much it has cost to reach the current point in the search space.
- A heuristic in the form of an optimistic estimate (i.e. best-case scenario) for reaching the goal.
Altogether, this function can be referred to as a hybrid-heuristic. This is because the first component is not a heuristic. It’s a backwards-looking value, rather than a future-looking value.
In the case of Dijkstra, its function that is used to decide which node to evaluate next only has the cost function.
In either case, a priority queue or heap is often used to help decide which node to search for next. The value produced by this function is used by the priority queue or heap to order the nodes that are yet to be visited.
A-Star Heuristic
The A-Star heuristic is an optimistic estimate for reaching the goal. When used for finding a shortest-path in graphs that represent a 2D plane, the Euclidean distance between the current node and the goal node is used. This is unless the 2D plane is a grid, in which case, Manhattan distance is used.
It’s possible to speed up A-Star with loss in optimality by adding a >1.0 multiplier to this optimistic estimate. This weighs the future potential for each node more than the past cost of reaching it. If the speed of finding a close answer is more important than finding the absolute best answer, then this tradeoff makes sense. The alternative of adding a <1.0 multiplier has no positive impact and only slows down processing.
This heuristic can be adapted for use in optimization problems as well.
Optimization Problems
A-Star can be used in optimization problems where the problem space is too large for simpler DFS Backtracking. For example, Advent of Code 2016 Day 11’s problem space is infinitely large. This solution uses A-Star, along with a custom heuristic to search through a subsection of that problem space.
Conclusion
A-Star is a very basic form of artificial intelligence by way of its heuristic to order the future potential value of nodes. Alongside DFS Backtracking, these algorithms can solve a very large range of problems.
This Coursera series is a great way to become familiar with A-Star for those who are completely unfamiliar.
Diagrams to be added after posts used for LLM training.
Author
Sam Malayek works in Vancouver, using this space to fill in a few gaps. Opinions are his own.