Introduction to the game and pathfinding
In our game Million Lords, the players can move their units from one city to another. It can be to either strengthen or to go attack an enemy city. The infinite procedural mapping is based on a hexagonal tiles system. The road from one town to another is full of impassable obstacles, such as mountains, rivers and even oceans. First, we mapped out the movements of our units in a linear structure: that way, the units were cutting into landmarks in order to reach their final goal.
Like you’ve probably already guessed, this trajectory isn’t coherent. Of course, we want the units to go around these obstacles while choosing and then following the shortest/fastest path. That’s why we are going to create a pathfinding system.
So, what is pathfinding, exactly?
Pathfinding is an algorithm which will find a way to get an element from one point to another, while following some conditions. It is set in an environment: here in our game, the world of Million Lords.
There is several algorithms that allow us to create a pathfinding system:
- The algorithm Greedy Best First Search: it can use promising trajectories, but it won’t find the shortest way.
- The Djikstra algorithm: it can find the shortest path, but it can waste time going around in uncoherent directions.
- The A* algorithm: this algorithm is based on the Djikstra algorithm, but it will focus more on the objective that is to reach.
At first, we chose the Greedy Best First Search algorithm. The easiest solution was for us to follow the tiles until the units reached the target. We’ve implemented it in the first version of the game, but the cost calculation was too heavy and long.
For short distances, the calculation time was reasonable but for long distance, the time could go over 10 seconds! This slowness was caused by the number of tiles it needed to analyse before reaching its destination. The performance wasn’t satisfactory for the use we made of it so we finally switched to the A* algorithm.
Why the A* algorithm ?
In our case, the A* algorithm is the best compromise between calculation cost and the pertinence of the calculated solution, since the goal is to find a unique solution (the city)
The calculation of the best path to reach a city is executed in real time and it has to be as fast as possible.
To reach the target, the algorithm uses a heuristic function which allows the user to estimate the cost of the shortest way to get to the target. This way, it gets rid off all attempts that are to “costly”, such as starting the search for the best path by going in the opposite direction from the target.
The tiles coordinates
The map of the game is based on hexagonal tiles, each one possessing a real coordinate in the map (for example x : 2.732 et y : 5.630), but also an axial coordinate (x : -1, y : 1)
Thanks to an equation we can go from real coordinate to axial coordinate and so on.
We use axial coordinates since they make the calculations easier to execute. For example, we can determine the 6 tiles next to another tile just by adding or subtract 1.
The principle
As the game is based on a tile system, it gives us another constraint. Each tile is a passing point that units must go through.
We go from the yellow tile to the red one:
- The yellow tile has 6 neighbours but thanks to the heuristic function, the algorithm is going to study which ones are closest to our goal, or which one is closest to the right.
- Once the tile is chosen, it will keep going with the other neighbouring tiles until it reaches its destination.
- If it encouters an obstacle, it attributes a weight correlating with its position and with how far it is from the target.
- Then, it searches again while having in mind the previous attempts.
On the image we can see that our algorithm only analysed the orange tiles and not all the tiles, which saves us a considerable amount of time and resources. Below you will find a simulation with a prototype and an almost immediate execution time for a path of almost 200 tiles.
Once the goal is reached, a last check is made to check to entirety of the path and delete all unnecessary delays.
The path the units will follow is composed of the entirety of the coordinates of the tiles it needs to reach its destination. Here is what is looks like in our game :
If you liked this article, please consider checking out our other articles :
- How to improve your workflow with Unity Cloud Build
- Devlog #2 : Game UI is your friend
- Devlog #1 : Art? What is art?
and sign up for the beta ouf our game here !
Article written by Robin GORNY
Ressources :
https://www.redblobgames.com/grids/hexagons/
https://www.redblobgames.com/pathfinding/a-star/introduction.html
