[In this article, first published in Game Developer magazine's 2011 Career Guide issue, indie game developer, educator, and FlashPunk API creator Chevy Ray Johnston details the basics of AI pathfinding.]
I'm currently located in my 10th floor apartment and I want to get to the coffee shop down the street, so how do I get there? It's time to do some pathfinding.
Everyday Pathfinding
Well, here is my usual route: exit my apartment, turn the corner down the hall, enter the elevator, exit the lobby, and then walk down the street until I reach the shop. I don't walk around the building, because that would take longer; and I don't jump out the window because, although that would be quicker, it would likely be detrimental to the condition of my spine. So I start along my path, but alas, the elevator is broken.
Suddenly, my optimal path to caffeinated goodness has been intercepted! But I've considered this possibility (or at least some wise builders have), and I continue on to the stairwell at the end of the hall. Since I'm on the 10th floor, this is slower than the elevator, but eventually I make it to the bottom and exit out the back of the building. From here, I recalculate: I need to get back on track to the coffee shop, so I walk around the building to the front-facing street, and voilà, I have reunited with my optimal path and can reach my destination.
Welcome to pathfinding, something humans do every day when we get up on our feet and walk from A to B. The question of how to do this in games is something that game developers are faced with all the time, and have been solving and re-solving for decades.
For example, let's say you're making a dungeon crawler or an MMORPG, and the player clicks on a location on the screen, indicating they want their avatar to walk there. Unless your game world is painfully empty, then there are going to be obstacles that they will have to navigate around, under, or deal with in order to reach that location. Or perhaps you're making an RTS game, and you select a group of tanks you've just built and order them to rendezvous somewhere. They're going to not only have to do the same thing, but also avoid running into (and overlapping with) each other as they do so.
When dealing with games, you're dealing with abstract game objects, which don't intuitively know how to navigate around each other and terrain obstacles. In fact, they don't even inherently know that any of these other objects exist. It's your duty as a programmer to use the information available in your game world to communicate to your objects what paths you want them to take and how to determine those paths.
The more complex your worlds are, and the more conditions your pathfinding requires, the more complex this solution becomes. But to jump right into some of the more advanced methods employed by programmers today would be overkill. Being able to break down a larger procedure into a set of specific, logical instructions is an invaluable skill for a game developer. By starting with a simple problem, solving it, and then introducing complexities one by one, we can approach the problem of how to get from A to B one baby step at a time.
Break Down The Problem
If we take a look at Figure 1, we have everything we need to solve this problem at its most basic level: a player, coffee, and a playing field. I want to get to the coffee, but to do so, I have to navigate across the playing field, which I have broken down into a set of grid cells. I have done this to simplify the problem as much as possible, so we'll say that our game player (myself), can only move between adjacent cells (right, left, down, or up).
Figure 1
Our pathfinding is limited to the information we have, so what is that? We have our start position (0,0) and our goal position (4,2). Now all we have to do when we move our player is compare his position with the one he wants to move to, and determine his movement based on that. If you were to code that, it might look something like this:
Move Horizontally
if COFFEE IS TO MY RIGHT
MOVE RIGHT
else if COFFEE IS TO MY LEFT
MOVE LEFT
Move Vertically
if COFFEE IS BELOW ME
MOVE DOWN
else if COFFEE IS ABOVE ME
MOVE UP
So here we have two chunks of code. The first moves him horizontally, and the second moves him vertically. If we keep alternating between the two as they're running, starting with the first, the results will be as in Figure 2.
Figure 2
Coffee achieved! Even if you don't understand that code, the concept should be quite clear. If the coffee is right, move right, otherwise move left; the same goes for up and down. Even using very simple logic like that, Mr. Happy here finds his coffee using what appears to be the shortest path available, in six steps.
It's really helpful for game developers to think critically about the pathfinding problem they need to solve, and to solve that problem in the most fitting way possible. Since there was nothing blocking Happy's way to the coffee, this particular solution was easy. So what happens to this solution if we suddenly toss an obstacle in the way?
In Figure 3, you can see that the method works for one step, but then it halts. Our logic says, "He needs to move right, but he can't," and "He's in the right y-position, so don't move vertically." This means he doesn't move anywhere once he hits that wall. He is forever caffeine-deprived, poor fellow.
Figure 3: We've all had moments like this.
Since we've introduced a complexity that breaks our pathfinding, we now need to introduce a solution to handle that complexity. We need to tell our character to do something different in the case where he encounters a wall. So what I've done now is adjust the pseudo-code from before to take the wall into account:
Move Horizontally
if COFFEE IS TO MY RIGHT
if WALL IS TO MY RIGHT
MOVE UP
else
MOVE RIGHT
else if COFFEE IS TO MY LEFT
MOVE LEFT
What we've done here is add another condition to the horizontal portion of our code, which will handle the case in which we hit a wall. If we then apply this, our happy protagonist will make it to the coffee as seen in Figure 4.
Figure 4: Wall: 0 Coffee: 1
While this worked for that particular case, it's easy to see how we could once again break this method: if we add a whole bunch of walls on top of this one, our player will just move up along them until he can get past. Considering that it would be much faster to go under them, instead of all the way around, this solution isn't really our best.
You'll notice that the pseudo-code is a branching tree, and the branches of this tree are always the actions in red. The blue parts are where we use logical conditions to split the tree into more branches to handle different cases (more complexities). The more complexities we have, the more conditions and branches our logic tree will have, and the better our player's movement will be.
But sometimes there are so many possible conditions that it is nearly impossible for a game developer to foresee and handle them all. Or they can, but the result will be such a large and complex tree that it uses up too much computation and slows down the game. What many clever programmers have done to handle this is come up with special algorithms that are designed to "search" an area, rather than evaluate behavior on a step by step basis, until they find the target location. I don't have enough time and space to explain all these algorithms, but I will cover one in particular, because once you understand how it operates, it is much easier to make sense of the context in which pathfinding code often occurs.
