Implement Archetypes

[KnockerPulsar]

The current layout of component data is very simple, but it leaves a lot to be desired in terms of performance and compactness.

Each level has a component container which is essentially a map from a certain component type to the vector containing its data. Since each entity might or might not have a specific component, this requires each component in the vector to be wrapped by an optional. When iterating over a set of components for a certain system, we then iterate over all entities, checking if they have the required components (as in, all components hold some value) and return the tuple of component references if so. This last part is handled inside the multi iterator so it's transparent to users, but it does incur a performance and space penalty due to having to check the components for each entity in the level.

Archetypes (see: this, and this) would help solve this problem by separating each set of entities containing a set of components into their own container. Iterating over these entites would be straightforward as you once you find an archetype with a set of components, you're sure that all entities belonging to it have the components you're looking for. It gets a bit complicated when you want to iterate over subsets, but I think some sort of chained iterator would fix this as a first solution.

Example

Here, if we want to iterate over entities with components {A, B}, we'll have to find the archetype corresponding to them, then iterator over the vector(s) of components inside them blindliy.

For iterating over all entities with component A, we'll have to find all archetypes where this component is contained ({A}, {A, B}, {A, B, C}), then we'd need to chain the iterators of each vector so that we can iterate over them all. A solution to this could be to have a container for the vectors of each primitive component (A, B, or C), where it holds a vector for each archetype, and the archetype just references that vector. This would make it easy to iterate over just primitive components, combinations of them, or archetypes.

[KnockerPulsar]

So the first prototype I settled on was a bit simpler than I expected. In essence, we have:

• TypeSet: A class that allows for easy comparison of types without having their order break things ({A,B} == {B, A}).
• Archetype: Collection of type erased vectors, each vector containing the data of one component of the archetype. By definition, the length of all vectors are equal.
• Archetypes: Handles the management of archetype queries. For example, if you have two archetypes {A, B, C}, { B, C, D} and you want to iterate over {B, C} only. Archetypes checks which archetypes have {B, C} as a subset and collects their iterators into a chaining iterator which the user can use seamlessly to iterate over all {B, C} pairs.
• ChainIterator: Chains a bunch of MultiIterators to allow easy iteration over subsets of multiple archetypes.

This implementation is still missing mapping from entities to archetypes and moving entities between archetypes by adding or removing components, but I see it as a good start.

Something that might require some improvement later on is querying for subsets of archetypes. Currently it's done via a linear search and comparison of the query and all other typesets, but I think it might be good to either:

1. Cache the result after the first query (need to take into account invalidating the cache whenever a relevant archetype is added or removed)
2. Maybe use the graph which will be used for adding / removing components to also figure out what archetypes are supersets of our query by starting from the query and following the each 'add' edge.