6 Jul 2013

Entity-Component-System Revisited

This old blog post about the Nebula3 Application Layer is the 3rd-popular-post on my blog, very likely because it was linked from Stack Overflow. I always wanted to write a followup to this post, because if I would design such a system again, it would look quite differently today.

First a quick recap of the original system:

  • the original system consists of the following classes:
    • Entity: a container for Properties and Attributes, can receive Messages which are distributed to its Properties
    • Property: attached to an Entity, implements some part of the entities "game logic", receives and processes messages
    • Message: a small object which is sent to an Entity and distributed to Properties which may handle them
    • Attribute: key/value pairs attached to entities
    • Manager: singletons which implement global game logic
    • the only pre-defined Manager is the EntityManager which is a container for Entities, and allows to query for entities
    • Entities and Properties have several per-frame callbacks and are called back by the EntityManager
  • the motivation behind this system:
    • to have a simple, extensible high-level framework for implementing game-play logic
    • fix extension-through-inheritance problems through composition
  • and the problems of the original system:
    • poor spatial locality: Entities, Properties and Messages are isolated heap objects and can be spread all over the address space in the worst case
    • high cost for creation and destruction: all objects are dynamically allocated, this is especially a problem for Messages, there may be thousands of Messages created and destroyed per frame
    • high cost for settings/getting Attributes: setting or getting an attribute value involves a O(log2 n) lookup
    • high overhead for on-frame callbacks: the EntityManager calls several callbacks every frame on each entity, with many entities the call-overhead is non-trivial
    • reliance on virtual methods: almost all public methods in properties are virtual, because the message handler and callback methods are implemented in a Property base class, with specialised properties as subclasses

In the old single-player Drakensang games we had up to two-thousand game entities in some bigger maps, and we ran into real performance problems because the entity system is so heavy-weight.

So here's how I would implement a similar system today, keep in mind that this is just a "Gedankenexperiment", and I will make up some stuff while I type (but most of it has been lingering in the back of my head for quite a while now).

The main goals are to improve performance by making the system less dynamic, reduce memory fragmentation and reduce message-passing and object creation overhead.

Here we go:

1. Move all the interesting code into separate subsystems

In the original entity system, Managers and Properties would often implement actual game logic, and could become big, complicated and unwieldy.

The new entity system would only be minimal glue code between (ideally autonomous) subsystems, each with a Facade singleton as its main public interface. Such subsystems could be: rendering, AI, physics, audio, and also anything else what makes up the game. The last point is important: Even when already using such autonomous subsystems for low-level stuff like rendering or audio it is tempting to write the actual game logic "along the way" inside Properties without separating it into additional "game logic subsystems", which is guaranteed to soon end in an unmaintainable mess.

Ideally, each of the autonomous subsystems can live (and be tested) on its own, and will not interact with other subsystems (the physics world must not know about the rendering world or the audio world and so on).

One of the main jobs of the entity-component-system is to control and coordinate the data flow between those autonomous subsystems, it glues the subsystems together (e.g. getting the desired motion from the AI/navigation system into the physics system, and getting position updates from the physics system into the rendering system).

The other job is to provide different types of game objects (for instance different unit types in a strategy games) by combining small, reusable Component objects which implement different aspects/behaviours of the game logic.

The important thing to keep in mind is that all the classes of the new entity system will only provide a slim layer of glue between subsystem which contain all the meaty stuff.

What's in the new entity system

Properties will now be called Components, but their role will be the same. Managers and Attributes will go away (reasons are detailed below). Entities and Messages will keep their names and roles.

Fixing the Spatial Locality and Cost of Creation

Entities and Components would be created from pre-allocated object pools. Live Entities and Components would ideally be located next to each other without big memory holes inbetween. As public handle to an Entity I would probably use an EntityID instead of a (smart) pointer, the EntityID would be a 32-bit integer, some bits used as index into the entity pool, and some bits as a unique wrap-around-counter to prevent that an old Id points to a recycled object in the pool.

Entities and Components

An Entity would be a template class which must be partly implemented by the game programmer tailored to his project. The max number of Components the Entity can hold is a template parameter. There's a private C array of raw pointers to Components contained inside the Entity class, and programmer-provided template-methods to gain safe access to those Component objects.

An example: let's say the components-access template method would be called Component(), then invoking a method "SetTransform()" on a component "Location" would look like this:

entity->Component<Location>()->SetTransform(m);

Hmm, this looks mighty ugly though... The advantage is that the Component<> method will resolve to a simple inlined pointer indirection, which is as cheap as it gets. But I will have to think of some nicer looking code...

Attributes

Attributes will very likely go away completely because the cost for setting/getting is too high (this involved a binary search). Instead entity state will be exposed through simple inline getter methods in Component classes. There are not setter methods, because direct, unchecked manipulation of internal entity state by an "outsider" would be too dangerous. Manipulating an entity is exclusively done by sending messages to the entity.

There must still be a more dynamic, generalised way to initialise and manipulate an entity (this was a nice side-effect of the general attribute-system), for instance to implement persistence or communicate with remote applications (like a level editor). For this, some general serialisation mechanism to and from a simple binary stream must be implemented.

The Entity Registry

This would be a singleton used as factory and container of entities (basically the facade of the entity system). It would allow creation of entities, resolve an EntityID into a pointer, probably lookup entities by name (if having human-readable entity names makes sense at all), and sending messages to entities. This would be similar to the old EntityManager, but it would not call any per-frame methods on entities (it would be desirable if the new entity-system wouldn't any type of per-frame-tick at all).

Components and Messages

Sending a message to an entity should not involve creating a message object, instead a message is just a simple, short-lived stream of plain-old-data bytes in some hidden memory buffer. There will be a unique message type identifier, which is a simple 32-bit integer value (or maybe an enum) at the front of the byte stream.

Messages are processed by Component objects, which can subscribe to specific message types at the central EntityRegistry by associating a message type with a handler method:

entityRegistry->Subscribe(msgType, componentType, methodPtr);

A message is sent to one or more entities through the central EntityRegistry by calling one of several "PushMsg" template methods which accept a variable number of arguments. Each combination of arg types will resolve to a template specialisation under the hood. The advantage is again, that none of this involves expensive "dynamic" code, each specific message signature will resolve to a piece of code which is very likely inlined and just consists of writing values to memory:

entityRegistry->PushMsg(entityId, msgType, arg0, ...);

This will write the args to an internal memory area (with proper alignment), and and call the handler method of subscribers, which will be provided with some sort of pointer to the start of the arguments, read/decode the arguments and perform some action with them. The disadvantage here is that there's no type-safety for the message arguments. If the caller and handlers don't agree about the order and types of arguments bad things will happen at run time, so it might still be better to use simple message classes instead of multiple typed arguments:

MyMsg msg(x, y, z);
entityRegistry->PushMsg(entityId, msg);

This would have the overhead of an extra object created on the stack (still better then on the heap), and would involve defining dozens or hundreds of message classes which would only consist of setters and getters, this should be a job for a code generator (we have something similar already called NIDL files, which are used to generate C++ message classes from a simple XML description). The advantage is type-safety and automatic agreement between sender and handler about the message arguments, plus the message class constructor can setup default argument values.

The default PushMsg() method will probably call the subscribers immediately. It might be desirable to also have deferred message handling, where the sender defines a time in the future when the message should be handled. It might also be possible to use this mechanism to send messages between remote objects across threads, processes and physical machines, but this might go a bit too far.

What about the Managers?

Managers don't really have a place in the new entity-system. Their role is taken over by the Facade singletons of the autonomous subsystems.

Conclusion

I think the original ideas behind the Nebula3 Application Layer as a flexible Entity-Component-System still make a lot of sense for a high level game framework, but today I look at the original implementation as too "heavy-weight" both in design and implementation. If I were to rewrite the system (and I'm tempted, but other stuff has higher priority) I would start as described here. What the end-result would look like is on another page, I tend to restart such systems from scratch several times if the code "doesn't look right" :)

Written with StackEdit.