In part 2 we built a very basic, minimal functionality Entity Component System framework. It is definitely lacking on features and it’s a bit of a pain to use on a project. In part 3 we are going to expand on the framework to make it more developer friendly.

What are the problems

First let’s explore what makes the minimal ECS painful. For me there are two issues that stand out:

1. I’m constantly forgetting to add a Component class to my template causing compile issues.
2. Iterating data is painful especially when wanting entities with specific, required components.

Problem 1: forgotten components

Starting with the first issue of dealing with the templates. We could go with a dynamically registered set of components. The issue is that every time we add or iterate data we are going to have to check if the component is added yet. That means every frame we are checking for components multiple times. Is there a way that we could shift that registration to one time?

ECS Views

A View gives us a middle ground to static and dynamic components. The View declares what components it needs to exist as template. Yes we can still forget to add a component to our view, but it’s much more localized. Bonus: Importing external systems can add components for us without having to register them.

We should build the View in a way where we don’t need to check components each frame. Ideally this should happen when we register a system. That will end up happening once when we are initializing the game scene. The View will be limiting what a developer can access to only what we have made sure exists.

Refactor to support views

First we will need to do a bit of a refactor. We need the View to be able to access the data of the EcsManager. We also need the system registration to know the View exists. Having the data and systems in a combined EcsManager gives us a circular dependency. EcsManager needs View needs EcsManager.

To fix this we split the EcsManager into a ComponentManager and a SystemManager. I’m not going to detail how this is done since it is just moving code around. Check out the code to see how I arranged it.

Dealing with Dyanmic Components

Previously we used a tuple to store each of the components. With dynamic types we can’t just use a tuple. We need to store an unknown number of things. The only thing we can be sure of is that our design won’t let the number of components change frame by frame.

We can’t simply store each SparseMap in a vector. A vector can only have a single type of data. What we could do is have every SparseMap<T> extend from an abstract class. With a parent ComponentContainer we can now store pointers to every SparseMap<T>. We do end up having a level of indirection in calling methods on the container, but I’m expecting the performance impact to be worth the trade off.

While we are at it, let’s also create another DataHolder<T> class in between. This will eventually let us use different containers besides SparseMap. We do need our ComponentManager to expose a few methods that the ComponentManager will need to do on everything. Removing data and finalizing updates should be able to happen without knowing the component type.

class ComponentContainer {
public:
  ComponentContainer() {}
  virtual ~ComponentContainer() {}

  virtual void remove(EntityID entity) = 0;
  virtual size_t size() = 0;
  virtual bool hasEntity(EntityID entity) = 0;
  virtual void finalizeUpdates() = 0;
};

template <typename T>
class DataHolder : public ComponentContainer {
public:
  DataHolder() {}
  virtual ~DataHolder() {}

  virtual void add(EntityID entity, T value) = 0;
  virtual void remove(EntityID entity) = 0;
  virtual size_t size() = 0;
  virtual bool hasEntity(EntityID entity) = 0;
  virtual EntityID getEntityAtIndex(size_t index) = 0;
  virtual std::optional<size_t> findIndexOfEntity(EntityID entity) = 0;
  virtual T* getComponentAtIndex(size_t index) = 0;
  virtual T* getComponentForEntity(EntityID entity) = 0;
  virtual void finalizeUpdates() = 0;
};

We will need to store our data in a way that we can find a container easily. C++ has a handy type_index that will give us a hash for every type in our program. This means we can use an unordered_map to map any component type to a data container. Also I am using unique_ptr instead of just a plain pointer, so that memory is done for me. I’m forgetful after all.

unordered_map<type_index, unique_ptr<ComponentContainer>> components;

Accessing data from components just needs the type_index. Note the return of type_index needs to be const and also a reference to compile and work correctly.

template <typename T>
DataHolder<T>* getDataHolder() {
  auto& type = std::type_index(typeid(T));

Something we should do is allow a developer to set whatever custom DataHolder they may want. We will default everything to our SparseMap for quick development. This should only happen at load time, so we will also want a method that just gets whatever is already set up. Inside out ComponentManager, we add:

template <typename T>
using DefaultHolderType = SparseMap<T>;

template <typename T>
DataHolder<T>* getDataHolder() {
  const auto& type = std::type_index(typeid(T));
  assert(components.find(type) != components.end() &&
    "Component does not have a data holder set up");

  return (DataHolder<T>*) components[type].get();
}

template <typename T, typename HolderType>
DataHolder<T>* getOrAddDataHolder() {
  const auto& type = std::type_index(typeid(T));
  if (components.find(type) == components.end()) {
    return addDataHolder<T, HolderType>();
  }
  return getDataHolder<T>();
}

template <typename T>
DataHolder<T>* getOrAddDefaultDataHolder() {
  return getOrAddDataHolder<T, DefaultHolderType<T>>();
}

template <typename T, typename HolderType>
DataHolder<T>* addDataHolder() {
  const auto& type = std::type_index(typeid(T));
  assert(components.find(type) == components.end() &&
    "Component already has a data holder defined");

  components[type] = std::make_unique<HolderType>();
  return (DataHolder<T>*) components[type].get();
}

Building the View

We already had code in our ComponentManager for fetching data. We can just take that code and split it into a new ECS View. This code was written to expect all types to be defined as a template and do compile time checks. We leave that as is. The only change is now to fetch a component we do manager->getDataHolder<T>() instead of get<SparseSet<T>>().

Where this does get a bit complex is the compile time checks. We can no longer rely on the tuple to do the checks for us. This is where static_assert and constexpr can come in handy. These will essentially run code on the compiler to check if the component is valid. Variable templates can be iterated just like any linked list: with recursion! There’s some handy C++ utilities like is_same to check if two types are the same thing.

template<typename Check, typename VCFirst, typename... VCRest>
constexpr bool componentInList() {
  if constexpr (std::is_same<Check, VCFirst>::value) {
    return true;
  }
  // Without this, the compiler has no idea what to do
  // with "componentInList<>" or "componentInList<Check,>".
  // So only recurse if we have anything else.
  if constexpr (sizeof...(VCRest) > 0) {
    return componentInList<Check, VCRest...>();
  }
  else {
    return false;
  }
}

Something we do have to decide is what should happen when a developer calls to remove all components from an entity. There are two choices:

1. remove only components the view has access to
2. remove all components

To determine the best course ask yourself one thing. Why would someone call “removeAllComponentsFromEntity”. They probably want to delete the entity. The character just fell off the map. If we only delete a few components, then the character may still be lingering on. Yes we could run into an instance where someone means to only delete some, but I think most cases will want to delete all.

We have everything to implement our View class now. It will probably look something like this.

template<typename... Components>
class View {
public:
  View(ComponentManager* componentManager) : manager(componentManager) {}

  EntityID createEntity() {
      return manager->createEntity();
  }

  void removeAllComponentsFromEntity(EntityID id) {
      manager->removeAllComponentsFromEntity(id);
  }

  template <typename T>
  T* getComponentForEntity(EntityID entity) {
      static_assert(
          componentInList<T, Components...>(),
          "View does not contain requested component."
          );
      auto c = manager->getDataHolder<T>();
      return c->getComponentForEntity(entity);
  }

  // You've seen these methods before. The static assert and getDataHolder is all that changes.

  template <typename T>
  bool componentHasEntity(EntityID entity) {}

  template <typename T>
  size_t sizeOfComponent() {}

  template <typename T>
  EntityID getEntityAtIndex(size_t index) {}

  template <typename T>
  T* getComponentAtIndex(size_t index) {}

  template <typename T>
  void addComponentToEntity(EntityID entity, T value) {}

  template <typename T>
  void removeComponentFromEntity(EntityID entity) {}

private:
  ComponentManager* manager;
};

Speaking of re-usability, what if I want to call another piece of code that doesn’t need the same view? The view we have must contain everything the re-usable method needs. A subview method would let us take a view and trim it down to a subset. This way we can re-use something like spawnCharacter in different systems. C++ does let us override methods for how a View is casted to another view for a nice looking API. We also should also provide a method in case we ever want it without casting.

template<typename... ComponentsSlice>
operator View<ComponentsSlice...>() {
  return subview<ComponentsSlice...>();
}

template<typename... ComponentsSlice>
View<ComponentsSlice...> subview() {
  static_assert(
    (isComponent<ComponentsSlice>() && ...),
      "Subviews cannot include components not in the original view."
    );

  return View<ComponentsSlice...>(manager);
}
template<typename T>
static constexpr bool isComponent() {
  return componentInList<T, Components...>();
}

Why did we need this isComponent() thing? We’ve run into a tricky spot of needing to check two variable templates. We can’t iterate over both at the same time. The isComponent let’s us separate the iterations. Now we can iterate the subview’s components and check each one, then iterate the parent view’s components for validity.

Using views with systems

The final requirement is that the views should be validated and created when a system is registered. We will need to create the view and store it somewhere, so it can be used when the system is called. Fun fact of the day: a struct that implements operator() is a valid std::function. We can wrap the view into a struct and make it callable.

// A ViewSystem is any system that takes a view in.
// All user written systems will be ViewSystems.
template <typename... Components>
using ViewSystem = std::function<void(View<Components...>*)>;

template <typename... Components>
struct ViewSystemRunner {
  ViewSystemRunner(
      View<Components...> v,
      ViewSystem<Components...> sys
  ) : view(v), system(sys) {}

  void operator()() {
    system(&view);
  }

private:
  View<Components...> view;
  ViewSystem<Components...> system;
};

Now in our EcsManager we can have our addSystem method wrap the user’s method. We could use std::function as a parameter in, but I’ve found MSVC++ to have issues deducing templates. I really do not want to specify the View’s template yet again when I add the system. I want the compiler to deduce it for me. Turns out though a C-style function pointer works. This does limit us from using class instance methods. There is a way to enable it, but that will be for a later episode.

template <typename... Components>
void addSystem(void (*system)(View<Components...>*)) {
  View<Components...> view = CopperEcs::createView<Components...>(&components);
  ViewSystemRunner<Components...> runner(view, system);
  systems.addSystem(runner);
}

That’s all of the major parts of the ECS Views. We went from code that looked like

EcsManager<Transform, Camera, Team, Score, Input, AndManyMore> ecs;

ecs.addSystem(handleGravity);

void handleGravity(EcsManager<Transform, Camera, Team, Score, Input, AndManyMore> ecs) {}

To something more like

EcsManager ecs;

ecs.addSystem(handleGravity);

void handleGravity(View<Transform> ecs) {}

Problem 2: iterating data

Our next problem is iterating data. It get’s really ugly when we want to iterate all entities with more than one component. Just look at this:

void checkCollisions(View<Transform, BoundingBox>* ecs) {
  for (size_t i = 0; i < ecs.sizeOfComponent<BoundingBox>(); i++) {
    EntityID entity = ecs->getEntityAtIndex(i);
    if (!ecs->componentHasEntity<Transform>(entity)) {
      continue;
    }

    BoundingBox* bbox = ecs->getComponentAtIndex<BoundingBox>(i);
    Transform* transform = ecs->getComponentForEntity<BoundingBox>(entity);
  }
}

Requiring more than 1 component starts adding more and more hasEntity checks. Someone is bound to forget one and that someone is me. Worse yet is the code below that. Who didn’t notice that the BoundingBox is fetched with an index and Transform with the entity? Technically we could fetch both with the EntityID and never an index, but this is just asking for trouble. Copy paste errors or someone forgetting if it needs to be i or j or whatNumberIsThis are going to happen. These indices are also an implementation detail that is leaking into developer code. They really need to go.

I have tried a few different styles over the last year to see what I liked.

// 1.
// functional. Performs good, but Visual Studio loves to claim it's broken even though it works.
// Also the auto formatter hates me and leaves the trailing `})` indented too much.
view->forEach<BoundingBox, Transform>([](EntityID entity, BoundingBox* bbox, Transform* transform) {})

// 2.
// incomplete iterator. Performs good. Just not perfect. But so close!
for (auto it = view.begin<BoundingBox, Transform>(); it != view.end<BoundingBox, Transform>(); ++it)

// 3.
// embrace the iterator, but performance was horrible
for (auto [entity, bbox, transform] : view.query<BoundingBox, Transform>())

// 4.
// still embracing the iterator, but tried again 8 months later.
// Still have yet to test performance to say if it is good.
for (auto it : view.query<BoundingBox, Transform>()) {
  EntityID entity = it.getEntity();
  BoundingBox* bbox = it.getComponent<BoundingBox>();
}

Fancy iterators

To achieve the last style we will need three more classes:

1. Something to hold all of the indices to query
2. The iterator itself to find the next item that matches our required components
3. A query class to provide begin and end for the foreach loop using a limited set of Components

The iterator works by scanning the first component in a specification, aka a Shape. The shape specifies all components an entity must have to be returned. A dumb ECS engine can just iterate the first one and hope the developer will pick the smallest component first. A smart ECS engine can figure out which component is smaller and iterate that. We want the smallest one, because it’s fewer things to be checked.

Next we look through all other components to see if the entity has that component. We want to get back an index (or pointer, but that’s my next iteration!) if it does exist. Now we can cache all of these references (index or pointer) to let the developer fetch them later. Since we’ve catched the reference, we don’t have to scan the component a second time later.

The most challenging part of our iterator is the “next” or ++it. We can’t just go to the next thing. We have to check if that next entity even has everything we need. We’re going to do a forward_iterator. In other words we don’t provide --it or random access. Random access isn’t possible in a O(1), aka constant time, manner. We can’t predict the next entity. Backwards iterators are possible to implement, I’m just not implementing them is all. But we could.

I’m not showing Entry here as it’s just a simple class that wraps the cached indices.

template <typename FirstComponent, typename... RestComponents>
class Iterator {
public:
  using iterator_category = std::forward_iterator_tag;
  using value_type = Entry<FirstComponent, RestComponents...>;
  using difference_type = size_t;
  using pointer = Entry<FirstComponent, RestComponents...>*;
  using reference = Entry<FirstComponent, RestComponents...>&;

  Iterator& operator++() {
    next();
    return *this;
  }

  // By the way, doing `it++` is probably a lot slower than you would otherwise think.
  Iterator operator++(int) {
    Iterator it = *this;
    ++(*this);
    return it;
  }

  bool operator==(Iterator other) const {
    return manager == other.manager && index == other.index;
  }

  bool operator!=(Iterator other) const {
    return !(*this == other);
  }

  reference operator*() {
    return entry;
  }

private:
  ComponentManager* manager;

  // The current index. This is still a leaky abstraction that will be fixed later.
  size_t index;

  // Cache the size to know when we reach the `end()`.
  size_t size;

  Entry<FirstComponent, RestComponents...> entry;

  void next() {
    bool hasall = true;
    do {
      ++index;
      hasall = set_values(std::index_sequence_for<RestComponents...>{});
    } while (!hasall && index < size);
  }

  template <std::size_t... Is>
  bool set_values(std::index_sequence<Is...>) {
    if (index >= size) {
      return false;
    }
    EntityID id = manager->getDataHolder<FirstComponent>()->getEntityAtIndex(index);

    std::optional<size_t> maybes[1 + sizeof...(RestComponents)];
    maybes[0] = index;
    ((
      maybes[Is+1] = manager->getDataHolder<RestComponents>()->findIndexOfEntity(id)
      ), ...);

    // Since we iterate the entities of FirstComponent
    // we can assume there is at least one true.
    bool has_all = true && (maybes[Is+1].has_value() && ...);

    if (has_all) {
      entry.entity = id;
      entry.indices[0] = maybes[0].value();
      ((entry.indices[Is+1] = maybes[Is+1].value()), ...);
      return true;
    } else {
      return false;
    }
  }

There’s a new fanciness of C++ I should explain: index_sequence. We have a list of Components in our template. We need to turn those into an index of an array that is our cache. index_sequence gives us a way to match a Component in RestComponents to some index.

Make sure that in the constructor of the iterator it needs to actually validate the iterator. If someone manages to create an iterator with an index that does not match the shape, then everything breaks. This also means we can create an iterator with index 0 and if nothing matches the shape, then it will also equal end().

explicit Iterator(size_t start, ComponentManager* componentManager) :
  manager(componentManager), index(start), entry(mgr) {
  size = manager->getDataHolder<FirstComponent>()->size();

  // Can't just call next, because then we will skip the first entry!
  if (!set_values(std::index_sequence_for<RestComponents...>{})) {
    next();
  }
}

Something we could do is add optional values to our iterators. The issue is that we are doing a lookup and cache for every component. If a method does not actually need to check every optional, then we have wasted time. I’m going to leave it to a developer to just use the view to check has and get on optionals.

The Query class isn’t super interesting and fairly basic. It just creates begin() and end() to fetch iterators for the C++ foreach. A find(EntityID) method also exists for look ups and iteration starting at a point. You can check out the code to see how overly basic they are.

What’s next

Long term I want to get rid of caching indices of the SparseMap in the Iterators. What if someone has a QuadTree backed data holder? Any DataHolder that is not randomly accessible by index would not be supported.

I need to check the performance of this and find the slow points. Adding data might benefit from using std::copy or a sort of emblace style instead of push style. But maybe it is fast as is and I don’t need to do anything.

One way to find out how good a system is: just use it. A common phrase in the tech world is “eat your own dogfood”. On Part 4 we are going to build ECS Command, a game similar to Missile Command. That will help us uncover some pain points and keep iterating.