Engine Internals: Managing a Game World
Every game needs a way to manage the world you play in. In our case it’s a 3D world with lots of stuff in it. You have bullets whizzing by, explosions everywhere and armies marching on their path of glory. Our world needs to be drawn beautifully and fast, and the article you are now reading is about how we built the system that forms the framework to make all of this possible.
Data-Oriented Design
To understand the architecture of our scene management system you need to have a basic understanding of a programming paradigm called Data-Oriented Design. The core principle behind DOD is the fact that everything is regarded as a transformation of data from one form to another. In essence, everything is a data problem and the focus is on designing the data that represents the world state and the processes that change it.
The focus of Data-Oriented Design is on implementation as opposed to representing real world concepts in code. Instead of implementing abstractions such as a “cat” we focus on what makes up the cat: what is the data that defines the properties of the cat.
In practical terms, using the cat as an example, we think of the cat as an entity that is the sum of its parts. The cat, for instance, might have four legs, a fur coat and a brain. All of these properties are interpreted as separate components but the end result of the whole system is the cat itself.
Another important aspect of Data-Oriented Design is that program execution on actual real world hardware takes centre stage. No program is thought of being executed on a purely theoretical computing machine, as that is never the case. Instead, when designing our data and the processes operating on it, we consider the underlying architecture and its properties.
One such aspect is memory access speed. When Moore’s Law took hold of the computing industry and processing power shot through the roof, memory access speed, however, was left behind. A major reason for this is that memory takes up a lot of space and needs to be stored at a distance from the CPU. And distance equals latency. This property makes memory layouts incredibly important, as they dictate how memory is accessed and how well the available processor optimisations can be utilised. It’s worth noting that there are some experimental systems in development, which place memory closer to where it’s used, thus effectively reducing the issue of memory fetch latency.
For a comprehensive study of Data-Oriented Design, I encourage you to take a look this web book written by Richard Fabian.
Components and Entities
Our scene management system is based on components, as in the cat approach described above. Each component is at its core a data structure that defines certain properties. Components are linked together through entities. Entities themselves are mostly convenience constructs. They could be replaced by a single ID, but we chose to build some logic into them to optimise some scene handling tasks.
Each component has a single system associated with them. These systems are autonomous in that they manage all the resources allocated for the components that they manage. Their only link to the entity management system is a structure of function pointers that define operations for creating component instances as well as rendering and updating them.
A component system implements a number of processes operating on the component instances. These include updating all the components and rendering them. The component system also implements the interface for finding individual components based on the entity pointer or the ID of the component.
Entities are created from templates that define the set of components to create and link to the entity. The individual component templates contain references to resources such as materials and meshes. These references are resolved when the template is loaded, which turns the creation of individual component instance into pretty much a memory copy. This was a design choice that was initially made because the system was first used for effects, which needed to be created really fast and would have relatively short lifespans.
Divide and Conquer
Part of the power of entity component systems comes from the separation of responsibility. This makes extending the system as easy as creating a new component system. Changing an existing component also doesn’t affect other component systems as long as the interface doesn’t change.
The separation into autonomous units of implementation naturally also results in opportunities for parallel working. When systems are more loosely connected it’s less likely that changes in one system will conflict with work happening in another system.
Component systems are always updated based on their priority. Instead of updating all components of a single entity at a time we update all the components of a single system in one go. This allows us to define a static execution order for each of the processes making it much easier to handle dependencies between different systems.
Optimised for Data Access
As was already mentioned above, Data-Oriented Design recognises that all applications run on real world hardware. This is highlighted in the ability of each component system to fully control its memory allocation and data layouts. The only visible aspect of the component data layout through the component system interface is a single opaque pointer. As a matter of fact, it doesn’t even have to be a pointer and could, for instance, just be an ID that is managed by the component system.
As you might already be aware of, memory access speeds are driven by cache efficiency. This is the concept of how well we are able to utilise the processor’s hierarchical caches to limit the times that a round trip to actual off-chip storage (RAM, disk etc.) needs to be made. Caches are updated in bursts with a typical cache line length being around 64 bytes. This means that 64 bytes will be updated regardless of whether you need only a single byte or 64. This, naturally, should explain why it’s important to have information that is used together close to each other.
The benefit of the component approach is that each component can define the layout for its data. Take a look at the following code listing for an example of how data could be laid out for more optimised access.
As you can see, there are multiple use cases, each requiring access to different data. For instance, we don’t need to access the IDs or entity pointers of the transform to update the world transform matrices. Note that in the above example, the index into each of the arrays defines the identity of the component instance.
Let’s compare the optimised data layout to the above unoptimised one. Say we wanted to find a single transform based on its ID. To do this we would have to loop through all the instances of the monolithic Transform structure reading only a single field. But because we are always reading full cache lines of data we might be reading in parts of the world matrix and potentially the entity pointer (depending on alignment). This would in turn mean that for checking just the ID we would likely be forced to do N fetches into the main RAM (or slower caches) just to find the correct ID.
If we were to use the more optimised layouts and the array of IDs, we would just be iterating over a vector of 32-bit unsigned integers laid out consecutively in memory. Since you can have 16 of these in a single cache line that’s 64 bytes wide, we could check 16 IDs with a single read from the main RAM (or slower caches).
Again, these kind of optimisations are possible because the component system is fully responsible for all the resource allocations and the memory layouts it uses.
Component System Examples
Finally, I wanted to give some examples of components that we have built:
- The model component defines a collection of meshes to render and the materials to render them with.
- The camera component is responsible for orchestrating the scene rendering. It hooks into the engine entity draw call interface and makes sure all the models, for instance, are drawn using the correct camera configuration.
- The animation component is responsible for playing a single animation and handles blending between different animation clips. There is also an animation controller component that is responsible for managing more complex animation transition graphs, which in turn command the individual animation components.
- The transform component discussed above is responsible for defining a position and orientation in the scene. Different components are linked to this component to define their spatial information.
- The particles component manages a single particle emitter. This allows us to add particle emitters to any objects in the scene. With the help of transform and animation components we can also drive the emitters with bone animation, seamlessly blending them into character animation.
The above examples are all from the engine and rendering side. We don’t use the engine entity system for gameplay code, because it doesn’t guarantee determinism. This is actually an interesting discussing in itself that I will reserve a whole blog post for.
Summary
The entity component system approach is a great way to split functionality into autonomous systems that are easy to manage and can also be used as units of work on large projects. They allow us to optimise our memory usage and access patterns so we can get the most out of the underlying platforms. Entity component systems are also a good example of Data-Oriented Design, which focuses on architecting software that runs well on real world hardware.
