A Three Parts Tutorial

This tutorial consists of three parts.
You are currently looking at part 2.
If you haven’t done so already, I can recommend you to check out part 1 first.
Otherwise you miss the intro, some very useful explanations and the creation of the player entity.
Don’t worry, part 2 won’t go anywhere.

If you’ve completed part 1 already, be prepared for more fun.
A lot of stuff you’ll learn in this one.

The World

Currently we can create entities, we defined some components and we sort of created a system.
However, our ECS is still not finished and usable.
This was the moment I somewhat got stuck on my game engine.
I couldn’t figure out a good way to bring this all together.

The problem that we are facing is how do we store the components, link them together with entities and then be able to use entities as well as components in our systems.
The solution should also be somewhat Data Oriented friendly, since that is the whole goal of my game engine.

It took me a lot of researching and looking at other people’s ECS implementations to realize I needed something what others often call The World.
In the Zel Game Engine I call it Level as I use it to create levels with.

Level System

The level system is what holds all the entities, components and systems. It’s like this bubble where everything exists in, but it can’t communicate with anything outside this bubble.
So when you create multiple levels, you can not actually make an enemy in level 1 communicate to another enemy in level 2 where the player is or vice versa.

However the way we are going to set up the level makes it so that you only pay for what you need.
Do you have a level with only UI stuff? Then you don’t have to run any other systems or store any other data than just the things you need for that UI.

So let’s first create a new header file called level.h.
Then we create a struct in which we will store all our data in.
We already have a way to store our entities, so let’s put the vector and queue, in which we store our entities, in the level struct.

#pragma once
#include <vector>
#include <queue>

struct level
{
	//entities
	std::vector<uint8_t> entities = { 0 };
	std::queue<uint32_t> empty_entities_spots;
};

We need to change our entities code to make it use this level struct.
Fortunately it’s very simple. 

Remove the includes for vector and queue and replace them with the include for level.h.
You can get rid of the entities and empty_entities_spots variables, as we store this data in level now.
Then in the create and destroy function we change the code to use the entities and empty_entities_spots variables in the level through its pointer.
Your entities.h should like the code below.

#pragma once
#include <stdint.h>
#include "level.h"

#define CAPACITY_ENTITIES 0xFFFFFF
#define GENERATION_BIT 24

#define GET_GENERATION(id) ((id & 0xFF000000) >> GENERATION_BIT)
#define GET_INDEX(id) (id & CAPACITY_ENTITIES)
#define CREATE_ID(generation, index) (generation << GENERATION_BIT) | index

// The upper 8 bits is the generation
// The lower 24 bits is the actual index in the array
typedef uint32_t entity_id;

entity_id create_entity(level* level)
{
	if (!level->empty_entities_spots.empty())
	{
		uint32_t empty_spot = level->empty_entities_spots.front();
		level->empty_entities_spots.pop();
		level->entities[empty_spot] += 1;
		entity_id new_entity = CREATE_ID(level->entities[empty_spot], empty_spot);
		return new_entity;
	}

	level->entities.push_back(1);
	return CREATE_ID(1, level->entities.size() - 1);
}

void destroy_entity(level* level, entity_id entity)
{
	uint32_t entity_index = GET_INDEX(entity);
	level->entities[entity_index] += 1;
	level->empty_entities_spots.push(entity_index);
}

It’s smart to test this out before we continue.
For that we need a way to create a level (and destroy it as well).
We could just do it like this:

level* test_level = new level;
delete test_level;

However, later on we might need to run some other code when creating or destroying a level.
So why not write some simple functions for that?
We could simple do this at the bottom of our level.h file.

level* level_create()
{
	level* new_level = new level;
	return new_level;
}

void level_destroy(level* level)
{
	delete level;
}

Then to really be able to test our new code, we need some small changes in our main.cpp.
We need to create our level and pass it into the entity functions.

#include <stdio.h>
#include "movement_system.h"
#include "entities.h"
#include "level.h"

void main()
{
	level* test_level = level_create();
	entity_id player_entity = create_entity(test_level);

	//We also hard code the delta time for now
	//We aim for 60FPS, so one frame should take
	//1/60th of a second
	float delta_time = 1.0f / 60.0f;

	while (1)
	{
		//movement_update(delta_time, &player);

		printf("Player's entity ID: %d\n", player_entity);
	}

	destroy_entity(test_level, player_entity);
	level_destroy(test_level);
}

When we run our code again we’ll see our lovely entity 16777217 again. Which indicates our new entity and level code works!

Storing Components

The next step is to look at our components and how we are going to store them.
In what way can we link components to entities?

The design I have is inspired from Austin Morlan’s simple ECS.
He uses arrays with a fixed size to store the components and then map the entities to the data.
We will do it in a similar way, but be prepared, as we will use some templates in this part.
I will do my best to explain every step.

We will create two classes.
These will hold the actual data of the components.
We divide this into two classes because the base is the same across all components.
While the other class inherits from this base class and implements type specific functions.
We also use the base class to be able to store the components in the level data.

I used classes here because I couldn’t come up with a better way to store the components.
The same can be said about using templates here. I just didn’t know of a better way to do it.

Let’s start with the base class.
Create a new header file called component_base.h.

#pragma once
#include "entities.h"

class ComponentBase
{
protected:
	generational_ptr component_to_entity[MAX_ENTITIES]; 
	generational_ptr entity_to_component[MAX_ENTITIES];
	uint32_t last_component = 0;
};

First we add arrays to be able to map the components to entities and vice versa.
As you can see we use generational_ptr here as well as MAX_ENTITIES.
We need to define these in entities.h.

#pragma once
#include <stdint.h>
#include "level.h"

#define MAX_ENTITIES 0xFFFF

#define CAPACITY_ENTITIES 0xFFFFFF
#define GENERATION_BIT 24

#define GET_GENERATION(id) ((id & 0xFF000000) >> GENERATION_BIT)
#define GET_INDEX(id) (id & CAPACITY_ENTITIES)
#define CREATE_ID(generation, index) (generation << GENERATION_BIT) | index

// The upper 8 bits is the generation
// The lower 24 bits is the actual index in the array
typedef uint32_t entity_id;

struct generational_ptr
{
	entity_id id;
	uint8_t generation;
};

We can determine how many entities may exist with MAX_ENTITIES.
I like it to be 0xFFFF or 65535, as that should be more than enough.

The generational_ptr is just a struct which will make our live easier.
So make sure the top of your entities.h file looks the same as above.

This is all the data that we need in the base class.
Now we can take a look at the functions.

public:
	virtual void destroy(entity_id entity) = 0;
	virtual void free() = 0;

	entity_id get_entity(uint32_t component);
	bool has_component(entity_id entity);

With the two arrays, which function as a kind of map, we can check if an entity has a component.
However there may be cases where you need to find out which entity is linked to a component.
That’s why we add the get_entity and has_component functions.
The base class can easily handle this.

We also need to destroy and sometimes free components.
However the base class has no idea what type the component is.
So the component class will handle this, therefore they are marked as virtual here.

Create a new source file called component_base.cpp.
We will declare the get_entity and has_component functions in there.

#include "component_base.h"

entity_id ComponentBase::get_entity(uint32_t component)
{
	uint32_t component_index = GET_INDEX(component);
	uint8_t component_generation = GET_GENERATION(component);
	generational_ptr entity_pointer = component_to_entity[component_index];
	if (entity_pointer.generation != component_generation)
	{
		return 0;
	}

	return entity_pointer.id;
}

First we look at get_entity.
It may seem more difficult than it actually is.

When calling get_entity we need to input the component handle.
This handle contains the index for the map as well as the generation.
So we first separate those two.

With the component index we can get the generational pointer to the entity.
Remember that this is not an actual pointer.
It just stores the ID of the entity assigned to the component as well as the generation of the associated component.

Therefore we need to make sure the generations match up.
If this is not the case, then the component is actually not assigned to anything anymore.
This could happen when an entity was not destroyed correctly or when trying to access a destroyed component.

If the generations do not match up we return a 0.
Which is the way to say something went wrong and there was no result.
Otherwise we can safely return the ID of the entity.

Let’s move on to the next one.

bool ComponentBase::has_component(entity_id entity)
{
	uint32_t entity_index = GET_INDEX(entity);
	uint8_t entity_generation = GET_GENERATION(entity);
	generational_ptr component_pointer = entity_to_component[entity_index];

	return component_pointer.generation == entity_generation;
}

We create the has_component function which takes an entity as parameter.
The function is pretty similar to the get_entity function.

Just like with get_entity we first extract the index and generation.
This time we take them from the entity.

Then we use the entity index to get the generational pointer to the component.
This should contain the generation of the entity.
If the generations are the same, we know this component is tied to the entity.
That means the entity indeed has the component and so the function returns true.

However if the generations are not the same, the entity doesn’t have that kind of component attached to it. Therefore the function returns false.

That’s it for the component base class really.
We can now take a look at the component class itself, which inherits from the base class.

Component Class

Storing the actual component data is done in the component class instead of the base class.
We do it this way, because we have many different types.
We will make the component class a templated class.
Which means the class will be targeted to the type you put in.
Then we can easily store and manage the different types of components.

You may still have no idea how a templated class works.
I think the best way to explain it is by using it, so sit tight.

Of course the first thing we do is create a new header file called component_class.h
We already know we need to declare two functions defined in the base class.
The destroy and the free functions. So let’s declare empty functions for those first.

#pragma once
#include "component_base.h"

template <typename T>
class Component : public ComponentBase
{
public:
	void destroy(entity_id entity)
	{
		// We run this when destroying a specific component or an entity
	}

	void free()
	{
		// We run this to clean up this class when the level gets destroyed
	}
};

The most important task of this class is to store all the component data of a specific component type.
That way we can have a Component class for all the transforms, a Component class for all the rigidbodies, etc.
We can simply store these components in a vector. So add the following line right below the free function.

private:
	std::vector<T> components = { {} };

You may now be wondering, what is that T doing there?

When creating a vector you need to specify which type you put inside the vector.
That is exactly what we are doing here.
However, we don’t know what types of components we will have yet.
That’s where templates come in.

At the top of the class you see template.
This is what makes this Component class a templated class.
When creating an instance of this class you need to specify the type you want to use, just like with a vector.
Then in the class itself T will represent that specific type.

So when we want to create a Component class to store our transforms, we can do the following.

Component<transform_t>* transform_components = new Component<transform_t>();

In the Component class itself T will then represent the transform_t type.
That means a vector will be created to store our transform components in.

If you still don’t understand templates completely, this explanation may help.

Creating Components

With that out of the way we can look at what else we need in our Component class.
Of course we need a way to create or add a component through this class.
As well as a way to retrieve a component that belongs to an entity.

We will first look at creating components.
Add the following just above the destroy function.

	T* create(entity_id entity, T component)
	{
		// Create/Add a component here
	}

As you can see we will also use templates for this function.
The function needs to know which entity the component must be attached to.
As well as the component itself.
So you first create the component and then use this function to add it to the vector of the class.

The important thing here is to properly register the entity and the component in the component_to_entity and entity_to_component arrays.
We can use the last_component variable in the base class for this.
Which always points to the next empty spot in the component_to_entity array.

	T* create(entity_id entity, T component)
	{
		if (last_component == MAX_ENTITIES - 1)
		{
			printf("Maximum amount reached, can't add any more components\n");
			return nullptr;
		}

		++last_component;

		uint32_t last_index = last_component;
		components.push_back(component);
		component_to_entity[last_index].id = entity;
		component_to_entity[last_index].generation += 1;
		uint32_t new_component_id = CREATE_ID(component_to_entity[last_index].generation, last_component);
	}

Of course we first check if we are allowed to create a component.
Then we simply add the component to the vector.
It’s index in the vector is already determined through the last_component value.

After that we can use the index to set the id to the entity’s ID and increase the generation by 1.
With that generation value and the component’s index we create the component’s ID.
That’s only half of what needs to happen.

T* create(entity_id entity, T component)
	{
		if (last_component == MAX_ENTITIES - 1)
		{
			printf("Maximum amount reached, can't add any more components\n");
			return nullptr;
		}

		++last_component;

		uint32_t last_index = last_component;
		components.push_back(component);
		component_to_entity[last_index].id = entity;
		component_to_entity[last_index].generation += 1;
		uint32_t new_component_id = CREATE_ID(component_to_entity[last_index].generation, last_component);

		uint32_t entity_index = GET_INDEX(entity);
		uint8_t entity_generation = GET_GENERATION(entity);
		entity_to_component[entity_index].id = new_component_id;
		entity_to_component[entity_index].generation = entity_generation;

		return &components[last_index];
	}

We need to link the component with its ID to the entity as well.
Therefore we grab the entity’s index and generation.
Then modify the entry in entity_to_component to point its id to the new component ID.
Of course we need to make sure the generation is the same as the entity’s.

Finally we can return a pointer to the newly created component.
It may look like much is happening, but it’s just adding the component to the vector and changing some values to associate the component to an entity ID.

Getting Components

Properly managing these values makes it rather easy to get a component associated to an entity though.

So let’s look at the get_component function which we can write below the create function.
It may look familiar as it is almost the same code as has_component in the base class.

	T* get_component(entity_id entity)
	{
		uint32_t entity_index = GET_INDEX(entity);
		uint8_t entity_generation = GET_GENERATION(entity);
		generational_ptr component_pointer = entity_to_component[entity_index];
		if (component_pointer.generation != entity_generation)
		{
			printf("[zel_component class] get component return nullptr | Entity: %d | Type: %s\n", entity, typeid(T).name());
			return nullptr;
		}

		uint32_t component_index = GET_INDEX(component_pointer.id);
		return &components[component_index];
	}

To get a component, we of course need the entity ID it’s associated to as parameter.
We will then grab the index and generation of that entity like usual.

Just like in has_component we can look at the generation in the generational pointer.
This generational pointer is obtained through the entity_to_component array.
We check if the two generations match.
If they don’t, then the entity does not have this kind of component attached to it.

However if the two generations do match, that means the component pointed to by the generational pointer is valid. So we can grab that component from the vector and return its pointer.

Destroying Components

When creating components, you should also destroy them.
However some components may need to do some extra stuff before getting destroyed.
For example, a material component may need to destroy a texture or shader first.

That’s why we need to add a function pointer, that will take care of this.
We make it so that the user defines this function when registering component types.

So just below our free function we can define this destroy_function.

void(*destroy_function)(T*);

We will use this pointer to call the function in our destroy.

void destroy(entity_id entity)
	{
		uint32_t entity_to_destroy_index = GET_INDEX(entity);
		generational_ptr component_pointer = entity_to_component[entity_to_destroy_index];
		if (component_pointer.generation != GET_GENERATION(entity))
		{
			printf("Generation not equal, component already destroyed.\n");
			return;
		}

		uint32_t component_to_destroy_index = GET_INDEX(component_pointer.id);

		destroy_function(&components[component_to_destroy_index]);
	}

Just like with some other code, we first check if the component is actually valid and associated to the entity.
After that we can grab the components index and call its destroy function.
This way we made sure there won’t be any memory leaks, assuming the destroy_function properly freed any memory.

void destroy(entity_id entity)
	{
		uint32_t entity_to_destroy_index = GET_INDEX(entity);
		generational_ptr component_pointer = entity_to_component[entity_to_destroy_index];
		if (component_pointer.generation != GET_GENERATION(entity))
		{
			printf("Generation not equal, component already destroyed.\n");
			return;
		}

		uint32_t component_to_destroy_index = GET_INDEX(component_pointer.id);

		destroy_function(&components[component_to_destroy_index]);

		if (component_to_destroy_index == last_component)
		{
			component_to_entity[component_to_destroy_index].id = 0;
			component_to_entity[component_to_destroy_index].generation += 1;
			entity_to_component[entity_to_destroy_index].id = 0;
			entity_to_component[entity_to_destroy_index].generation += 1;
			return;
		}

		// Fill in empty spot in array
		generational_ptr entity_pointer_to_swap = component_to_entity[last_component];
		components[component_to_destroy_index] = components[last_component];
		component_to_entity[component_to_destroy_index] = entity_pointer_to_swap;
		component_to_entity[last_component].generation += 1;

		entity_to_component[GET_INDEX(entity_pointer_to_swap.id)].id = component_pointer.id;
		entity_to_component[entity_to_destroy_index].generation += 1;
	}

The last thing we need to do is make sure the map is still correct.
If the component is the last one in the vector, then we can just modify that entry.
Otherwise we need to swap the components entry with the last one in the vector.
This is important, as we want tightly packed arrays to reduce cache misses.

We simply set the IDs to zero. This is more for ourselves when debugging.
You can then easily see a component has been destroyed.
The generation is increased so they will not match up with any component or entity anymore.

Freeing All Components

That leaves us with only one function left to implement.

When destroying a level you need to free up all the components that level has used.
That’s the mission of the free function.
Again using the destroy_function to make sure all the memory used by the components is freed properly.

	void free()
	{
		if (destroy_function == NULL)
		{
			components.clear();
			return;
		}

		uint32_t components_size = components.size();
		for (size_t i = 1; i < components_size; ++i)
		{
			destroy_function(&components[i]);
		}
		components.clear();
	}

If the destroy_function is not set and equals NULL we can simply clear the vector and that’s it.
However, if it is set, then we loop over all the components and run the destroy_function for it.
Afterwards clearing the vector as well.

Some Small Modifications

That concludes the Component and ComponentBase classes we need for our ECS implementation.

You can try to run the code again to see if you followed along correctly.
However, you probably see some errors pop up about some functions already being defined.

We need to put the functions declared in entities.h and level.h into source files.
First create a new source file called entities.cpp.
Then copy the create and destroy functions to it.

#include "entities.h"

entity_id create_entity(level* level)
{
	if (!level->empty_entities_spots.empty())
	{
		uint32_t empty_spot = level->empty_entities_spots.front();
		level->empty_entities_spots.pop();
		level->entities[empty_spot] += 1;
		entity_id new_entity = CREATE_ID(level->entities[empty_spot], empty_spot);
		return new_entity;
	}

	level->entities.push_back(1);
	return CREATE_ID(1, level->entities.size() - 1);
}

void destroy_entity(level* level, entity_id entity)
{
	uint32_t entity_index = GET_INDEX(entity);
	level->entities[entity_index] += 1;
	level->empty_entities_spots.push(entity_index);
}

Your new source file should look like above.
Don’t forget to include the header file.

We need to make sure the functions are still defined in the header file though.

#pragma once
#include <stdint.h>
#include "level.h"

#define MAX_ENTITIES 0xFFFF

#define CAPACITY_ENTITIES 0xFFFFFF
#define GENERATION_BIT 24

#define GET_GENERATION(id) ((id & 0xFF000000) >> GENERATION_BIT)
#define GET_INDEX(id) (id & CAPACITY_ENTITIES)
#define CREATE_ID(generation, index) (generation << GENERATION_BIT) | index

// The upper 8 bits is the generation
// The lower 24 bits is the actual index in the array
typedef uint32_t entity_id;

struct generational_ptr
{
	entity_id id;
	uint8_t generation;
};

entity_id create_entity(level* level);
void destroy_entity(level* level, entity_id entity);

That’s how your entities.h file should look like right now.

One down, one to go.
So do the same with the create and destroy functions in level.h.
Creating a new source file called level.cpp.

#include "level.h"

level* level_create()
{
	level* new_level = new level;
	return new_level;
}

void level_destroy(level* level)
{
	delete level;
}

Your new source file should look like that.

Now for the header file.

#pragma once
#include <vector>
#include <queue>

struct level
{
	//entities
	std::vector<uint8_t> entities = { 0 };
	std::queue<uint32_t> empty_entities_spots;

};

level* level_create();
void level_destroy(level* level);

That’s how your level.h file should look like.

When you now build the software you should have no errors.
If you did, make sure you didn’t miss a step along the way.
Look closely at the errors you get.
Otherwise leaving a comment may help.

End of Part 2

You just completed part 2.
Again you may want to take a little break.
Or even better, just come back tomorrow.
When you return, you can find part 3 over here.

Last modified: June 11, 2021

Comments

Write a Reply or Comment

Your email address will not be published.