A* (A Star) Path Finder in Javascript

Wiki said...

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.

Read more on Wikipedia

Notes

The core of this algorithm is quite simple, but code examples that are highly optimised can be confusing. This is the process of the calculation needed to find a good or shortest path.

Start at the first node, get all of its neighbours and calculate their g, h and F values, add these neighbour nodes to the 'open set'. Move the current node to the 'closed set'. Now find the lowest F value node in the 'open set' and repeat the calculations on its neighbours. Keep doing this until we run out of nodes or reach the destination.

g = parent g + distance to parent
Cost or distance to get here from the start node via the best path so far

h = Sqrt( dist_x * dist_x + dist_y * dist_Y )
Distance to destination node in a straight line. This is the heuristic value that makes this A* and not just Dijkstra.

F = g + h

With weights
F = (g * gWeight) + (h * hWeight)

Manhattan? No not the cocktail. This option would not allow diagonal moves and h would be calculated dist_x + dist_y. I have not implemented this but worth thinking about.

Weight of h

By adjusting the weight of the node h value you can adjust how the algorithm works. A very low h weight results in the algorithm checking many or even all of the nodes, but will most likely find the shortest path. A very high weight results in the algorithm checking fewer nodes but may not find the shortest path.

A higher h value pulls the pathfinder towards the destination quickly, but won't allow other paths to be explored.

Implementations of A* need to be tuned to their environment, either producing very fast and efficient results or always getting the shortest path at any cost.

Optimisation

The code here is not optimised, for every loop of the program ALL the nodes in the map will 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 this code is 300 nodes per second.

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

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

o3 - Math calculations and more

The Javascript Math routines are reported as being a bit slow and we use Square Root on all node explorations. Note - These ideas do not seem to produce any noticeable improvements, will continue to fiddle...

Distance to neighbour : Recalculated every time through the generic distance to node function, but in reality there are only two possible values of 1 or 1.4 for the neighbour distance. We could check this and return the correct distance without doing the calculations. This would save some math operations and a Sqrt() function.

Square Root Lookup : There are a finite number of square root calculations the program could make in any map. Create an array storing all these values in a lookup table, we can then just pull the answer out of the array without having to do the Sqrt function.

Floating point numbers : Whole numbers are much faster to process than floating points. Some of the g and h values are stored as floating point and require an additional Math.round(). Time to look at all the Math functions and how we are using number variables. Goal is to make sure everything is an integer and use a minimum of Math calls / functions.

Javascript specific : Is there anything specific about the way Javascript works that could improve the code. Is it the most memory efficient way of dealing with the data. For example, the difference in speed between using forEach or a for loop.

Web Workers : won't improve the speed of the routine, but can work in the background without freezing the page. For these demos we could add a progress bar or loading icon. May also be suitable for distributed processing on multiple hosts.

Memory : With very large maps memory usage can get very high, for me this is not a problem, but it would be good to have memory optimisation included. How can the memory footprint be reduced?