summaryrefslogtreecommitdiff
path: root/ecs/src/component/storage.rs
diff options
context:
space:
mode:
Diffstat (limited to 'ecs/src/component/storage.rs')
-rw-r--r--ecs/src/component/storage.rs251
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
{