There has been no shortage of academic research into finding efficient ways to find paths. Its use in games, logistics, and mapping makes it an important topic for any aspiring programmer to try their hand in.
One of the most famous algorithms for computing the quickest route between two points is the A* algorithm. In this article, we’ll go over how A* works and even do a quick implementation of the algorithm in Javascript.
What is the A* algorithm?
A* is an improved version of Dijkstra’s search algorithm that was developed at the Stanford Research Institute. It makes use of heuristics(educated guesses that help reduce the time taken to compute the result) to increase its performance and efficiency. Unlike Dijkstra, this algorithm is specific i.e. it only finds the shortest path from one point to another instead of all possible end-points. It is used in online maps, video games, artificial intelligence, and other similar applications.
Implementation
In our Javascript implementation, we will use arrays to track our path over a grid but we can use other data structures like a heap or a graph to improve the overall performance of our code. You can find the complete code below:
A* works by considering all the adjacent points around our starting point and computing a cost function(Which you can think of as time or distance) for each of the adjacent points. Since our goal in pathfinding is to find the path that requires the least cost, we will then explore the option that has the least cost, and repeat this process until we reach our end point.
The cost value of a point is computed by adding the distance from that point to our starting point, to the distance from that point to the ending point. Note that since we are working over a grid, we are using what’s called the taxicab norm to measure distance(The sum of horizontal and vertical differences between the points). The way you choose to measure distance is going to depend on the problem you are working on. For example, if your agent is able to move diagonally on the grid, you probably would use the euclidean norm.
There you have it! We just implemented a basic version of the A* search algorithm in JavaScript. You can take this to the next level by adding obstacles, allowing diagonals, etc. You can even create an animation that shows the path being traced from the starting point to the end.
No matter what you’re developing, you don’t want to be bogged down by your computer’s infrastructure. At Codesphere, we’re building an all-in-one development platform that lets you develop with the full power of the cloud behind you.
Let us know in the comments how you plan to use this algorithm.
Happy coding!
Top comments (6)
what is this
if (openSet[i].f < openSet[lowestIndex]) {?Compare number and obj instance ?
Good catch! It should be openSet[lowestIndex].f, since we are comparing the cost values. Fixing the gist now
Small question, is it pronounced “A star”?
Yep!
I've never seen it pronounced out loud to be honest
I converted it to use a canvas, added diagonal movement, and added obstacles. It works well. I'm hoping to use it to draw lines in a flow chart script. Thanks for the help!
code with additions