alecmce

reflections on interactive software engineering and architecture

© 2014 Alec McEachran

My name is Alec McEachran. I am an interactive software engineer at YouTube, working in a team of talented interactive engineers building YouTube for TV, deployed across multiple hardware devices to millions of users. More about me.

I am currently rebuilding this website in Jekyll. If you find anything broken, please contact me via twitter.

How Does An Entity System Work? 26 July 2013

In a previous article I attempted to make a case for using an Entity System as an architecture for game engineering. In this second article, I explain the core mechanism that makes an Entity System tick, and broadly how it is implemented.

Games in which the state of objects are in constant flux - arcade games - are very different beasts to other kinds of software application. Most of the time, an application has a stable state, and responds to external input by updating the state, and then surfacing that change to users. Arcade games by contrast demand change at regular intervals. The simple expression of this is that at the heart of every arcade game is a ‘main game loop’, which is fundamentally a list of state-changes that happen with or without external input, culminating in the surfacing of those changes to users by re-rendering the screen.

An Entity System manages that loop for you by offering a simple interface for all the algorithms that update the game: the System, and a mechanism for pulling into those algorithms all the data that needs to be updated, the Collection.

Entities, Components and Systems

An Entity System is an architecture for developing games that maintains a strong separation between the data that describe the game’s state, and the algorithms that express the game’s behaviour.

Entities are the atoms of an Entity System. An entity is a stateful, independent thing that persists over a period of time during a game. In an Entity System, an entity begins life as a stateless container and is populated with components, which ascribe state to the entity.

Systems contain the algorithms that read, manipulate and write the entities’ states. Commonly, systems iterate once per-frame, and iterate over a collection of entities (although several edge-case scenarios exist which complicate this simple structure).

Defining Collections

Collections are subsets of entities defined in terms of their components. A collection is defined as an array of necessary components: an entity that contains all the necessary components is a member of the collection; an entity that does not have one necessary component is not a member.

The collection is the primary mechanism that bonds together the entities, components, and systems. Most systems depend on and iterate over one collection per frame.

Imagine a simple game in which some entities with a Position are in motion defined by a Velocity. This imaginary MovementSystem will iterate over all and only those entities that have the two components Position and Velocity.

In Dust the MovementSystem would be defined like this:

systems
  .map(MovementSystem)
  .toCollection([Position, Velocity]);

Systems are executed in the order that they are mapped, though they may also be weighted, so that higher-weighted systems precede lower-weighted systems. In general, the iterate method of each system is called each frame.

The system itself may then resemble something like this:

class MovementSystem
{
  @inject public var collection:Collection;
  public function iterate(deltaTime:Float)
  {
    for (entity in collection)
    {
      var position:Position = entity.get(Position);
      var velocity:Velocity = entity.get(Velocity);
      position.x += velocity.dx * deltaTime;
      position.y += velocity.dy * deltaTime;
    }
  }
}

The system relies on the collection having only those entities that have both Position and Velocity components. If such an entity has the Velocity component removed, then the next time the main game loop runs, it will not be a member of the MovementSystem’s collection.

Maintaining Collections

Importantly, there are usually many systems that use any given component. A Position may be written in a MovementSystem but will be read in lots of other systems. The diagram below shows the structure of an imaginary arcade game. Each color represents a collection for the corresponding system, defined by the corresponding components.

systems

My preferred way to maintain which entity is a member of which collection is to assign to each component an integer, and then maintain for each Entity and each Collection a Bitfield that describes their structure.

Consider the following diagram, which reflects the structure of an entity with various components added. As components are added, the corresponding bits are set, and as components are removed they are removed, maintaining a bitfield that can be described as an integer (for applications with more components than the biggest int has bits (commonly 32), a more complicated bitfield has to be defined as an array of integers):

entity

Collections are similarly defined as a bitfield corresponding to their necessary components. In this way, whether an entity is a member of collection or not is reduced to a simple bitwise calculation (~entityBits & collectionBits) == 0:

collection_satisfaction

Membership of a collection is not checked every iteration. Generally, entities’ structure remain fairly stable so when a component is added or removed the change is cached, and then at the start of the iteration loop collection membership is updated. In Dust, this process is itself defined in a system, the UpdateCollectionsSystem.

Criticisms

A common criticism of this approach is that it is wasteful. If an entity’s velocity is zero, why update the position; if it doesn’t move, why redraw it? At first look, it appears that this approach to architecture will lead to an extremely slow, expensive application. The response to this is in two parts: we approach these problems scientifically (because we can), and when the criticism is true, we fix it.

The structure of an Entity System lends itself to measurement. If all algorithms in your main-game loop are wrapped into a unified interface and called from a centralized place, then it is relatively simple to measure how much time each of them takes. Each system can be wrapped in a mechanism that records the amount of time a system takes to run. As needed, rolling or total means and distributions can be calculated and surfaced and analyzed.

The simplicity of measurement leads to a the approach of writing systems in the simplest possible way to achieve functionality, and then moving on. If later on, performance becomes a concern your metrics will identify the main problems for you. Premature optimization is a waste and is easily worked around.

When a problem is identified, there are many options for remedying it. If an AI loop that makes decisions based on surrounding objects is slowing down the application, it may be enough to adjust how often it runs from once-per-frame to once-per-second, or slower. If the renderer is causing headaches, then the solution becomes more complex. Moving from a full-blitter to a dirty-blitter on a CPU, or more ensuring batched draw calls to the GPU are difficult problems. In these sorts of cases, I have found the problematic system can be refactored to produce manipulate a data structure that is then passed through to a separate, architecturally-agnostic module specific to the high-cost task.

Of course, if for a particular arcade game many or most systems are merely placeholders or input aggregators for other modules, then there is a strong case that an Entity System architecture is not appropriate for that game. To that application’s developer: Good luck! It must be really something; please let me know what architecture does work for you!

Conclusions

The Entity System architecture is an opinionated architecture; it wants you to code in a particular way. Instead of creating classes for your game entities and encapsulating functionality, it expects you to treat all entities in the game as fundamentally the same kind of thing: the Entity, to which stateful Components are added.

The architecture’s utility then comes from how it allows the definition and management of Collections that ensure systems only iterate over entities appropriate to them. A simple, efficient mechanism for this is to express the configuration of an Entity and the definition of a Collection through bitfields, which can then be manipulated quickly to establish collection membership.

In an up-coming article I will demonstrate how to build a simple arcade game with my current Haxe Entity System library, Dust. Dust will remain as an early alpha until I release my first dust-based game (in production), after which I will tighten up the API and release it on haxelib.

blog comments powered by Disqus