What is pathfinding ?

Pathfinding is the art (let’s use big words here šŸ™‚ ) of finding a path between two points : a start and a goal.
It’s a whole field of artificial intelligence in computer science.
You can find pathfinding uses in robotics, GPS navigation systems and video games.

Pathfinding uses algorithms to compute a path.
Algorithms are a “step-by-step procedure for calculations” (source: Algorithm article on Wikipedia). Basically it’s a set of instructions for the computer to execute a specific task.
In video games, pathfinding is used to give directions to non-playable characters (NPC) most of the time. It’s also used in real-time strategy (RTS) games or in massively multiplayer online role playing (MMORPG) games where the player can click somewhere on the screen and his character will go to the destination clicked.

But how does the computer know where the player has clicked?
In a 2D game, all the screen coordinates have an equivalent in the game map.
In a 3D game where you can move the camera, a straight ray is projected from the click position toward the closest obstacle.

Also how does the computer know where a character can walk, move in a game world?
You have to specify it thanks to an abstract structure. It’s a set of data that’s abstract because the player can’t see it during normal play. (there’s a lot of other abstract structures in video games to help developers map events in the game levels)
Here are some of the most used different type of abstract structures for pathfinding:
– Grid
The default one and simplest to understand. Unfortunately this one needs a lot a tiles to take into account obstacles which are not rectangular. And when we need more tiles, we need more computation.
– Triangulation
It’s a grid… but made only of triangles. It’s much better to take into account obstacles
– Waypoints
The more limited one. In this one, characters only move on straight line predetermined.
– Navigation mesh
The most recent and used one. Here characters move from area to area. In each area they can move freely in straight line to any point. To move to another area, they must reach a point near the intersection of the current area and the next one.

Most of the time, these structures are in 2D even in 3D game, to make it easier to do the computation for both the developers and computers. The speed of reaction of a character or a unit must be very quick so the player doesn’t lose patience. So sometimes it’s even better to use an algorithm who find a good-enough path between two points than a slow algorithm who will find the shortest path.
But we can divide pathfinding algorithms in 3 types:
– The ones to find the tiles to use in the abstract structure
– The ones finding the way in the selected tiles before. So it will determine by which point and how it should cross each of the selected time. It seems easy but it’s not. (more on that in a next post)
– The ones smoothing the path determined by the previous algorithm. Depending on the unit moving, if it’s a human character we can make it turning in curbs instead of straight angles, going straight instead of zig-zags, etc.

All of this, is meant to give you an outlook of what pathfinding is. I hope it interested you. I’ll probably write more about it in a future post.

To end this post, this is what happen when pathfinding is not correctly done in video games:

For more information, about this subject:
Amit’s A* Pages
Fixing Pathfinding Once and For All

– “Path Search Demo” software from Bryan Stout







Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: