diff options
Diffstat (limited to 'ecs/src/component/storage')
| -rw-r--r-- | ecs/src/component/storage/archetype.rs | 385 | ||||
| -rw-r--r-- | ecs/src/component/storage/graph.rs | 432 |
2 files changed, 0 insertions, 817 deletions
diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs deleted file mode 100644 index a7fe7ed..0000000 --- a/ecs/src/component/storage/archetype.rs +++ /dev/null @@ -1,385 +0,0 @@ -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::lock::Lock; -use crate::uid::{Kind as UidKind, Uid}; -use crate::util::{Either, HashMapExt}; - -#[derive(Debug)] -pub struct Archetype -{ - id: Id, - entities: Vec<Entity>, - entity_index_lookup: HashMap<Uid, usize>, - component_index_lookup: HashMap<Uid, usize>, - component_ids: Vec<Uid>, -} - -impl Archetype -{ - pub fn new(id: Id, component_ids: impl AsRef<[Uid]>) -> Self - { - Self { - id, - entities: Vec::new(), - entity_index_lookup: HashMap::new(), - component_index_lookup: component_ids - .as_ref() - .iter() - .enumerate() - .map(|(index, id)| (*id, index)) - .collect(), - component_ids: component_ids.as_ref().to_vec(), - } - } - - 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 is_subset(&self, other: &Self) -> bool - { - self.component_index_lookup - .keys_is_subset(&other.component_index_lookup) - } - - pub fn get_entity_by_id(&self, entity_uid: Uid) -> Option<&Entity> - { - 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: Entity) - { - self.entity_index_lookup - .insert(entity.uid, self.entities.len()); - - self.entities.push(entity); - } - - pub fn remove_entity(&mut self, entity_uid: Uid) -> Option<Entity> - { - //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_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() - } - - pub fn component_ids_unsorted(&self) -> impl Iterator<Item = Uid> + '_ - { - self.component_index_lookup.keys().copied() - } - - pub fn component_ids_sorted(&self) -> impl Iterator<Item = Uid> + '_ - { - self.component_ids.iter().copied() - } - - pub fn contains_matching_component(&self, component_id: Uid) -> bool - { - 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> -{ - iter: SliceIter<'archetype, Entity>, -} - -impl<'archetype> Iterator for EntityIter<'archetype> -{ - type Item = &'archetype Entity; - - fn next(&mut self) -> Option<Self::Item> - { - self.iter.next() - } -} - -#[derive(Debug)] -pub struct Entity -{ - uid: Uid, - components: Vec<EntityComponent>, -} - -impl Entity -{ - pub fn new(uid: Uid, components: impl IntoIterator<Item = EntityComponent>) -> Self - { - Self { - uid, - components: components.into_iter().collect(), - } - } - - pub fn uid(&self) -> Uid - { - self.uid - } - - pub fn components(&self) -> &[EntityComponent] - { - &self.components - } - - pub fn remove_component( - &mut self, - component_id: Uid, - archetype: &Archetype, - ) -> EntityComponent - { - let index = archetype - .get_index_for_component(component_id) - .expect("Archetype should contain component"); - - self.components.remove(index) - } - - pub fn insert_component( - &mut self, - component_id: Uid, - component: EntityComponent, - archetype: &Archetype, - ) - { - let index = archetype - .get_index_for_component(component_id) - .expect("Archetype should contain component"); - - self.components.insert(index, component); - } -} - -#[derive(Debug)] -pub struct EntityComponent -{ - component: Lock<Box<dyn Any>>, - name: &'static str, -} - -impl EntityComponent -{ - pub fn new(component: Box<dyn Any>, component_name: &'static str) -> Self - { - Self { - component: Lock::new(component, component_name), - name: component_name, - } - } - - pub fn component(&self) -> &Lock<Box<dyn Any>> - { - &self.component - } - - pub fn name(&self) -> &str - { - self.name - } -} - -/// Archetype ID. -#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)] -pub struct Id -{ - hash: u64, -} - -impl Id -{ - pub fn new_empty() -> Self - { - Self { hash: 0 } - } - - 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 component_id_iter = component_ids.into_iter().peekable(); - - if component_id_iter.peek().is_none() { - return Self::new_empty(); - } - - for comp_id in component_id_iter { - assert!( - prev_component_id.is_none_or(|prev_comp_id| *comp_id >= prev_comp_id), - "Cannot create archetype ID from a unsorted component metadata list" - ); - - prev_component_id = Some(*comp_id); - - 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 deleted file mode 100644 index 76200f9..0000000 --- a/ecs/src/component/storage/graph.rs +++ /dev/null @@ -1,432 +0,0 @@ -use std::vec::IntoIter as VecIntoIter; - -use hashbrown::{HashMap, HashSet}; - -use crate::component::storage::archetype::{Archetype, Id as ArchetypeId}; -use crate::uid::{Kind as UidKind, Uid}; -use crate::util::{BorrowedOrOwned, StreamingIterator}; - -#[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 exists_before = self.archetype_index_lookup.contains_key(&id); - - 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 - }); - - if !exists_before { - 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") - })) - } - - #[cfg(feature = "vizoxide")] - pub fn iter_nodes(&self) -> impl Iterator<Item = &ArchetypeNode> - { - self.nodes.iter() - } - - pub fn dfs_archetype_add_edges( - &self, - archetype_id: ArchetypeId, - ) -> Option<ArchetypeAddEdgeDfsIter<'_>> - { - let node = self.get_node_by_id(archetype_id)?; - - Some(ArchetypeAddEdgeDfsIter { - graph: self, - stack: vec![( - BorrowedOrOwned::Borrowned(node.archetype()), - node.edges - .iter() - .map(|(comp_id, edges)| (*comp_id, edges.clone())) - .collect::<Vec<_>>() - .into_iter(), - )], - visited: HashSet::new(), - }) - } - - fn create_missing_edges(&mut self, archetype_id: ArchetypeId) - { - 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!(); - }; - - for other_archetype_node in nodes_before.iter_mut().chain(nodes_after.iter_mut()) - { - if archetype_node.archetype().component_cnt() - > other_archetype_node.archetype().component_cnt() - && other_archetype_node - .archetype() - .is_subset(archetype_node.archetype()) - { - Self::create_missing_subset_node_edges( - archetype_node, - other_archetype_node, - ); - - continue; - } - - if other_archetype_node - .archetype() - .is_superset(archetype_node.archetype()) - { - Self::create_missing_superset_node_edges( - archetype_node, - other_archetype_node, - ); - } - } - } - - fn create_missing_subset_node_edges( - target_node: &mut ArchetypeNode, - subset_node: &mut ArchetypeNode, - ) - { - let uniq_comp_id = target_node - .archetype() - .component_ids_sorted() - .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( - target_node: &mut ArchetypeNode, - superset_node: &mut ArchetypeNode, - ) - { - if superset_node.archetype().component_cnt() - > target_node.archetype().component_cnt() + 1 - { - let first_unique_comp_id = superset_node - .archetype() - .component_ids_sorted() - .find(|other_archetype_comp_id| { - !target_node - .archetype() - .contains_component_with_exact_id(*other_archetype_comp_id) - }) - .or_else(|| { - if target_node.archetype().component_cnt() != 0 { - return None; - } - - superset_node.archetype().component_ids_sorted().next() - }) - .expect("Not possible"); - - target_node - .get_or_insert_edges(first_unique_comp_id, ArchetypeEdges::default) - .add = Some(target_node.make_add_edge(first_unique_comp_id).0); - - return; - } - - if superset_node.archetype().component_cnt() - != target_node.archetype().component_cnt() + 1 - { - return; - } - - let extra_comp_id = superset_node - .archetype() - .component_ids_unsorted() - .find(|comp_id| { - !target_node - .archetype() - .contains_component_with_exact_id(*comp_id) - }) - .expect("Archetype should contain one extra component ID"); - - superset_node - .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) - .remove = Some(target_node.archetype().id()); - - target_node - .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) - .add = Some(superset_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!(matches!( - component_id.kind(), - UidKind::Component | UidKind::Pair - )); - - self.edges.entry(component_id).or_insert_with(insert_fn) - } - - #[cfg(feature = "vizoxide")] - pub fn iter_edges(&self) -> impl Iterator<Item = (&Uid, &ArchetypeEdges)> - { - self.edges.iter() - } - - 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, Clone)] -pub struct ArchetypeEdges -{ - pub add: Option<ArchetypeId>, - pub remove: Option<ArchetypeId>, -} - -type ArchetypeAddEdgeDfsIterStackElem<'graph> = ( - BorrowedOrOwned<'graph, Archetype>, - VecIntoIter<(Uid, ArchetypeEdges)>, -); - -#[derive(Debug)] -pub struct ArchetypeAddEdgeDfsIter<'graph> -{ - graph: &'graph Graph, - stack: Vec<ArchetypeAddEdgeDfsIterStackElem<'graph>>, - visited: HashSet<ArchetypeId>, -} - -impl<'graph> ArchetypeAddEdgeDfsIter<'graph> -{ - pub fn new(graph: &'graph Graph, start_nodes: &[ArchetypeId]) -> Self - { - Self { - graph, - stack: start_nodes - .iter() - .map(|start_node_id| { - let start_node = graph - .get_node_by_id(*start_node_id) - .expect("Start node does not exist"); - - ( - BorrowedOrOwned::Borrowned(start_node.archetype()), - start_node - .edges - .iter() - .map(|(comp_id, edges)| (*comp_id, edges.clone())) - .collect::<Vec<_>>() - .into_iter(), - ) - }) - .collect(), - visited: start_nodes.iter().copied().collect::<HashSet<_>>(), - } - } - - pub fn push( - &mut self, - item: ( - BorrowedOrOwned<'graph, Archetype>, - VecIntoIter<(Uid, ArchetypeEdges)>, - ), - ) - { - self.stack.push(item); - } - - pub fn pop(&mut self) - { - self.stack.pop(); - } -} - -impl<'graph> StreamingIterator for ArchetypeAddEdgeDfsIter<'graph> -{ - type Item<'a> - = ArchetypeAddEdgeDfsIterResult<'graph, 'a> - where - Self: 'a; - - fn streaming_next(&mut self) -> Option<Self::Item<'_>> - { - let (_, edges_iter) = self.stack.last_mut()?; - - let Some((component_id, edges)) = edges_iter.next() else { - self.stack.pop(); - - return Some(ArchetypeAddEdgeDfsIterResult::NoEdgesLeftForArchetype); - }; - - let Some(add_edge) = edges.add else { - return Some(ArchetypeAddEdgeDfsIterResult::NoAddEdge); - }; - - if self.visited.contains(&add_edge) { - return Some(ArchetypeAddEdgeDfsIterResult::AddEdgeAlreadyVisited); - } - - self.visited.insert(add_edge); - - let Some(add_edge_archetype) = self.graph.get_node_by_id(add_edge) else { - return Some(ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { - archetype: &self.stack.last().unwrap().0, - add_edge_archetype_id: add_edge, - add_edge_component_id: component_id, - }); - }; - - self.stack.push(( - BorrowedOrOwned::Borrowned(add_edge_archetype.archetype()), - add_edge_archetype - .edges - .iter() - .map(|(comp_id, edges)| (*comp_id, edges.clone())) - .collect::<Vec<_>>() - .into_iter(), - )); - - Some(ArchetypeAddEdgeDfsIterResult::AddEdge { - add_edge_archetype_id: add_edge, - add_edge_component_id: component_id, - }) - } -} - -#[derive(Debug)] -pub enum ArchetypeAddEdgeDfsIterResult<'graph, 'iter> -{ - AddEdge - { - add_edge_archetype_id: ArchetypeId, - add_edge_component_id: Uid, - }, - NoEdgesLeftForArchetype, - NoAddEdge, - AddEdgeAlreadyVisited, - AddEdgeArchetypeNotFound - { - archetype: &'iter BorrowedOrOwned<'graph, Archetype>, - add_edge_archetype_id: ArchetypeId, - add_edge_component_id: Uid, - }, -} |