Data Oriented Entity Component System Part 1: Our approach
This blog post will be about our research on an Entity Component System (ECS) and why we went for an ECS instead of the other solutions. We won’t go too indepth about what an ECS is as several good articles can be found in the reference section at the end of the blog and that’s why we thought it would not be worth the time investment to write another one.
We did some research in the past few weeks and settled on our approach of a multithreaded Data Oriented ECS. As our project currently is in pre-production stage of development we are almost sure that the approach that we are going take is going to change in the future as soon as we run into new issues which we had not foreseen. Those issues and how we solve them will be discussed in future blog posts.
Why an Entity Component System?
For our custom engine we need a way to define our game objects. There are several ways to do this but we went for an ECS as it fits all our requirements.
We do not know what our target game is going to be so we need something that can easily be tuned to fit our game later on.
- Easy to use
Designers need to be able to make games with the system so this rules out a hardcoded hierarchy that would require engineers to make change to allow for new game object types.
- Makes development easier
It should be simple to develop with as we will be iterating over this system a few times. If we then because of a change need to change other things as well we’re doing it wrong.
Another way of defining game objects would be using a hierarchy of inheritance but that is not flexible at all. It is however a very simple way of doing it and not so difficult to use for the designers. However that stops as soon as the designer wants a new type of game object. Then an engineer is required to change the hierarchy which could potentially be a lot of work.
Why Data oriented and multithreaded?
As this project is oriented around learning about engine design and all of us have once touched and written an ECS before we add some more challenges:
We are interested in this challenge as this is an opportunity for us to learn how to deal with multithreading as it is becoming more and more important in the game industry.
- Data Oriented Design
Ties in well with the multithreading and forces us to learn how to think about data which again is a learning opportunity.
Data Oriented Design
As mentioned above we want to take a shot at data oriented design, to learn how it works and how we could utilize it to create better software now and in the future.
Since data oriented design is widely discussed by people much more qualified to do so we’ll leave you with references to the material we found most useful instead of restating what they already said.
- Practical Examples in Data Oriented design by Niklas Frykholm
If you don’t have time to read all the references, or just need a quick refresher. By using data oriented design we aim to create modular code which is faster by being more cache friendly and easier to multithread. We plan to achieve this by optimizing access patterns, focusing on data layout and isolating transforms so they can be ran on many elements at once.
Our current approach
As for our engine, we decided to pursue a data oriented entity component system. In this we will focus on systems, our entities being reduced to simple IDs linking together components in multiple systems.
For our entities we choose to use simple IDs, this allows us to still find all components belonging to a specific entity. Without needing to keep a list of all entities and their components. Instead we can create mappings from entities to components within each of the systems. Enforcing the ownership the systems have over the components.
This also ties into how we structure our update code. Since we no longer have lists of components belonging to each entity we cannot perform our update by iterating over all entities and their respective components. Instead we iterate over each system, which in turn update all the components they own. This way of updating also adheres better to data oriented design and simplifies multithreading. Since we now group all similar logic to be done at once.
The next thing to consider is how to map entities to components. The main consideration here is that we want the systems to be free in how they order their data. This stops us from using pointers to the components directly and requires us to add a layer of indirection. While it is possible to use our entity mapping for this layer of indirection, this would mean that either we use a slow lookup for every access to a component. Or use a sparse array to store all the component references.
To overcome this issue we opted for using two layers of indirection, each of these indirections tuned to their specific use cases. The first is an mapping from entities to handle ids. This mapping allows us to make a dense handle array, reusing slots when possible. While this lookup is slow it is meant to be performed once, after which the handle id can be cached and used for the rest of the components lifetime.
The second mapping is from handle id to internal reference. Since we can guarantee that the internal reference slot will never move during the lifetime of the component this can be done with a simple lookup in an array. As a result we can now move around data in within the systems however we see fit, we just have to make sure we keep the internal reference updated in the handle mapping.
Now this is where we jump into unknown territory as all blogs that we encountered about ECS stop here. We need to synchronize our data in two ways. Multithreaded areas need to sync up after all threads are done with the data. Component systems need to sync up after each other.
The multithreading is an obvious one but still very difficult to achieve. We need to sync the threads that work away on the components after they are done with the data. Currently our approach will be similar to what is described in the multithreaded engine development talk of the Destiny engine: https://www.youtube.com/watch?v=v2Q_zHG3vqg
The component systems is a bit harder and we haven’t come to a decision on how to do this yet as we don’t know yet what the other areas of the engine that use these systems are expecting. An example of a system that needs to sync with other system is the transform component and the mesh rendering component. We need to match these component in an efficient way however we also might want to sort the meshes differently than that we sort the transform components.
That there is one of the issues that we still have to solve and it will be discussed in a future blog posts!