diff options
Diffstat (limited to 'ecs/src/component')
| -rw-r--r-- | ecs/src/component/storage.rs | 181 | ||||
| -rw-r--r-- | ecs/src/component/storage/archetype.rs | 177 | ||||
| -rw-r--r-- | ecs/src/component/storage/graph.rs | 36 |
3 files changed, 241 insertions, 153 deletions
diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs index 40909fb..b27b552 100644 --- a/ecs/src/component/storage.rs +++ b/ecs/src/component/storage.rs @@ -1,4 +1,4 @@ -use std::any::type_name; +use std::any::Any; use std::array::IntoIter as ArrayIter; use std::cell::RefCell; use std::vec::IntoIter as VecIntoIter; @@ -17,8 +17,6 @@ use crate::component::storage::graph::{ ArchetypeEdges, Graph, }; -use crate::component::Component; -use crate::type_name::TypeName; use crate::uid::{Kind as UidKind, Uid}; use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt}; @@ -35,14 +33,43 @@ pub struct ArchetypeSearchTerms<'a> impl ArchetypeSearchTerms<'_> { - fn excluded_contains(&self, uid: Uid) -> bool + fn excluded_contains(&self, comp_id: Uid) -> bool { - self.excluded_components.binary_search(&uid).is_ok() + let comp_id_kind = comp_id.kind(); + + debug_assert!( + comp_id_kind == UidKind::Component + || (comp_id_kind == UidKind::Pair + && comp_id.target_component() != Uid::wildcard()) + ); + + let is_found = self.excluded_components.binary_search(&comp_id).is_ok(); + + if !is_found && comp_id_kind == UidKind::Pair { + return self.excluded_components.iter().any(|excluded_comp_id| { + excluded_comp_id.kind() == UidKind::Pair + && excluded_comp_id.has_same_relation_as(comp_id) + && excluded_comp_id.target_component() == Uid::wildcard() + }); + } + + is_found + } + + fn contains_conflicting(&self) -> bool + { + self.excluded_components.iter().any(|excluded_comp_id| { + self.required_components + .binary_search(excluded_comp_id) + .is_ok() + }) } - fn required_contains(&self, uid: Uid) -> bool + fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool { - self.required_components.binary_search(&uid).is_ok() + self.required_components + .iter() + .all(|comp_id| archetype.contains_matching_component(*comp_id)) } } @@ -61,13 +88,9 @@ impl Storage search_terms: ArchetypeSearchTerms<'search_terms>, ) -> ArchetypeRefIter<'_, 'search_terms> { - let archetype_id = ArchetypeId::new(&search_terms.required_components); + let archetype_id = ArchetypeId::new(search_terms.required_components); - if search_terms - .excluded_components - .iter() - .any(|excluded_comp_id| search_terms.required_contains(*excluded_comp_id)) - { + if search_terms.contains_conflicting() { return ArchetypeRefIter { storage: self, pre_iter: Either::B(Vec::new().into_iter()), @@ -82,8 +105,21 @@ impl Storage self.imaginary_archetypes .borrow_mut() .push(ImaginaryArchetype { - id: archetype_id, - component_ids: search_terms.required_components.to_vec(), + id: ArchetypeId::new(search_terms.required_components.iter().filter( + |required_comp_id| { + required_comp_id.kind() != UidKind::Pair + || required_comp_id.target_component() != Uid::wildcard() + }, + )), + component_ids: search_terms + .required_components + .iter() + .copied() + .filter(|required_comp_id| { + required_comp_id.kind() != UidKind::Pair + || required_comp_id.target_component() != Uid::wildcard() + }) + .collect(), }); let found_archetypes = self.find_all_archetype_with_comps(&search_terms); @@ -117,7 +153,7 @@ impl Storage return Err(Error::EntityAlreadyExists(uid)); } - let empty_archetype_id = ArchetypeId::from_components_metadata(&[]); + let empty_archetype_id = ArchetypeId::new_empty(); let archetype_node = self.graph.get_or_create_node(empty_archetype_id, &[]); @@ -161,16 +197,9 @@ impl Storage pub fn add_entity_component( &mut self, entity_uid: Uid, - component: (Uid, Box<dyn Component>), + (component_id, component_name, component): (Uid, &'static str, Box<dyn Any>), ) -> Result<(), Error> { - let (component_id, component) = component; - - debug_assert!( - !component.self_is_optional(), - "Adding a optional component to a entity is not supported" - ); - let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { return Err(Error::EntityDoesNotExist(entity_uid)); }; @@ -184,7 +213,7 @@ impl Storage if archetype_node .archetype() - .has_component_with_id(component_id) + .contains_component_with_exact_id(component_id) { return Err(Error::ComponentAlreadyInEntity { entity: entity_uid, @@ -192,56 +221,36 @@ impl Storage }); } - let add_edge_archetype_id = match archetype_node + let add_edge_archetype_id = if let Some(add_edge_id) = archetype_node .get_or_insert_edges(component_id, ArchetypeEdges::default) .add { - Some(add_edge_id) => { - if !self.graph.contains_archetype(add_edge_id) { - let (_, add_edge_comp_ids) = self - .graph - .get_node_by_id(archetype_id) - .expect("Archetype should exist") - .make_add_edge(component_id); - - self.graph.create_node(add_edge_id, &add_edge_comp_ids); - } - - add_edge_id - } - None => { - let archetype_node = self + if !self.graph.contains_archetype(add_edge_id) { + let (_, add_edge_comp_ids) = 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_id); + .get_node_by_id(archetype_id) + .expect("Archetype should exist") + .make_add_edge(component_id); - archetype_node - .get_edges_mut(component_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); - } - - add_edge_id + self.graph.create_node(add_edge_id, &add_edge_comp_ids); } - }; - { - let add_edge_archetype_node = self + add_edge_id + } else { + let archetype_node = self .graph - .get_node_by_id_mut(add_edge_archetype_id) - .expect("Add edge archetype should exist"); + .get_node_by_id(archetype_id) + .expect("Archetype should exist"); - let add_edge_archetype_edges = add_edge_archetype_node - .get_or_insert_edges(component_id, ArchetypeEdges::default); + let (add_edge_id, add_edge_comp_ids) = + archetype_node.make_add_edge(component_id); - add_edge_archetype_edges.remove = Some(archetype_id); - } + if !self.graph.contains_archetype(add_edge_id) { + self.graph.create_node(add_edge_id, &add_edge_comp_ids); + } + + add_edge_id + }; let archetype_node = self .graph @@ -261,7 +270,7 @@ impl Storage entity.insert_component( component_id, - ArchetypeEntityComponent::new(component), + ArchetypeEntityComponent::new(component, component_id, component_name), add_edge_archetype, ); @@ -292,7 +301,7 @@ impl Storage if !archetype_node .archetype() - .has_component_with_id(component_id) + .contains_component_with_exact_id(component_id) { return Err(Error::ComponentNotFoundInEntity { entity: entity_uid, @@ -312,11 +321,6 @@ impl Storage 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); @@ -367,9 +371,12 @@ impl Storage ) -> Vec<ArchetypeId> { let Some(mut search_iter) = - self.graph.dfs_archetype_add_edges(ArchetypeId::new(&[])) + self.graph.dfs_archetype_add_edges(ArchetypeId::new_empty()) else { // If the root archetype doesn't exist, no other archetype can exist either + // + // TODO: The above comment is not true. Cases where imaginary archetypes have + // been created should be handled as well return Vec::new(); }; @@ -398,11 +405,7 @@ impl Storage continue; } - if !search_terms - .required_components - .iter() - .all(|comp_id| node.archetype().has_component_with_id(*comp_id)) - { + if !search_terms.archetype_contains_all_required(node.archetype()) { continue; } @@ -415,14 +418,6 @@ impl Storage } } -impl TypeName for Storage -{ - fn type_name(&self) -> &'static str - { - type_name::<Self>() - } -} - #[cfg(feature = "vizoxide")] impl Storage { @@ -602,8 +597,7 @@ pub struct ArchetypeRefIter<'storage, 'search_terms> search_terms: ArchetypeSearchTerms<'search_terms>, } -impl<'component_storage, 'search_terms> Iterator - for ArchetypeRefIter<'component_storage, 'search_terms> +impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> { type Item = &'component_storage Archetype; @@ -656,10 +650,7 @@ impl<'component_storage, 'search_terms> Iterator self.storage.imaginary_archetypes.borrow_mut().push( ImaginaryArchetype { id: add_edge_archetype_id, - component_ids: add_edge_archetype_comps - .iter() - .map(|comp_id| *comp_id) - .collect::<Vec<_>>(), + component_ids: add_edge_archetype_comps.clone(), }, ); @@ -673,8 +664,6 @@ impl<'component_storage, 'search_terms> Iterator )), found.into_iter(), )); - - continue; } _ => { unreachable!(); @@ -784,7 +773,7 @@ mod tests let archetype_node = new_storage .graph - .get_node_by_id(ArchetypeId::from_components_metadata(&[])) + .get_node_by_id(ArchetypeId::new_empty()) .expect("Archetype for entities with no component doesn't exist"); assert_eq!(archetype_node.archetype().component_cnt(), 0); @@ -792,7 +781,7 @@ mod tests assert_eq!( new_storage.entity_archetype_lookup.get(&uid).copied(), - Some(ArchetypeId::from_components_metadata(&[])) + Some(ArchetypeId::new_empty()) ); } } diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs index 5306cf9..bb29701 100644 --- a/ecs/src/component/storage/archetype.rs +++ b/ecs/src/component/storage/archetype.rs @@ -1,12 +1,15 @@ +use std::any::Any; +use std::array::IntoIter as ArrayIntoIter; use std::hash::{DefaultHasher, Hash, Hasher}; +use std::iter::{Enumerate, Filter, Map, RepeatN, Zip}; +use std::option::IntoIter as OptionIntoIter; use std::slice::Iter as SliceIter; use hashbrown::HashMap; -use crate::component::{Component, Metadata as ComponentMetadata}; use crate::lock::Lock; use crate::uid::{Kind as UidKind, Uid}; -use crate::util::HashMapExt; +use crate::util::{Either, HashMapExt}; #[derive(Debug)] pub struct Archetype @@ -116,8 +119,54 @@ impl Archetype self.component_index_lookup.len() } + pub fn get_matching_component_indices( + &self, + component_id: Uid, + ) -> MatchingComponentIter + { + assert!( + component_id.kind() == UidKind::Component + || component_id.kind() == UidKind::Pair + ); + + if component_id.kind() == UidKind::Pair + && component_id.target_component() == Uid::wildcard() + { + return MatchingComponentIter { + inner: Either::A( + self.component_ids + .iter() + .enumerate() + .zip(std::iter::repeat_n(component_id, self.component_ids.len())) + .filter( + (|((_, other_comp_id), component_id)| { + other_comp_id.kind() == UidKind::Pair + && other_comp_id.has_same_relation_as(*component_id) + }) + as MatchingComponentIterFilterFn, + ) + .map(|((index, other_comp_id), _)| (*other_comp_id, index)), + ), + }; + } + + MatchingComponentIter { + inner: Either::B( + [component_id] + .into_iter() + .zip(self.get_index_for_component(component_id)), + ), + } + } + pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize> { + assert!( + component_id.kind() == UidKind::Component + || (component_id.kind() == UidKind::Pair + && component_id.target_component() != Uid::wildcard()) + ); + self.component_index_lookup.get(&component_id).copied() } @@ -131,14 +180,70 @@ impl Archetype self.component_ids.iter().copied() } - pub fn has_component_with_id(&self, component_id: Uid) -> bool + pub fn contains_matching_component(&self, component_id: Uid) -> bool { - debug_assert_eq!(component_id.kind(), UidKind::Component); + let component_id_kind = component_id.kind(); + + debug_assert!( + component_id_kind == UidKind::Component || component_id_kind == UidKind::Pair + ); + + if component_id.kind() == UidKind::Pair + && component_id.target_component() == Uid::wildcard() + { + return self.component_ids.iter().any(|other_comp_id| { + other_comp_id.kind() == UidKind::Pair + && other_comp_id.has_same_relation_as(component_id) + }); + } + + self.contains_component_with_exact_id(component_id) + } + + pub fn contains_component_with_exact_id(&self, component_id: Uid) -> bool + { + let component_id_kind = component_id.kind(); + + debug_assert!( + component_id_kind == UidKind::Component + || (component_id_kind == UidKind::Pair + && component_id.target_component() != Uid::wildcard()) + ); self.component_index_lookup.contains_key(&component_id) } } +type MatchingComponentIterFilterFn = fn(&((usize, &Uid), Uid)) -> bool; + +type MatchingComponentIterMapFn = fn(((usize, &Uid), Uid)) -> (Uid, usize); + +type InnerMatchingComponentIterA<'archetype> = Map< + Filter< + Zip<Enumerate<SliceIter<'archetype, Uid>>, RepeatN<Uid>>, + MatchingComponentIterFilterFn, + >, + MatchingComponentIterMapFn, +>; + +type InnerMatchingComponentIterB = Zip<ArrayIntoIter<Uid, 1>, OptionIntoIter<usize>>; + +#[derive(Debug)] +pub struct MatchingComponentIter<'archetype> +{ + inner: Either<InnerMatchingComponentIterA<'archetype>, InnerMatchingComponentIterB>, +} + +impl Iterator for MatchingComponentIter<'_> +{ + type Item = (Uid, usize); + + fn next(&mut self) -> Option<Self::Item> + { + self.inner.next() + } +} + #[derive(Debug)] pub struct EntityIter<'archetype> { @@ -209,26 +314,31 @@ impl Entity #[derive(Debug)] pub struct EntityComponent { - name: &'static str, - component: Lock<Box<dyn Component>>, + id: Uid, + component: Lock<Box<dyn Any>>, } impl EntityComponent { - pub fn new(component: Box<dyn Component>) -> Self + pub fn new( + component: Box<dyn Any>, + component_id: Uid, + component_name: &'static str, + ) -> Self { Self { - name: component.type_name(), - component: Lock::new(component), + id: component_id, + component: Lock::new(component, component_name), } } - pub fn name(&self) -> &str + #[allow(dead_code)] + pub fn id(&self) -> Uid { - self.name + self.id } - pub fn component(&self) -> &Lock<Box<dyn Component>> + pub fn component(&self) -> &Lock<Box<dyn Any>> { &self.component } @@ -243,56 +353,33 @@ pub struct Id impl Id { - pub fn new(component_ids: &impl AsRef<[Uid]>) -> Self + pub fn new_empty() -> Self { - if component_ids.as_ref().is_empty() { - 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() } + Self { hash: 0 } } - pub fn from_components_metadata<'a>( - components_metadata: impl IntoIterator<Item = &'a ComponentMetadata>, - ) -> Self + pub fn new<'a>(component_ids: impl IntoIterator<Item = &'a Uid>) -> Self { let mut hasher = DefaultHasher::new(); let mut prev_component_id: Option<Uid> = None; - let mut comp_metadata_iter = components_metadata.into_iter().peekable(); + let mut component_id_iter = component_ids.into_iter().peekable(); - if comp_metadata_iter.peek().is_none() { - return Self { hash: 0 }; + if component_id_iter.peek().is_none() { + return Self::new_empty(); } - for comp_metadata in comp_metadata_iter { - if prev_component_id - .is_some_and(|prev_comp_id| comp_metadata.id < prev_comp_id) - { + for comp_id in component_id_iter { + if prev_component_id.is_some_and(|prev_comp_id| *comp_id < prev_comp_id) { panic!( "Cannot create archetype ID from a unsorted component metadata list" ); } - prev_component_id = Some(comp_metadata.id); - - if comp_metadata.is_optional { - continue; - } + prev_component_id = Some(*comp_id); - comp_metadata.id.hash(&mut hasher); + comp_id.hash(&mut hasher); } Self { hash: hasher.finish() } diff --git a/ecs/src/component/storage/graph.rs b/ecs/src/component/storage/graph.rs index 11160e7..29fa937 100644 --- a/ecs/src/component/storage/graph.rs +++ b/ecs/src/component/storage/graph.rs @@ -140,19 +140,31 @@ impl Graph } fn create_missing_subset_node_edges( - target_node: &ArchetypeNode, + target_node: &mut ArchetypeNode, subset_node: &mut ArchetypeNode, ) { let uniq_comp_id = target_node .archetype() .component_ids_sorted() - .find(|id| !subset_node.archetype().has_component_with_id(*id)) + .find(|id| { + !subset_node + .archetype() + .contains_component_with_exact_id(*id) + }) .unwrap(); subset_node .get_or_insert_edges(uniq_comp_id, ArchetypeEdges::default) .add = Some(subset_node.make_add_edge(uniq_comp_id).0); + + if target_node.archetype().component_cnt() + == subset_node.archetype().component_cnt() + 1 + { + target_node + .get_or_insert_edges(uniq_comp_id, ArchetypeEdges::default) + .remove = Some(subset_node.archetype().id()); + } } fn create_missing_superset_node_edges( @@ -169,7 +181,7 @@ impl Graph .find(|other_archetype_comp_id| { !target_node .archetype() - .has_component_with_id(*other_archetype_comp_id) + .contains_component_with_exact_id(*other_archetype_comp_id) }) .or_else(|| { if target_node.archetype().component_cnt() != 0 { @@ -196,7 +208,11 @@ impl Graph let extra_comp_id = superset_node .archetype() .component_ids_unsorted() - .find(|comp_id| !target_node.archetype().has_component_with_id(*comp_id)) + .find(|comp_id| { + !target_node + .archetype() + .contains_component_with_exact_id(*comp_id) + }) .expect("Archetype should contain one extra component ID"); superset_node @@ -234,7 +250,10 @@ impl ArchetypeNode insert_fn: impl FnOnce() -> ArchetypeEdges, ) -> &mut ArchetypeEdges { - debug_assert_eq!(component_id.kind(), UidKind::Component); + debug_assert!(matches!( + component_id.kind(), + UidKind::Component | UidKind::Pair + )); self.edges.entry(component_id).or_insert_with(insert_fn) } @@ -245,13 +264,6 @@ impl ArchetypeNode self.edges.iter() } - 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 |