Hordes of enemies will be featured in our upcoming Action-RPG Warhammer 40,000: Inquisitor – Martyr. For example, Nurglings are nasty little creatures that swarm Inquisitors, essentially overwhelming them… but how exactly are they programmed in a complex, destructible environment?

Let our Lead Gameplay Programmer György Flórea (“Giggs”) explain it in his own words:

“This time at Neocore, I faced with another exciting pathfinding problem when the management proposed the concept of hordes during the early development of Warhammer 40,000 [Inquisitor – Martyr]. They told me we need them, because we don’t have them. This task surprised me because with all the innovation we could only work with the fraction of the computing power we have utilized in The Incredible Adventures of Van Helsing.

The pathfinding in Van Helsing was already good, but very limited in what it could do with changes in the terrain. With Inquisitor – Martyr’s destructible environments, it’s a different proposal. The task was basically: “create smarter pathfinding while using less computing power”.

Calculating pathfinding isn’t too taxing in static environments, but it becomes harder when there are moving enemies that need to be circumnavigated or pushed aside. The worst case scenario is when every moving creature is trying to rush towards the same point. Creatures with melee attacks trying to kill the same target, in a horde! So my first request toward management was to make levels with fewer creatures waiting in packs, and there should be more enemies with ranged abilities. 

With that done I was trying to figure out the solution for horde creatures pushing each other aside, jumping over each other. After moping around a bit, I found these expectations helpful:

• It’s okay for horde creatures to be deliberately dumb
• It actually looks good if they don’t react to environmental changes instantly
• Members of the horde should not circumnavigate each other, rather just keep their distance
• Individual units should not be smart on their own, they should follow the same target on the same path as the others

So after the first panic, the solution kind of proposed itself: fluid simulation!

In fluid simulation, particles (in this case: units) simply migrate from dense areas to less dense areas. To make this work, there needs to be a grid, where we calculate particle density per tile according to their location, so particles can determine their movement vector from the density of adjacent tiles (to move towards less dense tiles).

Sounds simple, but this, in itself, isn’t enough. To move the fluid to a given target, tiles need to take the movement vector of the pathfinding into consideration as well. We should know the path to the target from every point on the grid map. We can calculate this with a simple graph algorithm called Breadth-First Search, starting from the nearest tile to the target. With too many tiles, this could be taxing on computing power, but here’s the trick: as we said, the horde can be dumb, so it’s okay if they don’t calculate their path with the most recent target position. So pathfinding can run in the background, and when it’s ready, we swap the actual grid to the new one, and as it’s updating with the newest pathfinding calculation, the horde can move forward with the previously completed pathfinding calculation results. We can even help navigating through static obstacles by giving their tiles the highest density, so these would drive the creatures away from them.The behavior of the horde is influenced by taking tile density and movement vectors into consideration, and according to which one we put more emphasis on, the horde will spread out, or form a tighter blob, and by putting more emphasis on the movement vector calculated in the previous iteration, the horde will have a harder time changing direction (this simulates momentum). These factors can be manipulated by designers, but the system is smart as well. If a unit is in the midst of a horde, and the tile density is high, the momentum of the horde will be bigger.

Horde creatures are controlled by a special, independent AI, so that creatures won’t diverge from the horde. This is responsible for skill use of creatures near the target, pushing each other aside, or for fitter creatures jumping over dying units. 

After this I had to figure out one more thing: how the horde should handle units that somehow did fall behind. The grid cannot be infinitely big, so some of the creatures can remain off the grid, and there is no information on how to control them. So horde AI has a few categories based on how much time passes since the unit has fallen behind.

If the unit gets off the grid:

• The unit moves forward with horde according to the last pathfinding calculation results received when it was still on the grid
• The receives a movement vector pointing towards the nearest tile on the grid, the unit moves there
• The unit uses a pathfinding algorithm to find the horde’s target
• Letting the unit off the hook. It will find its way to the horde if it comes near again. Falling behind means the regular unit AI takes over.

See the dataslate that illustrates all this.