From 9226356b7b54c4c5b036b6fee00bba376245c5f3 Mon Sep 17 00:00:00 2001 From: HampusM Date: Fri, 24 Jul 2026 22:32:21 +0200 Subject: feat(engine-ecs): add traversal query term --- engine-ecs/src/component/storage.rs | 240 +++++++++++++++++++++----- engine-ecs/src/component/storage/archetype.rs | 32 +++- 2 files changed, 223 insertions(+), 49 deletions(-) (limited to 'engine-ecs/src/component') 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 { - pub present: &'a [Uid], - pub absent: &'a [Uid], + pub(crate) present: ArrayVec, + pub(crate) absent: ArrayVec, + pub(crate) traverse: ArrayVec, 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 +{ + pub kind: TraversalKind, + pub relation: Uid, + pub terms: fn(&Self) -> SearchTerms, + pub term_metadata: TermMetadata, +} + +impl Traversal +{ + 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 SearchTerms { 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, + ) -> 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( &self, - search_terms: &ArchetypeSearchTerms<'_>, + search_terms: &SearchTerms, ) -> Vec { 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, VecIntoIter>, dfs_iter: ArchetypeAddEdgeDfsIter<'storage>, - search_terms: ArchetypeSearchTerms<'search_terms>, + search_terms: &'search_terms SearchTerms, } -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, + ); fn next(&mut self) -> Option { - 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::::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::::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::>(); + let mut add_edge_archetype_comps = archetype + .component_ids_sorted() + .collect::>(); 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 ArchetypeRefIter<'_, '_, TERM_CAP> { fn find_edges_of_imaginary_archetype( &self, - imaginary_archetype_comps: &[Uid], + imaginary_archetype_comps: ArrayVec, ) -> 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, + component_ids: ArrayVec, +} + +fn do_traversals( + storage: &Storage, + archetype: &Archetype, + traversals: &[Traversal], + results: &mut ArrayVec, +) -> 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( + storage: &Storage, + ent_id: Uid, + traversal: &Traversal, + terms: &SearchTerms, + results: &mut ArrayVec, +) -> 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)] diff --git a/engine-ecs/src/component/storage/archetype.rs b/engine-ecs/src/component/storage/archetype.rs index c5cce10..236bf97 100644 --- a/engine-ecs/src/component/storage/archetype.rs +++ b/engine-ecs/src/component/storage/archetype.rs @@ -107,11 +107,6 @@ impl Archetype 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() @@ -182,6 +177,33 @@ impl Archetype self.contains_component_with_exact_id(component_id) } + pub fn get_matching_component_ids( + &self, + component_id: Uid, + ) -> impl Iterator + use<'_> + { + if component_id.is_pair() && component_id.target() == Uid::wildcard() { + return Either::A( + self.component_ids + .iter() + .filter(move |other_comp_id| { + other_comp_id.is_pair() + && other_comp_id.has_same_relation_as(component_id) + }) + .copied(), + ); + } + + Either::B( + (if self.contains_component_with_exact_id(component_id) { + Some(component_id) + } else { + None + }) + .into_iter(), + ) + } + pub fn contains_component_with_exact_id(&self, component_id: Uid) -> bool { debug_assert!( -- cgit v1.2.3-18-g5258