Category: FrontPage

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.



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.



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.



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.

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.

Captain on the bridge!

During the last weeks we have spent a lot of time designing the Eric’s bridge. We went through quite a few iterations until we ended up with something that we could all agree upon. Coming up with something that visualizes the bridge as it is know from the original stories while keeping it open to everything we need to do with it in the game was a bit tricky. The bridge couldn’t be too huge and empty for example since we need some space for the characters to move around and the navigation system to work properly. Also we needed seating for all three characters in addition to enough open space to walk around an interact with the objects in the location.
The bridge of the Eric can be considered a hub between different locations in the game. In order to travel to different planets or space stations Rick, Hubert or Evi need to be on the bridge and use the navigation computer to plot a course for the destination. This also involves a new little mini-game we haven’t yet talk about :) Furthermore being on the bridge allows you to actually look out in space and see which location you are currently in. This works out really well, since you can look out and see the stars and planets ahead of you or the vast landscape of an alien planet the Eric has just landed on. This really adds something to the mood.

As usual everything is to be considered work-in-progress and we might make further changes and tweaks later on. But it is always good to get stuff out and get feedback, so we wanted to share the current state of the location with you. Have a look at the screenshot below and let us know what you think. As usual all feedback is welcome.


The screenshot was taken in-game and shows the the three stations for Rick, Evi and Hubert. We have the pilot chair with the navigation computer in the front and Hubert and Evi’s stations on the sides. We are still playing around with different camera positions to what looks best. What you see in the screenshot now might not necessarily be the final perspective used in the game, but we couldn’t resist showing you a nice space vista! You can blame our Crytek heritage for this irrepressible urge :) Have fun!




Steam Game

Check us out on Greenlight!

Latest Tweets