# Movement system for thousands of entities

I want to implement a movement system for armies of multiple thousand units. However, I struggle to get the movement "stable" when there are more than a few hundred units.

The problem: When too many units move and start pushing against each other, the center of the army becomes "unstable" and jiggles around. This is especially noticeable when an army tries to move through a chokepoint or against a soft blocker.

For reference, the goal is a movement system like in They Are Billions: https://youtu.be/zYGTbt2vXtQ?t=788 (from 13:10). While I don't need THAT many entities, emphasis is on how smooth the zombies group/clump up when their path is blocked. No jiggling, just smooth pushing against a common front.

I tried impulse-based collision resolution, Verlet integration, and classical steering behaviors. However, I eventually always ran into the same issue. It seems that I am not able to properly stabilize the center of forces where most entities push into each other, but maybe I am just taking an incorrect approach.

Do you have an idea how to approach this or have resources on implementing such a system? If you need more information, please let me know.

• I really want to understand how to solve this, "just use library XY" unfortunately does not help
• Solution must not be tied to a specific game engine
• Movement is currently just constant velocity towards a common point for all entities
• Entity shape is always a circle (although of different sizes)
• Efficiency in general is important, "just do 1000 substeps per iteration" is not a solution

Cheers!

Myself, I'd solve this with a combination of flow field pathfinding and local avoidance.

First, the flow field: for each army, initialize a graph of map locations spanning the army and their goals (could be a grid, a navmesh, or whatever you like to use). Each node should initially store "infinite" distance to goal as its value. Then select the goal nodes - the places or targets that army should be pathing toward - and set those node values to 0, adding them to a queue of recently changed nodes.

While that queue is non-empty, take a node out, call it "parent", and iterate over its neighbours. If the neighbour's value is more than the parent's plus the distance between the parent and that neighbour, reduce it to that value and stuff it into the queue. (If your terrain has different traversal costs, traps the armies should try to avoid, etc., you can add this as a penalty to the distance)

When this iteration completes, you have a distance field that you can convert to a flow map: at each node, the flow direction points toward the neighbour with the least sum of value + edge cost (or an interpolation between two neighbours, if that makes sense for your graph structure). Now an army unit anywhere can just do a simple look up to find the best direction to move toward the army's goals.

The advantage here is the processing work scales with the size and density of your pathing graph, not the number of units. So you can support gobs of units, as long as you keep your map subdivisions reasonable.

You can also use the distance field to order your units from those closest to the goal to those farthest away, and iterate over them to update their positions in that order. This helps avoid bottlenecking: units in front have a chance to move out of the way before units behind them try to move.

(In case you're worried about the cost of sorting many units, note that the order will usually change very little from frame to frame, and does not have to be perfect to be of benefit. So you can store the units in almost-sorted order, and incrementally update it a bit each frame, so that it converges toward sorted order without ever needing to sort the whole list in one go)

Now you don't need to do any fancy force-based repulsion or anything like that. Each time it's a unit's turn to move, the units ahead of it are already at their final positions for the frame, so it can treat them as stationary obstacles. Use spatial hashing so you can find obstacles within one movement step of this unit quickly, without searching the whole map. You can alternate between moving units of opposing armies to neutralize any advantage one side gets from moving first.

The unit can now sample points in an arc with the radius of its movement step - directly in the flow field direction, and if that's obstructed, also check a little to the left and right. For each possible destination, check whether it's within the collision radius of another unit plus this unit's own collision radius - if so, backtrack the destination point to the circumference of that summed radius and try again. Of those non-intersecting points, choose the one with the lowest distance field value to path towards.

You can keep track of units that have moved less than their full speed in recent ticks, and increase how wide / how many times they scan for alternatives, so stalled units get more aggressive about trying to go around the obstacle, while unobstructed units just march forward without paying any extra cost to look around.

This type of approach should be jitter-free, since units only move "downhill" and collision influence only flows one way, and scale up to many thousands of units with the right graph/spatial hashing structures and cache-friendly data layout.

• Thanks for this amazing answer, it is exactly in the direction I hoped for. While my first impulse was "thanks, but the pathfinding part is already solved", your approach of (re)using the distance field for ordering is what's new to me (and very interesting). I will try this out in the next days and post a reply whether this worked out. Commented Sep 8, 2022 at 18:55
• Today I had the time to implement your suggestion and it works great! Thanks again! Commented Sep 10, 2022 at 22:14
• In case someone else finds this question: For the backtracking of movement destinations in case of blocked paths, this math stackexchange post was really helpful: math.stackexchange.com/a/913522 Commented Sep 10, 2022 at 22:14