home dir commission contact

while developing a game of sufficient complexity, you’ll need to figure out a solution for abstracting over the idea of an “object” and updating its state every frame. you may find this is non-trivial. this article will offer different solutions for this.

naive approach

the first idea one may have would be to simply have an array of “entities” and calling their update method, like so:

type Entity = {
	tick(): void;
};

type State = {
	entities: Entity[];
};

const update = (state: State) => {
	for (let i = 0; i < state.entities.length; i++) {
		state.entities[i].tick();
	}
};

this certainly works for the basic task, but what if we need to destroy an entity? additionally, what if an entity needs to access another entity (for collisions)? a quick solution might look something effectively like this:

type Entity = {
	tick(state: State): void;
	destroy: boolean;
};

type State = {
	entities: Entity[];
};

const update = (state: State) => {
	for (let i = 0; i < state.entities.length; i++) {
		state.entities[i].tick(state);
		if (state.entities[i].destroy) {
			// remove the entity at index `i`
			state.entities.splice(i, 1);
			// decrement `i`, since all entities afterward just shifted back a space 
			i--;
		}
	}
};

this still works! and, it is very simple - an undeniably good reason to use it. however, you must consider the surface area of error you can make now.

  1. you are giving entities unconditional access to the entire state of entites now - what if one of them removes an entity? suddenly your update loop is no longer accurate.
  2. the performance cost of simply removing an element is similarly non-trivial. in the example, we use an element removal method that shifts following elements backwards to maintain ordering. if we didn’t care about order and used a method that, say, swapped out the element with the array’s last element, then popped, this would be faster (decrementing i would still be necessary). however, in some cases, this may not be ideal either. in a lower-level language like C, if one wanted to store entities in the array without likely another allocation (or, in place), if the entity size is large enough, with enough entities, even that operation could be a bottleneck.
  3. it may not be ideal to add any kind of flags to entities (the destroy property), which could be seen as an implementation detail of the update function that an entity shouldn’t have access to.
  4. it isn’t possible to support an entity ergonomically having references to other entities.
    • in most garbage collected languages like TypeScript, you could just have an entity “A” with a property of type Entity. however, if the pointee is ‘destroyed’, A is now holding a reference to a dead entity, which may cause bugs if A doesn’t take care to confirm that its entity isn’t destroyed before using it.
    • without a garbage collector, having references like this is almost impossible. with C, for example, keeping around a pointer or an index to an entity inside the array are both obviously unsound ideas, as the array may shift around elements.

if these points are acceptable, by all means, use it. as you’ll read though, there are ways of mitigating all of this without terribly much more complexity.

encapsulation

many will harp about ‘useful abstractions’. a novice programmer may hear this and think to design simpler apis on top of more difficult ones for easier usage throughout a project. they might not think about how an abstraction can be short lived, or even act as a dynamic permission layer. for example:

type Entity = {
	tick(ctx: Context): void;
};

type State = {
	entities: Entity[];
};

type Context = {
	state: State;
	entity_add(entity: Entity): void;
	// or more methods
};

const update = (state: State) => {
	const context: Context = {
		state: state,
		entity_add(entity: Entity) {
			this.state.entities.push(entity);
		},
	};
	// note for typescript users: a class may be more suitable for this

	for (let i = 0; i < state.entities.length; i++) {
		state.entities[i].tick(context);
	}
};

consider how tick() now only has access to the operations we want it to have access to. one can imagine how if, say, Entity had a draw() method, it could take a different context type that doesn’t allow for an entity to modify other entities.

generational approach

an easy way to avoid moving around data is to give each slot of our entities array two states: “has entity” and “has no entity”. in TypeScript here, we will represent this as either Entity and null respectively:

type State = {
	entities: (Entity | null)[];
};

in C, this might literally be a null pointer, or a field in an entity struct.

then while updating this, we check to make sure an entity isn’t null before calling tick():

const update = (state: State) => {
	for (let i = 0; i < state.entities.length; i++) {
		const entity = state.entities[i];
		
		if (entity === null) {
			continue;
		}
		
		entity.tick();
	}
};

‘destroying’ an entity is now trivial - just set its index to null. additionally, keeping a reference to an entity can just be a number (this is preferable to an actual reference, as now when you index into the array, you should check if the slot was null).

when adding an entity like this, you now search the array for an empty slot, and if there is an empty slot, add the entity to it. otherwise, if there are no empty slots, simply push the entity to the end of the array. this isn’t efficient though; worst case, adding an entity could search the entire array every single time.

const entity_add = (state: State, entity: Entity): number => {
	for (let i = 0; i < state.entities.length; i++) {
		if (state.entities[i] === null) {
			state.entities[i] = entity;
			return i;
		}
	}
	state.entities.push(entity);
	return state.entities.length - 1;
};

const entity_destroy = (state: State, index: number) => {
	state.entities[index] = null;
};

we can modify our state to maintain a stack of indexes to empty slots:

type State = {
	entities: (Entity | null)[];
	empty: number[];
};

// now adding and destroying aren't that slow

const entity_add = (state: State, entity: Entity): number => {
	const empty = state.empty.pop();

	if (empty !== undefined) {
		state.entities[empty] = entity;
		return empty;
	}
	else {
		// there are no empty slots
		state.entities.push(entity);
		return state.entities.length - 1;
	}
};

const entity_remove = (state: State, index: number) => {
	// it would be a bad idea to even allow the possibility of `state.empty` having the same number multiple times.
	// we also don't care to check for bounds, as the array never gets smaller.
	if (state.entities[index] !== null) {
		state.entities[index] = null;
		state.empty.push(index);
	}
};

if we allow an entity to keep a index to other entities, then there is a small bug we can make here. what if an entity “A” keeps a reference to entity “B” for an extended period of time. during this time, B gets destroyed - fair enough, A only has an index, so when A tries to access B, it only gets null. however, elsewhere, “C” gets added into the slot that B was at. now the index A’ was keeping is technically valid, but pointing to a completely different entity!

we can fix this by giving our indexes and slots an additional number, essentially representing how old it is. the idea is simple: each entity slot will have a number called a “generation”, and the entity itself. when we give out indexes, it will be both a number representing actual array index to the entity, and the exact “generation” that was at the slot during the index’s creation. when an entity is destroyed, we set it to null like usual. but, when we add back into it, we increment the slot’s generation. now if an entity was keeping an index to that hypothetical slot, it should check to see if the index’s generation is the same as the slot’s generation. if it isn’t, then this index is no longer valid.

code might help illustrate this better:

// first, we define an `Index` and `Slot` with their respective generations:

type Index = {
	index: number;
	generation: number;
};

type Slot = {
	entity: Entity | null;
	generation: number;
};

// `State` now works with `Slots`.

type State = {
	entities: Slot[];
	empty: number[];
};

const entity_add = (state: State, entity: Entity): Index => {
	const empty = state.empty.pop();

	if (empty !== undefined) {
		const slot: Slot = state.entities[empty];
		
		// increment generation, invalidating all previous `Index`s pointing to this slot
		slot.generation += 1;
		slot.entity = entity;

		return {
			index: empty,
			generation: slot.generation,
		};
	}
	else {
		// there are no empty slots

		// create a new one
		const slot: Slot = {
			entity: entity,
			generation: 0,
		};

		// add slot
		state.entities.push(slot);

		return {
			index: state.entities.length - 1,
			generation: slot.generation,
		};
	}
};

const entity_remove = (state: State, index: Index) => {
	if (state.entities[index.index].entity !== null) {
		// note that we don't have to do anything with generation here
		state.entities[index.index].entity = null;
		state.empty.push(index);
	}
};

now that we are managing indexes like this, we need to provide a safe api for accessing entities:

const entity_get = (state: State, index: Index): Entity | null => {
	const slot = state.entities[index.index];

	if (slot.generation !== index.generation) {
		return null;
	}

	return slot.entity;
};

delegation

games are uniquely “object-like”, in that it’s often easy to see how one can segment the behaviour of one game object into a single type. this isn’t always the case however, and some situations may make it difficult to reason about what behaviour should go where.

one architectural idea could be to separate behavioural concerns even further; maybe we can remove tick() from Entity.

going back to this simple example:

type Entity = {
	tick(state: State): void;
};

type State = {
	entities: Entity[];
};

const update = (state: State) => {
	for (let i = 0; i < state.entities.length; i++) {
		state.entities[i].tick(this);
	}
};

here is a simple idea:

type Entity = {};

// new:
type System = {
	tick(state: State): void;
};

type State = {
	entities: Entity[];
	// new:
	systems: System[];
};

const update = (state: State) => {
	// now we update systems
	for (let i = 0; i < state.systems.length; i++) {
		state.systems[i].tick(this);
	}
};

Entitys can now simply be data, and a System can access the Entitys it needs to perform the same thing an Entity would have done.

where our previous implementation might have looked like this:

type Player = Entity & {
	x: number;
	y: number;
};

const create_player = (): Player => {
	return {
		x: 0,
		y: 0,
		tick(state) {
			this.x += 1;
		},
	};
};

this idea would look like this:

// `Entity` is empty, but whatever
type Player = Entity & {
	x: number;
	y: number;
};

const create_player = (): Player => {
	return {
		x: 0,
		y: 0,
	};
};

const create_player_system = (): System => {
	return {
		tick(state) {
			// as previously discussed, letting this access entities like this is a bad idea
			for (let i = 0; i < state.entities.length; i++) {
				// the subset of TypeScript this article uses doesn't let us prove if an entity is of any given type.
				// in actual TypeScript, one might imagine using `instanceof` if `Player` was a class.
				// imagine there is something in this condition proving the entity is a `Player`.
				if (/* condition */) {
					const self = state.entities[i];
					self.x += 1;
				}
			}
		},
	};
};

this is, admittedly, a bit more boilerplate. however, consider the flexibility. one could imagine implementing a system that adds rain particles given some specific conditions that’d be awkard to write from an entity, or a system that cleans up entities too far from the camera. this segmentation allows you to avoid having to worry about the implications of these kinds of things being entities. what if a rogue entity accidentally deleted a “don’t destroy the universe” entity? that could just be a system.

rust

this article makes no mention of Rust, as Rust does not allow &mut to alias, which makes the idea of an updatable list of entities impossible.

changelog

  • (26-01-13) initial release