Our board : a random 30x20 maze generated using a Prim's algorithm.
Globo (our green mascot in the middle) is the player and the blue capsule is the goal.

Trace let by the player using A* (A-Star) pathfinding algorithm to reach the goal.

Here is, to be compared, trace let by the player using Dijkstra's pathfinding algorithm to reach the goal.

Finally, the trace let by the player using a Depth First Search pathfinding algorithm to reach the goal.

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*) :

Manhattan distance map (from right bottom destination) : h(n)

Dijkstra distance map (from top left root) : g(n)

A* distance map : g(n) + h(n)

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
    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.
}

1. Here is our board.

2. Compute the distance to all neighbours and add them to the priority queue.

3. All nodes have the same root distance, however we select the right one as it has a smaller Manhattan distance.

4. Once again we compute the distance of the neighbours and add them to the priority queue.

5. Once again, our heuristic favorise the path that get closer to the target.

6. Here we go : destination found in a wink!