Dumb wip ecs engine

main.rs

use std::any::{Any, TypeId};
use std::collections::HashMap;
use std::fmt::Debug;
use std::hash::{Hash};
use std::hint::black_box;
use std::io::Read;
use std::marker::PhantomData;
use std::time::Instant;
use rand::Rng;

// This is dumb idea, I should use hibitset
// But anyway I think total 256 components are enough for me
// pub struct ComponentId(u8);
pub type ComponentId = u8;

#[derive(Copy, Clone, Debug, PartialOrd, PartialEq, Ord, Eq, Hash)]
pub struct BitSet {
    bitmask: [u64; 4],
    pub id: u8,
}

impl BitSet {
    pub fn new() -> Self {
        Self {
            bitmask: [0u64; 4],
            id: 0,
        }
    }

    pub fn insert_id(&mut self, id: u8) -> &mut Self {
        let index = id / 64;
        let position = id - index * 64;
        self.bitmask[index as usize] = self.bitmask[index as usize] | 1 << position;

        self
    }

    pub fn remove_id(&mut self, id: u8) -> &mut Self {
        let index = id / 64;
        let position = id - index * 64;
        let bit_to_remove = 1 << position;
        self.bitmask[index as usize] = !(self.bitmask[index as usize] ^ bit_to_remove);

        self
    }

    pub fn from_id(id: u8) -> Self {
        let mut bitmask = [0u64; 4];
        let index = id / 64;
        let position = id - index * 64;
        bitmask[index as usize] = 1 << position;

        Self {
            id,
            bitmask,
        }
    }

    pub fn contains(&self, other: &BitSet) -> bool {
        let mut result = true;

        for (a, b) in self.bitmask.iter().zip(other.bitmask.iter()) {
            result &= a & b == *b
        }

        result
    }

    pub fn contains_id(&self, id: u8) -> bool {
        let index = id / 64;
        let position = id - index * 64;

        self.bitmask[index as usize] & 1 << position > 0
    }
}

pub trait Component: 'static + Debug {
    fn get_type_id(&self) -> TypeId {
        TypeId::of::<Self>()
    }
}

#[derive(Debug)]
pub struct ComponentVec<T: Component>
{
    pub list: Vec<T>,
}

impl<T: Component> ComponentVec<T> {
    pub fn new() -> Self {
        Self {
            list: Vec::new()
        }
    }
}

#[derive(Debug)]
pub struct TypelessComponentVec
{
    list: Box<dyn Any>,
}

impl TypelessComponentVec {
    pub fn new<T: Component>() -> Self {
        Self {
            list: Box::new(ComponentVec::<T>::new()),
        }
    }

    pub fn get_mut<T: Component>(&mut self) -> &mut ComponentVec<T>
    {
        self.list.downcast_mut::<ComponentVec<T>>().unwrap()
    }

    pub fn get<T: Component>(&self) -> &ComponentVec<T>
    {
        self.list.downcast_ref::<ComponentVec<T>>().unwrap()
    }
}

#[derive(Debug)]
pub struct Archetype {
    pub set: HashMap<TypeId, TypelessComponentVec>,
    pub entity_row_map: HashMap<u64, usize>,
}

impl Archetype {
    pub fn new() -> Self {
        Self {
            set: HashMap::new(),
            entity_row_map: HashMap::new(),
        }
    }

    pub fn get<T: Component>(&self) -> &ComponentVec<T> {
        let list = self.set.get(&TypeId::of::<T>()).unwrap().get::<T>();

        list
    }

    pub fn get_mut<T: Component>(&mut self) -> &mut ComponentVec<T> {
        let list = self.set.get_mut(&TypeId::of::<T>()).unwrap().get_mut::<T>();

        list
    }

    pub fn print_list<T: Component>(&self) {
        let list = self.set.get(&TypeId::of::<T>()).unwrap().get::<T>();

        for a in list.list.iter() {
            println!("{:?}", a);
        }
    }
}


pub trait ComponentSet {
    fn get_bit_id_set(id_map: &HashMap<TypeId, ComponentId>) -> BitSet;
    fn insert(self, archetype: &mut Archetype, entity_id: u64);
    fn create_archetype(&self) -> Archetype;
    fn get_type_id() -> Vec<TypeId>;
}

impl<T: Component> ComponentSet for T {
    fn get_bit_id_set(id_map: &HashMap<TypeId, ComponentId>) -> BitSet {
        let mut bitset = BitSet::new();

        let id = id_map.get(&TypeId::of::<T>()).unwrap().clone();
        bitset.insert_id(id as u8);

        bitset
    }

    fn insert(self, archetype: &mut Archetype, entity_id: u64) {
        let b = archetype.set.get_mut(&TypeId::of::<T>()).unwrap().get_mut::<T>();
        b.list.push(self);
        archetype.entity_row_map.insert(entity_id, b.list.len() - 1);
    }

    fn create_archetype(&self) -> Archetype {
        let mut archetype = Archetype::new();
        archetype.set.insert(TypeId::of::<T>(), TypelessComponentVec::new::<T>());

        archetype
    }

    fn get_type_id() -> Vec<TypeId> {
        vec![TypeId::of::<T>()]
    }
}

impl<T: Component> ComponentSet for (T, )
{
    fn get_bit_id_set(id_map: &HashMap<TypeId, ComponentId>) -> BitSet {
        let mut bitset = BitSet::new();

        let id = id_map.get(&TypeId::of::<T>()).unwrap().clone();
        bitset.insert_id(id as u8);

        bitset
    }

    fn insert(self, archetype: &mut Archetype, entity_id: u64) {
        archetype.set.get_mut(&TypeId::of::<T>()).unwrap().get_mut::<T>().list.push(self.0);


        let len = archetype.set.get_mut(&TypeId::of::<T>()).unwrap().get_mut::<T>().list.len() - 1;
        archetype.entity_row_map.insert(entity_id, len);
    }

    fn create_archetype(&self) -> Archetype {
        let mut archetype = Archetype::new();
        archetype.set.insert(TypeId::of::<T>(), TypelessComponentVec::new::<T>());


        archetype
    }

    fn get_type_id() -> Vec<TypeId> {
        vec![TypeId::of::<T>()]
    }
}

impl<T: Component, V: Component> ComponentSet for (T, V)
{
    fn get_bit_id_set(id_map: &HashMap<TypeId, ComponentId>) -> BitSet {
        let mut bitset = BitSet::new();

        let id = id_map.get(&TypeId::of::<T>()).unwrap().clone();
        bitset.insert_id(id as u8);

        let id = id_map.get(&TypeId::of::<V>()).unwrap().clone();
        bitset.insert_id(id as u8);

        bitset
    }

    fn insert(self, archetype: &mut Archetype, entity_id: u64) {
        archetype.set.get_mut(&TypeId::of::<T>()).unwrap().get_mut::<T>().list.push(self.0);
        archetype.set.get_mut(&TypeId::of::<V>()).unwrap().get_mut::<V>().list.push(self.1);

        let len = archetype.set.get_mut(&TypeId::of::<T>()).unwrap().get_mut::<T>().list.len() - 1;
        archetype.entity_row_map.insert(entity_id, len);
    }

    fn create_archetype(&self) -> Archetype {
        let mut archetype = Archetype::new();
        archetype.set.insert(TypeId::of::<T>(), TypelessComponentVec::new::<T>());
        archetype.set.insert(TypeId::of::<V>(), TypelessComponentVec::new::<V>());

        archetype
    }

    fn get_type_id() -> Vec<TypeId> {
        vec![TypeId::of::<T>(), TypeId::of::<V>()]
    }
}

pub trait Query<'a> {
    type ResultType;
    fn get_bitset(component_map: &HashMap<TypeId, ComponentId>) -> BitSet;
    fn run(component_map: &'a HashMap<TypeId, ComponentId>, archetype_map: &'a HashMap<BitSet, Archetype>) -> Box<dyn Iterator<Item=Self::ResultType> + 'a>;
}


impl<'a, T: Component> Query<'a> for (T, ) {
    type ResultType = (&'a T, );

    #[inline(always)]
    fn get_bitset(component_map: &HashMap<TypeId, ComponentId>) -> BitSet {
        let mut bitset = BitSet::new();

        bitset.insert_id(component_map.get(&TypeId::of::<T>()).unwrap().clone());

        bitset
    }

    #[inline(always)]
    fn run(component_map: &'a HashMap<TypeId, ComponentId>, archetype_map: &'a HashMap<BitSet, Archetype>) -> Box<dyn Iterator<Item=Self::ResultType> + 'a> {
        let bitset = Self::get_bitset(component_map);

        Box::new(archetype_map
            .iter()
            .filter(move |x| x.0.contains(&bitset))
            .map(|x| &x.1.get::<T>().list)
            .flatten().map(|x| (x,)))
    }
}

impl<'a, T: Component, V: Component> Query<'a> for (T, V) {
    type ResultType = (&'a T, &'a V);

    #[inline(always)]
    fn get_bitset(component_map: &HashMap<TypeId, ComponentId>) -> BitSet {
        let mut bitset = BitSet::new();

        bitset.insert_id(component_map.get(&TypeId::of::<T>()).unwrap().clone());
        bitset.insert_id(component_map.get(&TypeId::of::<V>()).unwrap().clone());

        bitset
    }

    #[inline(always)]
    fn run(component_map: &'a HashMap<TypeId, ComponentId>, archetype_map: &'a HashMap<BitSet, Archetype>) -> Box<dyn Iterator<Item=Self::ResultType> + 'a> {
        let bitset = Self::get_bitset(component_map);

        let a = archetype_map
            .iter()
            .filter(move |x| x.0.contains(&bitset))
            .map(|x| x.1)
            .map(|x| x.get::<T>())
            .map(|x| &x.list)
            .flatten();

        let b = archetype_map
            .iter()
            .filter(move |x| x.0.contains(&bitset))
            .map(|x| x.1)
            .map(|x| x.get::<V>())
            .map(|x| &x.list)
            .flatten();

        let result = a.zip(b);

        Box::new(result)
    }
}

pub struct World {
    entity_id_counter: u64,
    component_id_counter: u8,
    pub component_id_map: HashMap<TypeId, ComponentId>,
    pub archetype_id_map: HashMap<BitSet, Archetype>,
}

impl World {
    pub fn new() -> Self {
        Self {
            entity_id_counter: 0,
            component_id_counter: 0,
            component_id_map: HashMap::new(),
            archetype_id_map: HashMap::new(),
        }
    }

    fn get_new_entity_id(&mut self) -> u64 {
        self.entity_id_counter += 1;
        self.entity_id_counter
    }

    fn get_new_component_id(&mut self) -> u8 {
        self.component_id_counter += 1;
        self.component_id_counter
    }

    pub fn insert_entity<T: ComponentSet>(&mut self, component_set: T) -> u64 {
        let entity_id = self.get_new_entity_id();

        for type_id in T::get_type_id() {
            if !self.component_id_map.contains_key(&type_id) {
                let new_id = self.get_new_component_id();
                self.component_id_map.insert(type_id, new_id);
            }
        }

        // let set_id = component_set.get_type_id();
        let bitset = T::get_bit_id_set(&self.component_id_map);

        if !self.archetype_id_map.contains_key(&bitset) {
            let new_archetype = component_set.create_archetype();
            self.archetype_id_map.insert(bitset, new_archetype);
        }

        let archetye = self.archetype_id_map.get_mut(&bitset).unwrap();
        component_set.insert(archetye, entity_id);

        entity_id
    }

    #[inline(always)]
    pub fn query<'a, T: Query<'a>>(&'a mut self) -> Box<dyn Iterator<Item=T::ResultType> + 'a> {
        T::run(&self.component_id_map, &self.archetype_id_map)
    }
}

#[derive(Debug)]
struct Foo {
    foo: u8,
}

impl Component for Foo {}

#[derive(Debug, Copy, Clone)]
struct Bar {
    bar: u8,
}

impl Component for Bar {}

fn main() {
    let mut world = World::new();
    let mut rng = rand::thread_rng();

    const N: usize = 10_000_000;

    let mut vec = Vec::with_capacity(N);

    for _ in 0..N {
        vec.push(Bar { bar: black_box(rng.gen()) });
    }
    let mut vec2 = Vec::with_capacity(N);

    for i in 0..N {
        vec2.push((&vec[i],));
    }

    let start_time = Instant::now();
    let mut sum = 0u64;

    for (i,) in vec2 {
        sum += black_box(i.bar) as u64;
    }

    println!("Array: {}ms Sum: {}", start_time.elapsed().as_micros(), sum);

    for _ in 0..N {
        world.insert_entity(Bar { bar: black_box(rng.gen()) });
    }

    let query = world.query::<(Bar, )>();

    let start_time = Instant::now();
    let mut sum = 0u64;

    for (bar,) in query {
        sum += bar.bar as u64;
    }

    println!("Query: {:?}ms Sum: {}", start_time.elapsed().as_micros(), sum);


    let bitset = <(Bar,) as Query>::get_bitset(&world.component_id_map);

    let query = world.archetype_id_map
        .iter()
        .filter(move |x| x.0.contains(&bitset))
        .map(|x| &x.1.get::<Bar>().list).flatten();

    let start_time = Instant::now();
    let mut sum = 0u64;

    for (bar) in query {
        sum += black_box(bar.bar) as u64;
    }

    println!("Direct: {:?}ms Sum: {}", start_time.elapsed().as_micros(), sum);
}