diff options
Diffstat (limited to 'ecs/src/component/storage.rs')
| -rw-r--r-- | ecs/src/component/storage.rs | 251 |
1 files changed, 226 insertions, 25 deletions
diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs index 0e1a03d..b68f89d 100644 --- a/ecs/src/component/storage.rs +++ b/ecs/src/component/storage.rs @@ -1,7 +1,9 @@ use std::any::type_name; -use std::iter::{Chain, Flatten}; +use std::array::IntoIter as ArrayIter; +use std::cell::RefCell; +use std::vec::IntoIter as VecIntoIter; -use hashbrown::{HashMap, HashSet}; +use hashbrown::HashMap; use crate::component::storage::archetype::{ Archetype, @@ -9,13 +11,15 @@ use crate::component::storage::archetype::{ Id as ArchetypeId, }; use crate::component::storage::graph::{ - ArchetypeAddEdgeRecursiveIter, + ArchetypeAddEdgeDfsIter, + ArchetypeAddEdgeDfsIterResult, ArchetypeEdges, Graph, }; use crate::component::{Component, Metadata as ComponentMetadata}; use crate::type_name::TypeName; use crate::uid::{Kind as UidKind, Uid}; +use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt}; use crate::EntityComponent; pub mod archetype; @@ -27,27 +31,50 @@ pub struct Storage { graph: Graph, entity_archetype_lookup: HashMap<Uid, ArchetypeId>, + imaginary_archetypes: RefCell<Vec<ImaginaryArchetype>>, } impl Storage { - pub fn iter_archetypes_with_comps( + pub fn search_archetypes( &self, - component_metadata: impl AsRef<[ComponentMetadata]>, + component_metadata: &[ComponentMetadata], ) -> ArchetypeRefIter<'_> { - let archetype_id = ArchetypeId::from_components_metadata(&component_metadata); + let archetype_id = ArchetypeId::from_components_metadata(component_metadata); + + let Some(add_edge_recursive_iter) = + self.graph.dfs_archetype_add_edges(archetype_id) + else { + self.imaginary_archetypes + .borrow_mut() + .push(ImaginaryArchetype { + id: archetype_id, + component_ids: component_metadata + .iter() + .filter_map(|comp_metadata| { + if comp_metadata.is_optional { + return None; + } + + Some(comp_metadata.id) + }) + .collect::<Vec<_>>(), + }); + + let found_archetypes = self.find_all_archetype_with_comps(component_metadata); + + return ArchetypeRefIter { + storage: self, + pre_iter: Either::B(found_archetypes.clone().into_iter()), + dfs_iter: ArchetypeAddEdgeDfsIter::new(&self.graph, &found_archetypes), + }; + }; ArchetypeRefIter { storage: self, - iter: [archetype_id].into_iter().chain( - self.graph - .recurse_archetype_add_edges(archetype_id) - .into_iter() - .flatten() - .flatten(), - ), - visited: HashSet::new(), + pre_iter: Either::A([archetype_id].into_iter()), + dfs_iter: add_edge_recursive_iter, } } @@ -288,6 +315,69 @@ impl Storage Ok(()) } + + pub fn create_imaginary_archetypes(&mut self) + { + for imaginary_archetype in self.imaginary_archetypes.get_mut().drain(..) { + if self.graph.contains_archetype(imaginary_archetype.id) { + continue; + } + + self.graph + .create_node(imaginary_archetype.id, &imaginary_archetype.component_ids); + } + } + + fn find_all_archetype_with_comps( + &self, + component_metadata: &[ComponentMetadata], + ) -> Vec<ArchetypeId> + { + let comp_metadata_not_opt_cnt = component_metadata + .iter() + .filter(|comp_metadata| !comp_metadata.is_optional) + .count(); + + let Some(mut search_iter) = + self.graph.dfs_archetype_add_edges(ArchetypeId::new(&[])) + else { + // If the root archetype doesn't exist, no other archetype can exist either + return Vec::new(); + }; + + let mut found = Vec::<ArchetypeId>::new(); + + while let Some(node_id) = search_iter.streaming_next() { + let ArchetypeAddEdgeDfsIterResult::AddEdge(node_id) = node_id else { + continue; + }; + + let node = self + .graph + .get_node_by_id(node_id) + .expect("Graph node found through DFS doesn't exist"); + + if node.archetype().component_cnt() < comp_metadata_not_opt_cnt { + continue; + } + + if !component_metadata + .iter() + .filter(|comp_metadata| !comp_metadata.is_optional) + .all(|comp_metadata| { + node.archetype().has_component_with_id(comp_metadata.id) + }) + { + continue; + } + + found.push(node.archetype().id()); + + search_iter.pop(); + } + + found + } } impl TypeName for Storage @@ -302,11 +392,8 @@ impl TypeName for Storage pub struct ArchetypeRefIter<'storage> { storage: &'storage Storage, - iter: Chain< - std::array::IntoIter<ArchetypeId, 1>, - Flatten<Flatten<std::option::IntoIter<ArchetypeAddEdgeRecursiveIter<'storage>>>>, - >, - visited: HashSet<ArchetypeId>, + pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>, + dfs_iter: ArchetypeAddEdgeDfsIter<'storage>, } impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage> @@ -315,15 +402,122 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage> fn next(&mut self) -> Option<Self::Item> { - let archetype_id = self - .iter - .find(|archetype_id| !self.visited.contains(archetype_id))?; + 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"), + ); + } - let archetype = self.storage.get_archetype_by_id(archetype_id)?; + let archetype_id = loop { + match self.dfs_iter.streaming_find(|res| { + matches!( + res, + ArchetypeAddEdgeDfsIterResult::AddEdge { .. } + | ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { .. } + ) + })? { + ArchetypeAddEdgeDfsIterResult::AddEdge(add_edge_archetype_id) => { + break add_edge_archetype_id + } + ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { + archetype, + add_edge_archetype_id, + add_edge_component_id, + } => { + let mut add_edge_archetype_comps = archetype + .component_ids_sorted() + .map(|id| ComponentMetadata { id, is_optional: false }) + .collect::<Vec<_>>(); + + add_edge_archetype_comps.insert_at_partition_point_by_key( + ComponentMetadata::new_non_optional(add_edge_component_id), + |comp_metadata| comp_metadata.id, + ); + + self.storage.imaginary_archetypes.borrow_mut().push( + ImaginaryArchetype { + id: add_edge_archetype_id, + component_ids: add_edge_archetype_comps + .iter() + .map(|comp_metadata| comp_metadata.id) + .collect::<Vec<_>>(), + }, + ); + + let found = + self.find_edges_of_imaginary_archetype(&add_edge_archetype_comps); + + self.dfs_iter.push(( + BorrowedOrOwned::Owned(Archetype::new( + add_edge_archetype_id, + &add_edge_archetype_comps + .iter() + .map(|metadata| metadata.id) + .collect::<Vec<_>>(), + )), + found.into_iter(), + )); + + continue; + } + _ => { + unreachable!(); + } + } + }; - self.visited.insert(archetype_id); + Some( + self.storage + .get_archetype_by_id(archetype_id) + .expect("Archetype should exist"), + ) + } +} - Some(archetype) +impl<'storage> ArchetypeRefIter<'storage> +{ + fn find_edges_of_imaginary_archetype( + &self, + imaginary_archetype_comps: &[ComponentMetadata], + ) -> Vec<(Uid, ArchetypeEdges)> + { + self.storage + .find_all_archetype_with_comps(&imaginary_archetype_comps) + .into_iter() + .filter_map(|found_id| { + let found_archetype = self.storage.get_archetype_by_id(found_id).unwrap(); + + if found_archetype.component_cnt() < imaginary_archetype_comps.len() + 1 { + return None; + } + + let unique_comp_id = found_archetype + .component_ids_sorted() + .find(|id| { + !imaginary_archetype_comps + .iter() + .any(|comp_metadata| comp_metadata.id == *id) + }) + .expect("Oh noooo"); + + let mut add_edge_comp_ids = imaginary_archetype_comps + .iter() + .map(|comp_metadata| comp_metadata.id) + .collect::<Vec<_>>(); + + add_edge_comp_ids + .insert_at_partition_point_by_key(unique_comp_id, |id| *id); + + let add_edge = ArchetypeId::new(&add_edge_comp_ids); + + Some(( + unique_comp_id, + ArchetypeEdges { add: Some(add_edge), remove: None }, + )) + }) + .collect::<Vec<_>>() } } @@ -349,6 +543,13 @@ pub enum Error }, } +#[derive(Debug)] +struct ImaginaryArchetype +{ + id: ArchetypeId, + component_ids: Vec<Uid>, +} + #[cfg(test)] mod tests { |