Blog

Procedural generation is a fun thing to mess around with. When coupled with data-oriented design, an entity component system (ECS) in this case, the ability to scale and change functionality reveals itself. In this article, I will describe how I took expensive NPC behavior and tweaked it for a 500x performance gain while retaining all functionality.

ECSplanation

To define behavior in an ECS, you can use systems (functions) that perform logic on a world. Systems may query lists of entities according to which components they possess. For instance, if I want to step every animation forward with every frame, I can create a system to do this (using bitECS and JavaScript here):

// ~/systems/animation-step.ts
import { defineQuery, Not } from "bitecs";
import { AnimationMixer } from "three";
import { AnimationMixerComponent } from "~/components/animation";
import { Disabled } from "~/components/disabled";

// Specify what combination of components we're looking for
const animationMixerQuery = defineQuery([
    AnimationMixerComponent, 
    Not(Disabled)
]);

export function animationStepSystem(world) {
    // List the entities that match our query
    for (const entity of animationMixerQuery(world)) {
        // Pull the component data for this entity
        const mixer: AnimationMixer = AnimationMixerComponent["data"][entity];
        mixer.update(0.16); // Preferably delta time
    }
    return world;
}

Note that it isn't ideal to have complex objects as components (for both cache performance and component serialization), but you can still do it if the alternative is greatly inconvenient. The optimal strategy is to use primitives (numbers, enums, characters, etc.) within a structure of arrays.

Additionally, you can query for when a component is added, removed, or changed. The system will act on these lists when they are next called. Some people even use components as event flags (which are useful when events are required by multiple systems).

As a result of every system acting on the entire world, the functionality compounds. A new system does not require changes in your code. They can be added and removed as modules. When a few simple systems combine, though, you easily have complex functionality. Completely decoupled with high cohesion. It's what you might want as a software developer, maintainer, and project manager. On the other hand, there may be unintended side effects that prove difficult to debug. No architecture is perfect for every use case.

Behavior

To get started, I'll define what I want the NPCs to do:

1. Take a humanoid form,
2. Collide with their surroundings,
3. Move in the same way that they player does,
4. Animate according to their movement,
5. Walk towards the player, and
6. Navigate around the map.

I won't go into much detail on how the NPCs have been created. To create a 'class' of entity, you can set up a function that instantiates an entity and adds all the necessary components with default values. The pattern is similar to a factory. Systems from the player were reused, so all I needed to add was the controller implementation for NPCs.

Object Permanence

When an object is out of sight, it might as well not exist for the most part. Right now, every object has physics and rendering applied constantly, regardless of how close it is to our character. In traditional game design, you would use a "level of detail" system; objects further away receive lower-quality models, infrequent logic calls, and more. Because my map is almost guaranteed to occlude entities after a certain distance, I can entirely disable the rendering and physics accordingly.

Without applying these changes, the game handles about 20 NPCs walking around. To "disable" an entity, I just add the Disabled component and consider it within world queries.

Toggling Entities

The first step to these optimizations is to apply the Disabled component when some conditions are met. There are a few mechanisms you can use to determine the occlusion state of an entity. To provide a balance of performance to functionality, we can use multiple methods to weed out entities:

1. Chunking entities: A 'chunk' is an area of the world that is given some coordinates. We can sort entities out into these chunks by snapping their position into a grid. At this point, they can be retrieved for occlusion testing on a map with roughly O(1) performance. A quadtree may be better suited, but it is more complicated to implement. For simplicity, here is the flat grid:

const chunkSize = 30;
const entityPosition = Collider["data"][entity].translation();

// Get the chunk coordinates of a given entity
const chunkX = Math.floor(entityPosition.x / chunkSize);
const chunkZ = Math.floor(entityPosition.z / chunkSize);

// Add the entity ID to the new chunk when it changes
chunks[chunkX][chunkZ].push(entity);

// To get the entities within a chunk:
const nearbyEntities = chunks[chunkX][chunkZ];

2. Raycasting: Now that we have a list of objects near the players, we can use raycasting to test for a sightline between the player and the NPC. The raycast is a query to the physics scene in this instance, checking every object in the area; this makes it quite the expensive operation. If there is a sightline, we can confidently say that the object should be disabled:

// Get the delta position from one object to another
const direction = deltaObj<RAPIER.Vector3>(
    playerPos,
    enemyPos
);

// Create the ray from the enemy's position towards the player
const ray = new RAPIER.Ray(
    enemyPos, 
    direction
);

// Test this ray against the physics world
const res = physicsWorld.castRay(
    ray, // The ray we're testing
    1, // The time-of-impact, which is 1 
       // due to our non-normalized vector
    false, // Ignore the collider that our ray starts in
    undefined, // Filter flags
    undefined, // Filter groups
    Collider["data"][player], // Filter collider
    undefined, // Filter rigidbody
    colliderEnemyFilter // Filter predicate
);

Rendering Performance

It is extremely taxing to have dozens of skeletal objects animating at the same time. Each bone is updated internally by three.js every frame. There are a few ways we can optimize this. Due to the high memory and CPU utilization, it's best to start with a technique known as "pooling".

Instead of giving every NPC its own mesh, we can use a proxy system of sorts. Because we know that only 20 or so of these skeletons can render performantly, it doesn't make sense to store more than 20 in memory. This optimization involves cloning the model 20 times and reusing them whenever an NPC appears on the screen. Each pooled mesh can attach to their own entity. You can use entity relations to apply a pooled character model to an NPC.

To optimize unused pooled objects, disable them within the threejs scene. Additionally, we can add a Not(Disabled) component to the animation update system:

const animationMixerQuery = defineQuery([
    AnimationMixerComponent,
    Not(Disabled)
]);

The biggest downside here is that every character is going to look more-or-less the same. You can't really do too much about it with complicated models. If you need a lot of unique characters, it may be best to load them into memory on a worker thread as necessary (or just use a better-equipped language).

Physics Performance

One of the larger bottlenecks when getting started was with the KinematicCharacterController from the RAPIER physics engine. Even if you don't query the character controller, it still runs physics checks every frame. To solve this, I just .free() Disable'd character controllers. When they are re-enabled, I reinstantiate the character controller. It's not too expensive to instantiate these, but it would be a good idea to pool them instead.

Maintaining Behavior

Since the characters just walk up to a known-traversable node at a consistent speed, we don't need the character controller to do this. We can just move the position accordingly. If the NPC is at its destination, it can head for the next pathnode or stop moving. Almost all offscreen behavior will be simple enough to run across all NPCs; they can stop at nodes to complete actions that flip something's state, but there isn't a need for physics queries or anything like that. Either way, I doubt whatever this project turns into will need 10,000 NPCs.

Summary

I hope these insights into how I optimized my little game prove helpful to someone. There isn't much in the way of code samples, but the high level descriptions hopefully give some ideas about how to conserve resources in different use cases. More of this project will come soon.

Credits

This work is based on "Nathan Animated 003 - Walking 3D Man" (https://sketchfab.com/3d-models/nathan-animated-003-walking-3d-man-143a2b1ea5eb4385ae90a73657aca3bc) by Renderpeople (https://sketchfab.com/renderpeople) licensed under CC-BY-4.0 (http://creativecommons.org/licenses/by/4.0/)