diff options
Diffstat (limited to 'ecs/src/component/storage.rs')
| -rw-r--r-- | ecs/src/component/storage.rs | 762 |
1 files changed, 261 insertions, 501 deletions
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(&[])) + ); } } |