Pathfinding for Dummies and Artificial Intelligence

Today we would like to give you a glimpse into how we tackle character navigation in Rick Future and how it is done in computer games in general.

Who needs Navigation?
Navigation, or Pathfinding to be exact, is needed in all games that have character moving by themselves – in other words, AI characters. It doesn’t matter whether that is your player character’s best friend and she’s just following you around, or whether it’s an enemy alien trying to eat your spleen. They all need to navigate around the levels to try and get from point A to point B – which is probably you.

Navigation_AI_transparent

 

Why is this difficult? Every toddler can do this!
Pathfinding is a bigger issue than one might think at first. Rarely can a character in a game get from point A to B in a straight line. There might be obstacles in between. The destination might lie in another room, on the other side of a wall. Or maybe there is just uneven terrain. Without Pathfinding, enemies would fall into holes, get stuck behind obstacles or simply walk straight into a wall.

The AI needs to find a path to his destination that leads through a door, or around that big crate in the middle of the room. But while this is a simple task for the human brain that all of us accomplish every day in real life without giving it a second thought – this is a HUGE problem for a computer. Let us explain why.

The AI has no idea what areas it is allowed to walk in, how much of a height difference the character could climb with a single step, or that it should use an open door, but not an open window to get into a house. The entire concept of a window is unknown to a computer. To the code, it is all just polygons. The object in front of it could be a sturdy wall, or it could be a flower.

Navigation_BlockedPath_transparent

 

Giving the computer something it can understand
To make navigation possible, game developers need to give the Pathfinding AI some information about the area that they are in, and in a way that they can understand. This is called a “Navigation Setup”. The most important part of this is defining an area in which the characters are allowed to move in. Here is an example from the engine room of Rick Future, without and with the navigation setup.

EngineRoom_Clean

EngineRoom_Nav

The blue area in the picture above is the area that the character is allowed to move in. Notice how the area avoids obstacles and walls. As long as the character only ever stays inside of this area, she won’t intersect with any of the geometry. This area is set up by the level designer, and is invisible in the final game.

The pathfinding is restricted to the inside of this area. That means, to get from one point to another, an character cannot leave the blue area at any time. That way the character won’t try to walk through walls, or jump up onto the second floor without using the door or the stairs.

The huge advantage of this is that the code that computes the path for a character can be relatively fast. In theory, the code could analyze all objects in the room and try to guess whether it counts as an obstacle or not. But that would eat up a lot of processing power. With just a little bit of extra setup for each level, the hardware requirements of a game can be kept at a reasonable level.

And that’s it!
And this is how basic navigation works in games.
While there are many different algorithms that can calculate these paths, and many different ways a navigation setup can be done, this basic principle is the same for all games, from Call of Duty to Rick Future.

Note:
The AI has a lot of other things to consider that I didn’t mention. Here are a few examples: A character that is very fat might need to take a longer route, because he can’t fit through small spaces. He should also keep a larger distance to the walls, so that his body doesn’t intersect with the geometry. The list goes on, but this would go well beyond an short introduction.

Leave a Reply

You must be logged in to post a comment.

Steam Game

Check us out on Greenlight!
Greenlight



Latest Tweets