If you are making an RPG or RTS game, chances are that you will need to use some kind of pathfinding and/or local avoidance solution for the behaviour of the mobs. They will need to get around obstacles, avoid each other, find the shortest path to their target and properly surround it. They also need to do all of this without bouncing around, getting stuck in random places and behave as any good crowd of cows would:
In this blog post I want to share my experience on how to achieve a result that is by no means perfect, but still really good, even for release. We'll talk about why I chose to use Unity's built in NavMesh system over other solutions and we will create an example scene, step by step. I will also show you a couple of tricks that I learned while doing this for my game. With all of that out of the way, let's get going.
Choosing a pathfinding library
A few words about my experiences with some of the pathfinding libraries out there.
Aron Granberg's A* Project
This is the first library that I tried to use, and it was good. When I was doing the research for which library to use, this was the go-to solution for many people. I checked it out, it seemed to have pretty much everything needed for the very reasonable price of $99. There is also a free version, but it doesn't come with Local Avoidance, so it was no good.
Purchased it, integrated it into my project and it worked reasonably well. However, it had some key problems.
- Scene loading. It adds a solid chunk of time to your scene loading time. When I decided to get rid of A* and deleted all of its files from my project (after using it for 3 months), my scene loading time dropped to 1-2 seconds, up from 5-10 seconds when I press "Play". It's a pretty dramatic difference.
- RVO Local Avoidance. Although it's one of the library's strong points, it still had issues. For example, mobs were getting randomly stuck in places where they should be able to get through, also around corners, and stuff like that. I'm sure there is a setting somewhere buried, but I just could not get it right and it drove me nuts. The good part about the local avoidance in this library is that it uses the RVO algorithm and the behaviour of the agents in a large crowd was flawless. They would never go through one another or intersect. But when you put them in an environment with walls and corners, it gets bad.
- Licensing issues. However the biggest problem of the library since a month ago is that it doesn't have any local avoidance anymore (I bet you didn't see that one coming). After checking out the Aron Granberg's forums one day, I saw that due to licensing claims by the UNC (University of North Carolina), which apparently owned the copyright for the RVO algorithm, he was asked to remove RVO from the library or pay licensing fees. Sad.
UnitySteer
Free and open source, but I just could not get this thing to work. I'm sure it's good, it looks good on the demos and videos, but I'm guessing it's for a bit more advanced users and I would stay away from it for a while. Just my two cents on this library.
Unity's built in NavMesh navigation
While looking for a replacement for A* I decided to try out Unity's built in navigation system. Note - it used to be a Unity Pro only feature, but it got added to the free version some time in late 2013, I don't know when exactly. Correct me if I'm wrong on this one. Let me explain the good and bad sides of this library, according to my experience up to this point.
The GoodIt's quick. Like properly quick. I can easily support 2 to 3 times more agents in my scene, without the pathfinding starting to lag (meaning that the paths take too long to update) and without getting FPS issues due to the local avoidance I believe. I ended up limiting the number of agents to 100, just because they fill the screen and there is no point in having more.
Easy to setup. It's really easy to get this thing to work properly. You can actually make it work with one line of code only:
agent.destination = target.position;
Besides generating the navmesh itself (which is two clicks) and adding the NavMeshAgent component to the agents (default settings), that's really all you need to write to get it going. And for that, I recommend this library to people with little or no experience with this stuff.
Good pathfinding quality. What I mean by that is agents don't get stuck anywhere and don't have any problem moving in tight spaces. Put simply, it works like it should. Also, the paths that are generated are really smooth and don't need extra work like smoothing or funnelling.
The BadNot the best local avoidance. It's slightly worse than RVO, but nothing to be terribly worried about, at least in my opinion and for the purposes of an ARPG game. The problem comes out when you have a large crowd of agents - something like 100. They might intersect occasionally, and start jiggling around. Fortunately, I found a nice trick to fix the jiggling issue, which I will share in the example below. I don't have a solution to the intersecting yet, but it's not much of a problem anyway.
That sums up pretty much everything that I wanted to say about the different pathfinding solutions out there. Bottom line - stick with NavMesh, it's good for an RPG or RTS game, it's easy to set up and it's free.
Example project
In this section I will explain step by step how to create an example scene, which should give you everything you need for your game. I will attach the Unity project for this example at the end of the post.
Creating a test scene
Start by making a plane and set its scale to 10. Throw some boxes and cylinders around, maybe even add a second floor. As for the camera, position it anywhere you like to get a nice view of the scene. The camera will be static and we will add point and click functionality to our character to make him move around. Here is the scene that I will be using:
Next, create an empty object, position it at (0, 0, 0) and name it "player". Create a default sized cylinder, make it a child of the "player" object and set its position to (0, 1, 0). Create also a small box in front of the cylinder and make it a child of "player". This will indicate the rotation of the object. I have given the cylinder and the box a red material to stand out from the mobs. Since the cylinder is 2 units high by default, we position it at 1 on the Y axis to sit exactly on the ground plane:
We will also need an enemy, so just duplicate player object and name it "enemy".
Finally, group everything appropriately and make the "enemy" game object into a prefab by dragging it to the project window.
Generating the NavMesh
Select all obstacles and the ground and make them static by clicking the "Static" checkbox in the Inspector window.
Go to Window -> Navigation to display the Navigation window and press the "Bake" button at the bottom:
Your scene view should update with the generated NavMesh:
The default settings should work just fine, but for demo purposes let's add some more detail to the navmesh to better hug the geometry of our scene. Click the "Bake" tab in the Navigation window and lower the "Radius" value from 0.5 to 0.2:
Now the navmesh describes our scene much more accurately:
I recommend checking out the Unity Manual here to find out what each of the settings do.
However, we are not quite done yet. If we enter wireframe mode we will see a problem:
There are pieces of the navigation mesh inside each obstacle, which will be an issue later, so let's fix it.
- Create an empty game object and name it "obstacles".
- Make it a child of the "environment" object and set its coordinates to (0, 0, 0).
- Select all objects which are an obstacle and duplicate them.
- Make them children of the new "obstacles" object.
- Set the coordinates of the "obstacles" object to (0, 1, 0).
- Select the old obstacles, which are still direct children of environment and turn off the Static checkbox.
- Bake the mesh again.
- Select the "obstacles" game object and disable it by clicking the checkbox next to its name in the Inspector window. Remember to activate it again if you need to Bake again.
Looking better now:
If you download the Unity project for this example you will see that the "ground" object is actually imported, instead of a plane primitive. Because of the way that I initially put down the boxes, I was having the same issue with the navmesh below the second floor. Since I couldn't move that box up like the others (because it would also move the second floor up), I had to take the scene to Maya and simply cut the part of the floor below the second floor. I will link the script that I used to export from Unity to .obj at the end of the article. Generally you should use separate geometry for generating a NavMesh and for rendering.Here is how the scene hierarchy looks like after this small hack:
Point and click
It's time to make our character move and navigate around the obstacles by adding point and click functionality to the "player" object. Before we begin, you should delete all capsule and box colliders on the "player" and "enemy" objects, as well as from the obstacles (but not the ground) since we don't need them for anything.
Start by adding a NavMeshAgent component to the "player" game object. Then create a new C# script called "playerMovement" and add it to the player as well. In this script we will need a reference to the NavMeshAgent component. Here is how the script and game object should look like:
using UnityEngine;
using System.Collections;
public class playerMovement : MonoBehaviour {
NavMeshAgent agent;
void Start () {
agent = GetComponent< NavMeshAgent >();
}
void Update () {
}
}
Now to make the character move, we need to set its destination wherever we click on the ground. To determine where on the ground the player has clicked, we need to first get the location of the mouse on the screen, cast a ray towards the ground and look for collision. The location of the collision is the destination of the character.
However, we want to only detect collisions with the ground and not with any of the obstacles or any other objects. To do that, we will create a new layer "ground" and add all ground objects to that layer. In the example scene, it's the plane and 4 of the boxes.
If you are importing the .unitypackage from this example, you still need to setup the layers!
Here is the script so far:
using UnityEngine;
using System.Collections;
public class playerMovement : MonoBehaviour {
NavMeshAgent agent;
void Start () {
agent = GetComponent< NavMeshAgent >();
}
void Update () {
if (Input.GetMouseButtonDown(0)) {
// ScreenPointToRay() takes a location on the screen
// and returns a ray perpendicular to the viewport
// starting from that location
Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
RaycastHit hit;
// Note that "11" represents the number of the "ground"
// layer in my project. It might be different in yours!
LayerMask mask = 1 < 11;
// Cast the ray and look for a collision
if (Physics.Raycast(ray, out hit, 200, mask)) {
// If we detect a collision with the ground,
// tell the agent to move to that location
agent.destination = hit.point;
}
}
}
}
Now press "Play" and click somewhere on the ground. The character should go there, while avoiding the obstacles along the way.
If it's not working, try increasing the ray cast distance in the Physics.Raycast() function (it's 200 in this example) or deleting the mask argument from the same function. If you delete the mask it will detect collisions with all boxes, but you will at least know if that was the problem.
If you want to see the actual path that the character is following, select the "player" game object and open the Navigation window.
Make the agent follow the character
- Repeat the same process as we did for the "player" object - attach a NavMeshAgent and a new script called "enemyMovement".
- To get the player's position, we will also add a reference to the "player" object, so we create a public Transform variable. Remember to go back in the Editor connect the "player" object to that variable.
- In the Update() method set the agent's destination to be equal to the player's position.
Here is the script so far:
using UnityEngine;
using System.Collections;
public class enemyMovement : MonoBehaviour {
public Transform player;
NavMeshAgent agent;
void Start () {
agent = GetComponent< NavMeshAgent >();
}
void Update () {
agent.destination = player.position;
}
}
Press "Play" and you should see something like the following screenshot. Again, if you want to show the path of the enemy object, you need to select it and open the Navigation window.
However, there are a few things that need fixing.
- First, set the player's move speed to 6 and the enemy's speed to 4. You can do that from the NavMeshAgent component.
- Next, we want the enemy to stop at a certain distance from the player instead of trying to get to his exact location. Select the "enemy" object and on the NavMeshAgent component set the "Arrival Distance" to 2. This could also represent the mob's attack range.
- The last problem is that generally we want the enemies to body block our character so he can get surrounded. Right now, our character can push the enemy around. As a temporary solution, select the "enemy" object and on the NavMeshAgent component change the "Avoidance Priority" to 30.
Here is what the docs say about Avoidance Priority:
When the agent is performing avoidance, agents of lower priority are ignored. The valid range is from 0 to 99 where: Most important = 0. Least important = 99. Default = 50.
By setting the priority of the "enemy" to 30 we are basically saying that enemies are more important and the player can't push them around. However, this fix won't work so well if you have 50 agents for example and I will show you a better way to fix this later.
Making a crowd of agents
Now let's make this a bit more fun and add, let's say 100 agents to the scene. Instead of copying and pasting the "enemy" object, we will make a script that instantiates X number of enemies within a certain radius and make sure that they always spawn on the grid, instead of inside a wall.
Create an empty game object, name it "spawner" and position it somewhere in the scene. Create a new C# script called "enemySpawner" and add it to the object. Open enemySpawner.cs and add a few public variables - one type int for the number of enemies that we want to instantiate, one reference of type GameObject to the "enemy" prefab, and one type float for the radius in which to spawn the agents. And one more - a reference to the "player" object.
using UnityEngine;
using System.Collections;
public class enemySpawner : MonoBehaviour {
public float spawnRadius = 10;
public int numberOfAgents = 50;
public GameObject enemyPrefab;
public Transform player;
void Start () {
}
}
At this point we can delete the "enemy" object from the scene (make sure you have it as a prefab) and link the prefab to the "spawner" script. Also link the "player" object to the "player" variable of the "spawner".
To make our life easier we will visualise the radius inside the Editor. Here is how:
using UnityEngine;
using System.Collections;
public class enemySpawner : MonoBehaviour {
public float spawnRadius = 10;
public int numberOfAgents = 50;
public GameObject enemyPrefab;
public Transform player;
void Start () {
}
void OnDrawGizmosSelected () {
Gizmos.color = Color.green;
Gizmos.DrawWireSphere (transform.position, spawnRadius);
}
}
OnDrawGizmosSelected() is a function just like OnGUI() that gets called automatically and allows you to use the Gizmos class to draw stuff in the Editor. Very useful! Now if you go back to the Editor, select the "spawner" object and adjust the spawnRadius variable if needed. Make sure that the centre of the object sits as close to the floor as possible to avoid spawning agents on top of one of the boxes.
In the Start() function we will spawn all enemies at once. Not the best way to approach this, but will work for the purposes of this example. Here is what the code looks like:
using UnityEngine;
using System.Collections;
public class enemySpawner : MonoBehaviour {
public float spawnRadius = 10;
public int numberOfAgents = 50;
public GameObject enemyPrefab;
public Transform player;
void Start () {
for (int i=0; i < numberOfAgents; i++) {
// Choose a random location within the spawnRadius
Vector2 randomLoc2d = Random.insideUnitCircle * spawnRadius;
Vector3 randomLoc3d = new Vector3(transform.position.x + randomLoc2d.x, transform.position.y, transform.position.z + randomLoc2d.y);
// Make sure the location is on the NavMesh
NavMeshHit hit;
if (NavMesh.SamplePosition(randomLoc3d, out hit, 100, 1)) {
randomLoc3d = hit.position;
}
// Instantiate and make the enemy a child of this object
GameObject o = (GameObject)Instantiate(enemyPrefab, randomLoc3d, transform.rotation);
o.GetComponent< enemyMovement >().player = player;
}
}
void OnDrawGizmosSelected () {
Gizmos.color = Color.green;
Gizmos.DrawWireSphere (transform.position, spawnRadius);
}
}
The most important line in this script is the function NavMesh.SamplePosition(). It's a really cool and useful function. Basically you give it a coordinate it returns the closest point on the navmesh to that coordinate. Consider this example - if you have a treasure chest in your scene that explodes with loot and gold in all directions, you don't want some of the player's loot to go into a wall. Ever. You could use NavMesh.SamplePosition() to make sure that each randomly generated location sits on the navmesh. Here is a visual representation of what I just tried to explain:
In the video above I have an empty object which does this:
void OnDrawGizmos () {
NavMeshHit hit;
if (NavMesh.SamplePosition(transform.position, out hit, 100.0f, 1)) {
Gizmos.DrawCube(hit.position, new Vector3 (2, 2, 2));
}
Back to our example, we just made our spawner and we can spawn any number of enemies, in a specific area. Let's see the result with 100 enemies:
Improving the agents behavior
What we have so far is nice, but there are still things that need fixing.
To recap, in an RPG or RTS game we want the enemies to get in attack range of the player and stop there. The enemies which are not in range are supposed to find a way around those who are already attacking to reach the player. However here is what happens now:
In the video above the mobs are stopping when they get into attack range, which is the NavMeshAgent's "Arrival Distance" parameter, which we set to 2. However, the enemies who are still not in range are pushing the others from behind, which leads to all mobs pushing the player as well. We tried to fix this by setting the mobs' avoidance priority to 30, but it doesn't work so well if we have a big crowd of mobs. It's an easy fix, here is what you need to do:
- Set the avoidance priority back to 30 on the "enemy" prefab.
- Add a NavMeshObstacle component to the "enemy" prefab.
- Modify the enemyMovement.cs file as follows:
using UnityEngine;
using System.Collections;
public class enemyMovement : MonoBehaviour {
public Transform player;
NavMeshAgent agent;
NavMeshObstacle obstacle;
void Start () {
agent = GetComponent< NavMeshAgent >();
obstacle = GetComponent< NavMeshObstacle >();
}
void Update () {
agent.destination = player.position;
// Test if the distance between the agent and the player
// is less than the attack range (or the stoppingDistance parameter)
if ((player.position - transform.position).sqrMagnitude < Mathf.Pow(agent.stoppingDistance, 2)) {
// If the agent is in attack range, become an obstacle and
// disable the NavMeshAgent component
obstacle.enabled = true;
agent.enabled = false;
} else {
// If we are not in range, become an agent again
obstacle.enabled = false;
agent.enabled = true;
}
}
}
Basically what we are doing is this - if we have an agent which is in attack range, we want him to stay in one place, so we make him an obstacle by enabling the NavMeshObstacle component and disabling the NavMeshAgent component. This prevents the other agents to push around those who are in attack range and makes sure that the player can't push them around either, so he is body blocked and can't run away. Here is what it looks like after the fix:
It's looking really good right now, but there is one last thing that we need to take care of. Let's have a closer look:
This is the "jiggling" that I was referring to earlier. I'm sure that there are multiple ways to fix this, but this is how I approached this problem and it worked quite well for my game.
- Drag the "enemy" prefab back to the scene and position it at (0, 0, 0).
- Create an empty game object, name it "pathfindingProxy", make it a child of "enemy" and position it at (0, 0, 0).
- Delete the NavMeshAgent and NavMeshObstacle components from the "enemy" object and add them to "pathfindingProxy".
- Create another empty game object, name it "model", make it a child of "enemy" and position it at (0, 0, 0).
- Make the cylinder and the cube children of the "model" object.
- Apply the changes to the prefab.
This is how the "enemy" object should look like:
What we need to do now is to use the "pathfindingProxy" object to do the pathfinding for us, and use it to move around the "model" object after it, while smoothing the motion. Modify enemyMovement.cs like this:
using UnityEngine;
using System.Collections;
public class enemyMovement : MonoBehaviour {
public Transform player;
public Transform model;
public Transform proxy;
NavMeshAgent agent;
NavMeshObstacle obstacle;
void Start () {
agent = proxy.GetComponent< NavMeshAgent >();
obstacle = proxy.GetComponent< NavMeshObstacle >();
}
void Update () {
// Test if the distance between the agent (which is now the proxy) and the player
// is less than the attack range (or the stoppingDistance parameter)
if ((player.position - proxy.position).sqrMagnitude < Mathf.Pow(agent.stoppingDistance, 2)) {
// If the agent is in attack range, become an obstacle and
// disable the NavMeshAgent component
obstacle.enabled = true;
agent.enabled = false;
} else {
// If we are not in range, become an agent again
obstacle.enabled = false;
agent.enabled = true;
// And move to the player's position
agent.destination = player.position;
}
model.position = Vector3.Lerp(model.position, proxy.position, Time.deltaTime * 2);
model.rotation = proxy.rotation;
}
}
First, remember to connect the public variables "model" and "proxy" to the corresponding game objects, apply the changes to the prefab and delete it from the scene.
So here is what is happening in this script. We are no longer using transform.position to check for the distance between the mob and the player. We use proxy.position, because only the proxy and the model are moving, while the root object stays at (0, 0, 0). I also moved the agent.destination = player.position; line in the else statement for two reasons: Setting the destination of the agent will make it active again and we don't want that to happen if it's in attacking range. And second, we don't want the game to be calculating a path to the player if we are already in range. It's just not optimal. Finally with these two lines of code:
model.position = Vector3.Lerp(model.position, proxy.position, Time.deltaTime * 2);
model.rotation = proxy.rotation;
We are setting the model.position to be equal to proxy.position, and we are using Vector3.Lerp() to smoothly transition to the new position. The "2" constant in the last parameter is completely arbitrary, set it to whatever looks good. It controls how quickly the interpolation occurs, or said otherwise, the acceleration. Finally, we just copy the rotation of the proxy and apply it to the model.
Since we introduced acceleration on the "model" object, we don't need the acceleration on the "proxy" object. Go to the NavMeshAgent component and set the acceleration to something stupid like 9999. We want the proxy to reach maximum velocity instantly, while the model slowly accelerates.
This is the result after the fix:
And here I have visualized the path of one of the agents. The path of the proxy is in red, and the smoothed path by the model is in green. You can see how the bumps and movement spikes are eliminated by the Vector3.Lerp() function:
Of course that path smoothing comes at a small cost - the agents will intersect a bit more, but I think it's totally fine and worth the tradeoff, since it will be barely noticeable with character models and so on. Also the intersecting tends to occur only if you have something like 50-100 agents or more, which is an extreme case scenario in most games.
We keep improving the behavior of the agents, but there is one last thing that I'd like to show you how to fix. It's the rotation of the agents. Right now we are modifying the proxy's path, but we are copying its exact rotation. Which means that the agent might be looking in one direction, but moving in a slightly different direction. What we need to do is rotate the "model" object according to its own velocity, rather than using the proxy's velocity. Here is the final version of enemyMovement.cs:
using UnityEngine;
using System.Collections;
public class enemyMovement : MonoBehaviour {
public Transform player;
public Transform model;
public Transform proxy;
NavMeshAgent agent;
NavMeshObstacle obstacle;
Vector3 lastPosition;
void Start () {
agent = proxy.GetComponent< NavMeshAgent >();
obstacle = proxy.GetComponent< NavMeshObstacle >();
}
void Update () {
// Test if the distance between the agent (which is now the proxy) and the player
// is less than the attack range (or the stoppingDistance parameter)
if ((player.position - proxy.position).sqrMagnitude < Mathf.Pow(agent.stoppingDistance, 2)) {
// If the agent is in attack range, become an obstacle and
// disable the NavMeshAgent component
obstacle.enabled = true;
agent.enabled = false;
} else {
// If we are not in range, become an agent again
obstacle.enabled = false;
agent.enabled = true;
// And move to the player's position
agent.destination = player.position;
}
model.position = Vector3.Lerp(model.position, proxy.position, Time.deltaTime * 2);
// Calculate the orientation based on the velocity of the agent
Vector3 orientation = model.position - lastPosition;
// Check if the agent has some minimal velocity
if (orientation.sqrMagnitude > 0.1f) {
// We don't want him to look up or down
orientation.y = 0;
// Use Quaternion.LookRotation() to set the model's new rotation and smooth the transition with Quaternion.Lerp();
model.rotation = Quaternion.Lerp(model.rotation, Quaternion.LookRotation(model.position - lastPosition), Time.deltaTime * 8);
} else {
// If the agent is stationary we tell him to assume the proxy's rotation
model.rotation = Quaternion.Lerp(model.rotation, Quaternion.LookRotation(proxy.forward), Time.deltaTime * 8);
}
// This is needed to calculate the orientation in the next frame
lastPosition = model.position;
}
}
At this point we are good to go. Check out the final result with 200 agents:
Final words
This is pretty much everything that I wanted to cover in this article, I hope you liked it and learned something new. There are also lots of improvements that could be made to this project (especially with Unity Pro), but this article should give you a solid starting point for your game.
Originally posted to http://blackwindgames.com/blog/pathfinding-and-local-avoidance-for-rts-rpg-game-with-unity/
Nice article indeed, but I can only imagine a bunch of zombies doing that pursuit haha, i think a bit of noise like random enemy radious while they are on pursuit mode could be an interesting tradeoff realism vs performance, did you tried?