After processing an order given by the decisional system, our AI Agent will most likely need to move from point A to point B. This by also avoiding obstacles, keeping track of the best terrain to use, and much more.

How can this be achieved? And, most importantly, how can it be efficient?

By the end of this article, you will understand:

• what is the difference between pathfinding and a pathfinding algorithm,
• what modern game engines already have for pathfinding,
• and how can it all help you in your upcoming game.

Let’s get started!

Pathfinding 101

The modern game engines of today do a great job hiding the complex layers of a pathfinding process.

But what is pathfinding, and why should you care about it?

Let’s start with why it’s important to understand the core concepts. First, imagine you are using a default system readily available in your game engine of choice – be it Unity, Unreal, or Godot. Most likely it’s a form of NavMesh (navigation mesh).

What you might not be realizing is that you and other 10.000+ game developers are using the same exact way of moving an object from A to B. Why is this a problem? Most cars use the same wheels and no one cares, right?

When you are using your car its tires are a commodity. A common good that is almost indistinguishable from the other tires. Do you want your game to feel exactly like the other 10.000 games? If so, close the tab and stop reading.

Don’t get me wrong. It’s easy and convenient to use the default systems for a while. But if you want to take your game to the next level, you need to seriously consider offering some unique functionalities “never seen before”.

Now what makes a pathfinder? It’s made out of a domain (or space, where the action happens) and an algorithm (usually the one that determines the sequence of steps used to arrive at the destination).

Some of the most common domains are grids, graphs, navmeshes.

The most common algorithm used in game development for pathfinding is A*.

You might have guessed the bigger picture by now. We need to take the map where the action happens and apply on top of it an algorithm like A*. This will return a sequence of steps that our AI Agent needs to take from its current position to reach the destination.

This is a pathfinder, in a nutshell.

A* and other Algorithms

The brain of the whole system is the algorithm. One of the most used algorithms in gamedev for pathfinding is A*.

Luckily, most game engines have this one already implemented for us to use. In engines like Unity it is hidden inside the navmesh functionality and unfortunately, we cannot just use A* on a different domain. This is one downside of the engine because it forces developers to use navmeshes if they want to use the built-in systems.

But what if your game doesn’t have a mesh-like structure but rather a hex grid, or just a plain grid? Then you have to implement A* from scratch. But not if you use Godot.

Godot does offer pathfinding both at the navmesh level as well as a stand-alone A* algorithm ready for you to use. Should you try Godot? Definitely. But that’s for another episode.

How does A* work, then? It starts from a point A and tries to expand and move towards a point B. On its way, it might encounter obstacles and needs to avoid them. One of the worst cases for A* are obstacles that are U-shaped because the tendency will be to go straight to the target and not see the bigger picture – that by doing this you end up stuck between the walls.

This is, of course, an oversimplification. In my upcoming Game AI course I go deep into details for a simpler pathfinding algorithm, with examples. If you want to find more about that, check here.

Navmeshes

No pathfiding discussion can leave out one of the most important ways to process the map and make it pathfinding-ready: enter navmeshes.

A navmesh, or navigation mesh, is a data structure that is automatically generated by the engine on top of your existing 3D objects. It consists of convex polygons chained together, forming a simplified version of your map.

This simplified version can then be used to run an A* algorithm which will generate a path from one point to another.

In most cases, this is more than enough. At least for testing purposes. If your map is more exotic such as a grid, hexagons or even planets in space then a navmesh is a no-go for you.

There might be ways to try to fit this structure to handle other things but my advice is to understand where it shines and where it doesn’t and try to use the best available one. It will save you a lot of time in the process.

What’s best for you

Is there such a thing as the best pathfinder? Depends. If we are talking about raw speed, A* might be the fastest. But there are use-cases that the fastest algorithm cannot solve. One of them is generating a flow field for an Real Time Strategy Game.

Try experimenting with more than navmeshes and see what works for you.

All the best,
Adrian.