Advanced Data Structures: Implementing the A* Algorithm in JavaScript
The A* Algorithm is Great for Efficient Pathfinding: A Practical Guide on How to Build from Scratch
A fun little algorithm to play with and it’s more useful than you’d think
The A* (A-star) algorithm is one of the most common pathfinding algorithms around. If you’re a game developer, you’ve probably heard about it, or used it yourself.
It’s also one of the easiest ways to solve the problem of going from A to B without bumping into any of the obstacles in the middle.
So in this article, we’re going to take a quick peak at how it works, and how you’d go about implementing your own A* code in JavaScript.
Notice that for the sake of keeping this article focused on the algorithm itself, I’m not going to be using any graphical representation library or game library to showcase the results. I’ll simply print the output on the terminal .
Feel free to implement this code in your own graphical context and if you do, share the results, I’d love to see the algorithm at work!
What is the A* algorithm?
Quickly, for those of you who’ve actually never heard about the algorithm:
The A* algorithm was first described in a 1968 paper by Peter Hart, Nils Nilsson, and Bertram Raphael of Stanford University. It was developed as a way to efficiently find the shortest path between two points on a map. The algorithm is a variant of the best-first search algorithm, which uses a heuristic function to guide the search and prioritize the most promising paths.
While you might find alternative use cases for it, given how mathematically speaking, it can be used to find the shortest path inside a graph, the most common use case for this algorithm is to implement pathfinding inside games.
Think of a 2D strategy game, it’s the classic point-and-click example, you’ll be constantly clicking somewhere on the map for your units to go there. Using this algorithm, they can efficiently find their way to the right spot avoiding hitting any obstacles in the middle.
Of course, this is not the most realistic-looking algorithm, and the results will not look super great. But it’s a great starting point, so it’s still very much worth understanding it.
How can you implement the A* pathfinding?
Without getting into code just yet, the basic algorithm behind A* is the following:
You first need to define a grid-based map, where each cell in the grid represents a location that the search can visit. If you’re using a big pixel-accurate map, you’ll likely be turning it into a grid-based one by increasing the size of your pixels, close to the size of the entity being moved.
Then when moving from one grid to the next, you don’t have to have your units jumping those many pixels, you can implement an interpolation-based movement that will calculate the points between two others and give you a smooth result.
The map should also include information about the cost of moving between cells and any obstacles that cannot be traversed.
Next, you need to define the heuristic function that estimates the cost of moving from the current location to the destination. This function will be used constantly during the pathfinding process, hence it needs to give a result fairly quickly and it’s OK for it to be an estimate, it doesn’t have to be super exact.
This function should be chosen based on the specific problem being solved and the available information about the map and the destination. For example, if the map is a two-dimensional grid and the destination is a point on the grid, the heuristic function could simply be the Euclidean distance between the current location and the destination.
Once the map and the heuristic function are defined, you can implement the main loop of the A* algorithm, which consists of the following steps:
- Add the starting location to an open set, which is a list of locations that have been visited but not yet expanded (we’ll talk about what “expanding” means in a second).
- Select the location from the open set that has the lowest total cost, which is the sum of the cost of moving from the starting location to this location and the estimated cost of moving from this location to the destination.
- Expand the selected location by adding its neighboring locations to the open set, if they are not already in the open set and not obstacles.
- Update the cost of moving to each neighboring location, if it is lower than the previously stored cost.
- If you’ve made it to the destination, construct the shortest path by following the chain of lowest-estimated cost.
- Repeat the previous steps until the destination is reached or the open set is empty, in which case there is no path to the destination.
Finally, you can implement additional features and optimizations, such as allowing for diagonal movement and using data structures with faster search and insertion operations to improve the efficiency of the algorithm.
In theory, that should give you all you need to implement the code, however, because I’m a very practical guy, I’m going to show you how the above steps translate to code.
Writing your JavaScript version of the A* algorithm
Let’s start by looking at the “star” of the show (see what I did there? *wink* *wink*): the implementation of the aStar function:
Let’s clear up some terms from the code:
- The
frontierarray contains the nodes that are about to be evaluated. - The
exploredarray contains the nodes that have already been evaluated, hence once we find the destination (represented with thegoalvariable), we’ll return that array, that’s where our path will be. - There are two functions that we’re not showing yet:
heuristicsandgenerateNextSteps, the way you implement them in your code will depend on the context for it. In this example, my “map” is a grid of points, so that simplifies my task quite a bit, if you’re using something different and more accurate, you might want to use another implementation.
The flow of this function is pretty much as we already explain:
- Keep the list of nodes to be evaluated inside an array.
- For every node being evaluated, get the surrounding nodes (when possible) and add those to the array from the previous point.
- For each of these nodes, calculate the cost (which is the cost of going from the starting point up to this node), and its estimated value which is the cost of going from the goal to it added to the cost of going from its position to the goal (we’ll use the
heuristicfunction for that). - If we reach the goal, then we return the list of nodes we’ve been looking at so far.
- If we run through all nodes and we haven’t returned just yet, then there is no path to find, and we return
null.
Getting the neighbors of a node
To get the surrounding nodes, all you have to do is make sure the coordinates are within the bounds of the grid and that those coordinates are not obstacles:
The code might not be pretty, but it illustrates the case very well. This simple implementation doesn’t even consider diagonal movement, so that could also be an improvement you might want to implement on your own.
Right now the code only picks the nodes above our current one, below it, and either directly to the right or to the left. Its only constraints: that they must be valid coordinates, and that those coordinates aren’t defined as “obstacles” in the map (we’ll look at how that is done in a second).
Understanding obstacles
For our obstacles, I’m just going to use another global array where I’m keeping a list of objects with coordinates, a width and a height (that for my case, I’ll keep at 1 in both cases).
Like this:
And to check if a coordinate matches an obstacle, I’m just going to write a simple function, like this:
Let’s now take a look at our heuristic function.
Estimating the cost of getting from a node to the destination
Notice how I used the word “estimating” instead of “calculating”. That’s because this function can’t possibly know exactly the cost of getting to the destination, which would require it to know the exact path.
However, we can get a fairly good idea of how much “effort” we need to get to the final destination.
In my case, I decided to go with a heuristic function that uses the euclidean distance between two points. But you’ll have to find the best option or your own scenario.
Just keep in mind that you’ll have to take into account obstacles. If there are obstacles between the node and the destination, then there needs to be a penalty for that node, otherwise I can be picked up by the algorithm incorrectly.
The implementation I used was the following:
I’m essentially returning the distance between two points plus the penalty if there are any obstacles in between.
The way to find if the path between two points contains obstacles, is by calling the pathIntersectsObstacles function.
The implementation of it will, of course, depend on the type of map you’re using, but for my grid I went with:
The function gets all the points in a straight line between the star and end coordinates. It then iterates over them and finds any matches with the list of obstacles (line 10).
Finally, if you’re interested in the details, here is the getPath function. It calculates all the points inside the straight line created by the two points we’re using:
We now have everything we need to run the algorithm. The only thing missing, is a way for us to visualize the results.
Displaying the results in the terminal
Since I’m not using any graphic libraries for this, I’m going to quickly plot the output of this algorithm into the terminal using a 10x10 matrix.
This function also highlights how to traverse the results from the aStar function, after all, that function doesn’t just return the final path, it returns other nodes that were explored during the process.
We need to iterate over that array using the estimate property calculated using our heuristic function in ascending order. That will give us the most efficient path.
And we’ll use the cost property to make sure we don’t repeat nodes that have the same cost but different estimates. This piece of the logic can be seen between lines 25 and 36 of the above code.
The rest of the function simply takes care of setting up the rest of the grid, and marking the interesting points (start, obstacles and the goal).
The output of this function looks like this when executed with a starting point of (0,0), a goal of (7,7) and 3 obstacles denoted by the “-” on the map:
As you can appreciate, the algorithm moves diagonally without using diagonal movement (it goes right first ,and then down, and then right, and so on). It also gets as close to the obstacles as it can, but it does a good job of avoiding them as well.
Did you like what you read? Consider subscribing to my FREE newsletter where I share my 2 decades’ worth of wisdom in the IT industry with everyone. Join “The Rambling of an old developer” !
Practical use cases for the A* algorithm
Of course, the most common practical use case for this algorithm is game development. I already mentioned how this algorithm can be used to find the shortest path between two points.
As you can see from the example, it can also be made to take into account the terrain, so it’s a very cheap way of solving pathfinding.
You can also take this same concept, and use it for robotics. Have you ever seen a Roomba moving? It doesn’t do it as a person would. You can probably implement at least some of its movement patterns using the A* algorithm as well.
Finally, if you want to get creative with this algorithm, you can use it to find the most efficient way of packing items into containers. If you think about it, by treating the container as a grid and considering the items as blocks that must be placed into the grid in a specific order, the algorithm can then search for the shortest path to fit all of the blocks into the container while minimizing any unused space.
This can be accomplished by defining a cost function that takes into account the size and shape of the items, the shape and size of the container, and any constraints on the placement of the items (such as the need for certain items to be placed together).
I’m going to leave that implementation for you as an exercise though, because this article is too long already :P
The A-Star algorithm is one of the oldest and easiest pathfinding methods there are, it’s also very efficient and has the added bonus of taking the terrain into consideration, so it can avoid static obstacles.
Of course, there are other more sophisticated ones out there, but this is a great starting point.
Have you ever used this algorithm in the past? Or are you planning on using it? Share your plans in the comments, I’d love to know what you’re working on!
Build Apps with reusable components, just like Lego
Bit’s open-source tool help 250,000+ devs to build apps with components.
Turn any UI, feature, or page into a reusable component — and share it across your applications. It’s easier to collaborate and build faster.
Split apps into components to make app development easier, and enjoy the best experience for the workflows you want:
