NPC swarm simulation

By Lennart van Dorp

The project

I had been working on a side project with a first person controller. While thinking of ways of turning it into an actual game I considered that making it a wave based zombie game would be a pretty good way of making it fun while still keeping the scope somewhat manageable.

For a few years around the 2010's the density of zombie games on the market was immense. The ones I played most probably being Left 4 Dead and Black Ops 2 Zombies. The latter of which is probably a formula I would like to iterate on. While I think the wave based zombie shooting is fun, it doesn't scale extraordinarily well. At a certain point, the only thing making the game harder is the amount of health the zombies have. In order to improve this, I would like to be able to create a zombie system where the maximum amount of zombies is greatly increased. So difficulty can be ramped up in more ways than health.

Furthermore the behavior of zombies in that game is not very interesting in my opinion. The zombies always move towards the player in with an A* optimized route. Making them extremely predictable.

I have made a system for having a large group of agents move around a space and towards the player in a believable manner. Things that were important here were to only use information that the character would believably have and to keep the performance manageable.

The system was intended to be put into a first person zombie game with large amounts of zombies attacking the player. Initially, I intended to make use of multithreading to be able to calculate more agents at once.

Swarming

Doing this type of research proved a challenge. Since there’s a large amount of points to start the research from. I started off manically running around the internet trying to find something that would help me. I don’t think I need to explain that this wasn’t the most optimal way of working. Luckily I got the advice that I should probably just focus on making the system I want to make and switch to the performance when that becomes a problem.

So I made a large group of navmesh agents that would follow the player around. This ran surprisingly well. Only when quadrupling the currently visible amount of agents, which was around a thousand, did the performance really reach intolerable levels. Of course, when put into a game, there will be other performance costs and the machine this ran on is quite strong. So, even though 64 FPS sounds pretty good, it’s not enough. On top of that, I wanted the behaviour of the agents to be more interesting. I wanted them to use the information they would realistically have. I wanted them to be more stupid and behave more like an animal than a planning person.

As it stands, the zombies simply rush toward the player as quickly as possible. This doesn’t feel like they are behaving in an interesting way. (Yes this is shade towards Call of Duty Zombies) Having all of them use the built in Unity navigation system is also quite heavy for the CPU. So next I’ll start looking at possible other solutions.

I remembered the Boids algorithm that we worked with earlier in the Game Development courses. So I started working on a way to implement this into the zombie logic. A good example that I used to make it in the past was the video made by Sebastian Lague.

The zombies should only be able to react to things that are close to them. Which is good, since that means zombies don't always have to check every other zombie. I could have written a system that would only check zombies against zombies that could potentially be close to them, but I cheated. I used Unity's physics system that does that anyway instead. Like this:

    private void OnTriggerEnter(Collider other)
    {
        if (other.CompareTag("Zombie")) { closeZombies.Add(other.attachedRigidbody); return; }
        if (other.CompareTag("Obstacle")) { closeObstacles.Add(other); return; }

    }

    private void OnTriggerExit(Collider other)
    {
        if (other.CompareTag("Zombie")) { closeZombies.Remove(other.attachedRigidbody); return; }
        if (other.CompareTag("Obstacle")) { closeObstacles.Remove(other); return; }
    }

They can then use the closeObstacles and the closeZombies to do the flocking and avoid obstacles. After implementing the Boids rules the agents’ behavior had become much more zombie-like. But since they group up so much, it would be much easier for a player to avoid them. Removing the alignment rule makes it so that the zombies do flock, but are less likely to clump up in big targets and groups.

I made a group of functions that could influence the direction that a zombie will choose to go. Below you can see the way it was implemented, it was easy to use this base to build upon. To add new rules and the strength of the influence of those rules.

        moveDir = (
            GetAverageSurroundingVel() * parent.conhesionStrength
            + GoAwayFromObstacles() * parent.obstacleAvoidanceStrength
            + GoAwayFromZombies() * parent.separationStrength
            + GoToZombies() * parent.alignmentStrength
            ) * parent.acc
            + GoUpHill()
            ;

As an example, this is what one of the rules looked like. This function would return a direction that would as good as possible move away from walls and other objects with the "Obstacle" tag.

    Vector3 GoAwayFromObstacles()
    {
        Vector3 averageDir = Vector3.zero;
        foreach (Collider o in parent.closeObstacles)
        {
            Vector3 closestPointDir = o.ClosestPointOnBounds(parent.transform.position) - parent.transform.position;
            if (closestPointDir.magnitude < parent.obstacleAvoidanceDist)
            {
                averageDir -= (closestPointDir).normalized / closestPointDir.magnitude;

            }
        }
        return averageDir.normalized;
    }

I have now increased the amount of agents to around 200 and the performance has, on my rather powerful device, dropped to around 50 Frames per second, even without any animations or other functionalities added to the game. I think it will be useful to use other methods to increase the performance of the application. The current implementation is noticeably heavier than the original Unity navigation system version. They do however behave in a much more interesting way to both look at and play with. While they are generally roaming around with no real goal, I have also added some smarter agents which uses the Unity nav system. The normal zombies will chase these smarter ones and so also move toward the player.

Looking at the profiler, I can deduce that a big part of the current performance cost is coming from the scripting in the zombies. Which is quite good to know. Especially since this is most likely to be easily converted into multithreaded code. This would then be a good moment to start working on multithreaded code.

Attempting DOTS 1.0

The tutorial I was working with showed me how to create Entities and how to run code in them moving the entities around the game world. I must say I was blown away by the amount of scripts and objects I could use at the same time. I was able to simulate and render thousands of cannonballs at the same time at acceptable performance.

Working with ECS and DOTS is significantly more complicated than working with regular MonoBehaviors. What would take you just putting an Update() function in a MonoBehavior in normal Unity takes a lot more steps when working with multithreading. You need an authoring script with a baker, that can turn the object into an entity. An IComponentData struct, that can save the different values for an entity. An IAspect struct that can forward this information to the entity. Then an ISystem struct that can schedule the job and the job itself. That is not even mentioning the DynamicBuffer that comes in place of lists and arrays, that requires you to write your own IBufferElementData.

If none of this made sense to you I don't blame you. Deciding to work with DOTS means sacrificing time, effort and at least 10% of your sanity.

//This is where the actual job is received from another struct so it can be scheduled
[BurstCompile]
public void OnUpdate(ref SystemState state)
{
    var ecbSingleton = SystemAPI.GetSingleton<EndSimulationEntityCommandBufferSystem.Singleton>();
    var ecb = ecbSingleton.CreateCommandBuffer(state.WorldUnmanaged);
    var zombieJob = new ZombieJob
    {
        ECB = ecb.AsParallelWriter(),
        DeltaTime = SystemAPI.Time.DeltaTime
    };
    zombieJob.ScheduleParallel();

    var triggerJob = new Trigger();
}

A few problems arose when I started working without the tutorial that made it impossible to quickly progress. I put a lot of effort into being able to transfer data to the individual entities. But most of all, since the 1.0 version that I am working with had only been released so recently, it was hard to find information that was accurate. This meant that most resources I could find had some kind of outdated aspect to it that was impossible to google. On top of that, the beta version of Unity I was working with is also still incomplete. Which can cause a whole new set of issues.

The two most important things I've learnt in the few almost wasted weeks I worked with Unity DOTS 1.0 were that this might just be the thing that can make unity an accessible way of rendering and running monumental amounts of things at once. Removing a hole bunch of limits that were previously put on Unity developers. The second thing I've learned is that Unity DOTS is just not ready yet. Working with it is an uphill struggle of fixing things that broke without any reason. Dozens of deprecated functions an structs. Meaning every thing you do research in has some kind of inaccurate information.

To at least get an idea of the positive difference using DOTS makes, I decided to do a little stress test of the technology and to compare it to using normal Unity Physics. So I made two versions of an application with 4000 simulated marbles that drop and interact. I was kind of inspired by a video I had found on stress testing Unity.

As you can see the behavior of both versions is pretty much the same only that the ECS version has nearly double the amount of FPS. That is an impressive improvement that should not be taken lightly.

What next?

Even though I was impressed with the potential of Unity DOTS. I did not think it would be enough to put the amount of work in it that I would have to, to convert the version of the zombies I had to an ECS version. So instead I decided to just continue work on the single threaded version and to improve the performance on that version.

To start I decided there should be a way for the zombies to follow the player around. Since the beginning we were talking about the possibility of the agents moving around by smell. Using nodes with a direction that they could follow.

This turned out to be pretty easy to implement. To avoid using too many GetComponent<>() functions, I decided to just use the transform of the object. The transforms position and rotation to be precise. When a zombie would find a new Scent, as I called them, the zombie would align themselves toward the direction the scent was moving. The scents that were placed by the player would disappear in time.

    Vector3 FollowScent()
    {
        if (parent.scent)
        {
            if (!ScentObstructedByWall())
            {

//I wanted to make sure the zombies could move through more cramped spaces, so I made sure that they would, if they hadn't passed the scent point yet, they would first move towards it. 
                if (Vector3.Dot(parent.scent.forward, parent.scent.forward - parent.transform.position) < 0)//If haven't passed the scent point yet. 
                {
                    return (parent.scent.forward + (parent.scent.position - parent.transform.position).normalized).normalized;
                }

                return parent.scent.forward;
            }
        }
        return Vector3.zero;
    }

I was quite impressed by how reliably this made the zombies follow the player around whenever they found a place the player had passed. It made the prototype something that is already quite fun to walk around in and to try to avoid the zombies always coming your way.

Optimisation

At this point I still wasn't really satisfied with the performance of the app though. However, maybe I could find a way of optimizing without resorting to multithreading. It wasn't necessary to make them find a new direction every single frame. So I made a zombie manager that would track which zombies had to be updated at which moment. I could choose how many zombies would be updated every frame. Then the direction the zombie would only change once every few frames, but I could make sure that the zombies would keep accelerating in the last calculated direction.

public override void UpdateZombie(float deltaTime)
{
    moveDir = (
        GetAverageSurroundingVel() * parent.conhesionStrength
        + GoAwayFromObstacles() * parent.obstacleAvoidanceStrength
        + GoAwayFromZombies() * parent.separationStrength
        + GoToZombies() * parent.alignmentStrength
        + FollowLeader() * parent.followLeaderStrength
        + FollowScent() * parent.scentStrength
        ) * parent.acc
        + GoUpHill()
        ;
    DrawGizmos();
    base.UpdateZombie(deltaTime);
}

public override void PhysicsUpdate()
{
    GoInDirection(moveDir);
}

After implementing this, the behavior of the zombies didn't noticeably change. The zombies still flocked around and followed the player. I also used some debugging tools to visualize the inner workings of the zombies. The white lines are cast from the updated zombies to all other zombies around it which it is conscious of. The white lines are cast towards each other agent one zombie is aware of. The green lines are cast towards a scent point that the zombie can see, the red ones towards scent points the cannot.

The performance increased impressively and an advantage to working like this is that it scales quite well. More zombies will not necessarily increase the calculation costs. It will only increase the amount of zombies that needs to be gone through, meaning each zombie is updated fewer times and their responsiveness can suffer, but the performance does lesser.

As you can see in the following examples, the performance increases immensely by utilizing this trick. I doubled the amount of zombies, but was still able to improve on the performance of the version with 200 by not updating all of them at once. Of course, as might be obvious from the videos, 400 zombies at once might be too many. But stress testing the possibilities is probably useful. At the very least it's fun.

Conclusion

I am pretty happy with what I have created, and I find it likely that I will use much of this code to actually make a game in the future.

I have wasted a little too much time in trying to create a DOTS version of the system. Time that I could have put into realizing the single threaded version even further. I could have added animations, more aggressive behavior towards the player once they had become close enough and much more. Had I cut my losses earlier.

That said, not only do I think the behavior I created is more complicated than in most zombie games. I think it could result in quite interesting gameplay.

Works Cited

andrew-lukasik. (2022, 5 9). How to implement ECS trigger collisions? (Unity.Physics 0.50). Retrieved from answers.unity.com: https://answers.unity.com/questions/1901025/ecs-collisions.html

Code Monkey. (2020, 1 12). Dynamic Buffers in Unity DOTS (Array, List). Retrieved from Youtube: https://www.youtube.com/watch?v=XC84bc95heI

Empires, H. (2019, 7 2). Ants are amazing Masters of Navigation - Ant Vlog #004. Retrieved from Youtube: https://www.youtube.com/watch?v=rpnXO2ew110

Fabrice. (2022, 7 29). ECS tutorial. Retrieved from Github: https://github.com/Unity-Technologies/EntityComponentSystemSamples/blob/master/DOTS_Guide/ecs_tutorial/README.md

Infallible code. (2020, 3 8). Unity Job System — A Practical Code Example. Retrieved from Youtube: https://www.youtube.com/watch?v=3o12aic7kDY

La CreArthur. (2020, 4 25). How many Rigidbodies can Unity support ? [2020 DOTS Edition]. Retrieved from Youtube: https://www.youtube.com/watch?v=U6idEdIEsa0

Lague, S. (2019, 8 26). Coding Adventure: Boids. Retrieved from Youtube: https://www.youtube.com/watch?v=bqtqltqcQhw

Turbo Makes Games. (2021, 7 20). How to Use Dynamic Buffers to Store Many Components on an Entity in Unity ECS - DOTS Tutorial 2022. Retrieved from Youtube: https://www.youtube.com/watch?v=Ki0AwYZw2Ac

Turbo makes games. (2021, 7 4). How to Use the Entity Manager in Unity ECS - DOTS 2022 Tutorial. Retrieved from Youtube: https://www.youtube.com/watch?v=Pa6Uf2jLUQg

Unity. (1017, 11 10). Unite Austin 2017 - Massive Battle in the Spellsouls Universe. Retrieved from Youtube: https://www.youtube.com/watch?v=GEuT5-oCu_I

Unity. (2022). Entities project setup. Retrieved from unity3d: https://docs.unity3d.com/Packages/com.unity.entities@1.0/manual/getting-started-installation.html

Unity. (n.d.). Interacting with Bodies. Retrieved from docs.unity3d.com: https://docs.unity3d.com/Packages/com.unity.physics@0.3/manual/interacting_with_bodies.html