A* Pathfinding algorithm: Classic and Custom approaches
- A* Classic
- A* Custom: our technique
- Known issues
- Interactive application
This is an informal article about the A* Pathfinding algorithm and the modifications made on it in order to solve the issues on our game project. This article contemplates a brief explanation of A* classic, the necessary improvements made on the algorithm as well as an interactive application. In the interactive application, it is possible to verify the execution both A* versions.
A pathfinding algorithm for a grid type of movement was necessary to the game. The desired movement could only be performed on vertical and horizontal directions (i.e. no diagonal steps). This pathfinding problem could be solved with a simple A* pathfinding algorithm implementation.
However, our game had some special movement mechanics that required features on our pathfinding implementation that the classic A* could not offer:
- The movement cannot be performed backwards.
- The classic A* has two types of tile: walkable and unwalkable. However, in our case, there are three types: walkable without cost, walkable with cost and unwalkable.
- The maximum cost that a path can have to reach the target.
- Dynamic blocked coordinates that are not relatable with the tile type.
Therefore, to better understand the features added on our pathfinding algorithm, it is necessary to understand how a basic implementation of A* works.
Before explaining how the A* algorithm works, it is necessary to understand the variables used on it. They are F, G and H values:
- F is the sum of G and H;
- G is the distance from the Initial point;
- H is the heuristic distance to the Target point, i.e. when counting distance, the map tile type does not matter, both walkable and unwalkable are valid.
Moreover, every map node has its own F, G and H values and a pointer to its parent node. The parent pointer is used to backtrack the path afterwards. So, the node struct will be as following:
A basic implementation of A* algorithm, written on a pseudo-language, is shown below:
A* Custom: our technique
As the classic A* algorithm did not offer the necessary features to solve the game pathfinding issues, the following features were added in the improved A* solution:
1. Cost feature
As the movement of the character is limited by movement points, which are consumed based on the map tile cost, modifications were added towards solving this issue.
- On the map, costs were added to the walkable tiles (tile cost). It can cost from zero to any positive number.
- The node structure now carries another variable: the cost to walk until that point (path cost). It is the sum of all parent nodes tile costs from the initial point to the current one.
- As input on the algorithm, the maximum cost that can be afforded on a path to the target must be set.
2. Blocked coordinates
In the grid, some coordinates could be blocked dynamically for specific time period. These blocked coordinates are not the same of unwalkable tiles because the former is set by the character perspective (dynamically) while the later is a map characteristic. As example of blocked coordinates: a specific character on the game cannot walk on the grass even it being a walkable tile on the map, so all grass will be blocked coordinates for him/her.
- As input on the algorithm, an array of blocked coordinates was added. These coordinates were blocked despite of their tile types.
3. Blocking initial movement directions
In the game grid movement, there are occasions on which moving backwards is not allowed. As the A* classic already ensures that there are no back steps on the final path, it is sufficient to block only one of the initial movement directions, the backward direction.
- As input on the algorithm, the direction that will be blocked on the first iteration of the algorithm was added. As example, if the character is facing right, it will not be able to move to the left on its first step.
In order to match the mentioned features above, the following node structure will be used on this improved version of A*.
- C_Value, the path cost from the initial note to it (based on parents tile costs)
An improved implementation of A* algorithm, written on a pseudo-language, is shown below:
- For games, be careful with the size of the grid because it increases the number of iterations to find the path.
- Adding C (path cost), can increase the number of iterations, as there is the possibility of a closed node becoming opened again because a new path with acceptable path cost was found to it.
- This solution does not find the cheapest path, but the shortest given a maximum path cost. Thus, it is a good application for games when the movement points are reset every round.
This improved A* algorithm was developed for a game called Alchemy Arena (https://mooncraftstudio.itch.io/alchemy-arena). It was used on the game as a solution for the AI movement and skill control. Feel free to use the content of this informal article in your games, applications, solutions.