Entity Component Scrapyard: Introduction

Hiiii person reading this.

EC-Scrapyard is a tutorial walkthrough thingy where we're going to write an ECS from scratch :3

This book is written with the assumption that the reader knows what an ECS is but not necessarily how it works or how to go about writing one. If you dont know what an ECS is there's a good writeup here

A few caveats before we start:

• We wont be using any dependencies, we will be using rust's standard library though :")
• We will only use safe code so #![forbid(unsafe_code)] will be placed at the top of lib.rs
• We wont touch on the Systems part of ECS because I personally feel that's better left to engines and users of the ECS to decide how best to structure the program

A lot of the ECS' in the rust ecosystem use something called 'archetypes' so we'll be writing an archetype based ECS in this book. If you dont know what archetypes are don't worry they'll be explained later on in the book when we get around to implementing them :) If you're impatient and want to look at it now you can go ahead and do that :P the section for that is here

A basic entity generator

Lets start with implementing a basic struct that will let us spawn and despawn entities. Every ECS has something like this and by starting here we can make progress without tackling some of the harder stuff immediately :)

Every ECS that has performance as a goal will not store data *in* their Entity struct but will instead have the Entity be a handle to component data. This is because when we ask the ECS for all components T1 and T2 if they're stored in the Entity struct they'll never be in cache when we go to access them. (This also has many borrowck issues, maybe for another book though :>) Whereas if we store a bunch of our T1 components in a Vec, when we iterate through it we'll end up having the next components loaded into cache which is far more efficient.

A simple way to implement this "Entity as a handle" thing would be to create a tuple struct that wraps a u32 or u64 or whatever size integer you want e.g.

pub struct Entity(u64);

we could then add some derives

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Entity(u64);

This would work pretty well, entities would be cheap to copy, compare with eachother, and they're relatively small in size which is good because we'll have a *lot* of entities in our ECS. Sequential ids hopefully will also make the code for generating new ids not super complex, we just add 1 to a counter.
The first entity we spawn is Entity(0) the second is Entity(1) the third Entity(2) etc etc etc

Well, lets try write up this entity spawning code and see if it ends up with any suprise complexity. Lets start by making a struct with that counter and our spawn method that increments it

struct EntityGenerator {
    next_id: u64,
}

impl EntityGenerator {
    fn spawn(&mut self) -> Entity {
        let entity = Entity(self.next_id);
        self.next_id += 1;
        entity
    }
}

Okay well thats not a lot of code although how exactly does self.next_id += 1 handle the case where self.next_id == u64::MAX we're unlikely to ever have this many entities but we probably ought to atleast see what will happen...

(click the run button :3)

#![allow(unused)]
fn main() {
#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Entity(u64);

struct EntityGenerator {
   next_id: u64,
}

impl EntityGenerator {
   fn spawn(&mut self) -> Entity {
       let entity = Entity(self.next_id);
       self.next_id += 1;
       entity
   }
}

let mut entity_generator = EntityGenerator { next_id: u64::MAX };
let entity = entity_generator.spawn();
dbg!(entity);
}

Oh, well that's not great...

We could explicitly use wrapping_add to avoid this panic, but then two calls to EntityGenerator::spawn could return the same entity and that's definitely undesirable. u64::MAX is a *really* big number so whether we panic or use wrapping_add is unlikely to make much of a difference.
For this guide I'm just going to panic but if you want to wrapping_add that's also fine :)
Note: overflow only panics in debug mode so if we want to panic on overflow we need to explicitly check for it

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Entity(u64);

struct EntityGenerator {
   next_id: u64,
}


impl EntityGenerator {
    fn spawn(&mut self) -> Entity {
        let entity = Entity(self.next_id);
        if self.next_id == u64::MAX {
            panic!("Attempted to spawn an entity after running out of IDs");
        }
        self.next_id += 1;
        entity
    }
}

fn main() {
    let mut entity_generator = EntityGenerator { next_id: u64::MAX };
    let entity = entity_generator.spawn();
    dbg!(entity);
}

If we run this hopefully we panic with our new error message...

thread 'main' panicked at 'Attempted to spawn an entity after running out of IDs'

Yep!

Okay the next thing we want to do is mark entities as dead, that's a pretty core thing for our ECS huh :P?
We'll want a despawn function but how is this function even going to work? We cant store the dead/alive status on the Entity itself because we can copy an entity before it's despawned and then it would still think it's alive.
We need to store all the despawned status of entities in our EntityGenerator

There are a few options for this

• A Vec<Entity> where we push dead entities to it, we would have to iterate the entire vec to check if an entity is dead which could be *super* slow so this is a non-starter.
• A Vec<bool> which we index with the entity's u64 and set to true when we despawn the entity. This would be super fast to check if an entity is dead/alive, if you're concerned about ram consumption with this you could use a bitset instead which would have 1/8th the usage of Vec<bool>
• A HashSet<Entity> and we just insert dead entities into it. This would also be pretty fast to check if an entity is dead/alive

Option #2 and #3 would both be valid choices but for this guide I'm going to go with the HashSet option because its simpler :) Option #2 should work well as a drop-in replacement for the hashset code though so feel free to do that on your own! :)

The Hashset method

The code here will likely speak for itself so I'll just show it-

struct EntityGenerator {
    next_id: u64,
    // New
    dead_entities: std::collections::HashSet<Entity>,
}

impl EntityGenerator {
    // -Snip

    fn despawn(&mut self, entity: Entity) {
        self.dead_entities.insert(entity);
    }

    fn is_alive(&self, entity: Entity) -> bool {
        I like my ``== false`` okay
        self.dead_entities.contains(&entity) == false
    }
}

At first glance this seems pretty correct right? but it isn't ^^" there's an implicit assumption in this code that we only ever receive entities that were spawned from this EntityGenerator but we can just ignore that and cause the generator to spawn a dead entity like so:

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Entity(u64);

struct EntityGenerator {
   next_id: u64,
   dead_entities: std::collections::HashSet<Entity>,
}

impl EntityGenerator {
   fn spawn(&mut self) -> Entity {
       let entity = Entity(self.next_id);
       if self.next_id == u64::MAX {
           panic!("Attempted to spawn an entity after running out of IDs");
       }
       self.next_id += 1;
       entity
   }

   fn despawn(&mut self, entity: Entity) {
       self.dead_entities.insert(entity);
   }

   fn is_alive(&self, entity: Entity) -> bool {
       self.dead_entities.contains(&entity) == false
   }
}

fn main() {
    use std::collections::HashSet;
    let mut gen_1 = EntityGenerator { next_id: 0, dead_entities: HashSet::new() };
    let mut gen_2 = EntityGenerator { next_id: 0, dead_entities: HashSet::new() };

    let e1_1 = gen_1.spawn();
    gen_2.despawn(e1_1);
    let e1_2 = gen_2.spawn();
    assert!(gen_2.is_alive(e1_2));
}

This is pretty problematic to say the least :P We can spawn entities with other generators, despawn them, and then spawn a dead entity. Looking back over our code with this in mind we can also see that if we call is_alive on an unspawned entity it would say yes... Soooooo how can we check for this?
We could store another Hashet for every spawned entity but that would be really slow and waste memory, what's better is that we can compare self.next_id to the entity's u64 to see if its indistinguishable from an entity spawned from this generator e.g.

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Entity(u64);

struct EntityGenerator {
   next_id: u64,
   dead_entities: std::collections::HashSet<Entity>,
}

impl EntityGenerator {
   fn spawn(&mut self) -> Entity {
       let entity = Entity(self.next_id);
       if self.next_id == u64::MAX {
           panic!("Attempted to spawn an entity after running out of IDs");
       }
       self.next_id += 1;
       entity
   }
    // -Snip

    fn despawn(&mut self, entity: Entity) {
        if self.is_alive(entity) {
            self.dead_entities.insert(entity);
        }
    }

    fn is_alive(&self, entity: Entity) -> bool {
        // self.next_id is the ID for the next entity so any entities with 
        // that ID or higher haven't been spawned yet
        if entity.0 >= self.next_id {
            panic!("Attempted to use an entity in an EntityGenerator that it was not spawned with");
        }
        self.dead_entities.contains(&entity) == false
    }
}

#[allow(unreachable_code)]
fn main() {
    use std::collections::HashSet;
    let mut gen_1 = EntityGenerator { next_id: 0, dead_entities: HashSet::new() };
    let mut gen_2 = EntityGenerator { next_id: 0, dead_entities: HashSet::new() };

    let e1_1 = gen_1.spawn();
    assert!(gen_2.is_alive(e1_1) == false);
    gen_2.despawn(e1_1);
    let e1_2 = gen_2.spawn();
    assert!(gen_2.is_alive(e1_2) == unreachable!());
}

I decided to panic in the is_alive method rather than return false because its pretty safe to say that it would be unintentional to do this so we should fail loudly to bring attention to it. It would also be completely fine to return false if you're opposed to panic'ing in libraries unnecessarily :)

To wrap this chapter up lets move all this code into a separate module, reexport the entity struct and then set everything to pub(crate) since we'll likely need this all elsewhere.

// /src/entities.rs
#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Entity(u64);

pub(crate) struct EntityGenerator {
    next_id: u64,
    dead_entities: std::collections::HashSet<Entity>,
}

impl EntityGenerator {
    pub(crate) fn spawn(&mut self) -> Entity {
        let entity = Entity(self.next_id);
        if self.next_id == u64::MAX {
            panic!("Attempted to spawn an entity after running out of IDs");
        }
        self.next_id += 1;
        entity
    }

    pub(crate) fn despawn(&mut self, entity: Entity) {
        if self.is_alive(entity) {
            self.dead_entities.insert(entity);
        }
    }

    pub(crate) fn is_alive(&self, entity: Entity) -> bool {
        // self.next_id is the ID for the next entity so any entities with
        // that ID or higher haven't been spawned yet
        if entity.0 >= self.next_id {
            panic!("Attempted to use an entity in an EntityGenerator that it was not spawned with");
        }
        self.dead_entities.contains(&entity) == false
    }
}

// /src/lib.rs
#![forbid(unsafe_code)]
pub(crate) mod entities;
pub use entities::Entity;

The full source code for this chapter can be viewed here

Now that we have entity spawning and despawning working it's about time to start storing some components, for that we need to learn about what archetypes are. Luckily that's exactly what the next chapter is for!

What are archetypes?

Archetypes are the underlying storage method we will be using to store components in our ECS. In our ECS we will use something like Vec<Archetype> to store everything.
An archetype stores *all* of the components on an entity and also only stores components from entities with the same set of components. E.G. an entity with *only* [T1, T2, T3] components would have all components stored in one archetype, and an entity with *only* [T1, T2, T3, T4] components would have all the components stored in a different archetype.

Let's say we have an archetype, we'll call it A_123. A_123 is storing components for entities that only have components [T1, T2, T3].
When we spawn an entity like so:

world.spawn((
  T1 { .. },
  T2 { .. },
  T3 { .. },
));

We need to find an archetype to place all these components into. As mentioned previously we want to find if there's an archetype that only stores components for entities with [T1, T2, T3], and, luckily for us, there is! It's A_123.

Let's take a quick look at what A_123 might look like internally and how we would go about placing these components into it.
In psuedocode we have some archetype struct that looks a bit like:

struct A_123 {
  column_1: Vec<T1>,
  column_2: Vec<T2>,
  column_3: Vec<T3>,
}

You might be wondering why we store each component type in a separate vec rather than something like this:

struct A_123(Vec<(T1, T2, T3)>);

There are a few reasons for this,

• The borrow checker will get angry at us if we have two Query's where one wants to access components T1 mutably and the other wants to access T2 immutably (We cant create an iterator over only *parts* of the (T1, T2, T3) tuple afterall)
• It's more performant to store the components in separate Vecs as when we iterate only T1 we dont needlessly load the T2 and T3 components into the cpu's cache.

With that explained lets look at some psuedocode for that spawn function we used earlier.

fn spawn(&mut self, data: (T1, T2, T3)) -> Entity {
  let a_123 = /* magically get the A_123 archetype */;

  let entity = self.entity_generator.spawn();
  a_123.entities.push(entity);

  a_123.column_1.push(data.0);
  a_123.column_2.push(data.1);
  a_123.column_3.push(data.2);

  entity
}

...Huh interesting how all this psuedocode looks awfully like Rust... I'm sure its just a coincedence ;)

There are a few things to talk about the above code:

• What's this entities field that suddenly appeared?
• Do we need to store any kind of metadata so that we know which entity every element in each of the component vecs corresponds to?

Both of these things are *actually* one and the same.
Because we store entities with *only* components [T1, T2, T3] in this archetype, the component vecs will always be the same length. This means that when we push components to the front of the vecs they'll all end up at the same index.

What we can do with this knowledge is have have a Vec<Entity> in the archetype and push the spawned Entity to the entities vec. We then have an implicit mapping where for every index in the component columns we can access the entities vec at the same index to check what entity this component is for. It's for the same reason that we can also access the other component columns at this index and the component will be for the same entity.

That last point is why Query's in archetype based ECS' are *so* fast. When we want to iterate all T1 and T2 components in our world we can just find every archetype that has a column for T1 and also a column for T2 and then blindly iterate both Vecs at the same time. Some psuedocode to hopefully help demonstrate what I mean:

fn iterate_T1_and_T2(archetype: &A_123) -> impl Iterator<Item = (&T1, &T2)> {
  archetype.column_1.iter().zip(archetype.column_2.iter())
}

Now that you (hopefully) have an understanding of how components get stored in archetype based ECS' and the performance advantages we can get from it, it's time to talk about one of the biggest flaws of the archetype model. Adding/Removing components is *really* slow.. like.. **really** slow.

Let's continue with our previous example of spawning our entity with components [T1, T2, T3]. It's sitting pretty comfortably in our A_123 archetype and we'll have super fast iteration times if we add more entities to this archetype and query for their components.

Now lets try adding a component to our entity. As previously mentioned our A_123 archetype stores entities which *only* have [T1, T2, T3] components as this lets us have amazing iteration speeds. Now let's say we add a component T4 to out entity, we would no longer fit this criteria which means we cant store our entity's components in A_123, we'll have to make a second archetype- A_1234 it will store components for entities who only have [T1, T2, T3, T4]

Lets write some quick psuedocode and see if the performance problem here speaks for itself:

fn add_T4_to_entity_in_A_123(&mut self, entity: Entity, data: T4) {
  let a_123 = /* magically get the A_123 archetype */;
  let index = /* magically get the index in the 
  component columns corresponding to the entity */;

  let a_1234 = /* magically get the A_1234 archetype */;

  a_1234.entities.push(entity);
  a_1234.column_4.push(data);

  // Oh no this doesnt look cheap at all
  a_1234.column_1.push(a_123.column_1.remove(index));
  a_1234.column_2.push(a_123.column_2.remove(index));
  a_1234.column_3.push(a_123.column_3.remove(index));

  self.archetypes.push(a_1234);
}

Aaaaaaaaand yep... we have to move each of the entity's components out of their columns in A_123. Then have to push the removed components to the respective columns in the other archetype (A_1234). That's a lot of moving around memory which isn't the fastest thing in the world- to say the least

There's not a whole lot we can do about this. The need to move all this memory around when adding/removing components is entirely necessary for the previously mentioned amazing iteration performance. Archetype ECS' are inherently about trading in add/remove performance in exchange for iteration performance.

There are others ways to model your ECS such as sparsesets which have signficantly better add/remove performance in exchange for worse iteration performance relative to archetype based ECS' (still fast though :P). There's no one best way to model an ECS, sparseset and archetype ECS' just make different tradeoffs :)

In the next part we'll actually create our Archetype struct

Creating our struct

Before we get started, in our src/lib.rs file we should add mod archetype; and then make a file at src/archetype.rs. All of the code in this chapter will be inside of this archetype.rs file

Our archetype struct needs to be able to store any number of component columns. The way to do this normally would be a Vec<ComponentColumn> however our component columns are going to be Vec's which are generic over the type they store. This is a bit problematic for since we want to store a set of things that aren't the same type

Luckily rust has a way of yeeting type information away- trait objects. We can implement a trait for every type of Vec and then store a Vec<Box<dyn TypeErasedVec>>. We can then downcase the trait object back to a concrete type whenever we need to. e.g. when we add/remove components

#![allow(unused)]
fn main() {
use std::any::Any;

trait ComponentColumn: Any {
    fn as_any(&self) -> &dyn Any;
    fn as_any_mut(&mut self) -> &mut dyn Any;
}

impl<T: 'static> ComponentColumn for Vec<T> {
    fn as_any(&self) -> &dyn Any {
        self
    }
    fn as_any_mut(&mut self) -> &mut dyn Any {
        self
    }
}

struct Archetype {
    entities: Vec<crate::Entity>,
    columns: Vec<Box<dyn ComponentColumn>>,
}
}

Here we define our ComponentColumn trait to be a supertrait of the Any trait. You might not have come across the Any trait before, it doesn't tend to come up very often when writing rust. The general idea behind the Any trait is that we cast a type to a trait object and then call downcast_ref/mut with a generic to turn it back into a concrete type. You can see the docs for std::any::Any here

Methods for creating an instance of our Archetype struct

We need some methods for creating instances of our Archetype struct. There are two situations that we'll be needing to create an Archetype in:

• When we add/remove a component we'll have to create the archetype that we need to move the entity to
• When we spawn an entity we'll have to create an archetype matching the component's given

We'll start with the add/remove situation because that's going to be easier to write.

The first thing we want to do is make a method on our ComponentColumn trait that returns a Box<dyn ComponentColumn> of the same type of Vec. This will let us create an archetype with the same set of columns as an existing one.

#![allow(unused)]
fn main() {
trait ComponentColumn: Any {
    fn as_any(&self) -> &dyn Any;
    fn as_any_mut(&mut self) -> &mut dyn Any;
    fn new_empty_column(&self) -> Box<dyn ComponentColumn>;
}

impl<T: 'static> ComponentColumn for Vec<T> {
    fn as_any(&self) -> &dyn Any {
        self
    }
    fn as_any_mut(&mut self) -> &mut dyn Any {
        self
    }

    fn new_empty_column(&self) -> Box<dyn ComponentColumn> {
        Box::new(Vec::<T>::new())
    }
}
}

Now lets look at the method for creating the archetype we want to move our entity to after an add/remove op:

#![allow(unused)]
fn main() {
impl Archetype {
    fn new_from_add<T: 'static>(from_archetype: &Archetype) -> Archetype {
        let mut columns: Vec<_> = from_archetype
            .columns
            .iter()
            .map(|column| column.new_empty_column())
            .collect();

        todo!("Actually add the column");

        Archetype {
            entities: Vec::new(),
            columns,
        }
    }

    fn new_from_remove<T: 'static>(from_archetype: &Archetype) -> Archetype {
        let mut columns: Vec<_> = from_archetype
            .columns
            .iter()
            .map(|column| column.new_empty_column())
            .collect();

        todo!("Actually remove the column");

        Archetype {
            entities: Vec::new(),
            columns,
        }
    }
}
}

We could *technically* merge these into one method and choose whether to add or remove depending on whether Vec<T> is already present in the columns. However whenever we call this method we'll *know* whether it's meant to be an add/remove, so if we make them separate methods we can add some checks that it's valid to add/remove a component from the archetype.

The code for new_from_add:

#![allow(unused)]
fn main() {
impl Archetype {
    fn new_from_add<T: 'static>(from_archetype: &Archetype) -> Archetype {
       let mut columns: Vec<_> = from_archetype
           .columns
           .iter()
           .map(|column| column.new_empty_column())
           .collect();
        /* snip */

        assert!(columns
            .iter()
            .find(|column| column.as_any().is::<Vec<T>>())
            .is_none());
        columns.push(Box::new(Vec::<T>::new()));

        /* snip */
       Archetype {
           entities: Vec::new(),
           columns,
       }
    }
}
}

We just assert! here instead of trying to recover because it's going to be a bug in our ECS if this assert fires and we really want that to happen loudly.

The code for new_from_remove:

#![allow(unused)]
fn main() {
    fn new_from_remove<T: 'static>(from_archetype: &Archetype) -> Archetype {
       let mut columns: Vec<_> = from_archetype
           .columns
           .iter()
           .map(|column| column.new_empty_column())
           .collect();
        /* snip */

        let idx = columns
            .iter()
            .position(|column| column.as_any().is::<Vec<T>>()).unwrap();
        columns.remove(idx);

        /* snip */
       Archetype {
           entities: Vec::new(),
           columns,
       }
    }
}

Same reason as above for why we just panic in here rather than try to recover :)

That should be everything we need for these two functions but before we move on lets add some tests to verify everything is working correctly

Tests for add/remove constructors

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;
    
    /* todo tests */
}
}

First tests we should add are some simple ones for testing those asserts/unwraps fire when trying to call new_from_(add/remove) on incorrect archetypes.

use std::any::Any;

trait ComponentColumn: Any {
    fn as_any(&self) -> &dyn Any;
    fn as_any_mut(&mut self) -> &mut dyn Any;
    fn new_empty_column(&self) -> Box<dyn ComponentColumn>;
}

impl<T: 'static> ComponentColumn for Vec<T> {
    fn as_any(&self) -> &dyn Any {
        self
    }
    fn as_any_mut(&mut self) -> &mut dyn Any {
        self
    }

    fn new_empty_column(&self) -> Box<dyn ComponentColumn> {
        Box::new(Vec::<T>::new())
    }
}

struct Archetype {
    entities: Vec<crate::Entity>,
    columns: Vec<Box<dyn ComponentColumn>>,
}

impl Archetype {
    fn new_from_add<T: 'static>(from_archetype: &Archetype) -> Archetype {
        let mut columns: Vec<_> = from_archetype
            .columns
            .iter()
            .map(|column| column.new_empty_column())
            .collect();

        assert!(columns
            .iter()
            .find(|column| column.as_any().is::<Vec<T>>())
            .is_none());
        columns.push(Box::new(Vec::<T>::new()));

        Archetype {
            entities: Vec::new(),
            columns,
        }
    }

    fn new_from_remove<T: 'static>(from_archetype: &Archetype) -> Archetype {
        let mut columns: Vec<_> = from_archetype
            .columns
            .iter()
            .map(|column| column.new_empty_column())
            .collect();

        let idx = columns
            .iter()
            .position(|column| column.as_any().is::<Vec<T>>())
            .unwrap();
        columns.remove(idx);

        Archetype {
            entities: Vec::new(),
            columns,
        }
    }

    fn builder() -> ColumnsBuilder {
        ColumnsBuilder(Vec::new())
    }

    fn new_from_columns(columns: ColumnsBuilder) -> Archetype {
        Archetype {
            entities: Vec::new(),
            columns: columns.0,
        }
    }
}

struct ColumnsBuilder(Vec<Box<dyn ComponentColumn>>);

impl ColumnsBuilder {
    fn with_column_type<T: 'static>(mut self) -> Self {
        if let Some(_) = self
            .0
            .iter()
            .find(|col| col.as_any().type_id() == std::any::TypeId::of::<Vec<T>>())
        {
            panic!("Attempted to create invalid archetype");
        }

        self.0.push(Box::new(Vec::<T>::new()));
        self
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn add_removes() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };

        let archetype = Archetype::new_from_add::<u32>(&archetype);
        assert!(archetype.columns.len() == 1);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u32>>())
            .is_some());

        let archetype = Archetype::new_from_add::<u64>(&archetype);
        assert!(archetype.columns.len() == 2);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u32>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u64>>())
            .is_some());

        let archetype = Archetype::new_from_remove::<u32>(&archetype);
        assert!(archetype.columns.len() == 1);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u64>>())
            .is_some());
    }

    #[test]
    #[should_panic]
    fn add_preexisting() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };
        let archetype = Archetype::new_from_add::<u32>(&archetype);
        let archetype = Archetype::new_from_add::<u32>(&archetype);
    }

    #[test]
    #[should_panic]
    fn remove_unpresent() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };
        let archetype = Archetype::new_from_remove::<u32>(&archetype);
    }

    #[test]
    #[should_panic]
    fn remove_unpresent_2() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };
        let archetype = Archetype::new_from_add::<u64>(&archetype);
        let archetype = Archetype::new_from_remove::<u32>(&archetype);
    }

    #[test]
    fn columns_builder() {
        let archetype = Archetype::new_from_columns(
            Archetype::builder()
                .with_column_type::<u32>()
                .with_column_type::<u64>()
                .with_column_type::<bool>(),
        );

        assert!(archetype.columns.len() == 3);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u32>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u64>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<bool>>())
            .is_some());
    }

    #[test]
    #[should_panic]
    fn columns_builder_duplicate() {
        let archetype = Archetype::new_from_columns(
            Archetype::builder()
                .with_column_type::<u32>()
                .with_column_type::<u32>(),
        );
    }
}

The next test we want is just something to call new_from_(add/remove) a bunch and assert that all the columns that we expect to be present are actually present:

use std::any::Any;

trait ComponentColumn: Any {
    fn as_any(&self) -> &dyn Any;
    fn as_any_mut(&mut self) -> &mut dyn Any;
    fn new_empty_column(&self) -> Box<dyn ComponentColumn>;
}

impl<T: 'static> ComponentColumn for Vec<T> {
    fn as_any(&self) -> &dyn Any {
        self
    }
    fn as_any_mut(&mut self) -> &mut dyn Any {
        self
    }

    fn new_empty_column(&self) -> Box<dyn ComponentColumn> {
        Box::new(Vec::<T>::new())
    }
}

struct Archetype {
    entities: Vec<crate::Entity>,
    columns: Vec<Box<dyn ComponentColumn>>,
}

impl Archetype {
    fn new_from_add<T: 'static>(from_archetype: &Archetype) -> Archetype {
        let mut columns: Vec<_> = from_archetype
            .columns
            .iter()
            .map(|column| column.new_empty_column())
            .collect();

        assert!(columns
            .iter()
            .find(|column| column.as_any().is::<Vec<T>>())
            .is_none());
        columns.push(Box::new(Vec::<T>::new()));

        Archetype {
            entities: Vec::new(),
            columns,
        }
    }

    fn new_from_remove<T: 'static>(from_archetype: &Archetype) -> Archetype {
        let mut columns: Vec<_> = from_archetype
            .columns
            .iter()
            .map(|column| column.new_empty_column())
            .collect();

        let idx = columns
            .iter()
            .position(|column| column.as_any().is::<Vec<T>>())
            .unwrap();
        columns.remove(idx);

        Archetype {
            entities: Vec::new(),
            columns,
        }
    }

    fn builder() -> ColumnsBuilder {
        ColumnsBuilder(Vec::new())
    }

    fn new_from_columns(columns: ColumnsBuilder) -> Archetype {
        Archetype {
            entities: Vec::new(),
            columns: columns.0,
        }
    }
}

struct ColumnsBuilder(Vec<Box<dyn ComponentColumn>>);

impl ColumnsBuilder {
    fn with_column_type<T: 'static>(mut self) -> Self {
        if let Some(_) = self
            .0
            .iter()
            .find(|col| col.as_any().type_id() == std::any::TypeId::of::<Vec<T>>())
        {
            panic!("Attempted to create invalid archetype");
        }

        self.0.push(Box::new(Vec::<T>::new()));
        self
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn add_removes() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };

        let archetype = Archetype::new_from_add::<u32>(&archetype);
        assert!(archetype.columns.len() == 1);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u32>>())
            .is_some());

        let archetype = Archetype::new_from_add::<u64>(&archetype);
        assert!(archetype.columns.len() == 2);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u32>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u64>>())
            .is_some());

        let archetype = Archetype::new_from_remove::<u32>(&archetype);
        assert!(archetype.columns.len() == 1);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u64>>())
            .is_some());
    }

    #[test]
    #[should_panic]
    fn add_preexisting() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };
        let archetype = Archetype::new_from_add::<u32>(&archetype);
        let archetype = Archetype::new_from_add::<u32>(&archetype);
    }

    #[test]
    #[should_panic]
    fn remove_unpresent() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };
        let archetype = Archetype::new_from_remove::<u32>(&archetype);
    }

    #[test]
    #[should_panic]
    fn remove_unpresent_2() {
        let archetype = Archetype {
            entities: Vec::new(),
            columns: Vec::new(),
        };
        let archetype = Archetype::new_from_add::<u64>(&archetype);
        let archetype = Archetype::new_from_remove::<u32>(&archetype);
    }

    #[test]
    fn columns_builder() {
        let archetype = Archetype::new_from_columns(
            Archetype::builder()
                .with_column_type::<u32>()
                .with_column_type::<u64>()
                .with_column_type::<bool>(),
        );

        assert!(archetype.columns.len() == 3);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u32>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u64>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<bool>>())
            .is_some());
    }

    #[test]
    #[should_panic]
    fn columns_builder_duplicate() {
        let archetype = Archetype::new_from_columns(
            Archetype::builder()
                .with_column_type::<u32>()
                .with_column_type::<u32>(),
        );
    }
}

Archetype constructor for when spawning entities

Now that we've finished up the constructors for when we add/remove components on an entity we need to make one for when we spawn an entity and need to build an archetype for it.

This one is a bit tricker because we want to take any # of component types when we create an archetype to spawn our entity into. We'll want some kind of builder struct that we can repeatedly call a function on to add component columns.

Something like this:

#![allow(unused)]
fn main() {
struct ColumnsBuilder(Vec<Box<dyn ComponentColumn>>);

impl ColumnsBuilder {
    fn with_column_type<T: 'static>(mut self) -> Self {
        if let Some(_) = self
            .0
            .iter()
            .find(|col| col.as_any().type_id() == std::any::TypeId::of::<Vec<T>>())
        {
            panic!("Attempted to create invalid archetype");
        }

        self.0.push(Box::new(Vec::<T>::new()));
        self
    }
}
}

We have to check that we don't try to create an archetype with two columns for the same component type. i.e. an archetype for entities with components [T, T] is nonsensical as an entity cannot have the same component added twice. Currently I just panic here if we detect that but it would be possible to return a Result here and propagate it up to the user

Now that we have a ColumnsBuilder lets add some methods to Archetype to use it

#![allow(unused)]
fn main() {
impl Archetype {
    /* snip */

    fn builder() -> ColumnsBuilder {
        ColumnsBuilder(Vec::new())
    }

    fn new_from_columns(columns: ColumnsBuilder) -> Archetype {
        Archetype {
            entities: Vec::new(),
            columns: columns.0,
        }
    }
}
}

An alternative way of implementing this would be to implement a trait for tuples of length 1 to some arbitrary limit and then create the columns in that trait. This has the downside of needing to use macros for the trait impl and we also would have a limit on how many components could be spawned on an entity without adding components separately. (We'll doing something like this later on when we implement iterators over our archetypes)

This should be us done with the method we'll use when creating an Archetype to spawn an entity into, we just need to add some tests before moving on :)

Tests for ColumnsBuilder

We'll want a test that our duplicate column checks work and also a general test that we have the expected columns after building an archetype from the ColumnsBuilder:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    /* snip */

    #[test]
    fn columns_builder() {
        let archetype = Archetype::new_from_columns(
            Archetype::builder()
                .with_column_type::<u32>()
                .with_column_type::<u64>()
                .with_column_type::<bool>(),
        );

        assert!(archetype.columns.len() == 3);
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u32>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<u64>>())
            .is_some());
        assert!(archetype
            .columns
            .iter()
            .find(|col| col.as_any().is::<Vec<bool>>())
            .is_some());
    }

    #[test]
    #[should_panic]
    fn columns_builder_duplicate() {
        let archetype = Archetype::new_from_columns(
            Archetype::builder()
                .with_column_type::<u32>()
                .with_column_type::<u32>(),
        );
    }
}
}

The full source code for this chapter can be viewed here