Let’s take a look at pathfinding. Pathfinding is the process where the game can determine a suitable or optimal path from one point to another by traversing the game’s terrain. It’s a critical part of almost all games (RPGs, RTSs, turn-based strategy.. basically anything that has a variable terrain or map is going to need a way to determine paths across it)

Pathfinding is hard in the sense that it takes a lot of computing power to accomplish. And it doesn’t get easier with newer hardware either – as computers get faster, games generally incorporate more complex terrain and more inhabitants, so pathfinding stays complex. For example, the average RTS devotes 30% of CPU time to video (prepping stuff for the GPU, plus UI etc), 30% on AI & scripts, and 30% on pathfinding (the remaining 10% on everything else).

Icefall uses two different pathfinding algorithms to improve efficiency. Being turn-based, I don’t have to worry about time-critical calculations, so paths should always be optimal path (it’s acceptable for realtime games to take a ‘best guess’ or suboptimal path – you can see this in games like Dragon Age or Diablo: if you click somewhere far away or obscured by obstacles, your character will try to walk there but they get stuck). Let’s talk about how Icefall’s pathfinding works specifically.

A* Pathfinding Algorithm

A* (Wikipedia entry) is the method Icefall uses to calculate the player’s path. If you click on a distant doorway or shop, your character will move towards it using the fewest steps possible, regardless of how convoluted the actual path is.It works by starting at the player’s current location, and looking at all of the neighbouring squares (all the squares that the player could reach in a single move). For each of those squares, it looks at the *absolute* distance between this position and the goal position (that the player is trying to reach). The absolute distance is just ‘the distance in a straight line, assuming there were no obstacles’.

This (simplified) example shows a very simple dungeon with a start and goal square. The three initial candidate squares have been marked with red circles (this is called ‘the open list’ of squares), and the number within represents the absolute distance between each square and the goal.

The algorithm selects one of the squares from the open list that has the lowest absolute cost. So in this case, it could select either of the “6” squares. Let’s say it picks the bottom one (to try and go in a straight line). The process is then repeated, with all of the neighboring squares from our new square evaluated for their absolute distance to goal – but with a new step. We add to that distance the number of squares that we have already taken to get there (in this case, 1, since we’ve only moved once so far). Note that we also briefly consider the start square, and the other two red circles, but we discard them because they’re already in our ‘open’ list.

We’ve found two new candidate squares to add to the ‘open list’ – both are of absolute distance to goal 5 and have a distance travelled of 1 (+1 in the diagram). Because we’ve now fully evaluated that bottom ‘6’ square, it’s moved from the open list to what we call the “closed list” (which just makes sure we don’t end up re-evaluating squares that we’ve already done).

Now, the process continues by picking one of the squares in the open list with the lowest absolute distance + distance already travelled. If multiple squares have the same total, we pick a square with the highest distance already travelled first – this ensures that if there is a direct path to the goal, we find it immediately. If we continue this for a few move evaluations, we’ll end up with something like this.

We evaluated the next two squares in the dead end, as they both had a combined total of 6, and they had the highest distance already travelled values. But then we reached a dead-end there (there were no valid moves from that 3/+3 square), so we next evaluate the remaining 5/+1 square. on the open list. It finds two new squares to add, a 6/+2 and a 5/+2. After this picture, the lowest total value that’s still open is actually the original red circle (it has a cost of 6. Our other open squares have values 7/0, 6/+2, and 5/+2). When evaluating it’s neighbors, we find that it has a shorter route to the square directly above it. Instead of 6/+2, it can be replaced with 6/+1 – this is fewer squares travelled to reach the same goal. So this square value is replaced in the open list. Evaluation then continues. Eventually, we’ll end up with the following table, and the optimal path.

 

In this contrived example, we end up evaluating almost every square, but the important part of this algorithm is that it will ALWAYS find the MOST EFFICIENT path possible. Apply these steps to any path (assuming the path can actually be reached), and you will get the best possible result in the end (note that this path has effectively “skipped the corners” in the tunnel, without us having to do any special coding to take this into account).

 

Summary

So, that’s how Icefall calculates paths for the player. Seems easy enough, but you can see a lot of squares may end up being evaluated (especially in a big dungeon that has dead ends). So, how do we calculate the pathfinding for monsters? Since there may be dozens or hundreds of these in an Icefall dungeon…? Stay tuned for next time!