Happy New Year, everyone.
So far, almost all of the work on hikari has been focused on rendering. In order to continue working on my terrain project, I need to flesh out more of the underlying engine systems. (To be perfectly clear: creating the impetus to work on these systems is part of why I choose this project to work on.) As a starting point, I want to set up an Entity Component System architecture for managing the simulation.
Why? Well, let’s look at what I have right now:
State of the World
The simulation state of the world is unceremoniously dumped in the World struct, which contains lists of meshes, particle systems, and other persistent data (i.e., sun direction.) Also worth noting, several important things are *missing* from this structure — the camera setup, for instance. This is largely an artifact of being hacked together with very little care while testing the renderer itself.
During rendering, the Renderer gathers a list of meshes by calling World::GetRenderMeshes(), which in turn does a lot of (ultimately unnecessary) work to splice together a list of RenderMesh structs from various sources. Terrain meshes and meshes loaded from OBJ files are stored by their various systems. This is less of a performance problem than it may seem (it only happens once a frame), but it’s still silly and ugly and bug prone.
Furthermore, there’s very little structure to the world state at the moment. Each RenderMesh contains a 4×4 world_from_local transform matrix and that is the only transform information known for any mesh. This works, but is less than ideal.
Entity Component System
My proposed solution to this problem is using an Entity Component System architecture to manage all of the simulation state. ECS is a pattern where each Entity in the world is composed of a collection of Components, each of which is processed by some System.
This is the point where most explanations of ECS seem to end. But I’ve explained the concept, not the implementation, and that’s important here. In a standard object-oriented model, you might implement ECS by having each entity store a list of references to components, that live in lists managed by the component’s system. This is certainly possible — both Invaders! and a second (abandoned) project on that engine used this method for entities. However, this led to nasty macros, code generation tools, and generally being a pain to work with. (A dynamic array *per entity*, eek!)
So. I’m not going to do that this time.
A key realization is that we basically never need a list of all components belonging to an entity (at runtime, at least.) So why store it? Systems which need to interact with each other can do so because they have the same entity ID. Without that list of components, the Entity is just a unique identifier, a glorified integer. Or a foreign key, if you’re familiar with relational databases. Because that’s all an ECS is: a hyper-specialized relational database.
Of course, there are some potential problems introduced here. For example, if an entity doesn’t know all it’s components, how can it destroy all of them when the entity is destroyed? Well, it can’t. But we can solve this problem on a per-system basis — query the entity list to see if a particular component’s owner is still alive, for example. Or, set up a way to register callbacks on entity destruction, for systems where the live check is too much overhead. For components that are cheap to update, maybe we don’t even care.
Okay, enough theory, let’s talk about something concrete. I’m borrowing a fair bit of the structure of my implementation from Niklas Gray’s blog series about the entity system in Bitsquid / Stingray.
An Entity is actually two numbers that together form a unique ID — index and generation. I use 32-bit and 16-bit integers for these. The index is unique among all *currently live* entities. The generation indicates how many times that index has been used. If I destroy an entity, its index is open for reuse, but the next entity created with that index will have a different generation.
The generation value is also stored in a list owned by the EntityManager. This list is indexed by the entity index. A given Entity value is valid if and only if its generation is equal to the generation value stored in the EntityManager at that index. This is not perfect — there are a finite number of bits in the generation value and it will eventually roll over and repeat. However, by increasing the number of bits, we can ensure this is *highly unlikely* in practice.
The EntityManager has three main operations: creating entities, destroying entities, and checking whether an entity is alive. Of these, the liveness check is by far the most common operation (any component that wants to ensure its owner is alive needs to call this!) In order for the IsAlive() call to be both fast and thread-safe, the generation lookup table can never be reallocated.
Easy enough, I’ll preallocate it. I need one slot for each possible (32-bit) entity index and each value is 16 bits, which gives us an array size of… 8 gigabytes.
Believe it or not this is fine. Because I’m going to cheat.
The important thing is that the address of the lookup table never changes, and that it can grow — without moving — to support however many entities end up being used. Instead of fully allocating the full size, we can instead use OS-specific calls to reserve that much *address space*. While the typical PC has somewhere between 2-16GB of physical memory, the address space of a 64-bit process is *enormous*. 8GB of address space is nothing. As more memory is needed, we can simply commit more pages in that range. And should we ever run on a PC with terabytes of RAM, there’s no artificial limitation keeping us from using all 4-billion or so entities.
No real code listings here, as most of it is uninteresting. Next time, we’ll look at some actual component systems, which are where the real benefits show up.