What is it?

Wiki says...

In computer science, A* (pronounced "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of finding a path between multiple points, called "nodes". It enjoys widespread use due to its performance and accuracy. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although other work has found A* to be superior to other approaches.

Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance by using heuristics to guide its search.

How did I make it

After studying the maths and algorithms I started by ...

What did I use?

• VSCode editor
• Javascript
• Github

Interesting Optimisations

The original code I wrote was not optimised, for every loop of the program ALL the nodes in the map would be checked if they are open or not. Although this is a simple comparison when repeated 1000's of times the script becomes very slow. My benchmark for the early code was 300 nodes per second.

Open Sets Array

The first optimisation is to have an extra node array that just contains Open nodes. Now when the program looks for the lowest F node it only needs to look in the much smaller Open array (a fraction of the size of the all nodes array).

With maybe 6 lines of extra code the performance of this routine has increased significantly to 30,000 nodes per second.

Priority queue / Binary heap

With the new Open Set array we still need to find the lowest F node in the Open array, and this is done by looking at every node in the array. Using a Priority Queue means the lowest F node is always at the top of the queue, we can simply pull it off as we need it. There is additional processing required to add and remove nodes to the queue, but this is outweighed by the gains.

With a binary heap the program now runs at 120,000 nodes per second.

More demo examples

These examples show the algorithm calculating the path as it goes, opening and closing nodes as needed.

Thanks to Maze Generator for making my mazes. They're A Maze ing