Press "Enter" to skip to content

Entity Component System

Why did I decide to use it? Well, it is not because it is very popular, but because it actually solved a problem (not the most difficult, but still a problem)! Always look for a solution to the problem, not for what is currently the most used architecture design.

The problem was that through the development process. It just so happened that the entity structure in the game had the following members:

struct entity
{
	... some members...
	entity_id ID;
	path_id PathID;
	//NOTE(enev): Only relevant for entities that get simulated!
	u32 OccIndex;

	render_piece* Pieces;
	u8 RenderPiecesAdded;
	u8 MaxRenderPieces;

	collision_volume* CollisionVolumes;
	u8 CollisionVolumesAdded;
	u8 MaxCollisionVolumes;
        ... other members ...
};

It is pretty much save to say that it looks as a SOA (structure of arrays) design.

Now, however it is getting tricky, because you need to be able to get a variable size array from memory! MaxRenderPieces and MaxCollisionVolumes can vary from 1 – 32 or more. Therefore when we add an entity with something along the lines of AddEntityToHash() we need to have at least two (depending on the number of “components”) arrays of variable sizes. When a big bomb lands on the middle of the map and it kills 50 ants, we have to delete them, right? You could say lets try with a linked list to preserve those arrays by chunks, but we cant do that because we expect first the pointer to be aligned meaning to be iterated with a for loop. Instead of a piece = piece->next;

for(u32 R = 0; R < Entity->RenderPiecesAdded; R++)
{
    render_piece* Piece = Entity->Pieces + R;
    //push geometry or do sth else...
}

… and we cannot predict what will be the size of the next entity request. It may want 15 render_pieces and 5 collision_volumes, but we may have space only for 13 and 3, right? That is Problem 1!

Problem 2: Currently, we do not like the use of allocating and freeing memory, especially for small sizes and frequently (sizeof(render_piece) = 144 bytes, the sizeof(collision_volume) = 68 bytes). What do I mean by frequently? Suppose we got 2000 simulated ants and 10 000 grassy/watery/firey tiles. Lets say your kingdom goes on fire and 500 ants die in 3 frames. They hold 16 pieces and 3 collision_volumes.

I held to this idea pretty strongly and I did not want to introduce components. What I came up with was that we will have some pretty large max number per entity 32 for pieces and 8 for collision_volumes! But it is too much to store it in the entity struct directly and it is not necessary to be the maximum for each entity, grass tiles can have a single render_piece and no collision_volume.

If we want this variability, lets store a hash with the freed pointers, so 32 pointers for the pieces and 8 pointers for the collision_volumes. When you go to add an entity with 17 render_pieces and 3 collision_volumes, we check the hash and we say is there any free render_pieces at slot 17 (meaning with size 17), if not look upwards and then find the closest occupied slot in this case 20 and use it, we do the same for collision_volumes. Now, if we use the hash slot at 20 it means that we have more than we need and we are fragmented. This fragmentation can be pretty heavy. For example, I deleted 100 entities with a single render_piece, so my hash has a singly linked list of 100 render_pieces each in array of size 1. If I now want an array of 4, we can’t use them, because we expect aligned memory, so we only look upwards, but there is nothing in the hash. Therefore in the worst case you can have the maximum number of entities multiplied with the max render pieces per entity x (almost 2). Pretty though!

Variable size arrays with direct indexing for no cache problems, without relying on heavy use of small allocations and deallocations, sounds too good! We have to loose at least one property (unfortunately).

Let’s get to the solution. (ahh… and btw internal means static, u32 is unsigned int 32 bits, same for u8, s32 is just signed)

struct entity
{
        ... some members
        u32 Pieces[MAX_RENDER_PIECES_PER_ENTITY];
	u32 CollisionVolumes[MAX_COLLISION_VOLUMES_PER_ENTITY];
	u8 ReservedRenderPieces;
	u8 ReservedCollisionVolumes;
	u8 RenderPiecesAdded;
	u8 CollisionVolumesAdded;
        ... other members
};

Now we changed from storing actual pointers to ids much smaller size, but lost the straight iterations or we think so. This gives us a big benefit, we completely avoid having to fight with allocations and fragmentation, because if there is a straight array of 10 000 render_pieces allocated there is no problem. We just have to make sure that we do not take any more than 10 000.

Here is the array of render_pieces:

struct render_pieces_array
{
	render_piece* Entries;
	entity_id* EntityIDs;
	u32* ChunkIndices;
	u32 Taken;
};

We want the EntityIDs, because we need to be able when we delete a piece (or component) to rewire back to the entity, we will see this in a second! ChunkIndices is specific to the design of this engine since we cannot simulate every entity. They are just too much. When we can’t get a simulated entity, we just say hey we need to know the chunk index together with the id to know in which chunks local hash storage to fetch from.

When we reserve space to link to entities after the huge 10 000 render_pieces allocation we do this:

internal void
ReserveNRenderPieces(u8 CountToReserve, entity* Entity, game_world* World)
{
	if(CountToReserve)
	{
		Assert(Entity->ID.ValueStored);
		Assert((Entity->ReservedRenderPieces + CountToReserve) <= MAX_RENDER_PIECES_PER_ENTITY);
		Assert((World->RenderPieces.Taken + CountToReserve) <= MAX_RENDER_PIECES);
		for(u32 E = 0; E < CountToReserve; E++)
		{
			u32 Index = World->RenderPieces.Taken + E;
			u32 LocalArrIndex = Entity->ReservedRenderPieces + E;
			World->RenderPieces.EntityIDs[Index] = Entity->ID;
			World->RenderPieces.ChunkIndices[Index] = Entity->ChunkIndex;
			World->RenderPieces.Entries[Index].ArrayIndex = LocalArrIndex;
			Entity->Pieces[LocalArrIndex] = Index;
		}
		Entity->ReservedRenderPieces += CountToReserve;
		World->RenderPieces.Taken += CountToReserve;
	}
}

Each render_piece has a member Piece->ArrayIndex that’s because you want to be able to reference directly the Entity->Pieces[ArrayIndex] instead of searching linearly, even if the count is relatively small (2-32).

internal render_piece*
GetRenderPiece(u32 ComponentID, game_world* World)
{
	Assert(ComponentID < MAX_RENDER_PIECES);
	render_piece* Result = World->RenderPieces.Entries + ComponentID;
	return Result;
}

internal render_piece*
AddRenderPiece(entity* Entity, game_world* World, ..............)
{
	Assert(Entity->ReservedRenderPieces > Entity->RenderPiecesAdded); 
	u32 ComponentID = Entity->Pieces[Entity->RenderPiecesAdded];
	render_piece* Piece = GetRenderPiece(ComponentID, World);
	AddRenderPiece(Piece, .....................);
	Entity->RenderPiecesAdded++;
	return Piece;
}

Now if most of the entities are added before the start of the game. (usually that is the case most of the time). We don’t actually loose cache locality very much since our GetRenderPiece() procedure is just a linear look up in a sequential buffer. Most entities will have 5 render_piece consecutively ordered also our render_piece structure is currently big we can get this size at least a third down.

Preserving locality may change in the future if in the case of a “wrong” world generation we have to revert then we might get hurt. That was one of the problems I was most concerned about. (This code has not been heavily profiled at all (these are just guesses) and probably it would not need to be, but just keep that in mind.)

internal void
_DeleteRenderPiece(u32 ArrayIndex, entity* Entity, game_world* World)
{
	Assert(Entity->ReservedRenderPieces);
	Assert(ArrayIndex < Entity->ReservedRenderPieces);

	u32 LastIndex = World->RenderPieces.Taken - 1;
	u32 ToBeOverWrittenIndex = Entity->Pieces[ArrayIndex];

	entity_id RewireID = World->RenderPieces.EntityIDs[LastIndex];
	u32 RewireChunkIndex = World->RenderPieces.ChunkIndices[LastIndex];
	u32 PieceIndex = World->RenderPieces.Entries[LastIndex].ArrayIndex;

	World->RenderPieces.Entries[ToBeOverWrittenIndex] = World->RenderPieces.Entries[LastIndex];
	World->RenderPieces.EntityIDs[ToBeOverWrittenIndex] = RewireID;
	World->RenderPieces.ChunkIndices[ToBeOverWrittenIndex] = RewireChunkIndex;
	World->RenderPieces.Taken--;
        //NOTE(enev): Unprotected, because we still want the entity even if it has been flagged for deletion!
	entity* RewireEntity = GetEntityFromSimOrChunkHashUnprotected(RewireID, RewireChunkIndex, World);
	Assert(PieceIndex < RewireEntity->ReservedRenderPieces);
	RewireEntity->Pieces[PieceIndex] = ToBeOverWrittenIndex;
}

//NOTE(enev): In case of deleting a single piece you need to
//get all pieces in front of you move them and set the correct ArrayIndex.
internal void
DeleteRenderPiece(u32 ArrayIndex, entity* Entity, game_world* World)
{
	_DeleteRenderPiece(ArrayIndex, Entity, World);
	for(s32 C = ArrayIndex; C < Entity->ReservedRenderPieces - 1; C++)
	{
		u32 ComponentID = Entity->Pieces[C + 1];
		render_piece* Piece = GetRenderPiece(ComponentID, World);
		Piece->ArrayIndex = C;
		Entity->Pieces[C] = ComponentID;
	}
	Entity->ReservedRenderPieces--;
}
..then when you want to delete every render_piece 
	Assert(World->RenderPieces.Taken >= Entity->ReservedRenderPieces);
	for(u32 R = 0; R < Entity->ReservedRenderPieces; R++)
	{
		_DeleteRenderPiece(R, Entity, World);
	}
..attach entity to free list

We do not zero the last component, because it will be completely overwritten by the next entity to get a render_piece!

That is all for now! I hope it comes in handy to you. Most of this code can be abstracted into templates (I hate ’em), if you have a lot more than two components and a little bit of time of course. Thank you for reaching to the end of the blog! Happy coding to every reader of my little post :).

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *