A* Pathfinding algorithm: Classic and Custom approaches

Summary:

- Introduction
- Issue
- A* Classic
- A* Custom: our technique
- Known issues
- Interactive application
- Conclusion

Introduction:

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.

Issue:

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.

A* Classic:

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:

NODE STRUCT:
- F_Value
- G_Value
- H_Value
- Parent

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.

New features:

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

New feature:

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

New feature:

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

Improved algorithm

In order to match the mentioned features above, the following node structure will be used on this improved version of A*.

NODE STRUCT:
- F_Value
- G_Value
- H_Value
- C_Value, the path cost from the initial note to it (based on parents tile costs)
- Parent

An improved implementation of A* algorithm, written on a pseudo-language, is shown below:

Known issues

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

Interactive application:

Try our interactive application on itch.io

App link: https://mooncraftstudio.itch.io/a-path-finding-interactive-custom

Conclusion

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.

Written by

Luciano Farias Puhl - @dotlut
Taylor de Oliveira Antes - @AORolyat