The different methods used in pathfinding, and how to implement them.
Hello again!
This article about Pathfinding, or “Entity movements in a 3D environment” will be in two parts.
This one will be an introduction on the subject while the second one (coming next week) will be about different ways to achieve this type of movement.
HOW TO MOVE AN ENTITY IN A 3D ENVIRONMENT?
Before answering this question, I’ll make sure we are on the same page about what I mean by “moving an entity” in this case.
In video games many elements need to be able to move around in a logical way in the environment. I’m not talking about every single things that move around, but only about the ones that need to follow a path or a calculated direction that is created based on rules put up by us, developers.
The first thing that comes to mind is AIs. They are the main type of entities in games with a need to move around without going through walls. However there are other type of entities that have the same needs. For example, units in an RTS moving on the map without going through building or other units.
Moreover, this article is about real 3D movements: moving on all three axis in the game world. Most games have 2D movements even in a 3D world. When your character is walking on the ground, you can move: forwards, backwards, left and right, but most of the time not up and down.
However before jumping directly on 3-axis movements, I’ll talk a little bit about two dimensional movements. Many elements are common between 2D and 3D movements, even most of the vocabulary. This will help approaching terminology and some basic type of algorithms.
If you are only interested about 3D movements approaches; you can read the second part of this article (coming out 06/10/17). In this second part I’ll present three ways to move an entity on 3 axis in a logical way in games.
Let’s Start!
2D METHODS & TERMINOLOGY
Even today, most games use 2D movements. On a plane surface, many algorithms exists to calculate a path. And this while taking obstacles in account. You certainly already heard of it, it’s called “Pathfinding” systems. The goal of these algorithms is to find a path in an environment. The most common type is A* (pronounced “A star”). I’ll talk a little bit about this one.
The A* is an algorithm that works with multiple points in a graph called nodes. It uses a starting node and a destination node as parameters and calculates the most effective path between those nodes in the graph. In a simple way, this algorithm works by comparing a movement “cost” at each node. The cost is the distance between a node and the destination. By calculating this cost and moving to each neighbor’s nodes, this system makes it possible to detect obstacles and find the optimal path by using the nodes that have the best cost to arrive at the destination.
Here we can see two implementations of an A* algorithm. The one on the right seems faster but returns a path that is less optimal than the left one. These implementations are different on the way they handle obstacles. The left one restarts from the starting point of each neighbors nodes at every obstacle encountered while the right one expands on neighbors nodes when facing an obstacle.
This shows us one important thing about A*, it’s a heuristic algorithm. Meaning that it will return a feasible solution in the shortest time possible, but it may not be the best solution, nor the more optimal or “natural” one.
That’s why it’s used in video games, where the perfect precision is most of the time less important than a balance between computing time and usable result. For example, the Dijkstra Algorithm that is the base of the A* is a non-heuristic one. It is much slower, but returns the best possible path in the node graph. To achieve that, the cost is calculated for each nodes of the graph. Therefore, this solution is not convenient for games except if you absolutely need the best path even if it’ll take much more time and processing power.
However, this type of algorithms are not always the best option for pathfinding. By nature, using an iteration by neighbor nodes can be slow in some environments.
Right here we can see two examples of situations where A* type algorithms are terrible. On the left, the calculated path does not seem optimal at all. On the right we can see the same type of problem. In both, the path to arrive at the destination is opposed to the direct direction towards it. Going node by node towards the destination is not a great solution to resolve this type of pathfinding problem. A* is not performing well in a complex environment where the path to a destination is opposed to its direct direction. It can still be used, but calculations will be longer.
Even then, A* is still the most used type of pathfinding algorithm today in games. Sometimes it’s even bi directional, meaning that the calculation is done in both way between the starting point and the destination point to get a faster result when both path meets each others.
Rare are other solutions used in games. Most of the time, an A* solution is implemented to fit the game needs. Other systems exist like the “Breadth First Search”, that calculates each neighbors without taking direction to the destination into account. Or the “Best-First” that computes the path from the first best node available defined by a set of rules. And some other ones I’ll talk about a bit later, but that are only used in specific cases.
These algorithms are convenient to implement and easy to visualize in a 2D environment as they are working in a 2D graph. An invisible layer can be created to represent this graph and entities can be linked to this logical layer to compute their movements.
In a 3D game, these algorithm are still usable. To use them we generate navigation meshes. A Navigation Mesh, or Navmesh, is a 3D object in the game world which covers every space where entities can move around. Like in a 2D game, it’s invisible to the player. A point between entities and this navmesh makes it possible to do the same calculation as in 2D. It’s this technique that most games use today. That why, in most engines, your entities using pathfinding must be on/touch a navmesh. And in most games, it’s enough. Most entities only need to move on the ground, from one plane to another, on which a navmesh can easily be created.
This way, most 3D games use the same A* algorithm that we just saw. We still find a graph of nodes on a 2D plane (each face of the navmesh), and blocking elements are calculated during the navmesh generation. Every part of the environment that should not be navigable by an entity can easily be removed just by making sure that no navmesh will be generated on these parts. Often, the engine will automatically make the link between multiples navmeshes to make the pathfinding seamless in all the environment. Sometimes, these links are put by hand when making the map.
The Navmeshs themselves can be placed by hand, computed automatically when creating the map or dynamically computed in runtime to update to a moving environment.
In some rare cases, another system using Navmeshes is used to stock navigation data. Like textures for example. The only condition to use an A* algorithm is to have a set of nodes to compute the path between them. The way to stock those informations makes it more or less easy to add more datas. On a navmesh each face can have a different cost for example. We can also use each pixel of a texture as an information about a node that we project after on a 3D surface for example. These other ways of stocking path-related datas can be really useful in another type of pathfinding system:
THE FLOWFIELD
Flowfield is a type of pathfinding used mainly in RTSs recently. It’s perfect for moving around many entities. This system works with multiples “Fields”, or layer of information forming a set called a Flowfield. Its goal is to detach pathfinding from the classical “one path solution” of most systems. In a game with multiple units on the same space, moving them around with dynamic obstacles requires to compute for each unit a new path at each environment change. This can be really hard on the computation side.
In a Flowfield system, at least 2 layers are necessary. First, a “Cost Field” or Heatmap: in this layer, an algorithm (like A*) computes the position of each node towards a destination and obstacle on the way and assigns a cost for each one. The cost of the destination being 0 and expending when going away.
A second layer called “Vector Field” stocks, for each node, the direction to the closest adjacent node having a lower cost than his own and other adjacent ones.
With these two layers, every entity on the flowfield can, independently move from a node to the destination by only following the vectors on the vector field. This system is really interesting for many units in a relatively small space. In other situations than that, it’s not worth the computing cost. An implementation for huge surfaces is harder than most other systems of pathfinding as it requires a lot of optimization to be viable.
And that’s where we stop for this first part! We took a look at some basics about Pathfinding and movements in 2D.
In part two, coming next week, it will all be about moving on the 3rd axis. I’ll talk about cases where this can be interesting/useful and about three ways to achieve that.
I hope you liked this first part! Please give us your feedbacks, we are not experts on this specific domain and what you read on this article comes from what we learned by doing games and trying to find solutions to our problems. We hope this can help others too.
Now that you have more knowledge on pathfinding, we’ll see you next week for part 2: How to implement pathfinding in your games (with examples in Unreal Engine 4 and Unity)!
