Making ECS with metaprogramming

Some programmers remember when OOP firs made its appearance. From what I know, it started with C++(at least that’s the famous one). The “innovative” way of viewing data. It was kind of that first thing that guided us, gave us direction on how to structure our software, or at least it should have.

Object oriented Programing

Let’s be honest here, whole OOP is just a heavy and slow chunk of garbage (I em talking to you Java) that for some reason is hard to get rid of. We live in the world full of objects and associations, so I can get why we steered this way, though I consider it very foolish to bring our real-life rules to software architecture. Don’t get me wrong, even I was once amazed by “elegance” of OOP (that was like two months after I started learning how to code). But if you actually try to build some object hierarch, big and complex, you will run into a problem and that is how to actually structure this mess. Cases of creating set of gigantic objects that have hundreds of properties, to account for each case and usage, aren’t that unusual. Sometimes you end up inheriting from an object but not using all its functionality, or even worse copy-pasting some logic. When it comes to it, I always go by the rule Newer Repeat Your Self.

Different view

So, what do we need to do to overcome OOF? Nothing new actually, just simple unions/components/structs, different mindset, and little bit of metaprogramming sugar. While OOP deals with problems at runtime, we will do better preparation beforehand. Inheritance will get replaced by composition, array of objects with objects of arrays, pointers with IDs. Most and for most, relationship will be defined by behaviour and not necessary data layout. Yes, this is ECS and we will abuse it to its full extent.

Entity Component System

Let’s focus on a concept first and then move on to implementation in next part. So, what exactly makes your architecture ESC? To be honest, only useful thing that name of it tells, is that you have to use components. What’s more complicated is a way how you use them. We could build an entity from components, right? Embed them in a bigger structure and… NO. Entity is not an object, even though the term is so generic that it can be anything. In our ECS dialect it’s simply a pointer to components or more precisely ID. Unsigned integer is enough to make an entity, and the components are stored in their own storage. This storage must be able to take an ID and give us pointer to component. We do not store pointer for later but use it right away and drop it es soon as possible because storage can reallocate and address change, we only keep ID. The way we store components is imperative to how well our application performs. Think a little, what could be the best container for our purpose? Maybe… HashMap? That doesn’t sound too bad, you can use unique identifiers to access specific set of components, with optimal time. Well, that’s some of the tasks we need to accomplish, but not all of them.

The Problems

We need to iterate trough components. We also want to iterate simultaneously on multiple threads. Some components will get accessed a lot. What if we want to render some component, if order of components changes each time hashmap reallocates, as we have to rehash everything, can produce ugly visual bugs. Other problem is that map is almost newer fully populated, so iterating can bump into empty spaces and have to skip them. Biggest problem is that our O(1) is not guaranteed, sometimes we can get very unlucky and get complexity lot higher. Is there something better though?

Pooling and Binary search

Why there are two options in the title? Well because it depends on how populous the components are when deciding which one to use. How can binary search help us anyway? Let’s explain that first.

BS

Binary search is algorithm that can find element in collection with complexity of O(log2 n), assuming the collection is sorted. Biggest advantage is that this is guaranteed to be a maximal complexity. One thing that you might not realize at first glance, is that BS is also good for sorting. We can figure out where to insert, to preserve collection sorted, with the same complexity. So, we ended up with sorted array in which order of components is predictable. We do not need any rehashing each time we increase size of container. 100% memory efficiency and fast iteration. Only trade-off is complexity and even that depends.

Pooling

On the other hand, we have pooling. If each entity has a component, we can simply use indexes as ids and keep track of free ids. Free ids can be stored in array and popped by binary search as needed. There will be empty spaces, but only minimal amount that we don’t really have to care about as we can just use BS instead if it does not fit.

All together

Now that we have our storage figured out, we can sketch out our structure of ESC.

At the start we are declaring the name of our ECS struct and type of id. Then we have two sections for components stored in poolStorage and section for components stored in BS. Next there is a section called entities that contains something like an object definition (but they are not). It looks like some strange imaginary language made for building ECS, doesn’t it? Well, I will spoil it right away. We will create this Domain Specific Syntax with metaprogramming.

Disadvantage of using components is that you have to get pointers to all of them first, remove or insert them in a context of some entity. Metaprogramming will provide us with generated boiler plate to make this process as easy as if we were using Objects, yet more flexible and faster.

End

There is still lot to do and talk about. For now, I can say that we will use Nim Programming Language and its awesome macros to build a simple ECS. I recommend you to check out a Nim tutorial, to be ready for what we will do. Don’t worry Nim syntax is simple, it will be lot of fun.