Recently, I have been implementing A* in my game. Let me tell you a little about it.
For those who do not know what this random shiny letter stands for, A* is a -probably the most mainstream- pathfinding algorithm. It is an algorithm that draws the shortest path between nodes (or tiles) while avoiding obstacles and considering that some links between nodes can take longer than others. It is the same as Dijkstra’s algorithm except A* looks for the shortest path while Dijkstra’s evaluates all possible paths.
The implementation phase was pretty straightforward. I followed a guide (I lost the link sorry 🙁) describing the algorithm for a square tilemap. I did not pay much attention to adapting it to hexagonal tiles. Iterate quickly and break things, we will see!
To test it, I asked my algorithm to compute a path from the bottom left tile of the map, to the center.
Okay, so there is clearly an issue here. Either my Pathfinder hit speedbumps on its way to the center or my algorithm has a problem. Let’s study it step by step.
I will not go into the details of the algorithm but here are a few key information to comprehend the problem. We select the tiles we visit based on a variable I named movementProgression. It is the sum of two things:
Sea Otter GamescurrentMovementCost, a variable that is incremented by the travel weight each time we visit a new cellestimatedRequiredMovement, the distance between the current cell and the destinationThis sum pretty much remains constant throughout the travel when faced with no obstacles and with equal transition weights because the movement cost increases while the distance decreases.
💡 I reused my tilemap generator variant (showcased in article #6) that shows the tile distance from the map centre. Every cell of the same color on a circle is at an equal distance from the centre.
The accessible cells are 2 and 3.
movement cost of 1 and an estimated required movement of D (D being the distance from 1 to the target)movement cost of 1 and an estimated required movement of D as wellFor each accessible cell, the movement progression is worth D + 1. So we arbitrarily choose a cell: cell 2.
Until here, everything works as intended. However, now, we would expect the path to continue onto either 4 or 5 but not at all onto 3.
The accessible cells are 3, 4 and 5.
movement cost of 2 (1 -> 2 -> 4) and an estimated required movement of D - 1 (we are one step closer to the center)movement cost of 2 and an estimated required movement of D - 1 as wellmovement cost of 1, estimated required movement of DNow, we realise that all three tiles have a movementProgression of D + 1. This means that, for the algorithm, they are all equally efficient when it comes to reaching our destination! This is clearly wrong because going from 2 to 3 does not take us any closer to our target...
The origin of the problem is very obvious: I tried to apply an algorithm thought for square tilemaps to hexagonal tilemaps. With squares, we evolve along two axes and have no situations where taking a detour could be considered equally efficient as another path. In my case, however, I use a hexagonal coordinate system, which technically means three possible axes to move around. Moreover, my coordinate system only has two parameters (odd-r configuration) whereas some three-parameter coordinate systems exist. This leads to some loss of information when switching from one horizontal line of hexagons to the other.
Firstly, the issue seems to come from cell 3 having a movement cost of 1. Indeed, when you think about it, if we choose to visit cell 3, our path will look like this: 1 -> 2 -> 3. As such, cell 3 should have a movement cost of 2. Following this theory, I thought I needed to recalculate movement costs for already existing neighbor cells when searching for new accessible cells.
However, later in the algorithm, we will need to do what is called backtracking. This step consists of going from the destination back to the starting point by searching for the cell with the lowest movement cost. This means that if I were to recompute the movement cost, the algorithm would not be able to consider the path 1 -> 3 if it lead to a dead-end. In short, not possible….
Then, I thought about what our issue meant in terms of concepts rather than formulas: because our movement cost calculation is “faulty” we need to give more importance to the decrease in distance to the target when walking the path.
Then, what is the solution? How about instead of summing the movement cost to the remaining distance to get the movement progression, we sum the movement cost to twice the remaining distance? As such, a decrease in distance is two times more relevant than an increase in movement cost!
movementProgression = currentMovementCost + 2 * estimatedRequiredMovement
To conclude, I did not test more complex use cases at the time of writing this article. And to be honest, I totally expect this solution to “bite me in the ass later on” (pardon my french) when I test it against obstacles and weighed cell transitions. Regardless, I find this topic interesting and hopefully, it will motivate some of you to implement your version of A* 😃
Thank you for reading to the end! I hope to see you in the next post. 🦦