Implementing the Pathfinder

One of the coolest features of an RTS game is that the selected units always find the best path to reach their destination, avoiding rocks, trees, buildings, and everything else on their way. There is an AI algorithm behind this feature, called a pathfinder, and it has a few different implementations. In this chapter, we will take a look at the most used algorithms and will focus on the Navigation Mesh (NavMesh).

We will implement the NavMesh on Unity by using the AI Navigation package, setting up our units as agents and the level items as obstacles, and letting the NavMesh find the best path and move the selected units to the destination, avoiding or moving around the obstacles. We are also going to learn how to use the visual debugging tool from the AI Navigation package to see in real time how the NavMesh finds the best path for the agents.

By the end of this chapter, you will learn what a pathfinder algorithm is and the difference between the most...

Technical requirements

The project setup in this chapter, with the imported assets, can be found on GitHub at https://github.com/PacktPublishing/Creating-an-RTS-game-in-Unity-2023 in the Chapter08 folder inside the project.

Understanding the pathfinder

The pathfinder is an Artificial Intelligence (AI) algorithm that has the objective of finding the best path between two points in a 2D or 3D world. The algorithm has a graph data structure that uses a set of nodes, and their adjacent connected nodes, to search for the best path.

The pathfinder is commonly used in RTS games, so the selected units and even the enemies can find the best path while avoiding blocks in the way. We are going to get an overview of the pathfinder algorithm and understand how it works.

The Greedy Best-First and A* algorithms

Game worlds can be represented, for example, as a grid of squares or hexes, with every cell being a node. The cell neighbors are the adjacent nodes used to determine the path. In the following figure, we can see the best path that the pathfinder can find from the blue cell to the orange cell, which is just a straight line:

Figure 8.1 – Pathfinding in a direct line

...

Implementing the pathfinder using the NavMesh

To implement the pathfinder using the NavMesh on Unity, we are going to add three components to the game from the AI Navigation package. The NavMesh, NavMesh Agent, and NavMesh Obstacle components will be configured separately but, at the end of this section, they are going to work together in our RTS game.

The NavMesh component

As we just saw, NavMesh is a data structure that contains all the walkable surfaces of the game world. There are a few different ways to use it: we could let the game generate all these data dynamically at runtime, or we could pre-generate these on our scene, using a process called baking. By baking the NavMesh data, we are optimizing our scene and calculating the pathfinder much faster, using the data pre-generated by the baking process.

Another optimization that we are going to use is to limit the NavMesh to a few layers. By including only the layers that we want the NavMesh to use in the calculations...

Debugging the NavMesh

The AI Navigation package has a very good visual debugging tool that shows on the Editor the calculations that the NavMesh is doing to find the best path around one obstacle in real time.

However, before starting to play with the visual debugging tool, we first need to change our Unity layout so we can see both the Scene view and the Game view at the same time. In the top-right corner of the Unity Editor, click on Layout and select the 2 by 3 option. Your layout will change to the one shown in the following figure:

Figure 8.12 – The Unity Editor with the 2 by 3 layout

You can always change back to the Default layout but, for now, the 2 by 3 layout will work better because we need to play the game in the Game view while looking at the visual debugging tool in the Scene view.

Now go ahead and hit the Play button in the Unity Editor, spawn a few Warriors, select them, and click somewhere in the map to make the selected units...

Summary

Well done for reaching the end of this chapter. The pathfinder is one of the core elements present in an RTS game, one thing that we must have in our game, and now it is working fully. The units can move freely on the map, avoiding obstacles, and even large groups can move through rocks and trees without being blocked by them, always trying to find the best path to the destination.

In this chapter, we learned what the pathfinder algorithm is, and we saw the theory and base concepts behind the most common implementations, from the relatively simple Greedy Best-First to the complex A*. We ended up looking at the NavMesh, the data structure most used in the games industry, and how to use the AI Navigation package in Unity and implement it in our RTS game.

The Dragoncraft game continues to expand, and we are building more features on top of those developed so far in this book. It is very rewarding to see the game taking shape and the scripts we developed are flexible enough...

Further reading

Although we saw a brief explanation of the concepts and theory behind different pathfinder algorithms, I recommend checking out the following books and links to learn more about them:

• Madhav, Sanjay. Game Programming Algorithms and Techniques. Addison-Wesley (2014)
• Buckland, Mat. Programming Game AI by Example. Wordware Publishing Inc. (2005)
• Navigation System in Unity: https://docs.unity3d.com/Packages/com.unity.ai.navigation@1.1/manual/NavigationSystem.html
• Inner Workings of the Navigation System: https://docs.unity3d.com/Packages/com.unity.ai.navigation@1.1/manual/NavInnerWorkings.html
• Virtuals (C# reference): https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/virtual