Overview
After playing a while with the ECS implementation of the Unity engine and liking it very much I decided to try recreate it as a challenge. As part of this challenge I need a way of storing the components grouped by entity; I solved this by creating a container called a Chunk
.
Unity uses archetypes to group components together and stores these components in pre-allocated chunks of fixed size.
I made a simple design of my implementation as clarification:
Here Archetype
is a linked list of chunks; the chunks contain arrays of all the components that make the archetype - in this case Comp1, Comp2 and Comp3. Once a chunk is full a new chunk is allocated and can be filled up and so on.
The chunk itself is implemented like this:
With this solution I can store the components grouped by entity while making optimal use of storage and cache because the components are tightly packed in an array. Because of the indirection provided by the array of indices I am able to delete any component and move the rest of the components down to make sure there aren't any holes.
Questions
I have some items I'd like feedback on in order to improve myself
- Is the code clear and concise?
- Are there any obvious performance improvements?
- Because this is my first somewhat deep-dive in templates, are there any STL solutions I could've used that I have missed?
Code
- chunk.h
Contains the container.
#pragma once
#include "utils.h"
#include "entity.h"
#include <cstdint>
#include <tuple>
template<size_t Capacity, typename ...Components>
class chunk
{
public:
struct index
{
uint16_t id;
uint16_t index;
uint16_t next;
};
chunk()
:
m_enqueue(Capacity - 1),
m_dequeue(0),
m_object_count(0)
{
static_assert((Capacity & (Capacity - 1)) == 0, "number should be power of 2");
for (uint16_t i = 0; i < Capacity; i++)
{
m_indices[i].id = i;
m_indices[i].next = i + 1;
}
}
const uint16_t add()
{
index& index = m_indices[m_dequeue];
m_dequeue = index.next;
index.id += m_new_id;
index.index = m_object_count++;
return index.id;
}
void remove(uint16_t id)
{
index& index = m_indices[id & m_index_mask];
tuple_utils<Components...>::tuple_array<Capacity, Components...>::remove_item(index.index, m_object_count, m_items);
m_indices[id & m_index_mask].index = index.index;
index.index = USHRT_MAX;
m_indices[m_enqueue].next = id & m_index_mask;
m_enqueue = id & m_index_mask;
}
template<typename... ComponentParams>
constexpr void assign(uint16_t id, ComponentParams&... value)
{
static_assert(arg_types<Components...>::contain_args<ComponentParams...>::value, "Component type does not exist on entity");
index& index = m_indices[id & m_index_mask];
tuple_utils<Components...>::tuple_array<Capacity, ComponentParams...>::assign_item(index.index, m_object_count, m_items, value...);
}
template<typename T>
constexpr T& get_component_data(uint16_t id)
{
static_assert(arg_types<Components...>::contain_type<T>::value, "Component type does not exist on entity");
index& index = m_indices[id & m_index_mask];
return std::get<T[Capacity]>(m_items)[index.index];
}
inline const bool contains(uint16_t id) const
{
const index& index = m_indices[id & m_index_mask];
return index.id == id && index.index != USHRT_MAX;
}
inline const uint32_t get_count() const
{
return m_object_count;
}
static constexpr uint16_t get_capacity()
{
return Capacity;
}
private:
static constexpr uint16_t m_index_mask = Capacity - 1;
static constexpr uint16_t m_new_id = m_index_mask + 1;
uint16_t m_enqueue;
uint16_t m_dequeue;
uint16_t m_object_count;
index m_indices[Capacity] = {};
std::tuple<Components[Capacity]...> m_items;
};
- utils.h
Contains utility functions for templates used by the chunk class.
// utils.h
#pragma once
#include <tuple>
#include <type_traits>
#include <algorithm>
// get total size of bytes from argumant pack
template<typename First, typename... Rest>
struct args_size
{
static constexpr size_t value = args_size<First>::value + args_size<Rest...>::value;
};
template <typename T>
struct args_size<T>
{
static constexpr size_t value = sizeof(T);
};
template<typename... Args>
struct arg_types
{
//check if variadic template contains types of Args
template<typename First, typename... Rest>
struct contain_args
{
static constexpr bool value = std::disjunction<std::is_same<First, Args>...>::value ?
std::disjunction<std::is_same<First, Args>...>::value :
contain_args<Rest...>::value;
};
template <typename Last>
struct contain_args<Last>
{
static constexpr bool value = std::disjunction<std::is_same<Last, Args>...>::value;
};
//check if variadic template contains type of T
template <typename T>
struct contain_type : std::disjunction<std::is_same<T, Args>...> {};
};
template<typename... Args>
struct tuple_utils
{
// general operations on arrays inside tuple
template<size_t Size, typename First, typename... Rest>
struct tuple_array
{
static constexpr void remove_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple)
{
First& item = std::get<First[Size]>(p_tuple)[index];
item = std::get<First[Size]>(p_tuple)[--count];
tuple_array<Size, Rest...>::remove_item(index, count, p_tuple);
}
static constexpr void assign_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple, const First& first, const Rest&... rest)
{
std::get<First[Size]>(p_tuple)[index] = first;
tuple_array<Size, Rest...>::assign_item(index, count, p_tuple, rest...);
}
};
template <size_t Size, typename Last>
struct tuple_array<Size, Last>
{
static constexpr void remove_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple)
{
Last& item = std::get<Last[Size]>(p_tuple)[index];
item = std::get<Last[Size]>(p_tuple)[--count];
}
static constexpr void assign_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple, const Last& last)
{
std::get<Last[Size]>(p_tuple)[index] = last;
}
};
};
Usage
auto ch = new chunk<2 * 2, TestComponent1, TestComponent2>();
auto id1 = ch->add();
auto id2 = ch->add();
auto contains = ch->contains(id1);
ch->assign(id1, TestComponent2{ 5 });
ch->assign(id2, TestComponent1{ 2 });
ch->remove(id1);
Tests
#include "chunk.h"
#define CATCH_CONFIG_MAIN
#include "catch.h"
struct TestComponent1
{
int i;
};
struct TestComponent2
{
int j;
};
struct TestComponent3
{
char t;
};
SCENARIO("Chunk can be instantiated")
{
GIVEN("A Capacity of 4 * 4 and 3 component types as template parameters")
{
chunk<4 * 4, TestComponent1, TestComponent2, TestComponent3> testChunk;
THEN("Chunk has Capacity of 4 * 4 and is empty")
{
REQUIRE(testChunk.get_capacity() == 4 * 4);
REQUIRE(testChunk.get_count() == 0);
}
}
}
SCENARIO("Items can be added and removed from chunk")
{
GIVEN("A Capacity of 4 * 4 and 3 component types as template parameters")
{
chunk<4 * 4, TestComponent1, TestComponent2, TestComponent3> testChunk;
auto entityId = 0;
WHEN("Entity is added to chunk")
{
entityId = testChunk.add();
THEN("Chunk contains entity with id")
{
REQUIRE(testChunk.contains(entityId));
REQUIRE(testChunk.get_count() == 1);
}
}
WHEN("Entity is removed from chunk")
{
testChunk.remove(entityId);
THEN("Chunk does not contain entity with id")
{
REQUIRE(!testChunk.contains(entityId));
REQUIRE(testChunk.get_count() == 0);
}
}
}
}
SCENARIO("Items can be given a value")
{
GIVEN("A Capacity of 4 * 4 and 3 component types as template parameters with one entity")
{
// prepare
chunk<4 * 4, TestComponent1, TestComponent2, TestComponent3> testChunk;
auto entity = testChunk.add();
auto value = 5;
WHEN("entity is given a type TestComponent2 with a value of 5")
{
testChunk.assign(entity, TestComponent2{ value });
THEN("entity has component of type TestComponent2 with value of 5")
{
auto component = testChunk.get_component_data<TestComponent2>(entity);
REQUIRE(component.j == value);
}
}
}
}