diff options
Diffstat (limited to 'engine-ecs/src/component/storage.rs')
| -rw-r--r-- | engine-ecs/src/component/storage.rs | 240 |
1 files changed, 196 insertions, 44 deletions
diff --git a/engine-ecs/src/component/storage.rs b/engine-ecs/src/component/storage.rs index a4944c7..4a1c035 100644 --- a/engine-ecs/src/component/storage.rs +++ b/engine-ecs/src/component/storage.rs @@ -17,7 +17,8 @@ use crate::component::storage::graph::{ ArchetypeEdges, Graph, }; -use crate::uid::Uid; +use crate::uid::{PairParams, Uid}; +use crate::util::array_vec::ArrayVec; use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt}; pub mod archetype; @@ -25,13 +26,56 @@ pub mod archetype; mod graph; #[derive(Debug)] -pub struct ArchetypeSearchTerms<'a> +pub struct SearchTerms<const TERM_CAP: usize> { - pub present: &'a [Uid], - pub absent: &'a [Uid], + pub(crate) present: ArrayVec<Uid, TERM_CAP>, + pub(crate) absent: ArrayVec<Uid, TERM_CAP>, + pub(crate) traverse: ArrayVec<Traversal<TERM_CAP>, TERM_CAP>, } -impl ArchetypeSearchTerms<'_> +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct TermMetadata +{ + pub level: u32, + pub index: u32, +} + +#[derive(Debug, Clone)] +pub struct Traversal<const TERM_CAP: usize> +{ + pub kind: TraversalKind, + pub relation: Uid, + pub terms: fn(&Self) -> SearchTerms<TERM_CAP>, + pub term_metadata: TermMetadata, +} + +impl<const TERM_CAP: usize> Traversal<TERM_CAP> +{ + fn relationship(&self) -> Uid + { + Uid::new_pair(&PairParams { + relation: self.relation, + target: Uid::wildcard(), + }) + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +#[non_exhaustive] +pub enum TraversalKind +{ + Up, +} + +#[derive(Debug)] +pub struct TraversalResult +{ + pub relation: Uid, + pub term_metadata: TermMetadata, + pub found_ent: Uid, +} + +impl<const TERM_CAP: usize> SearchTerms<TERM_CAP> { fn excluded_contains(&self, comp_id: Uid) -> bool { @@ -55,11 +99,9 @@ impl ArchetypeSearchTerms<'_> fn contains_conflicting(&self) -> bool { - self.absent.iter().any(|excluded_comp_id| { - self.present - .binary_search(excluded_comp_id) - .is_ok() - }) + self.absent + .iter() + .any(|excluded_comp_id| self.present.binary_search(excluded_comp_id).is_ok()) } fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool @@ -80,12 +122,12 @@ pub struct Storage impl Storage { - pub fn search_archetypes<'search_terms>( + pub fn search_archetypes<'search_terms, const TERM_CAP: usize>( &self, - search_terms: ArchetypeSearchTerms<'search_terms>, - ) -> ArchetypeRefIter<'_, 'search_terms> + search_terms: &'search_terms SearchTerms<TERM_CAP>, + ) -> ArchetypeRefIter<'_, 'search_terms, TERM_CAP> { - let archetype_id = ArchetypeId::new(search_terms.present); + let archetype_id = ArchetypeId::new(search_terms.present.iter()); if search_terms.contains_conflicting() { return ArchetypeRefIter { @@ -370,9 +412,9 @@ impl Storage } } - fn find_all_archetype_with_comps( + fn find_all_archetype_with_comps<const TERM_CAP: usize>( &self, - search_terms: &ArchetypeSearchTerms<'_>, + search_terms: &SearchTerms<TERM_CAP>, ) -> Vec<ArchetypeId> { let Some(mut search_iter) = @@ -594,29 +636,52 @@ pub enum VizoxideArchetypeGraphEdgeKind } #[derive(Debug)] -pub struct ArchetypeRefIter<'storage, 'search_terms> +pub struct ArchetypeRefIter<'storage, 'search_terms, const TERM_CAP: usize> { storage: &'storage Storage, pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>, dfs_iter: ArchetypeAddEdgeDfsIter<'storage>, - search_terms: ArchetypeSearchTerms<'search_terms>, + search_terms: &'search_terms SearchTerms<TERM_CAP>, } -impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> +impl<'component_storage, const TERM_CAP: usize> Iterator + for ArchetypeRefIter<'component_storage, '_, TERM_CAP> { - type Item = &'component_storage Archetype; + type Item = ( + &'component_storage Archetype, + ArrayVec<TraversalResult, TERM_CAP>, + ); fn next(&mut self) -> Option<Self::Item> { - if let Some(pre_iter_archetype_id) = self.pre_iter.next() { - return Some( - self.storage - .get_archetype_by_id(pre_iter_archetype_id) - .expect("Archetype should exist"), - ); + if let Some((pre_iter_archetype, pre_iter_traversal_results)) = + self.pre_iter.find_map(|archetype_id| { + let archetype = self + .storage + .get_archetype_by_id(archetype_id) + .expect("Archetype should exist"); + + let mut traversal_results = + ArrayVec::<TraversalResult, TERM_CAP>::default(); + + if do_traversals( + self.storage, + archetype, + &self.search_terms.traverse, + &mut traversal_results, + ) + .is_none() + { + return None; + }; + + Some((archetype, traversal_results)) + }) + { + return Some((pre_iter_archetype, pre_iter_traversal_results)); } - let archetype_id = loop { + let (archetype, traversal_results) = loop { match self.dfs_iter.streaming_find(|res| { matches!( res, @@ -633,7 +698,27 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> continue; } - break add_edge_archetype_id; + let add_edge_archetype = self + .storage + .get_archetype_by_id(add_edge_archetype_id) + .expect("Archetype should exist"); + + let mut traversal_results = + ArrayVec::<TraversalResult, TERM_CAP>::default(); + + if do_traversals( + self.storage, + add_edge_archetype, + &self.search_terms.traverse, + &mut traversal_results, + ) + .is_none() + { + self.dfs_iter.pop(); + continue; + }; + + break (add_edge_archetype, traversal_results); } ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { archetype, @@ -644,8 +729,9 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> continue; } - let mut add_edge_archetype_comps = - archetype.component_ids_sorted().collect::<Vec<_>>(); + let mut add_edge_archetype_comps = archetype + .component_ids_sorted() + .collect::<ArrayVec<_, 32>>(); add_edge_archetype_comps .insert_at_part_pt_by_key(add_edge_component_id, |comp_id| { @@ -659,13 +745,14 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> }, ); - let found = - self.find_edges_of_imaginary_archetype(&add_edge_archetype_comps); + let found = self.find_edges_of_imaginary_archetype( + add_edge_archetype_comps.clone(), + ); self.dfs_iter.push(( BorrowedOrOwned::Owned(Archetype::new( add_edge_archetype_id, - add_edge_archetype_comps.clone(), + add_edge_archetype_comps, )), found.into_iter(), )); @@ -676,25 +763,22 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> } }; - Some( - self.storage - .get_archetype_by_id(archetype_id) - .expect("Archetype should exist"), - ) + Some((archetype, traversal_results)) } } -impl ArchetypeRefIter<'_, '_> +impl<const TERM_CAP: usize> ArchetypeRefIter<'_, '_, TERM_CAP> { fn find_edges_of_imaginary_archetype( &self, - imaginary_archetype_comps: &[Uid], + imaginary_archetype_comps: ArrayVec<Uid, 32>, ) -> Vec<(Uid, ArchetypeEdges)> { self.storage - .find_all_archetype_with_comps(&ArchetypeSearchTerms { - present: imaginary_archetype_comps, - absent: &[], + .find_all_archetype_with_comps(&SearchTerms { + present: imaginary_archetype_comps.clone(), + absent: ArrayVec::default(), + traverse: ArrayVec::default(), }) .into_iter() .filter_map(|found_id| { @@ -757,7 +841,75 @@ pub struct EntityAlreadyExistsError; struct ImaginaryArchetype { id: ArchetypeId, - component_ids: Vec<Uid>, + component_ids: ArrayVec<Uid, 32>, +} + +fn do_traversals<const TERM_CAP: usize>( + storage: &Storage, + archetype: &Archetype, + traversals: &[Traversal<TERM_CAP>], + results: &mut ArrayVec<TraversalResult, TERM_CAP>, +) -> Option<()> +{ + // TODO: Optimize traversals. Caching is needed especially + + for traversal in traversals { + if traversal.kind == TraversalKind::Up { + archetype + .get_matching_component_ids(traversal.relationship()) + .find_map(|relationship| { + traverse_dfs( + storage, + relationship.target(), + traversal, + &(traversal.terms)(traversal), + results, + ) + })?; + } else { + unimplemented!(); + } + } + + Some(()) +} + +fn traverse_dfs<const TERM_CAP: usize>( + storage: &Storage, + ent_id: Uid, + traversal: &Traversal<TERM_CAP>, + terms: &SearchTerms<TERM_CAP>, + results: &mut ArrayVec<TraversalResult, TERM_CAP>, +) -> Option<()> +{ + let ent_archetype = storage.get_entity_archetype(ent_id)?; + + if terms + .absent + .iter() + .all(|absent_comp_id| !ent_archetype.contains_matching_component(*absent_comp_id)) + && terms.archetype_contains_all_required(ent_archetype) + && do_traversals(storage, ent_archetype, &terms.traverse, results).is_some() + { + results.push(TraversalResult { + relation: traversal.relation, + term_metadata: traversal.term_metadata, + found_ent: ent_id, + }); + + return Some(()); + } + + for relationship in ent_archetype.get_matching_component_ids(traversal.relationship()) + { + if traverse_dfs(storage, relationship.target(), traversal, terms, results) + .is_some() + { + return Some(()); + } + } + + None } #[cfg(test)] |