Note: code highlighting thanks to http://hilite.me/
Note2: This blog is primarily on template meta-programming--when the
opportunity presents--using it to solve practical problems. This post assumes
knowledge of C++17 fold expressions. If the reader is unfamiliar, this may not be the best learning material,
but if the reader gets the idea and wants a practical example, please read on.
Update July 30 2020: I realized a bit late a bug where non-const values
weren't always respect in the final solution. I haven't tracked it down yet so
just be warned.
Update July31: Fixed a bug that caused an infinite loop.
class Actor { // ... }; class Player : public Actor { // ... }; class Enemy : public Actor { // ... };
So each thing that an actor could do was represented in the base class and the
derived classes overrode that behavior in classic OOP style. Those were
simpler days.
I decided to rewrite my code to what I now understand is a fairly
industry-standard idea: The entity component system or ECS for short. From
what I gather, an ECS is a simple system where entities are merely ID's with a
set of components which define all relevant information important to that
entity. For example, its <X,Y> coordinates in the 2D space
of a 2d game, the type of an entity ({TREE, ITEM, PLAYER, etc...}),
perhaps information on how to draw it... basically anything that would have
gone in Actor or Player.
Proponents of ECS systems will argue for being a better alternative for OOP,
not requiring the base class to consider every possible action or attribute in
the game and cache efficiency--storing like information close together so that
iterations over all entities hopefully involve less cache misses. Sometimes
it's also argued that using ID's to relate objects to each other is much safer
than direct pointers. The alternative is
often std::shared_ptr with locking. Lastly, entities are
easier to extend, mix, match, and define than objects, not having to worry
about hierarchies, mix-ins, and multiple inheritance to get the desired
behavior.
Personally, I think writing a base class that considers every possible action
is not good OOP, but doing it the "right" way is probably less
appealing than the data-oriented ECS style. OOP works great for abstract
objects with variations on behavior, but game entities tend to vary more on
configuration. I think this simplicity sometimes comes at the cost of having
to reinvent mix-ins and hierarchies, but one can still put pointers and
virtual in an ECS by storing pointers.
Information on ECS's on the internet varies in quality as do their
implementations. I won't try to argue that I will present an objectively
better implementation than any others, these are just my ideas and the story
of my process to write one.
Ideas I didn't like
class Entity { GraphicsComponent gfx_component; PhysicsComponent phys_component; EtcComponent etc; // ... };
I think this is closer to the "right" OOP solution as it
encapsulates the complexity into smaller pieces which can then be as simple or
intricate as necessary. In practice, the segmentation of code logic and how
systems relate to each other may become unclear. In a grid-based game like
mine, entities will have an integer <X,Y> position on
the grid which maps to a very different position when rendering to the screen
which may even by offset slightly by animations. How do components refer to
each other? It encourages using virtual functions to customize
behavior, which is very tidy, but also involve a lot of boilerplate code and
isn't incredibly efficient. Lastly, it doesn't store like data together.
There's also the idea of having the Entity store a
vector of component objects and it's one of the more common
implementations I see, but this has the additional issue that one class needs
to consider all the complexity of the game. For example, if each component
object has a init(), update(), etc() functions,
they have to understand how to update themselves and interact with the world,
but the world needs to understand how to contain them leading to two mutually
referential system. That can be fine, but in my previous attempt, I found this
really complicated the definition of more interesting components.
using ComponentId = unsigned int;
template<typename T> struct ComponentData { EntityId id; T data; ComponentData(EntityId id, T data) : id(id), data(std::move(data)) { } };class Buffer { char* data = nullptr; // ... }; class EntityComponentSystem { std::unordered_map<ComponentId, Buffer> components; };
I think this idea gets closer. Each component type has a unique
ComponentId which is determined by the type system through
template magic and each Buffer holds an array of these
components that is manually managed by itself since
std:: classes like vector need to know what type it
contains and how large it is at compile time. This
std::unordered_map could be replaced by an
std::array if the number of different component types are
known in advance.
Actually, if the component types themselves are known and I happen to love
tuples, we could just do this:
template<typename T> struct ComponentData { EntityId id; T data; ComponentData(EntityId id, T data) : id(id), data(std::move(data)) { } }; using EntityId = unsigned int; template<typename...Components> class EntityComponentSystem { std::tuple<std::vector<ComponentData<Components>>...> components; };
and that's what I ended up with in my first iteration (link). One big and notable downside is that now, if I have a grid position, for
which I use my custom Vec<int> class, and a graphical
position, which uses a Vec<int> as well, they'll be stored
as the same component. It's tedious, but I implemented
GraphicalPosition and GridPosition classes to
differentiate.
It also means that the declaration of the ECS type needs to contain every
component used in the game, but I don't find that
too problematic.
From the above idea, we could construct a simple interface like this:
EntityComponentSystem<Pos, TextureRef> ecs; auto e1 = iu.write_new_entity(Pos(1, 2), TextureRef(tex1)); auto e2 = iu.write_new_entity(Pos(3, 4), TextureRef(tex2)); for (auto id : ecs.ids()) { Pos p; TextureRef tref; if (ecs.read(id, p, tref)) draw(p, tref); }
In the end, I use a much more efficient interface, but this gives an idea
about how it might be used. e1 and e2 are entity
ID's that have a Pos and TextureRef component which
can be read back out in order to draw them onto the screen if the entity has
both components.
One note, before we move on: Why an std::vector and not a hash
table keyed by the entity ID? Many entity component systems do it this way
and it's great for O(1) lookups, but the code I have planned out
has little need for fast random access and hash tables don't make good use
of CPU caches. If I run into performance issues, I can see if a hash fixes
it, but for now I'll stick to this. I think the larger concern is that a
particle system might require more efficient random deletion.
If only life was so simple...
Since my entity ID's monotonically increase (omitting
int32 overflow), keeping the component vectors sorted is
generally simple enough. I used std::lower_bound() to figure out
where to insert new elements, just in case, but generally entities don't
gain or lose components over time so they're almost always inserted at the
end. The component arrays are essentially parallel where
std::get<std::vector<ComponentData<X>>>[i] would resolve to the i'th X component of probably
the i'th entity, and ditto for Y. However, not all entities
have all components so some checking might be needed.
Say I want an algorithm that does this:
for (grid_pos, graphical_pos) in ecs.read_grid_and_graphical_pos() {graphical_pos = grid_pos * TILE_SIZE}
Well, if I can iterate through one, I can do two, right? Start at the
beginning, make sure they're pointing at the same element, and in the
increment step, increment one of them and then the other until it has the
same EntityId or higher and keep going back and forth until either
hits the end or they both have the same ID again.
Great! Simple! Problem: I have potentially N iterators and they're all of
different types. I want this syntax:
int sum = 0; for (auto [id, i, u] : ecs.read_all<int, unsigned>()) sum += i + u,
Obviously, this is non-trivial with tuples since we can't store iterators to
each container in a vector, we have to store them in yet another tuple.
My first idea was to have a range class parameterized by the containers
(std::vector<ComponentData<T>>...) and then for it to
define nested iterator classes parameterized by the iterator types of that
container. The basic issue with this is that the container could be const or
non-const, but I had to be able to differentiate since in one case, the
iterator class would store std::vector<T>::iterator and in
the other, ::const_iterator so I ended up writing it twice. But what
I landed with is so much better.
template<typename F, typename...T> constexpr auto tuple_map(F&& f, const std::tuple<T...>& t) { return std::tuple(f(std::get<T>(t))...); } template<typename F, typename...T> auto tuple_map(F&& f, std::tuple<T...>& t) { return std::tuple(f(std::get<T>(t))...); } // A range abstraction that allows multiple component data series to be iterated // lazily over in a range-based for loop. template<typename StoreTuple> class ComponentRange {
// A tuple of references to component storage. StoreTuple stores_;
protected:
template<typename IteratorTuple>
struct Iterator {
// ,,,
IteratorTuple its;
IteratorTuple ends;
bool sentinel = false;
// To know if all iterators are pointing to the same entity, we'll neet
// to remember what entity that is.
EntityId max_id;
// ...
Iterator(IteratorTuple its, IteratorTuple ends)
: its(std::move(its)), ends(std::move(ends)) {
// ...
}
Iterator() { sentinel = true; }
};
public:
explicit ComponentRange(StoreTuple stores)
: stores_(stores) { }
auto begin() const {
auto b = [](auto&& store) { return store.begin(); };
auto e = [](auto&& store) { return store.end(); };
return Iterator(tuple_map(b, stores_), tuple_map(e, stores_));
}
auto end() const {
return decltype(begin())();
}
};
The general idea is to be as unconstraining of types as possible so where
ever we can get away with not specifying a type, we do.
StoreTuple will generally resolve to something ugly like...
std::tuple<std::vector<ComponentData<X>>&, std::vector<ComponentData<Y>>&, ...>
tuple_map and tuple_foreach (the same function, it just
doesn't return a new tuple) are going to be the bread and butter of this
class. For reference about how difficult these functions were to write in
C++11/14, I implemented them way back in "Fun With Tuples".
If any of the its is at the end, the whole tuples is, which made
comparing to the end a bit tricky, thus a sentinel is used. I think a
variation on this idea could have been to consider two Iterators equal
if any of their its are equal, though.
We can't iterate through the tuples easily so it's best we work on them
uniformly, but we don't want any advancing past the max_id, which is
going to be the highest ID of an entity of all iterators. Just iterating once
is easy.
template<typename It> bool at_end(It it) const { return it == std::get<It>(ends); } // Note that the alternative to the above is // std::get<std::decay_t<decltype(it)>>(ends) if auto-typed (e.g. lambda). template<typename Iter> void increment_iter(Iter& it) { if (!at_end(it)) ++it; if (!at_end(it)) max_id = std::max(it->id, max_id); }
This handles the case where an iterator was under max_id, but in an
attempt to catch up it went over and set a new maximum.
Next, we have to handle incrementing all the iterators until they all line up
on one ID.
// A helper to catch up iterators that are behind. void increment_if_lower_than_max_id() { auto impl = [&](auto& it) { if (!at_end(it) && it->id < max_id) increment_iter(it); }; tuple_foreach(impl, its);
}
bool any_at_end() const { auto any = [](auto...args) { return (args || ...); }; auto pred = [this](const auto& it) { return at_end(it); }; return std::apply(any, tuple_map(pred, its)); } // True if all iterators point to the same ID. bool all_same() const { auto all = [](auto...args) { return (args && ...); }; auto equals_max_id = [this](const auto& it) { return it->id == max_id; }; return std::apply(all, tuple_map(equals_max_id, its)); } // After iteration, or on initialization, increment any iterators that // are behind. void catch_up() { while (!any_at_end() && !all_same()) increment_if_lower_than_max_id();
if (any_at_end()) its = ends; } Iterator& operator++() { // Increment at least once. tuple_foreach([this](auto& it) { increment_iter(it); }, its); catch_up(); return *this; } Iterator operator++(int) { Iterator old = *this; ++(*this); return old; }
And finally, comparisons.
bool operator==(const Iterator& other) const { return sentinel ? other == *this : any_at_end(); } bool operator!=(const Iterator& other) const { return !(*this == other); } auto operator*() const { auto data = [](const auto& it) -> auto& { return it->data; }; return std::tuple_cat(std::tuple(max_id), tuple_map(data, its)); }
The final gotcha is that on construction, not all the iterators might be
pointing to the same ID, so we have to call
catch_up() immediately. The full code for the constructor looks
like this:
Iterator(IteratorTuple its, IteratorTuple ends) : its(std::move(its)), ends(std::move(ends)) { max_id = EntityId{0}; tuple_foreach( [&](auto it) { if (!at_end(it)) max_id = std::max(max_id, it->id); }, its); catch_up(); // Ensure a valid initial starting position. } Iterator() { sentinel = true; }
Conclusions
The full code can be found here: https://gist.github.com/splinterofchaos/a67426bb95ea97b3f33fbc44406bc791
The implementation is incomplete at the time of this writing and some of the
interface is inconsistent or unnecessary, but it's a start.
And for the project in which I'm using it: https://github.com/splinterofchaos/py-srpg (Originally written in Python; the C++ conversion is on the
cpp branch at the time of this writing.)
Writing code like this used to be tedious, difficult, and involve heaps of
boilerplate, but at this point, fold expressions over a variable number of
types and arguments feels easier than a for loop from
i=0 to N.
The biggest frustrations for functional programming in C++ remain being things
like how in order to take a template function and convert it to a callable
function object, one has to wrap in a lambda and there exists weak partial
application. For example, in our begin() function.
auto begin() const { auto b = [](auto&& store) { return store.begin(); }; auto e = [](auto&& store) { return store.end(); }; return Iterator(tuple_map(b, stores_), tuple_map(e, stores_)); }
But things like fold expressions and class template argument deduction make
things absolutely much easier.
As for the iterator class, the logic is much less trivial than I'd hope an
iterator class to be, but I think the performance should be decent. If my
program ends up spending more time incrementing iterators than using the
values obtained, I think my bigger issue will be that my game's not doing
much. Most of the iterations through the ECS should be of very similar
entities and so in the general case, it should increment once and exit.
As for the entity class itself, I'll have to test it out a bunch. Obviously, I
worry that adding or removing large numbers of entities could be problematic,
but I imagine it'll be good enough for my purposes and there's plenty of room
for optimization, like maintaining a free list of deleted entity IDs and
component data, for one example. Still, when I'd used the same in Python, it
worked well so it should be better here.
