Collision Avoidance: The Math

The Problem

Each unit is represented by a circle, and its movement by an arrow. They should not ever intersect.

Often in games, we want to have a large number of units all moving through the same space. This could be, for instance, pedestrians on a sidewalk, traffic on a road, or a flock of birds or school of fish. Left to their own devices, these units would move right through each other on the way to their goals. This looks terribly unrealistic, because objects in real life don’t overlap each other. If we wanted, we could try to use physics collisions to make them bounce off of each other, but this would be GPU-meltingly expensive in a crowd of hundreds of units, and it wouldn’t even look realistic for units to ignore each other until they are actually touching. It would be far better to look ahead and find some way to avoid collisions before they happen.

The Naive Solution

Each yellow arc is the area in which the units will detect other units. Green circles are where these units have detected each other.

The simplest approach is to check an area in front of the unit and avoid any other units that are in the area. This can be done easily using the dot product of the orientation vector of the unit and the direction to other nearby units. If the dot product o . (p₁ - p₂) is less than a certain threshold based on the angle of the cone, then the unit is in the area. The unit can use any basic fleeing behavior to avoid the other unit.

Problems With The Solution

Not surprisingly, this approach is too simple and will lead to some unwanted behavior. Several examples are illustrated here.

The unit will flee to avoid the unit it has detected, even though they are moving in the same direction and will never collide.

The problems all stem from the fact that the units don’t have any sense of where other units are going, only where they are, and therefore don’t really know if they will collide — only that they are nearby. For instance, If two units are close to each other and moving in the same direction, they may detect an imminent collision and try to flee. The system is trying to enforce separation between the units, regardless of whether any separation will actually be necessary. Units moving in parallel will never collide, and trying to avoid a collision that won’t happen looks strange and unnatural.

The units are headed directly towards each other, but so far are outside each others’ search radius.

It is common for flee algorithms to only be active within a certain radius. Depending on the size of that radius and the speed of the units, they may not be able to avoid head-on collisions in time. The flee behavior won’t activate until the units are almost on top of each other, and may not be enough to avoid the collision.

Two units on a collision course are unaware of each other.

Units approaching each other at a shallow angle may be completely unaware of each other until a collision is already happening. The detection cone does not include units to the left and right of the current unit, so any units not directly in front will not be detected or avoided. The algorithm does not take both velocities into account and does not do any prediction, so it has no way of knowing that these other units will collide in the future. The other units may not enter the detection cone at all until the collision is already happening.

A Better Solution

A better solution needs to take the velocities of both units into account, and needs to predict the locations of units in the future. Such a system would immediately ignore units moving in the same direction, directly opposite one another, or other configurations that have no chance of colliding. At the same time, it should detect any other unit that will cross its path, regardless of where it is currently. We can do this by extrapolating the velocities of all units into the future, and calculating the closest it will approach any other given unit. It turns out this calculation is quite simple (derivation is given below).

The closest approach predicted by the system.

The time at which two given units will have their closest approach is given by -(△p . △v) / (△v . △v), which uses only two dot products and a division, which can be calculated very efficiently. Furthermore, we only need to worry about the collision that will happen the soonest, since avoiding that collision will change the location and time of any other collisions. We can calculate the time for all approaches, and only continue the rest of the math for the soonest one. It should therefore be possible to handle a fairly large number of units efficiently. However, since each unit must be compared with each other unit, the processing time grows with O(n²), so my implementation also added a spatial partition that greatly reduces the number of units that must be checked.

Threshold for collision detection.

After finding the time at which the closest approach happens, we can easily calculate the position of each unit by assuming they will continue to move linearly at a constant speed. Once we have these positions, we can check the distance between them to see if a collision will happen at that point. If the distance is greater than a certain threshold (the sum of the radii for circular units), then there will not be a collision, and we don’t need to do anything. If the distance is less than the threshold, then there will be a collision, and we should do something to avoid it. It may also be useful to define another, larger radius in which the units will not actually collide, but will avoid each other. This would help smooth out their motion a bit, and give more realistic behavior in crowds, where people will not step too closely to one another even if they won’t actually bump into each other.

Multiple approaches: The soonest approach won’t cause a collision, so it is ignored. The second approach will cause a collision, so the unit will attempt to avoid it. The third approach will also cause a collision, but it will be ignored for now, since avoiding the second collision may also avoid the third.

There are many techniques that could be used to avoid the collision. For my implementation, I simply added an acceleration to the unit directly away from the other unit. This works adequately well for my purposes, but could be improved upon (see conclusion).

Derivation

In my source, the equation for the closest approach time was given without any context or proof. Not wanting to take it at face value, I decided to derive it myself. It begins with the assumption that all units will be moving approximately linearly:

p(t) = p + v * t

Our objective is to find the time t such that the distance D(t) is minimized. To do this, we need a formula for D:

D(t) = ‖p₁(t) - p₂(t)‖ = ‖p₁ +v₂t - p₂ -v₁t‖ = ‖(p₁-p₂)+(v₁-v₂)t‖

We define △p = p₁-p₂ (the difference in the units’ current positions) and △v = v₁-v₂ (the difference in the units’ current velocities):

D(t) = ‖△p - △vt‖

Using the definition of the length of a vector:

D(t)² = (△p+△vt) . (△p+△vt)

Distributing the dot product:

D(t)² = △p . (△p+△vt) + △vt . (△p+△vt) = △p . △p + 2 △p . △vt+ △vt . △vt = ‖△p‖² + 2 △p . △vt + ‖△v‖²t²

Since we are looking for the minimum distance, we need to take the derivative with respect to time:

dD/dt = 1/(2 √(D(t)²)) * (2 △p . △v+ 2 ‖△v‖²t) = 1/√(D²) * (△p . △v+ ‖△v‖²t)

(Note that D² is a formula, not a value, so the square root doesn’t simply cancel out to equal D in a way that would be useful.) We then need to find the time where this derivative equals zero:

0 = (△p . △vt + ‖△v‖²t)/√(D²) = △p . △v+ ‖△v‖²t

-△p . △v= ‖△v‖²t

t = -(△p . △v) / ‖△v‖² = -(△p . △v) / (△v . △v)

Conclusion & Next Steps

Although this technique is better than the naive approach, I found that it is not perfect at avoiding collisions. In particular, units traveling directly behind a slower unit would often travel right through the unit in front of them. I believe this is due to the maximum acceleration being set too low, such that units cannot move out of the way quickly enough. Increasing the maximum acceleration made this less common, but did not remove it entirely. Another common problem is two units moving head-on towards another unit. Since they are only considering one potential collision, they cannot properly respond to two potential collisions happening near-simultaneously. The next feature I would want to add to this would be response to multiple collisions, weighted by how soon or close the collision is. The final common failure mode is a head-on collision, where both units react to the oncoming collision by trying to move the same way, still resulting in a collision (an awkward situation we’ve all experienced). This could be solved with smarter avoidance behavior, possibly by adding jitter or a preference to always move to the right.

Sources

[1] Millington, Ian and Funge, John. Artificial Intelligence For Games. Morgan Kaffman, 2009.