Mateusz Janusz. University of London, November 2017.

A* algorithm is one of the most popular computer algorithms used in path-finding and graph traversals. It can be used to find a shortest path. This algorithm is based on Dijkstra's algorithm with some characteristics of Breadth-First Search algorithm. A* uses the heuristic function to estimate the cost of a path from node n to the goal and therefore to decide which path to follow.

Given starting point and a goal, the algorithm for each move, examines the node n that has the lowest f(n) = g(n) + h(n) where g(n) is the cost of the path from the initial state to node n and h(n) is the heuristic cost of a path from node n to the goal.

A* was first described by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute in 1968 as an extension of Dijkstra’s 1959 algorithm.

1. Clone this repository
2. Open index.html in a browser
3. Set a grid size
4. Choose a grid type (square or diagonal)
5. Select start and goal node
6. Create obstacles by clicking on nodes
7. Press Start Search to run the algorithm

or try it here.

Green squares represent the shortest path found by the algorithm.