Collisional local avoidance extracted

Overview

Hi there, I have been recently looking into Nordeus demo and managed to separate it's collisional local avoidance which is in there is used for minions to avoid each other. So I thought to give some overview / impressions of my testing and maybe to bring some discussion and possible inspirations for future directions. Here is the GitHub repository for the project:

https://github.com/chanfort/CollisionalLocalAvoidance

Simulation setup

The collisional local avoidance have been completely separated from navigation and other systems in order to test the algorithm, its performance and limitations. Simulation is set to initially distribute units in a circle, laying in XZ plane. Units can only move and avoid each other in the same XZ plane. The Y component is not used in the algorithm itself but can be used anywhere outside, i.e. it can be obtained as the height of the terrain at particular location.

Units then are forced to move towards the circle centre positioned at (0, 0). I local avoidance would be not present, all simulation units would pass through this point (i.e. RenderedCenterPassageCollisionless scene in the project). This would cause units to get closer to each other and start overlapping if local avoidance is not present. Once local avoidance is introduced (i.e. RenderedCenterPassage), they are prevented to go straight to each other and instead have to move around each other in order to get closer to the centre. When most of the units are moving towards the centre, I call that phase as collapse. Units which are passing the centre, are not stopped there and continue to move to the opposite direction from where they came. When most of the units are passing through the centre, expansion phase begins. Here are some screenshots of how the view looks like during the collapse, at maximum compression and during the expansion.



From these screenshots we already start seeing how the algorithm behaves and what is happening at different stages.

Correctness

The simulation in the picture above uses 3000 units. As a result, units in the centre are causing enormous pressure, enforcing to reach high density central region. It seems like there is no algorithm which can perfectly avoid this problem. In this demo, we start seeing that the central region starts to form into a grid-like lattice structure. The lattice seems to be caused as the algorithm skips some neighbour units in order to calculate realistic repulsion velocity. I didn't figured out what determines the cell size, but it seems to be equal to 1. The artefact is reduced by using larger values for maxIterations and maxClosestDone (i.e. from default 6, 3 to 60, 30) in the collision algorithm (these can be set in CollisionSystemProperties component through inspector). However, this comes at a cost of performance degradation for very large number of units. Another possibility to reduce lattice artefact is to reduce radius. Then units will get closer to each other and it seems like it has some kind of smoothing affect on the lattice. It might be possible to break the lattice by slightly randomising velocities, introducing adaptive force or radius, which depends on the level of compression or other possible changes in the algorithm itself.

At the outskirts, where pressure is lower, units are avoiding each other nicely. In real game, it may rarely occur situations where compression levels are so high to cause the lattice to appear but it may occur in large open battle front lines where two armies collide with each other while approaching from opposite directions.

Performance

Probably the most interesting piece of this simulation is the collision performance. This basically can be understood as how many units the collision system can handle before it reaches unplayable frame rates. This is closely related to another question of how game update timestep (deltaTime) changes as a function of number of units, and how it is affected by collision system parameters. In order to make sure that we test only collisions system, we need to remove other expensive systems, such as rendering. In such case, units becomes invisible but they are still being processed in the simulation. There is NonRenderedCenterPassage scene included in the project as well, which uses units without rendering them. In such case we can use very large numbers, such as 10k - 40k of units in the simulation. There is also included script (WriteDeltatimeToFile) which writes deltaTime at different times of the simulation into a text file for further analysis. There are set 4 additional scenes for writing 10k, 20k, 30k and 40k unit simulation deltaTimes over first 3 minutes of the simulation. Running all of these tests produces the following plot.



This plot shows that 10k simulation performs at nearly the same deltaTime independently at what stage simulation actually is. Other three simulations shows that there is a performance impact on how many units are colliding in extremely crowded regions (perhaps native hash map lookups could become more expensive in the most inner loop).

The peak, visible for 20k-40k simulations, is occurring at the time when maximum compression is reached. The decline of deltaTime is visible after the maximum compression, i.e. when most of the units are starting to move outwards from the simulation. It is clear that more massive simulations have larger deltaTime at their peak. More massive simulations also have the fall-off tail extending longer in time. The time, at which deltaTime drops to the lowest value (where most of the units expanded from the centre) I call as relaxation time. So for 20k simulation, relaxation time is about 60s, for 30k - 100s, and for 40k - 150s. This effect is cause because it takes longer for more massive simulations to resolve central passage and for units escape into collision-free areas. As a result, simulations above 30k units may become badly performing if some regions reaches extreme compression.

The question here is if it is possible to adjust the simulation so that the peak would be minimised in the most crowded areas or even to flatten it. The collision-less simulation would not have a peak no matter how many units are overlapping in the centre. Current simulation setup has its parameters (such as maxIterations, maxForce, radius, maxVelocity, etc.) set as constants. The picture may change if these could be adjusted to be more adaptive based on local compression levels (i.e. using smaller radii at higher compression levels). As a result, there is much more to explore about this collision algorithm.

Summary

Collisional local avoidance allowed a big success for Nordeus demo. However, due to its deep integration, it was difficult to separate it from the demo and use it in other projects. I hope that these demos may help to re-use more easily the collisional local avoidance as well as to understand how it works. Tests show that the algorithm is capable to handle large simulations with tens of thousands of units at playable frame rates. We also should be aware about the algorithm limitations, such as lattice artefact and performance degradation in extremely compressed regions. These might bring some inspirations to improve the algorithm in the future by performing more analysis and making it more dynamic by allowing simulation parameters to become more adaptive to different compression levels.