Local Avoidance

How to use the local avoidance in the A* Pathfinding Project.

The local avoidance included in the A* Pathfinding Project is based on RVO: Reciprocal Velocity Obstacles and more specifically uses the ORCA algorithm. It is well suited to for example human agents that move around. It not particularly well suited to vehicles that cannot change their velocity quickly.

Overview

Local avoidance is used for making agents avoid each other, and also for simpler dynamic obstacle avoidance. In constrast to pathfinding, local avoidance is, as the name implies, very local. It only cares about the agents and obstacles that are close to the agent. It does not care about the global goal of the agent, and cannot find its way around larger obstacles.

On the other hand, handling small dynamic objects with pathfinding is often not very efficient, as paths would have to be recalculated for every tiny change. Local avoidance is much better suited for this.

The RVO system is divided into two parts. First there is the core simulation code. It is completely independent of Unity specific objects, such as GameObjects and MonoBehaviours. This core handles all simulation of local avoidance agents.

The second part is the Unity interface. Many of those classes are just wrappers for the corresponding core classes. The RVOController class is for example just a wrapper class for the Pathfinding.RVO.IAgent interface.

Examples

There are three example scenes included which show how the local avoidance system works. You can find them in Assets/AstarPathfindingProject/ExampleScenes/Example11_RVO as well as in Assets/AstarPathfindingProject/ExampleScenes/Example16_RVO 2D.

Integration

In your scene you should have exactly one RVOSimulator component. All other components will find this component automatically.

How you configure your agents depends on which movement script you are using.

If you are using the FollowerEntity movement script, you can enable the Local Avoidance checkbox on the movement script. If you are using the AIPath, RichAI, or a custom movement script, you should add the RVOController component to your agents.

These two ways expose essentially identical settings. The FollowerEntity uses the Entity Component System (ECS) internally, and so it cannot use the RVOController as a separate component. Internally, both are simulated in the exact same way.

Integration with physics

Often you want to have colliders on your agents, maybe to be able to hit them with bullets or something. However if you just add colliders (plus a rigidbody) to your agents you may see that the local avoidance quality goes down drastically in crowded scenarios. This is because when it is very crowded agents may overlap a tiny bit, the physics system will prevent that, but it will not do it in as nice a way as the local avoidance system, and this may lead to worse movement.

If you have colliders on your agents I recommend disabling collisions between the agents themselves to solve this. Put the agents in a separate layer and in the Unity physics settings you can disable collisions of that layer with itself. Note that Unity has separate settings for 2D and 3D physics, so make sure you change the right settings.

Keeping the agents on the navmesh

When using local avoidance, it is not hard to find cases where agents will manage to push other agents outside the graph. This is usually not desired, fortunately there are ways to mitigate this.

You can enable the RVOSimulator.useNavmeshAsObstacle option to make the local avoidance system treat the navmesh as an obstacle. This has a performance overhead, but agents will be much less likely to be pushed outside the graph.

Agents can also constrain themselves to the graph, without using local avoidance. If you are using the RichAI or FollowerEntity movement scripts, this automatically happens because the way they handle movement requires it. If you are using the AIPath script you can enable this using the constrainInsideGraph option. However, if the local avoidance agents are not aware of the navmesh (using the RVOSimulator.useNavmeshAsObstacle option), they may still try to move outside the graph, which can lead to some jittery behavior near the edges of the graph. Especially in crowded scenarios.

Below you can see an image where several agents using local avoidance were ordered to go to the same point in a corner. When not constraining the agents to the graph they are easily pushed inside obstacles.

Performance

So how fast is local avoidance then, you might wonder. It is very high performance. Especially if you take into account the fact that a local avoidance simulation does not need to run at a very high fps, that's just a waste of CPU cycles because the quality won't improve much. I have been able to simulate 30 000 agents at a good fps on my, admittedly quite beefy, computer (i9 processor, 16 cores). The local avoidance simulation ran at a fixed 60 fps and the game ran at a few hundred fps, with a lowest fps of around 60. The visualization for this simulation was done simply by creating a mesh which held one quad for each agent. The reason for this is that at such high numbers, creating a GameObject for every agent is really slow, just creating that many game objects took something like 10 seconds when I tested. The agents were setup in a circle, and each one tried to move to a point on the opposite side of the circle. So it was basically as crowded as it can get.

However, do not count on having this high number of agents in your game. The above test was very lightweight, and in a game there is usually lots of overhead from many other things.

The image above shows the aforementioned stress test.

Local Avoidance Priorities

All agents are equal, but some may be more equal than others. This is where priorities come in. If an agent has a higher priority, other agents will try to avoid it more, and it will also try to avoid other agents less.

In general, if one agent has a priority A, and another has priority B, then A will take this fraction of the responsibility of avoiding any collision: B / (A + B)


So, for example, if A has priority 1 and B has priority 2, then A will take 2/3 of the responsibility and B will take 1/3 of the responsibility.

Local Avoidance Layers

You can also make some agents completely ignore other characters by changing their agent layer, and which layers that they avoid. Every RVOController has one field for its own layer, and one for the layers it will will consider when avoiding other agents. Note that these layers are not the same thing as Unity layers. These are used purely for local avoidance.

This can be very useful if you are making a game with two teams. In those cases you often don't want agents of different teams to avoid each other. You can then put all agents of team A in one layer, and all agents of team B in another layer, and then make sure that agents only avoid agents in their own team's layer.

Player Characters

You may want your player character to be unaffected by local avoidance altogether, but you may want other agents to avoid the player. You can do this by manually setting the velocity of an RVOController component.

void Update () {
var x = Input.GetAxis("Horizontal");
var y = Input.GetAxis("Vertical");

var v = new Vector3(x, 0, y) * speed;

// Override the RVOController's velocity. This will disable local avoidance calculations for one simulation step.
rvo.velocity = v;
transform.position += v * Time.deltaTime;
}
This will make the local avoidance system skip calculations for that agent completely, and instead assume it will move with the velocity that you set. This can sometimes also be useful for moving obstacles, assuming that they are small enough that pathfinding is not necessary, and that its fine that they are circular.

There's an included sample script called ManualRVOAgent.cs which shows how you can intergrate your existing character movement script with local avoidance in this way.