# Quick Access

# Description

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.

# How To Build

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