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