NPCs or Non-Playable-Characters are all the characters in the game that are not controlled by the player, but that interact with him. They can range from the player's allies to enemies that try to kill him. One of the great challenges for game developers is to equip their NPCs with a series of behaviors that convey the appearance of life and intelligence.
One of the clearest signs of life is movement. If something moves on its own initiative, one of the reasons our mind instinctively considers is that it may be alive. On the other hand, one of the signs of a minimum of intelligence is that this movement occurs while avoiding obstacles in its path. If a creature moves when we approach it, but immediately runs into the wall in front of it, we may think that this creature is alive, but not that it is very intelligent.
That's why most game engines, as long as they have an artificial intelligence package, first include some kind of pathfinding tool to allow NPCs to orient themselves around the environment.
Godot is no exception and therefore incorporates pathfinding functionality using meshes, both in 2D and 3D. For simplicity, we will focus on the first area.
Creating a map
To orient ourselves, the best thing for humans is a map. The same goes for an engine. That map is based on our scenario, but to model it we need a node called NavigationRegion2D. We must add it to the scene of any level we want to map. For example, supposing that our level is based on several TileMapLayers (one with the floor tiles, another with the perimeter walls and another with the tiles of the obstacles inside the perimeter), the node structure with the NavigationRegion2D node could be the following:
 |
Node hierarchy with a NavigationRegion2D |
Note that the NavigationRegion2D node is the parent of the TileMapLayer since by default it only builds the map with the conclusions it draws from analyzing its child nodes.
When configuring the NavigationRegion2D through the inspector, we will see that it requires the creation of a NavigationPolygon resource, in this resource the map information of our level will be saved.
 |
Setting up a NavigationRegion2D |
Once the resource has been created, when clicking on it, we will see that it has quite a few properties to configure.
 |
Setting up a NavigationPoligon |
In a simple case like our example, only two parameters need to be configured:
- Radius : Here we will set the radius of our NPC, with a small additional margin. This way, the pathfinding algorithm will add this distance to the outline of the obstacles to prevent the NPC from rubbing against them.
- Parsed Collision Mask : All objects of the child nodes that are in the collision layers that we mark here will be considered an obstacle.
Once this is done, we will only need to mark the limits of our map. To do this, note that when you click on the NavigationPolygon resource in the inspector, the following toolbar will appear in the scene tab:
 |
Toolbar for defining the shape of a NavigationPolygon |
Thanks to this toolbar we can define the boundaries of our map. Then, NavigationRegion2D will be in charge of identifying obstacles and making "holes" in our map to indicate the areas through which our NPC will not be able to pass.
The first button (green) on the toolbar is used to add new vertices to the shape of our map, the second button (blue) is used to edit a vertex already placed, while the third (red) is used to delete vertices.
In a simple scenario, such as a tilemap, it may be enough to draw the four vertices that limit the maximum extension of the tilemap. In the following screenshot you can see that I have placed a vertex in each corner of the area I want to map.
 |
Vertices of our NavigationPolygon |
Once we have defined the boundaries of our map, we will have to start its generation. To do this, we will press the Bake NavigationPolygon button in the toolbar.
The result will be that NavigationRegion2D will mark in blue the areas where you can wander, once the limits of the map have been analyzed and the obstacles within them have been detected.
We will have to remember to press the Bake NavigationPolygon button whenever we add new obstacles to the level or move existing ones, otherwise the map of the navigable areas will not update.
 |
NavigationPolygon, after being baked. |
For an object to be identified as an obstacle, it has to be configured to belong to one of the collision layers that we have configured in the Parsed Collision Mask field of the NavigationPolygon. In the case of a TileMapLayer this is configured as follows:
- In those TileMapLayers that contain obstacles we will have to mark the Physics -> Collision Enabled parameter.
- In the Tile Set resource that we are using in the TileMapLayer, we will have to make sure to add a physical layer and place it in one of the layers contemplated in the Parsed Collision Mask of the NavigationPolygon.
- You must also add a navigation layer and set it to the same value as the NavigationRegion2D node's navigation layer.
For example, the TileMapLayer containing the interior obstacles in my example, has the following settings for the Tile Set:
 |
Setting up the TileMapLayer |
Then, inside the TileSet, not all tiles have to be obstacles, only those that have a collider configured. Remember that the tiles' colliders are configured from the TileSet tab. I won't go into more detail about this because that has more to do with the TileMaps configuration than with the navigation itself.
 |
Setting a tile's collider |
Using the map
Once the map is created, our NPCs need to be able to read it. To do this, they need a MeshNavigationAgent2D node in their hierarchy.
 |
The MeshNavigationAgent2D node within an NPC's hierarchy |
In a simple case, you may not even need to change anything from its default settings. Just make sure its Navigation Layers field is set to the same value as the NavigationRegion2D.
From your script, once you have a reference to the MeshNavigationAgent2D node, you will simply have to set the position you want to go to in the TargetPosition property of the MeshNavigationAgent2D. For example, if we had an NPC who wanted to hide at a point on the map, we could include a property in which we would ask the MeshNavigationAgent2D node to find the route to reach that point, as you can see in the screenshot.
 |
Setting a target position in a MeshNavigationAgent2D |
Once we have told the node where we want to go, it will calculate a route and give us the different stops on that route as we reach them.
In order for the node to tell us where the next stop on the path is, we will have to call the GetNextPathPosition() method. It is important to note that this method is responsible for updating quite a few things internal to the pathfinding algorithm, so a requirement is that we call it once in each call to _PhysicsProcess() of our NPC.
In the screenshot you have the _PhysicProcess() of the agent I'm using as an example. Most of the code in the screenshot refers to topics that are not the subject of this article, but I'm including it to provide some context. In fact, for what we're talking about, you only need to look at lines 221 to 225.
 |
Obtaining the next stop on the route, within the _PhysicsProcess. |
On line 225 you can see how we call GetNextPathPosition() to get the next point we need to go to in order to follow the path drawn to the target set in TargetPosition. How we get to that point is up to us. The MeshNavigationAgent2D simply guarantees two things:
- That there is no obstacle between the NPC and the next point on the route that he marks for you.
- That if you follow the route points that it gives you, you will end up reaching the objective... if there is a route that leads to it.
I want to emphasize this because, unlike Unity's NavigationAgent, Godot's does not move the NPC in which it is embedded. It simply gives directions on where to go.
Apart from the general case, there are certain caveats in the capture code that need to be made clear.
For starters, the Godot documentation says not to keep calling GetNextPathPosition() once you've finished traversing the path, otherwise the NPC may "shake" by forcing further updates to the pathfinding algorithm after already reaching the goal. That's why, on line 224, I check that we haven't reached the end of the path yet, before calling GetNextPathPosition(). So don't forget to check that IsNavigationFinished() returns false, before checking GetNextPathPosition().
On the other hand, the pathfinding algorithm takes a while to converge, especially at the beginning. If we ask it too early it will throw an exception. Typically it takes one or two physics frames (i.e. one or two calls to _PhysicsProcess). That is why on line 222 it checks if the IsReady property is true before continuing. The problem is that MeshNavigationAgent2D does not have an IsReady property (although it should have one), it is just a property I created myself to make a non-intuitive query:
 |
How to check that the pathfinding algorithm is ready to answer queries |
Basically, what the property does is ensure that the pathfinding algorithm has managed to generate at least one version of the path.
Conclusion
And that's it, by setting the TargetPosition of the MeshNavigationAgent2D, and going to the successive points marked by the calls to GetNextPathPosition(), you will be able to reach any reachable point of the NavigationRegion2D that you have defined.
With that you already have the basics, but if at any time you need to analyze the complete route that the algorithm has calculated, you can ask for it by calling the GetCurrentNavigationPath() method. This method will return an array with the positions of the different stops on the route.