Simulating a Crowd in Unity
Part 1: algorithmic simulation using DOTS
This project started out as a reinforcement learning environment. I wanted to train an agent to find the optimal strategy for navigating a tightly-packed crowd, mostly because I wanted to know if there was one. You don’t spend every morning rushing through the central train station at peak times and not think that there must be some way to outsmart the masses.
The plan was: simulate a simple crowd environment → train an RL agent to reach its goal fast → shave aeons off my commute by not being stuck behind slow walkers!
Unfortunately I never got to the training part but more on that later.
Step 1: Setting up
It made sense to use Unity for the simulation since I’m moderately familiar with it and I know it can be used as an RL environment.
First, we need the setting. In its simplest form, we’re talking about a confined space with one exit. In two dimensions, we can just specify white and black pixels on a texture and transform this into a sprite. I exposed the width, height, exit size, and relative exit position as modifiable parameters:
Step 2: Creating the crowd
If this is going to be an RL environment, I need two types of agents: NPCs which form a crowd and which follow a simple ish algorithm to reach the exit, and a unique player that operates on user input.
I couldn’t use simple game objects with rigid-body colliders and a movement script attached, if I wanted a framerate faster than 1 per second. Particles are fast, but there’s no way to make them collide with each other, so they were no option either.
I ended up using Unity DOTS, a fairly recent technology that requires a step away from comfy object orientation and into data-oriented design but which after a quick introduction is really easy to use and has lots of teaching material online. And best of all: it’s fast! I could specify the desired behaviour per agent and let Unity handle the simulation.
For spawning, there’s a beautiful algorithm explained here for randomly generating positions. I selected one of them for the player and the rest for the NPCs:
Step 3: Animating the crowd
This is where it got interesting. The idea was to have a straightforward, deterministic algorithm that controls the NPCs so that my smart little RL agent can learn to outmaneuver them. Of course, the concept of a mindless mass of people and only one independent thinker is far from realistic, but this little act of arrogance was a necessary abstraction given the reduced complexity of this project. To make it fair, everyone gets the same information:
- the position of the closest point on the exit line
- positions and velocities of the neighbours within a short radius (obtained through an overlap sphere check)
if path free: move
Naive choice. Each agent looks forward a certain distance in the direction of the exit and only moves if that space is free.
Here’s why this approach doesn’t work: The agents tend to get stuck near the sides of the exit because even if the colliders allow for partial movement in the desired direction, sometimes they just get in their own way. Not realistic behaviour.
But even before this phenomenon takes place, such a model is clearly too simple to represent realistic crowd movement. It’s missing the very important component of interaction with the other agents.
Reynolds’ behavioural model
This model was originally developed to describe flocks of birds or school of fish, where each individual chooses their own direction, yet the overall movement looks cohesive. Decisions are made only based on a locally observed neighbourhood, so it fits right into the constraints I set for this simulation.
For each agent, the model prescribes three goals:
1. Separation: don’t collide with your neighbours
2. Alignment: move at a similar speed as your neighbours
3. Cohesion: stay close to your neighbours
Qualitative analysis shows that following these rules creates realistic-looking behaviours.
In the present case, we must also specify another goal:
4. Destination: move towards the exit
Once the direction vector has been calculated for each goal, they are arbitrated in the following way:
- sort the vectors by a predefined list of priorities
- weight each vector by its deviation from the mean magnitude:
- add the weighted directions by priority to an accumulator up to a specified maximum magnitude
This way of merging the different goals respects predefined priorities but can still assign sufficient weight to a large vector in an emergency. It also ensures different goals don’t cancel each other out, which a simple (weighted) sum might do.
Going through the goals, it is clear that three of the four are relatively easy to compute. For an agent i with position p⁽ⁱ⁾, velocity v⁽ⁱ⁾, and N neighbours, we get:
Get Flavia M’s stories in your inbox
Join Medium for free to get updates from this writer.
2. Alignment: mean of neighbouring velocities.
3. Cohesion: mean of neighbouring positions, weighted by squared distance:
4. Destination: vector to the closest point on exit line (s, t):
(side note: I ended up scaling this vector to a minimum length to maintain its importance even close to the exit)
The one direction vector that’s not at all straightforward to find is dₛₑₚₐᵣₐₜᵢₒₙ. There exist many collision avoidance strategies, each tailored to slightly different problems than this one. In Reynolds’ paper, the exact algorithm isn’t detailed so I had to make do with what I could find in the literature.
(R)VO
Velocity obstacle is an analytical approach to collision avoidance and works like this: define a cone starting from your position and encapsulating the obstacle plus your own radius r around it. Then pick the best velocity that lies outside of that cone. When using reciprocal VO, the cone is only half as wide, because we expect the obstacle to be employing the same strategy and dodge the other half of the way.
For each obstacle n, we must now make sure that the direction v⁽ⁱ⁾ of agent i does not lie within the cone, in other words:
Note that there are still infinitely many valid directions to choose from. One selection mechanism is described here: uniformly sample points around p⁽ⁱ⁾, give them a score, then select the direction with the highest score that lies in the permitted zone.
In the standard collision avoidance setting, say two robots driving towards each other, it makes sense to have a target direction / position. Then, you can just score the sampled directions by how well they align with that.
So should we use the exit direction as the target? I wouldn’t be too sure. Steering the agent toward the exit is already taken care of by the fourth goal. Embedding it additionally into the collision avoidance mechanism would place disproportionate importance on the destination, not to mention tightly coupling what was previously nice and loose.
Instead, let’s assume that the current direction is kind of on track, and aim to maintain it. The score for a sampled velocity v is then a function of the current velocity v⁽ⁱ⁾:
Then we simply select the v with the highest score that lies outside of all VO cones.
So does this work? Unfortunately no. The velocity score introduces an improper bias towards the current direction and the agents get stuck once they stop moving. They can still be pulled out of a standstill by the influence of their moving neighbours. But as areas of stagnant agents grow larger, this becomes more and more difficult and the end of my simulation once again looks like this:
Besides, this method doesn’t compute an “avoidance vector” in the intuitive sense. We want something that points in the direction of separation and whose magnitude correlates to the emergency of avoiding the obstacle.
Fast obstacle avoidance
After some more research I found this article which seems to be exactly the separation vector I was looking for! It’s easy to implement by raycasting from each agent at regular angle intervals and using this formula to compute the avoidance direction:
with hyperparameters D and s and where the p⁽ⁿ⁾s are all the hit points of the raycasts.
Casting multiple rays per agent is expensive and may slow down even a DOTS simulation, so instead I’m using the neighbour p⁽ⁿ⁾s already present in the neighbourhood sphere.
The result
So here we have it, the final crowd simulation:
It’s fast and it’s realistic, the agents find the exit but also follow the general flow.
Two observations:
- sometimes, the agents overlap with each other. This really shouldn’t happen with Unity rigid-bodies and I’ve tried a few things but can’t really get rid of it. I suppose it’s because pressure builds up from the outside in and they’ve got nowhere to go — I’ve accidentally created a crowd crush.
- because the agents are all circles, they tend to form very dense structures that move as a whole and no individual movement is possible.
This makes it so there’s nothing to learn and I rather think that my RL algorithm will fail. So there goes my plan of learning the optimal strategy.
S̶t̶e̶p̶ ̶4̶:̶ ̶T̶r̶a̶i̶n̶i̶n̶g̶
After a short crash out, I started looking for solutions.
I could of course make the agents more varied: give them different sizes, use ovals instead of circles and make them face the movement direction. But do I really want all this added complexity? Plus it’s by no means certain that these adjustments are enough to create an environment suitable for reinforcement learning.
Instead, I’m going to skip the learning part and go straight to analysing the flow. My plan is to remove the player and visualise vector fields of average direction per position, duration until exit, etc. And then interpret them manually.
But all of this needs to first be implemented and I’ll put it in another article so .. stay tuned.
