The A* search algorithm, the swiss knife of CodinGame

I love CodinGame. For those who does not know what it is about, I suggest you to try. This is a nice website that can make you better with algorithms. I like to play in some clash of code from time to time but the best still is the bot programming competition.

In the last event, I needed a way to determine the fastest way to go from point A to point B. I could have use my swiss knife Dijkstra's algorithm but it was taking way too long to come up with an answer. So I had to find an alternative.

A-star

Looking around, I found a new algorithm I did not know about, the A* search algorithm. It's path search algorithm way better in term of performance than the Dijkstra. The complexity is O(b^d) where b is the branching factor but in fact, it mostly depend of the heuristic function that will be choosen. In this example, I will choose the Manhattan calculation but it could be way different. The significant impact of A* compare to Dijkstra is that we always prefer nodes that are closer to our target and avoid visiting nodes that are further away. That, in turn, makes our algorithm more efficient since we’ll be heading in the correct general direction at each step. So in the best scenario, we have a complexity equal to the distance of our tile. In the worst, we will cross the whole game and endup with the same complexity as the Dijkstra.

But better than doing a full theory course, it's better to go directly on an example. Let's take the following example, where the red is the starting tile and the green is the end goal.

Everytime a new tile will need to be analyze, we will put the tile in an array?named openTiles. At initialization, our red starting tile will be place in the array.

openTiles.push(startTile);        

Every tile placed in the?openTiles?array will be marked as visited for not going over the same tile twice.

Once done the process can start, the goal is to search first for the accessible tile neighboring our starting tile.

const adjacentTiles = this.getAdjacentTiles(currentTile.x, currentTile.y);        

In the example above, we have 3 of them. For each of them, we will calculate the h, g and f score. I will explain the letter one by one.

In my example, the h (heuristic) score is simply the Manhattan distance between the tile I am actually analyzing and the end tile. If I calculate the Manhattan distance for each of the tile, the result will be this:

So in our case, our 3 tiles has the following h score.

adjacentTile.h = this.manhattan(adjacentTile, endTile);        

Now, let's calculate the g score. In my scenario, every tile has a cost of 1 but we could imagine tiles with different cost such as crossing mountain could cost 3 while a plain could cost only 1.

const gScore = currentTile.g + adjacentTile.cost;        

Finally, we can calculate the f score for each tile, which is just the sum of the h and g scores.

Then, we start over with the tile that obtained the smallest f score.

currentTile = openTiles.reduce(
  (best, current) => (best && best.f < current.f ? best : current),
  openTiles[0]
);        

And we repeat the whole process.

Again and again,

Until the next tile to analyze is our ending tile or until we running out of tile to analyze in which case there is no path to the ending tile.

if (currentTile.x === xEnd && currentTile.y === yEnd) {
    hasPath = true;
    break;
}        

And voila! We found the shortest path from our starting tile to the ending tile in a very optimized way. For getting a full version of the code, you can get a look at it on my GitHub.

Last words

I did not know about this algorithm and it has been a savior in the last competition for winning over some of my opponents. I am still far from the first league but I am getting better and better. I am actually focusing a bit more on this field of programation and I hope to reach the legend league in the next competition. And you, have you ever use this algorithm? Could you say in which scenario?