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.


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)


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


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
    queue.add(start, 0);

    // 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.
        if (!queue.has(neighbor)) queue.add(neighbor, neighbor.distance);

  // Done ! At this point we just have to walk back from the end using the parent
  // If end does not have a parent, it means that it has not been found.