Game Programming

ECS Concepts - Part 2: Entities

by Cory on September 5, 2017 12:59 AM

Let’s get straight to the implementation details and the hugely retarded design decisions that I put into making my own entity class implementation. The nuts and bolts of an entity class boil down to having a container that stores many different component classes. This entity class should be able to have components both attached and accessed for reading and modification. How hard can that be, right? Well, it’s not if you want to make a really shitty one, but otherwise it’s a lot harder than it sounds. Or at least, it was hard for me. Cause I suck. See what I did there?

I’m pretty sure I was able to finish writing the entity class only because of a series of incredibly fortunate C++ related accidents. It started with me finding out about std::type_index. The type index stuff isn’t the most technically complex stuff in this post, but the implementation didn’t really start coming together until I found out about it. Type index lets you take the type of a class and use it as a key in associative STL containers. Then, after working for about a week or so and realized that I was still too stupid to finish writing the code and started reading more about template classes and functions, because I don’t know it seems like the sort of thing you resort to when everything else doesn’t work.

This is the story of that journey. It is a journey full of sitting around and thinking and lying in bed starting at the ceiling and more thinking and falling asleep without actually doing anything. It is a journey of me sitting in complete silence staring at my computer screen and then suddenly screaming “JESUS I’M RETARDED”. But I finally did it. And now you can too.

A Native Entity Implementation

Because I am a n00b my first shot at making an entity was to have a class that had an STL map of strings to component pointers. The entity class would be stored directly inside the map and the map would be searched whenever a specific component was needed.

// forward declaration (implementation left out of this example)
class Component;

class Entity {
public:
// stuff

Component* get(std::string id) {
if (this->components_.find(id) == this->components_.end()) {
return nullptr;
}

return this->components_[id];
}

void set(std::string id, Component* component) {
this->components_[id] = component;
}

private:
std::map<std::string, Component*> components_;
};

This is complete shit, don’t do this. There are a lot of problems with this mostly related to the way that entities are going to be used.

First of all, I use a string to identify component types. I thought I might want to store more than 1 of the same component type on a single entity. Also it seemed easy to do since I didn’t know any other way to identify different class types given just a pointer. This is terrible because I can use anything for a string and it doesn’t even have to correspond to what type of the component pointer really is. It would be a nightmare for people to use and/or debug this. Also I could do fucked up shit like make a GraphicsComponent class, provide it to my entity and supply a string id of “physics” if I wanted. Or maybe I could make a typo somewhere and then be unable to find a graphics component on the entity because it was stored as “grahpics”. Bleh.

The second thing that’s wrong with this is that it doesn’t give you the exact type of the component you ask for. If you look at the get() method, you’ll notice it returns a Component*. I quickly found that trying to use this implementation leads to a lot of dynamic casting or if statements for testing what kind of component I had. It takes a ton of boilerplate code just to access a component.

// assume I got a pre-built entity from somewhere
Component* c = entity.get(“graphics”);
GraphicsComponent* g = nullptr;

if (c != nullptr) {
g = dynamic_cast<GraphicsComponent>(c);
if (g != nullptr) {
// finally do stuff here...
}
}

This is super ugly, don’t you agree?

But wait, there’s more! Maybe you read up on some basic OOP design patterns and you were like holy fuck you idiot, you can use the visitor pattern to get the true data type of the component you want. Well that’s what I thought, don’t look at me like that. Here’s the thing. The visitor pattern is so close to being useful here, but it’s not the right tool for the job. (You’ll hear this a lot w.r.t. ECS stuff.) Remember how I said in the last update that I want to be able to casually create new components and have a ton of different kinds? The visitor pattern assumes that you already know all the different types of sub classes you will have and that you won’t change them very often. Unfortunately, this is a deal breaker here. We want to be able to add new components willy-nilly and not have to worry about updating random pieces of code in a bunch of different places. No good. It is usually impossible (or not allowed) for the end user to modify any preexisting code. The ideal implementation should allow you to define new components and just drop them into the framework with no other edits.

A side note on the visitor pattern: Polymorphism is an OOP concept that allows a programmer to supply a child class reference in place of a parent class reference. This lets you treat objects of different child types the same way, so long as the functionality required can be handled in the parent class. This is exactly what I took advantage of when I stored all the component pointers in the entity class. The visitor pattern lets you reverse this process using something called “double dispatch” (a great explanation is in the link above). The visitor lets you take a bunch of pointers to parent class instances and figure out what child class it is. Under normal circumstances where the class hierarchy doesn’t change very often this is a great tool.

Introduced in C++11: std::type_index

This stack overflow answer explains all the amazing things you can do with this feature:

https://stackoverflow.com/questions/20022546/why-use-stdtype-index-instead-of-stdtype-info

Google it if you must know more. I don’t remember what exactly I was doing when I found out about it, but I do remember it was late at night on like a Saturday and I was alone in my room. Just saying.

The entity class modified to incorporate type index looks like this:

#include <typeinfo> // for type_id()
#include <typeindex> // std::type_index

// forward declarations
class Component;
class GraphicsComponent : public Component;

class Entity {
public:
// stuff

template <typename ComponentType>
Component* get() {
std::type_index key(typeid(ComponentType));
if (this->components_.find(key) == this->components_.end()) {
return nullptr;
}

return this->components_[key];
}

template <typename ComponentType>
void set(ComponentType* component) {
std::type_index key(typeid(ComponentType));
this->components_[key] = component;
}

private:
// type_index replaces string
std::map<std::type_index, Component*> components_;
};

I had to change the get() and set() functions into template functions. Sorry. They are simple ones though. ComponentType is a type identifier, not a variable name. So, GraphicsComponent would be a valid value for ComponentType. Just do a mental text substitution of GraphicsComponent with ComponentType wherever it appears in the function. And this doesn’t just work for GraphicsComponent. The compiler will generate a separate function for any data type that you decide to shove in there (int, float, etc). Thus is the power of templates (a.k.a. generic programming). Also, don’t forget to make sure your compiler supports C++11 and has it enabled.

The new client usage is almost identical to the naive client code:

// assume I got a pre-built entity from somewhere
Component* c = entity.get<GraphicsComponent>();
GraphicsComponent* g = nullptr;

if (c != nullptr) {
g = dynamic_cast<GraphicsComponent>(c);
if (g != nullptr) {
// finally do stuff here...
}
}

Along with the template function modification, std::type_index resolves the first issue I had with the naive implementation. The get() and set() signatures have changed to have the id string removed. Now the component identification is transparent to the user because they don’t have to supply a string to specify which component they want. It is also safer because std::type_index guarantees that the keys will be unique for different class types and maps directly from the class type. Now the entity class is in total control of component storage.

If you examine the code closely, you’ll notice that this new code doesn’t let me add two components of the same type to an entity. I decided not to allow that for simplicity. I don’t think any of the professional ECS frameworks let you do either. If you need multiple instances of the same component types on a single entity, you’re better off splitting up that single entity into multiple entities. There doesn’t have to be a 1:1 correspondence between game objects and entities. For example you could have a huge boss that has a lot of different moving parts and you don’t have to make the entire boss a single entity. You can create a “boss root” entity that represents the entire boss and then have other entities owned by the root entity that represent parts of the boss, like having a “left arm” entity with a left arm graphic and stuff. At this high of a level, it’s all a matter of taste.

Also I want to point out that this ISN’T the horrible anti-pattern where you abuse RTTI and write a bunch of if statements and dynamic casts to figure out the type of an object and then do custom behavior depending on the result. Type index is basically just a hash that lets you input data types so you can index into a container. This is the best way to make sure class types are unique as map keys. I’m still constrained to storing component pointers though, so there’s still more to do.

Type Erasure

I am still storing and retrieving everything as component pointers which is a huge pain in the ass. Consider this: I already modified the get() and set() functions to be template functions, yet I’m returning the base component pointer. I can instead have it return ComponentType. Like this:

#include <typeinfo> // for type_id()
#include <typeindex> // std::type_index

class Entity {
public:
// stuff

template <typename ComponentType>
ComponentType* get() {
std::type_index key(typeid(ComponentType));
if (this->components_.find(key) == this->components_.end()) {
return nullptr;
}

return static_cast<ComponentType*>(this->components_[key]);
}

template <typename ComponentType>
void set(ComponentType* component) {
std::type_index key(typeid(ComponentType));
this->components_[key] = component;
}

private:
// type_index replaces string
std::map<std::type_index, Component*> components_;
};

So in the get() function, I changed the return type from Component* to the more specific ComponentType*. We can simply use a static cast to downcast it to ComponentType assuming that we modify the map only through set(). Note that I’m still storing the components in the map as component base class pointers.

This solves the last two problems with the naive implementation really nicely. The former of the two is solved because the get() function knows how to do the downcast now because we mapped the components using std::type_index when inserting into the map. And the latter problem is solved because with the template functions and std::type_index we can store ANY kind of object in the object map we want without having to code it in beforehand. This is actually too much power, so I’ll need to add some restrictions. More on this later.

The usage code is simplified to this:

// assume I got a pre-built entity from somewhere
GraphicsComponent* g = entity.get<GraphicsComponent>();
if (g != nullptr) {
// do your shit here FUCK YEAH
}

The <GraphicsComponent> part is optional in this example because the compiler can deduce the type of the return value. I like writing it out because it’s clearer and still looks nice.

I didn’t know it at the time, but this change I described is a variation on a technique that is called type erasure. My entity code is a very simple example. Type erasure comes up several times, especially in the messaging system. With a vengeance.

It’s hard to find a single sentence definition online so here goes nothing:

Type erasure is the act of separating type information from object instances and then later reconstituting the type information back into each instance (usually using template functions or classes) to retrieve the instance with its original type.

That’s my take on it anyway. Whatever. Who cares, am I right? Psh.

An Entity Implementation Using std::type_index and Templates

We’re almost there. I left something out. In the last section I ended up introducing an implicit contract regarding the components we can and can’t attach to the entity. The modified code requires that all components need to inherit from the component base class. I’m okay with this, but the user needs to be aware of this. I guess you just have to document somewhere that to make new components you need to inherit from Component, but that’s it! You don’t need to modify any other parts of the code so mission accomplished, biiiiitch.

We can do a little bit better though. Suppose you try and add a class to the entity that doesn’t inherit from Component? The compiler will complain about the static cast in the get() method. Shit.

But lo! Worry not! C++ also has features that let you create more complex template functions. To resolve this last problem, I can change the get() and set() methods to not accept anything that isn’t inherited from Component. “Holy shit, you can do that???”, you think. Yes, yes you can. cool

#include <typeinfo> // for type_id()
#include <typeindex> // std::type_index

class Entity {
public:
// stuff

template <
typename ComponentType,
typename std::enable_if<std::is_base_of<Component, ComponentType>::value>::type* = nullptr
>
ComponentType* get() {
std::type_index key(typeid(ComponentType));
if (this->components_.find(key) == this->components_.end()) {
return nullptr;
}

return static_cast<ComponentType*>(this->components_[key]);
}

template <
typename ComponentType,
typename std::enable_if<std::is_base_of<Component, ComponentType>::value>::type* = nullptr
>
void set(ComponentType* component) {
std::type_index key(typeid(ComponentType));
this->components_[key] = component;
}

private:
// type_index replaces string
std::map<std::type_index, Component*> components_;
};

In this final code, I added onto the template function header a second template parameter. This uses some standard library utilities that let you create boolean expressions at compile time to reason about class types. I use std::is_base_of to see if the ComponentType supplied is a child of Component and then use the ubiquitous std::enable_if to cause the template deduction to fail if this fact is not true. std::enable_if is a real doozy to wrap your head around. You might also want to look up “SFINAE” (substitution failure is not an error) if you don’t already know what that is.

Unfortunately if you supply an invalid ComponentType here the compiler will fail with an esoteric error message (I use gcc) but at least it fails.

Consider Using Factories to Create Components

Now the only problems I have left are making sure the person using the code (i.e. probably myself) doesn’t do anything fucking stupid. For instance, the only way we can screw up this setup now is if we take one component pointer and supply it to two or more different entities. It’ll work, but then you’ll either have memory leaks or double free problems later. Also depending how you use it, there could be unexpected behavior since the same exact component will be updated for both entities. I don’t think this is really anything I can eliminate via framework code, so I can only hope for the best.

However, there are things that you can do to mitigate it and encourage proper usage. First of all, you could use smart pointers instead of raw pointers. That’s enough to solve the memory issues in this case (at the cost of a little performance overhead). You could also use a factory to try and control the creation and lifetime of your components. To be honest, I don’t really know what I’m talking about when it comes to this stuff so I’ll just leave it out...

Further Optimizations (That I Did Not Do)

So basically an entity is just a container that holds components. A lot of professional game companies that need to optimize their games out the ass actually invert this structure. They store the individual components in separate lists, iterate through those lists when updating the game loop, and they don’t have entity lists at all.

Remember what I said at the very beginning?

In this context, an Entity is a... thing.

I lied. In some super optimized ultra-advanced professional frameworks, an entity isn’t even a thing. Some frameworks only have integer identifiers that stand in for entities. Components belong to an entity if they have its id. This reduces storage space overhead for having many entities, allowing you to have more entities in your game. And if you iterate through your component lists and program things cleverly (I don’t know the details), you can even avoid access times associated with reading components out of entities.

I didn’t do this because I think it reduces the intuitiveness of the framework and I don’t have a reason to super optimize it like this yet. We’re talking huge 3D games like Skyrim or GTA that probably do this, not my dinky 2D game. I’ll stick with entities as objects for now and see how far that takes me.

Github

So much for entities! That’s all the stuff I wanted to cover. I hope it was easy to follow and helpful. And if not, at least I can go back and read it in case I have a stroke or something and end up running around like Arnold Schwarzenegger in Total Recall.

I have the real code in my github repo. You can specifically look for these files:

/engine/ECS/Entity/Entity.h
/engine/ECS/Entity/Entity.cpp

There’s a lot of junk in there that I need to delete (from the naive implementation), so you’ll have to wade through that. And there’s an ObjectPool thingy encapsulating the components that I’ll explain later...

You can find examples where I use the new entity class in that repo too, which I left out of this post.

I’ll cover Component implementation details in the next post.



This Thought is part of Game Programming

Game programming general topic. I eventually hope to split this into separate ideas exclusively about specific games that I make.

back to the

top