The A* (A-Star) algorithm improves on Dijkstra’s by finding the shortest path more quickly. It was invented by Peter Hart, Nils Nilsson, and Bertram Raphael (three American computer scientists) and described in their paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” in 1968.

A* pathfinding algorithm is arguably the best pathfinding algorithm when we have to find the shortest path between two nodes. A* is the golden ticket, or industry standard, that everyone uses.

Dijkstra’s Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren’t promising. A* improves this by allowing the inclusion of extra information that the algorithm can use as part of the heuristic function:
- Dijkstra’s Algorithm use the distance from the root node.
- The A* algorithm uses both the actual distance from the root and the estimated distance to the goal.

That's it !
In fact A* algorithm is just a variant of Dijkstra's algorithm.

### Applications

As a variant of Dijkstra’s algorithm, A* is used everywhere : it is widely used in video games, in machine learning, navigation systems, autonomous vehicles, natural language processing (NLP) etc.

A* selects the path that minimizes the following function: $$f(n) = g(n) + h(n)$$ where:
- g(n) is the cost of the path from the starting point to node n (Dijkstra distance).
- h(n) is the estimated cost of the path from node n to the destination node, as computed by the Manhattan distance in our case.

Ok... but what's the Manhattan distance ?

The Manhattan distance (or Taxicab distance) origin is based on the well-known grid like street geography of the New York borough of Manhattan. It is the distance between two points in a grid based environment (with only horizontal and vertical moves). The Manhattan distance is the simple sum of the horizontal and vertical moves, whereas the diagonal or "as the crow flies" distance might be computed by applying the Pythagorean theorem.

This distance is ideal for our mazes that allow 4-way movement (up, down, left, right). $$h(n) = |goal.x - root.x| + |goal.y - root.y|$$

Here are the distance maps computed (Manhattan, Dijkstra and A*) :

We may reinforce the manhattan heuristic by using a factor. For instance : h(n)

## Steps

As simple as Dijkstra, the only change is the cost function (we add the manhattan distance) !

## Code


AStar(Maze maze, Node start, Node end) {
priority_queue queue();

// Init all distances with infinity
for (auto&& node : maze.nodes) {
node.distance = Infinity;
node.rootDistance = Infinity;

// Note: we may reinforce the manhattan heuristic by using a factor.
node.manhattanD = 2 * (Math.abs(end.x - node.x) + Math.abs(end.y - node.y));
}

// Distance to the root itself is zero
start.rootDistance = 0;

// Init queue with the root node

// Iterate over the priority queue until it is empty.
while (!queue.isEmpty()) {
curNode = queue.dequeue();  // Fetch next closest node
curNode.discovered = true;  // Mark as discovered

// Iterate over unvisited neighbors
for (auto&& neighbor : curNode.GetUnvisitedNeighbors())
{
// Update root minimal distance to neighbor including manhattan distance
neighbor.rDistance =
Math.min(neighbor.rootDistance, curNode.rootDistance + 1);
const minDistance =
Math.min(neighbor.distance, neighbor.rootDistance + neighbor.manhattanD);
if (minDistance !== neighbor.distance) {
neighbor.distance = minDistance;  // update mininmal distance
neighbor.parent = curNode;        // update best parent

// Change queue priority of the neighbor since it have became closer.
if (queue.has(neighbor)) queue.setPriority(neighbor, minDistance);
}

// Add neighbor to the queue for further visiting.