Hi All, Stuart here!
As the sole programmer at Hyper Luminal Games it’s my job to juggle all of our technology requirements and I’ll be showcasing some of the interesting tech we have! I plan to keep my posts high level and suitable for all kinds of developers whilst still providing useful tips from my experiences for the more experienced programmers. I thought I would kick off my first coding blog with something I have been working on recently; Pathfinding!
Instead of filling my blog posts with code I’d rather discuss the high level concepts involved and some language agnostic pseudo code, this can be reproduced into functional code in most languages using the pseudo code as a general design.
The last couple of months have seen me implementing Artificial Intelligence in lots of different ways, ranging from a turn-based system for a board game to a complex behaviour system for a real-time strategy game. All of which are based on the same core principles of pathfinding – The process of calculating the best route between two points. There are lots of different ways to do this; waypoints, grids and navigation meshes to name the more common solutions but behind all of these methods sits an algorithm, in games development it is usually some variation on the A* (A-Star) Algorithm.
What is the A* Algorithm?
A* is an improvement on Dijkstra’s algorithm where an additional heuristic is used to determine the most viable search route through the data source.
The example I’m going to show is from our game Pentaction: Medieval, a turn based board game played against the computer. The first step is to decide how to represent the game world, the simplest form is usually a square based grid like we used for Pentaction.
Once split up into manageable sections we can begin constructing our pathfinding. These sections are usually referred to as nodes, these hold information for the pathfinding algorithm to parse through – fitness (f), goal (g) and heuristic (h).
- The value of “g” is the moving cost when travelling from the starting node to the current node. This is inclusive of any additional costs per connection.
- The value for “h” is an estimated travelling cost from the current node to the ending goal node. This is the additional heuristic used to improve the accuracy of the pathfinding but determining the most efficient route more intelligently. This heuristic can take many forms determined by the complexity of the game world being traversed but for Pentaction a simple Manhattan distance was used (horizontal + vertical distance to the goal node).
- The value of “f” is the already known cost “g” plus the estimated cost “h” to provide the total cost from the start to the end. The lower this value the more cost efficient the path is estimated to be.
Additionally for more complex pathfinding information about the connections between nodes can be stored to symbolise more or less difficult game routes such as crossing a river or moving up a slope, this is usually stored as a cost (c). For Pentaction each node and node connection is identical so no additional information was needed but I will discuss this more with an example later on.
A* uses two lists to hold the games nodes, usually referred to as the Open and Closed lists. The Open list holds all of the games nodes that have not yet been entirely explored. The Closed list holds all of the nodes that have been fully explored. The nodes are processed by looking at each of their neighbours and the cost information stored for each movement.
Pseudo-code for a basic A* Algorithm:
Below is my scribbled Pseudo code from the planning stages of Pentaction. Much spelling and grammar fails!
I’ve rewritten the code more clearly below:
- Let P = starting point.
- Assign f, g and h values to P.
- Add P to the Open list. At this point, P is the only node on the Open list.
- Let B = the best node from the Open list (i.e. the node that has the lowest f-value).
- If B is the goal node, then quit – a path has been found.
- If the Open list is empty, then quit – a path cannot be found
- Let C = a valid node connected to B.
- Assign f, g, and h values to C.
- Check whether C is on the Open or Closed list.
- If so, check whether the new path is more efficient (i.e. has a lower f-value).
- If so update the path.
- ii. Else, add C to the Open list.
- Repeat step 5 for all valid children of B.
- If so update the path.
- Repeat from step 4.
A* in Pentaction
As Pentaction is a turn-based board game with limited movement options the pathfinding algorithm is used in a very specific way. The pathfinding is only a small part of a much larger AI rule based system. Let’s quickly step through the pathfinding section of that process:
Firstly each of the AI units are tested against each target unit to see if they can be reached.
Once each Units potential targets are calculated their distance values are stored. Each step is counted and the total distance from the starting node to the goal node is recorded for each move.
The AI rule based system is then executed to determine the most efficient move that the AI can make this turn. This decision is based on lots of different game factors which may well be the topic of future blog posts! Once the best move is identified the values stored from the pathfinding algorithm for this move are recalled and the Unit is moved on the game board. In this case very simply the best move is to take one step forward to get closer to each target equally.
A* Using Connectors and Obstacles
To demonstrate the use of additional node information I have produced a simple puzzle example. The puzzle is a simple path builder where the player must align the tiles correctly by rotating them to produce a complete path from start to finish. In this example the path must join the two blue squares, creating a seamless dirt road between them. The red square rocks are obstacles which cannot be passed or moved.
The additional node information is made up of two things; firstly if the node is a walkable tile or an obstacle and secondly the connecting edges of the tile. The connections for each tile are based on the path shape. The algorithm is only able to transition from one tile to another if both tiles has touching connectors. These connectors are repositioned as the player rotates the pieces to complete the path.
The pathfinding algorithm is run in real-time to check if a path has been completed. Once the path has been found the puzzle is locked in place and the algorithm shows the completed route.
I hope this simple introduction will get you excited to implement your own pathfinding solutions or even spark some creativity in your current implementation!
Thanks for reading, hopefully you enjoyed it and I’ll be blogging again soon!
Excellent A* Blog Post: http://www.policyalmanac.org/games/aStarTutorial.htm
Comparison of Techniques: http://www.gamesitb.com/pathgraham.pdf
Simple Example: http://www.raywenderlich.com/4946/introduction-to-a-pathfinding
C# Source Code: http://gigi.nullneuron.net/gigilabs/a-pathfinding-example-in-c/
Dijkstra’s Algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm