diff options
Diffstat (limited to 'ecs/src/component')
| -rw-r--r-- | ecs/src/component/local.rs | 3 | ||||
| -rw-r--r-- | ecs/src/component/storage.rs | 762 | ||||
| -rw-r--r-- | ecs/src/component/storage/archetype.rs | 216 | ||||
| -rw-r--r-- | ecs/src/component/storage/graph.rs | 269 |
4 files changed, 747 insertions, 503 deletions
diff --git a/ecs/src/component/local.rs b/ecs/src/component/local.rs index 20627bf..ad79f6f 100644 --- a/ecs/src/component/local.rs +++ b/ecs/src/component/local.rs @@ -11,11 +11,10 @@ pub struct Local<'world, LocalComponent: Component> local_component: ComponentRefMut<'world, LocalComponent>, } -unsafe impl<'world, LocalComponent> SystemParam<'world> for Local<'world, LocalComponent> +impl<'world, LocalComponent> SystemParam<'world> for Local<'world, LocalComponent> where LocalComponent: Component, { - type Flags = (); type Input = LocalComponent; fn initialize<SystemImpl>( diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs index ffd682e..0e1a03d 100644 --- a/ecs/src/component/storage.rs +++ b/ecs/src/component/storage.rs @@ -1,465 +1,312 @@ use std::any::type_name; -use std::borrow::Borrow; -use std::cell::RefCell; -use std::collections::{HashMap, HashSet}; -use std::slice::Iter as SliceIter; -use std::vec::IntoIter as OwnedVecIter; - -use crate::archetype::Id as ArchetypeId; -use crate::component::{ - Component, - IsOptional as ComponentIsOptional, - Metadata as ComponentMetadata, +use std::iter::{Chain, Flatten}; + +use hashbrown::{HashMap, HashSet}; + +use crate::component::storage::archetype::{ + Archetype, + ArchetypeEntity, + Id as ArchetypeId, +}; +use crate::component::storage::graph::{ + ArchetypeAddEdgeRecursiveIter, + ArchetypeEdges, + Graph, }; +use crate::component::{Component, Metadata as ComponentMetadata}; use crate::type_name::TypeName; -use crate::uid::Uid; -use crate::util::Sortable; +use crate::uid::{Kind as UidKind, Uid}; use crate::EntityComponent; +pub mod archetype; + +mod graph; + #[derive(Debug, Default)] pub struct Storage { - archetypes: Vec<Archetype>, - archetype_lookup: RefCell<HashMap<ArchetypeId, ArchetypeLookupEntry>>, + graph: Graph, entity_archetype_lookup: HashMap<Uid, ArchetypeId>, } impl Storage { - pub fn find_entities<CompMetadataList>( + pub fn iter_archetypes_with_comps( &self, - mut components_metadata: CompMetadataList, + component_metadata: impl AsRef<[ComponentMetadata]>, ) -> ArchetypeRefIter<'_> - where - CompMetadataList: Sortable<Item = ComponentMetadata>, - CompMetadataList: AsRef<[ComponentMetadata]>, { - components_metadata.sort_by_key_b(|component_metadata| component_metadata.id); - - let archetype_id = ArchetypeId::from_components_metadata(&components_metadata); + let archetype_id = ArchetypeId::from_components_metadata(&component_metadata); - // This looks stupid but the borrow checker complains otherwise - if self.archetype_lookup.borrow().contains_key(&archetype_id) { - return self.iter_archetypes_by_lookup(archetype_id); + ArchetypeRefIter { + storage: self, + iter: [archetype_id].into_iter().chain( + self.graph + .recurse_archetype_add_edges(archetype_id) + .into_iter() + .flatten() + .flatten(), + ), + visited: HashSet::new(), } - - let comp_ids_set = create_non_opt_component_id_set(components_metadata.as_ref()); - - let matching_archetype_indices = self - .archetypes - .iter() - .enumerate() - .filter_map(|(index, archetype)| { - if archetype.component_ids_is_superset(&comp_ids_set) { - return Some(index); - } - - None - }) - .collect(); - - self.archetype_lookup.borrow_mut().insert( - archetype_id, - ArchetypeLookupEntry { - component_ids: comp_ids_set, - archetype_indices: matching_archetype_indices, - }, - ); - - self.iter_archetypes_by_lookup(archetype_id) } - pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype> + pub fn get_archetype_by_id(&self, id: ArchetypeId) -> Option<&Archetype> { - let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; - - let archetype_index = - self.find_archetype_index_with_entity(*archetype_id, entity_uid)?; - - self.archetypes.get(archetype_index) + Some(self.graph.get_node_by_id(id)?.archetype()) } - #[cfg_attr(feature = "debug", tracing::instrument(skip_all))] - pub fn push_entity( - &mut self, - entity_uid: Uid, - mut components: Vec<Box<dyn Component>>, - ) -> Result<(ArchetypeId, Uid), Error> + pub fn create_entity(&mut self, uid: Uid) -> Result<(), Error> { - if self.entity_archetype_lookup.contains_key(&entity_uid) { - return Err(Error::EntityAlreadyExists(entity_uid)); - } - - components.sort_by_key(|component| component.self_id()); - - #[cfg(feature = "debug")] - tracing::debug!( - "Pushing entity with components: ({})", - components - .iter() - .map(|component| component.type_name()) - .collect::<Vec<_>>() - .join(", ") - ); - - let archetype_id = ArchetypeId::from_components_metadata( - &components - .iter() - .map(|component| ComponentMetadata::get(&**component)) - .collect::<Vec<_>>(), - ); - - let comp_ids_set = create_non_opt_component_id_set( - components - .iter() - .map(|component| ComponentMetadata::get(&**component)), - ); - - let archetype_index = - self.get_or_create_archetype(archetype_id, &comp_ids_set, &components); + debug_assert_eq!(uid.kind(), UidKind::Entity); - self.populate_matching_archetype_lookup_entries(&comp_ids_set, archetype_index); + if self.entity_archetype_lookup.contains_key(&uid) { + return Err(Error::EntityAlreadyExists(uid)); + } - let archetype = self - .archetypes - .get_mut(archetype_index) - .expect("Archetype is gone"); + let empty_archetype_id = ArchetypeId::from_components_metadata(&[]); - archetype.push_entity(entity_uid, components); + let archetype_node = self.graph.get_or_create_node(empty_archetype_id, &[]); - archetype - .entity_lookup - .insert(entity_uid, archetype.entities.len() - 1); + archetype_node + .archetype_mut() + .push_entity(ArchetypeEntity { uid, components: vec![] }); - self.entity_archetype_lookup - .insert(entity_uid, archetype_id); + self.entity_archetype_lookup.insert(uid, empty_archetype_id); - Ok((archetype_id, entity_uid)) + Ok(()) } - pub fn add_components_to_entity( + pub fn remove_entity( &mut self, entity_uid: Uid, - components: Vec<Box<dyn Component>>, - ) -> Option<()> + ) -> Result<Vec<EntityComponent>, Error> { - let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; - - let archetype_index = - self.find_archetype_index_with_entity(*archetype_id, entity_uid)?; - - let archetype = self.archetypes.get_mut(archetype_index)?; + let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { + return Err(Error::EntityDoesNotExist(entity_uid)); + }; - let contains_component_already = components - .iter() - .any(|component| archetype.component_ids.contains_key(&component.self_id())); - - if contains_component_already { - let component_cnt = components.len(); - - // TODO: return error - panic!( - "Entity with UID {:?} already contains one or more component(s) ({})", - entity_uid, - components - .iter() - .flat_map(|component| [component.type_name(), ", "]) - .enumerate() - .take_while(|(index, _)| { *index < (component_cnt * 2) - 1 }) - .map(|(_, component)| component) - .collect::<String>() - ); - } + let archetype_node = self + .graph + .get_node_by_id_mut(*archetype_id) + .expect("Archetype should exist"); - let entity = archetype.take_entity(entity_uid)?; + let entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); self.entity_archetype_lookup.remove(&entity_uid); - self.push_entity( - entity_uid, - entity - .components - .into_iter() - .map(|component| component.component.into_inner()) - .chain(components) - .collect(), - ) - .expect("Not supposed to return Err since the entity is removed"); - - Some(()) + Ok(entity.components) } - pub fn remove_components_from_entity( - &mut self, - entity_uid: Uid, - component_ids: impl IntoIterator<Item = Uid>, - ) -> Option<()> + pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype> { let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; - let archetype_index = - self.find_archetype_index_with_entity(*archetype_id, entity_uid)?; - - let archetype = self.archetypes.get_mut(archetype_index)?; - - let entity = archetype.take_entity(entity_uid)?; - - let component_ids_set = component_ids.into_iter().collect::<HashSet<_>>(); - - self.entity_archetype_lookup.remove(&entity_uid); - - self.push_entity( - entity_uid, - entity - .components - .into_iter() - .map(|component| component.component.into_inner()) - .filter(|component| !component_ids_set.contains(&component.self_id())) - .collect(), - ) - .expect("Not supposed to return Err since the entity is removed"); - - Some(()) + self.get_archetype_by_id(*archetype_id) } - fn populate_matching_archetype_lookup_entries( + pub fn add_entity_component( &mut self, - comp_ids_set: &HashSet<Uid>, - archetype_index: usize, - ) + entity_uid: Uid, + component: Box<dyn Component>, + ) -> Result<(), Error> { - let mut archetype_lookup = self.archetype_lookup.borrow_mut(); - - for (_, lookup_entry) in archetype_lookup.iter_mut() { - if &lookup_entry.component_ids == comp_ids_set { - continue; - } - - // There shouldn't be duplicate archetype indices in the lookup entry - if lookup_entry.archetype_indices.contains(&archetype_index) { - continue; - } + debug_assert!( + !component.self_is_optional(), + "Adding a optional component to a entity is not supported" + ); - if lookup_entry.component_ids.is_subset(comp_ids_set) { - lookup_entry.archetype_indices.push(archetype_index); - } + let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { + return Err(Error::EntityDoesNotExist(entity_uid)); + }; + + let archetype_id = *archetype_id; + + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + if archetype_node + .archetype() + .has_component_with_id(component.self_id()) + { + return Err(Error::EntityAlreadyHasComponent { + entity: entity_uid, + component: component.self_id(), + }); } - } - fn get_or_create_archetype( - &mut self, - archetype_id: ArchetypeId, - comp_ids_set: &HashSet<Uid>, - components: &[Box<dyn Component>], - ) -> usize - { - let mut archetype_lookup = self.archetype_lookup.borrow_mut(); - - let lookup_entry = archetype_lookup.entry(archetype_id).or_insert_with(|| { - ArchetypeLookupEntry { - component_ids: comp_ids_set.clone(), - archetype_indices: Vec::with_capacity(1), - } - }); - - if lookup_entry.archetype_indices.is_empty() { - self.archetypes.push(Archetype::new( - components.iter().map(|component| component.self_id()), - )); - - lookup_entry - .archetype_indices - .push(self.archetypes.len() - 1); - } + let add_edge_archetype_id = archetype_node + .get_or_insert_edges(component.self_id(), ArchetypeEdges::default) + .add + .unwrap_or_else(|| { + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + let (add_edge_id, add_edge_comp_ids) = + archetype_node.make_add_edge(component.self_id()); + + archetype_node + .get_edges_mut(component.self_id()) + .expect("Edges for component in archetype should exist") + .add = Some(add_edge_id); + + if !self.graph.contains_archetype(add_edge_id) { + self.graph.create_node(add_edge_id, &add_edge_comp_ids); + } - // SAFETY: Above, we push a archetype index if archetype_indices is empty so this - // cannot fail - unsafe { *lookup_entry.archetype_indices.first().unwrap_unchecked() } - } + add_edge_id + }); - fn find_archetype_index_with_entity( - &self, - archetype_id: ArchetypeId, - entity_uid: Uid, - ) -> Option<usize> - { - let archetype_lookup = self.archetype_lookup.borrow_mut(); + { + let add_edge_archetype_node = self + .graph + .get_node_by_id_mut(add_edge_archetype_id) + .expect("Add edge archetype should exist"); - let archetype_lookup_entry = archetype_lookup.get(&archetype_id)?; + let add_edge_archetype_edges = add_edge_archetype_node + .get_or_insert_edges(component.self_id(), ArchetypeEdges::default); - // TODO: Also have a hashmap for precise archetype ID -> archetype index lookup. - // This way is slow - archetype_lookup_entry - .archetype_indices - .iter() - .find(|archetype_index| { - let Some(archetype) = self.archetypes.get(**archetype_index) else { - return false; - }; - - archetype.has_entity(entity_uid) - }) - .copied() - } + add_edge_archetype_edges.remove = Some(archetype_id); + } - fn iter_archetypes_by_lookup(&self, archetype_id: ArchetypeId) - -> ArchetypeRefIter<'_> - { - let archetype_lookup = self.archetype_lookup.borrow(); + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); - // The archetype indices have to be cloned to prevent a panic when query - // iterations are nested. The panic happens because the archetype_lookup RefCell - // is borrowed and it tries to mutably borrow it - let archetype_indices = archetype_lookup - .get(&archetype_id) - .unwrap() - .archetype_indices - .clone(); + let mut entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); - ArchetypeRefIter { - indices: archetype_indices.into_iter(), - archetypes: &self.archetypes, - } - } -} + let add_edge_archetype = self + .graph + .get_node_by_id_mut(add_edge_archetype_id) + .expect("Add edge archetype should exist") + .archetype_mut(); -/// Component storage error -#[derive(Debug, Clone, thiserror::Error)] -pub enum Error -{ - #[error("Entity already exists")] - EntityAlreadyExists(Uid), -} + let component_index = add_edge_archetype + .get_index_for_component(component.self_id()) + .expect("Archetype should have index for component"); -impl TypeName for Storage -{ - fn type_name(&self) -> &'static str - { - type_name::<Self>() - } -} + entity.components.insert(component_index, component.into()); -#[derive(Debug)] -struct ArchetypeLookupEntry -{ - component_ids: HashSet<Uid>, - archetype_indices: Vec<usize>, -} + add_edge_archetype.push_entity(entity); -#[derive(Debug)] -pub struct Archetype -{ - component_ids: HashMap<Uid, usize>, - entity_lookup: HashMap<Uid, usize>, - entities: Vec<ArchetypeEntity>, -} + self.entity_archetype_lookup + .insert(entity_uid, add_edge_archetype_id); -impl Archetype -{ - fn new(component_ids: impl IntoIterator<Item = Uid>) -> Self - { - Self { - component_ids: component_ids - .into_iter() - .enumerate() - .map(|(index, component_id)| (component_id, index)) - .collect(), - entity_lookup: HashMap::new(), - entities: Vec::new(), - } + Ok(()) } - pub fn component_ids_is_superset(&self, other_component_ids: &HashSet<Uid>) -> bool + pub fn remove_entity_component( + &mut self, + entity_uid: Uid, + component_id: Uid, + ) -> Result<(), Error> { - if other_component_ids.len() <= self.component_ids.len() { - other_component_ids - .iter() - .all(|v| self.component_ids.contains_key(v)) - } else { - false + let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { + return Err(Error::EntityDoesNotExist(entity_uid)); + }; + + let archetype_id = *archetype_id; + + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + if !archetype_node + .archetype() + .has_component_with_id(component_id) + { + return Err(Error::EntityDoesNotHaveComponent { + entity: entity_uid, + component: component_id, + }); } - } - - pub fn get_entity(&self, entity_uid: Uid) -> Option<&ArchetypeEntity> - { - let entity_index = *self.entity_lookup.get(&entity_uid)?; - self.entities.get(entity_index) - } + let remove_edge_id = archetype_node + .get_or_insert_edges(component_id, ArchetypeEdges::default) + .remove + .unwrap_or_else(|| { + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + let (remove_edge_id, remove_edge_comp_ids) = + archetype_node.make_remove_edge(component_id); + + archetype_node + .get_edges_mut(component_id) + .expect("Edges for component in archetype should exist") + .remove = Some(remove_edge_id); + + if !self.graph.contains_archetype(remove_edge_id) { + self.graph + .create_node(remove_edge_id, &remove_edge_comp_ids); + } - pub fn entities(&self) -> EntityIter<'_> - { - EntityIter { iter: self.entities.iter() } - } + remove_edge_id + }); - pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize> - { - self.component_ids.get(&component_id).copied() - } + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); - fn push_entity( - &mut self, - entity_uid: Uid, - components: impl IntoIterator<Item = Box<dyn Component>>, - ) - { - self.entities.push(ArchetypeEntity { - uid: entity_uid, - components: components.into_iter().map(Into::into).collect(), - }); - } + let mut entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); - pub fn take_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity> - { - let entity_index = self.entity_lookup.remove(&entity_uid)?; + let (comp_to_remove_index, _) = entity + .components + .iter() + .enumerate() + .find(|(_, comp)| comp.id == component_id) + .expect("Entity should contain component"); - let entity = self.entities.remove(entity_index); + entity.components.remove(comp_to_remove_index); - for index in self.entity_lookup.values_mut() { - if *index > entity_index { - *index -= 1; - } - } + self.graph + .get_node_by_id_mut(remove_edge_id) + .expect("Remove edge archetype should exist") + .archetype_mut() + .push_entity(entity); - Some(entity) - } + self.entity_archetype_lookup + .insert(entity_uid, remove_edge_id); - fn has_entity(&self, entity_uid: Uid) -> bool - { - self.entity_lookup.contains_key(&entity_uid) + Ok(()) } } -#[derive(Debug)] -pub struct ArchetypeEntity -{ - uid: Uid, - components: Vec<EntityComponent>, -} - -impl ArchetypeEntity +impl TypeName for Storage { - pub fn uid(&self) -> Uid - { - self.uid - } - - pub fn components(&self) -> &[EntityComponent] - { - &self.components - } - - pub fn get_component(&self, index: usize) -> Option<&EntityComponent> + fn type_name(&self) -> &'static str { - self.components.get(index) + type_name::<Self>() } } #[derive(Debug)] -pub struct ArchetypeRefIter<'component_storage> +pub struct ArchetypeRefIter<'storage> { - indices: OwnedVecIter<usize>, - archetypes: &'component_storage [Archetype], + storage: &'storage Storage, + iter: Chain< + std::array::IntoIter<ArchetypeId, 1>, + Flatten<Flatten<std::option::IntoIter<ArchetypeAddEdgeRecursiveIter<'storage>>>>, + >, + visited: HashSet<ArchetypeId>, } impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage> @@ -468,154 +315,67 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage> fn next(&mut self) -> Option<Self::Item> { - let archetype_index = self.indices.next()?; + let archetype_id = self + .iter + .find(|archetype_id| !self.visited.contains(archetype_id))?; + + let archetype = self.storage.get_archetype_by_id(archetype_id)?; + + self.visited.insert(archetype_id); - Some( - self.archetypes - .get(archetype_index) - .expect("Archetype index in archetype lookup entry was not found"), - ) + Some(archetype) } } -#[derive(Debug)] -pub struct EntityIter<'archetype> +#[derive(Debug, thiserror::Error)] +pub enum Error { - iter: SliceIter<'archetype, ArchetypeEntity>, -} + #[error("Entity with ID {0:?} already exists")] + EntityAlreadyExists(Uid), -impl<'archetype> Iterator for EntityIter<'archetype> -{ - type Item = &'archetype ArchetypeEntity; + #[error("Entity with ID {0:?} does not exist")] + EntityDoesNotExist(Uid), - fn next(&mut self) -> Option<Self::Item> + #[error("Entity with ID {entity:?} already has component with ID {component:?}")] + EntityAlreadyHasComponent { - self.iter.next() - } -} + entity: Uid, component: Uid + }, -fn create_non_opt_component_id_set<Item>( - component_metadata_iter: impl IntoIterator<Item = Item>, -) -> HashSet<Uid> -where - Item: Borrow<ComponentMetadata>, -{ - component_metadata_iter - .into_iter() - .filter_map(|item| { - let component_metadata = item.borrow(); - - if component_metadata.is_optional == ComponentIsOptional::Yes { - return None; - } - - Some(component_metadata.id) - }) - .collect::<HashSet<_>>() + #[error("Entity with ID {entity:?} does not have component with ID {component:?}")] + EntityDoesNotHaveComponent + { + entity: Uid, component: Uid + }, } #[cfg(test)] mod tests { - - use ecs_macros::Component; - - use super::Storage; - use crate::archetype::Id as ArchetypeId; - use crate::component::{ - Component, - IsOptional as ComponentIsOptional, - Metadata as ComponentMetadata, - }; + use crate::component::storage::archetype::Id as ArchetypeId; + use crate::component::storage::Storage; use crate::uid::{Kind as UidKind, Uid}; - #[derive(Debug, Component)] - struct HealthPotion - { - _hp_restoration: u32, - } - - #[derive(Debug, Component)] - struct Hookshot - { - _range: u32, - } - - #[derive(Debug, Component)] - struct DekuNut - { - _throwing_damage: u32, - } - - #[derive(Debug, Component)] - struct Bow - { - _damage: u32, - } - - #[derive(Debug, Component)] - struct IronBoots; - #[test] - fn push_entity_works() + fn create_entity_works() { - let mut component_storage = Storage::default(); + let mut new_storage = Storage::default(); - component_storage - .push_entity( - Uid::new_unique(UidKind::Entity), - vec![ - Box::new(HealthPotion { _hp_restoration: 12 }), - Box::new(Hookshot { _range: 50 }), - ], - ) - .expect("Expected Ok"); + let uid = Uid::new_unique(UidKind::Entity); - assert_eq!(component_storage.archetypes.len(), 1); + new_storage.create_entity(uid).expect("Expected Ok"); - let archetype = component_storage - .archetypes - .first() - .expect("Expected a archetype in archetypes Vec"); + let archetype_node = new_storage + .graph + .get_node_by_id(ArchetypeId::from_components_metadata(&[])) + .expect("Archetype for entities with no component doesn't exist"); - assert_eq!(archetype.component_ids.len(), 2); + assert_eq!(archetype_node.archetype().component_cnt(), 0); + assert_eq!(archetype_node.archetype().entity_cnt(), 1); - // One entity - assert_eq!(archetype.entities.len(), 1); - - let entity_components = archetype - .entities - .first() - .expect("Expected a entity in archetype"); - - assert_eq!(entity_components.components.len(), 2); - - assert_eq!(component_storage.archetype_lookup.borrow().len(), 1); - - let mut components_metadata = [ - ComponentMetadata { - id: HealthPotion::id(), - is_optional: ComponentIsOptional::No, - }, - ComponentMetadata { - id: Hookshot::id(), - is_optional: ComponentIsOptional::No, - }, - ]; - - components_metadata.sort_by_key(|comp_metadata| comp_metadata.id); - - let archetype_lookup = component_storage.archetype_lookup.borrow(); - - let lookup_entry = archetype_lookup - .get(&ArchetypeId::from_components_metadata(&components_metadata)) - .expect("Expected entry in archetype lookup map"); - - let first_archetype_index = lookup_entry - .archetype_indices - .first() - .expect("Expected archetype lookup to contain a archetype reference"); - - assert_eq!(*first_archetype_index, 0); + assert_eq!( + new_storage.entity_archetype_lookup.get(&uid).copied(), + Some(ArchetypeId::from_components_metadata(&[])) + ); } } diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs new file mode 100644 index 0000000..ee3d7f8 --- /dev/null +++ b/ecs/src/component/storage/archetype.rs @@ -0,0 +1,216 @@ +use std::borrow::Borrow; +use std::hash::{DefaultHasher, Hash, Hasher}; +use std::slice::Iter as SliceIter; + +use hashbrown::HashMap; + +use crate::component::Metadata as ComponentMetadata; +use crate::uid::{Kind as UidKind, Uid}; +use crate::util::HashMapExt; +use crate::EntityComponent; + +#[derive(Debug)] +pub struct Archetype +{ + id: Id, + entities: Vec<ArchetypeEntity>, + entity_index_lookup: HashMap<Uid, usize>, + component_index_lookup: HashMap<Uid, usize>, +} + +impl Archetype +{ + pub fn new(id: Id, component_ids: impl IntoIterator<Item: Borrow<Uid>>) -> Self + { + Self { + id, + entities: Vec::new(), + entity_index_lookup: HashMap::new(), + component_index_lookup: component_ids + .into_iter() + .enumerate() + .map(|(index, id)| (*id.borrow(), index)) + .collect(), + } + } + + pub fn id(&self) -> Id + { + self.id + } + + pub fn is_superset(&self, other: &Self) -> bool + { + self.component_index_lookup + .keys_is_superset(&other.component_index_lookup) + } + + pub fn get_entity_by_id(&self, entity_uid: Uid) -> Option<&ArchetypeEntity> + { + let index = *self.entity_index_lookup.get(&entity_uid)?; + + Some(self.entities.get(index).unwrap_or_else(|| { + panic!( + "In invalid state! Index of entity with ID {entity_uid:?} is out of bounds" + ); + })) + } + + pub fn push_entity(&mut self, entity: ArchetypeEntity) + { + self.entity_index_lookup + .insert(entity.uid, self.entities.len()); + + self.entities.push(entity); + } + + pub fn remove_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity> + { + //debug_assert_eq!(entity_uid.kind(), UidKind::Entity); + + let entity_index = self.entity_index_lookup.remove(&entity_uid)?; + + if self.entities.len() == 1 { + return Some(self.entities.remove(entity_index)); + } + + let last_entity_uid = self + .entities + .last() + .expect(concat!( + "Invalid state. No entities in archetype but entry was ", + "removed successfully from entity index lookup" + )) + .uid; + + // By using swap_remove, no memory reallocation occurs and only one index in the + // entity lookup needs to be updated + let removed_entity = self.entities.swap_remove(entity_index); + + self.entity_index_lookup + .insert(last_entity_uid, entity_index); + + Some(removed_entity) + } + + pub fn entities(&self) -> EntityIter<'_> + { + EntityIter { iter: self.entities.iter() } + } + + pub fn entity_cnt(&self) -> usize + { + self.entities.len() + } + + pub fn component_cnt(&self) -> usize + { + self.component_index_lookup.len() + } + + pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize> + { + self.component_index_lookup.get(&component_id).copied() + } + + pub fn component_ids_unsorted(&self) -> impl Iterator<Item = Uid> + '_ + { + self.component_index_lookup.keys().copied() + } + + pub fn has_component_with_id(&self, component_id: Uid) -> bool + { + debug_assert_eq!(component_id.kind(), UidKind::Component); + + self.component_index_lookup.contains_key(&component_id) + } +} + +#[derive(Debug)] +pub struct EntityIter<'archetype> +{ + iter: SliceIter<'archetype, ArchetypeEntity>, +} + +impl<'archetype> Iterator for EntityIter<'archetype> +{ + type Item = &'archetype ArchetypeEntity; + + fn next(&mut self) -> Option<Self::Item> + { + self.iter.next() + } +} + +#[derive(Debug)] +pub struct ArchetypeEntity +{ + pub uid: Uid, + pub components: Vec<EntityComponent>, +} + +/// Archetype ID. +#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)] +pub struct Id +{ + hash: u64, +} + +impl Id +{ + pub fn new(component_ids: &impl AsRef<[Uid]>) -> Self + { + if component_ids.as_ref().len() == 0 { + return Self { hash: 0 }; + } + + debug_assert!( + component_ids.as_ref().is_sorted(), + "Cannot create archetype ID from unsorted component IDs" + ); + + let mut hasher = DefaultHasher::new(); + + for component_id in component_ids.as_ref() { + component_id.hash(&mut hasher); + } + + Self { hash: hasher.finish() } + } + + pub fn from_components_metadata( + components_metadata: &impl AsRef<[ComponentMetadata]>, + ) -> Self + { + if components_metadata.as_ref().len() == 0 { + return Self { hash: 0 }; + } + + debug_assert!( + components_metadata + .as_ref() + .is_sorted_by_key(|comp_metadata| comp_metadata.id), + "Cannot create archetype ID from a unsorted component metadata list" + ); + + let component_ids = + components_metadata + .as_ref() + .iter() + .filter_map(|component_metadata| { + if component_metadata.is_optional { + return None; + } + + Some(component_metadata.id) + }); + + let mut hasher = DefaultHasher::new(); + + for component_id in component_ids { + component_id.hash(&mut hasher); + } + + Self { hash: hasher.finish() } + } +} diff --git a/ecs/src/component/storage/graph.rs b/ecs/src/component/storage/graph.rs new file mode 100644 index 0000000..fe97933 --- /dev/null +++ b/ecs/src/component/storage/graph.rs @@ -0,0 +1,269 @@ +use hashbrown::hash_map::Values as HashMapValueIter; +use hashbrown::HashMap; + +use crate::component::storage::archetype::{Archetype, Id as ArchetypeId}; +use crate::uid::{Kind as UidKind, Uid}; + +#[derive(Debug, Default)] +pub struct Graph +{ + nodes: Vec<ArchetypeNode>, + archetype_index_lookup: HashMap<ArchetypeId, usize>, +} + +impl Graph +{ + pub fn create_node(&mut self, id: ArchetypeId, component_ids: &impl AsRef<[Uid]>) + { + debug_assert!(!self.contains_archetype(id)); + + let _ = self.get_or_create_node(id, component_ids); + } + + pub fn get_or_create_node( + &mut self, + id: ArchetypeId, + component_ids: &impl AsRef<[Uid]>, + ) -> &mut ArchetypeNode + { + let index = *self.archetype_index_lookup.entry(id).or_insert_with(|| { + self.nodes.push(ArchetypeNode { + archetype: Archetype::new(id, component_ids.as_ref()), + edges: HashMap::new(), + }); + + self.nodes.len() - 1 + }); + + self.create_missing_edges(id); + + self.nodes + .get_mut(index) + .expect("Archetype index from lookup is out of bounds") + } + + pub fn contains_archetype(&self, id: ArchetypeId) -> bool + { + self.archetype_index_lookup.contains_key(&id) + } + + pub fn get_node_by_id(&self, id: ArchetypeId) -> Option<&ArchetypeNode> + { + let index = self.archetype_index_lookup.get(&id)?; + + Some(self.nodes.get(*index).unwrap_or_else(|| { + panic!("In invalid state! Index of archetype with ID {id:?} is out of bounds") + })) + } + + pub fn get_node_by_id_mut(&mut self, id: ArchetypeId) -> Option<&mut ArchetypeNode> + { + let index = self.archetype_index_lookup.get(&id)?; + + Some(self.nodes.get_mut(*index).unwrap_or_else(|| { + panic!("In invalid state! Index of archetype with ID {id:?} is out of bounds") + })) + } + + pub fn recurse_archetype_add_edges( + &self, + archetype_id: ArchetypeId, + ) -> Option<ArchetypeAddEdgeRecursiveIter> + { + Some(ArchetypeAddEdgeRecursiveIter { + graph: self, + stack: vec![self.get_node_by_id(archetype_id)?.edges.values()], + }) + } + + fn create_missing_edges(&mut self, archetype_id: ArchetypeId) + { + let archetype_node = self + .get_node_by_id(archetype_id) + .expect("Archetype should exist"); + + let mut comp_ids = archetype_node + .archetype() + .component_ids_unsorted() + .collect::<Vec<_>>(); + + comp_ids.sort(); + + for component_id_index in 0..archetype_node.archetype().component_cnt() { + let mut comp_ids_without_comp = comp_ids.clone(); + + let removed_comp_id = comp_ids_without_comp.remove(component_id_index); + + let archetype_without_comp_id = ArchetypeId::new(&comp_ids_without_comp); + + let Some(archetype_node_without_comp) = + self.get_node_by_id_mut(archetype_without_comp_id) + else { + continue; + }; + + archetype_node_without_comp + .get_or_insert_edges(removed_comp_id, ArchetypeEdges::default) + .add = Some(archetype_id); + + let archetype_node = self + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + archetype_node + .get_or_insert_edges(removed_comp_id, ArchetypeEdges::default) + .remove = Some(archetype_without_comp_id); + } + + let archetype_node_index = *self + .archetype_index_lookup + .get(&archetype_id) + .expect("Archetype should exist"); + + let (nodes_before, nodes_rest) = self.nodes.split_at_mut(archetype_node_index); + + let ([archetype_node], nodes_after) = nodes_rest.split_at_mut(1) else { + unreachable!(); + }; + + let expected_component_cnt = archetype_node.archetype().component_cnt() + 1; + + for other_archetype_node in nodes_before.iter_mut().chain(nodes_after.iter_mut()) + { + if other_archetype_node.archetype().component_cnt() != expected_component_cnt + || !other_archetype_node + .archetype() + .is_superset(&archetype_node.archetype()) + { + continue; + } + + let extra_comp_id = other_archetype_node + .archetype() + .component_ids_unsorted() + .find(|comp_id| { + !archetype_node.archetype().has_component_with_id(*comp_id) + }) + .expect("Archetype should contain one extra component ID"); + + other_archetype_node + .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) + .remove = Some(archetype_id); + + archetype_node + .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) + .add = Some(other_archetype_node.archetype().id()); + } + } +} + +#[derive(Debug)] +pub struct ArchetypeNode +{ + archetype: Archetype, + edges: HashMap<Uid, ArchetypeEdges>, +} + +impl ArchetypeNode +{ + pub fn archetype(&self) -> &Archetype + { + &self.archetype + } + + pub fn archetype_mut(&mut self) -> &mut Archetype + { + &mut self.archetype + } + + pub fn get_or_insert_edges( + &mut self, + component_id: Uid, + insert_fn: impl FnOnce() -> ArchetypeEdges, + ) -> &mut ArchetypeEdges + { + debug_assert_eq!(component_id.kind(), UidKind::Component); + + self.edges.entry(component_id).or_insert_with(insert_fn) + } + + pub fn get_edges_mut(&mut self, component_id: Uid) -> Option<&mut ArchetypeEdges> + { + debug_assert_eq!(component_id.kind(), UidKind::Component); + + self.edges.get_mut(&component_id) + } + + pub fn make_add_edge(&self, component_id: Uid) -> (ArchetypeId, Vec<Uid>) + { + let mut edge_comp_ids = self + .archetype() + .component_ids_unsorted() + .chain([component_id]) + .collect::<Vec<_>>(); + + edge_comp_ids.sort(); + + let add_edge_id = ArchetypeId::new(&edge_comp_ids); + + (add_edge_id, edge_comp_ids) + } + + pub fn make_remove_edge(&self, component_id: Uid) -> (ArchetypeId, Vec<Uid>) + { + let mut edge_comp_ids = self + .archetype() + .component_ids_unsorted() + .filter(|id| *id != component_id) + .collect::<Vec<_>>(); + + edge_comp_ids.sort(); + + let remove_edge_id = ArchetypeId::new(&edge_comp_ids); + + (remove_edge_id, edge_comp_ids) + } +} + +#[derive(Debug, Default)] +pub struct ArchetypeEdges +{ + pub add: Option<ArchetypeId>, + pub remove: Option<ArchetypeId>, +} + +#[derive(Debug)] +pub struct ArchetypeAddEdgeRecursiveIter<'graph> +{ + graph: &'graph Graph, + stack: Vec<HashMapValueIter<'graph, Uid, ArchetypeEdges>>, +} + +impl<'graph> Iterator for ArchetypeAddEdgeRecursiveIter<'graph> +{ + type Item = Option<ArchetypeId>; + + fn next(&mut self) -> Option<Self::Item> + { + let iter = self.stack.last_mut()?; + + let Some(edges) = iter.next() else { + self.stack.pop(); + + return Some(None); + }; + + let Some(add_edge) = edges.add else { + return Some(None); + }; + + let add_edge_archetype = self + .graph + .get_node_by_id(add_edge) + .expect("Add edge archetype not found"); + + self.stack.push(add_edge_archetype.edges.values()); + + Some(Some(add_edge)) + } +} |