diff options
| author | HampusM <hampus@hampusmat.com> | 2026-05-21 17:55:20 +0200 |
|---|---|---|
| committer | HampusM <hampus@hampusmat.com> | 2026-05-21 17:55:20 +0200 |
| commit | 8022e8998290b067b8aa0cb9cba8ba410826bdab (patch) | |
| tree | 7171e79ce530e03079046ee8fd12167160c45480 /ecs/src/component/storage.rs | |
| parent | 412cee02c252f91bcf0b70a3f5cc5fca6d2b4c62 (diff) | |
chore: rename ecs* crates to engine-ecs*
Diffstat (limited to 'ecs/src/component/storage.rs')
| -rw-r--r-- | ecs/src/component/storage.rs | 795 |
1 files changed, 0 insertions, 795 deletions
diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs deleted file mode 100644 index dc38b6a..0000000 --- a/ecs/src/component/storage.rs +++ /dev/null @@ -1,795 +0,0 @@ -use std::any::Any; -use std::array::IntoIter as ArrayIter; -use std::cell::RefCell; -use std::vec::IntoIter as VecIntoIter; - -use hashbrown::HashMap; - -use crate::component::storage::archetype::{ - Archetype, - Entity as ArchetypeEntity, - EntityComponent as ArchetypeEntityComponent, - Id as ArchetypeId, -}; -use crate::component::storage::graph::{ - ArchetypeAddEdgeDfsIter, - ArchetypeAddEdgeDfsIterResult, - ArchetypeEdges, - Graph, -}; -use crate::uid::{Kind as UidKind, Uid}; -use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt}; - -pub mod archetype; - -mod graph; - -#[derive(Debug)] -pub struct ArchetypeSearchTerms<'a> -{ - pub required_components: &'a [Uid], - pub excluded_components: &'a [Uid], -} - -impl ArchetypeSearchTerms<'_> -{ - fn excluded_contains(&self, comp_id: Uid) -> bool - { - let comp_id_kind = comp_id.kind(); - - debug_assert!( - comp_id_kind == UidKind::Component - || (comp_id_kind == UidKind::Pair - && comp_id.target_component() != Uid::wildcard()) - ); - - let is_found = self.excluded_components.binary_search(&comp_id).is_ok(); - - if !is_found && comp_id_kind == UidKind::Pair { - return self.excluded_components.iter().any(|excluded_comp_id| { - excluded_comp_id.kind() == UidKind::Pair - && excluded_comp_id.has_same_relation_as(comp_id) - && excluded_comp_id.target_component() == Uid::wildcard() - }); - } - - is_found - } - - fn contains_conflicting(&self) -> bool - { - self.excluded_components.iter().any(|excluded_comp_id| { - self.required_components - .binary_search(excluded_comp_id) - .is_ok() - }) - } - - fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool - { - self.required_components - .iter() - .all(|comp_id| archetype.contains_matching_component(*comp_id)) - } -} - -#[derive(Debug, Default)] -pub struct Storage -{ - graph: Graph, - entity_archetype_lookup: HashMap<Uid, ArchetypeId>, - imaginary_archetypes: RefCell<Vec<ImaginaryArchetype>>, -} - -impl Storage -{ - pub fn search_archetypes<'search_terms>( - &self, - search_terms: ArchetypeSearchTerms<'search_terms>, - ) -> ArchetypeRefIter<'_, 'search_terms> - { - let archetype_id = ArchetypeId::new(search_terms.required_components); - - if search_terms.contains_conflicting() { - return ArchetypeRefIter { - storage: self, - pre_iter: Either::B(Vec::new().into_iter()), - dfs_iter: ArchetypeAddEdgeDfsIter::new(&self.graph, &[]), - search_terms, - }; - } - - let Some(add_edge_recursive_iter) = - self.graph.dfs_archetype_add_edges(archetype_id) - else { - self.imaginary_archetypes - .borrow_mut() - .push(ImaginaryArchetype { - id: ArchetypeId::new(search_terms.required_components.iter().filter( - |required_comp_id| { - required_comp_id.kind() != UidKind::Pair - || required_comp_id.target_component() != Uid::wildcard() - }, - )), - component_ids: search_terms - .required_components - .iter() - .copied() - .filter(|required_comp_id| { - required_comp_id.kind() != UidKind::Pair - || required_comp_id.target_component() != Uid::wildcard() - }) - .collect(), - }); - - let found_archetypes = self.find_all_archetype_with_comps(&search_terms); - - return ArchetypeRefIter { - storage: self, - pre_iter: Either::B(found_archetypes.clone().into_iter()), - dfs_iter: ArchetypeAddEdgeDfsIter::new(&self.graph, &found_archetypes), - search_terms, - }; - }; - - ArchetypeRefIter { - storage: self, - pre_iter: Either::A([archetype_id].into_iter()), - dfs_iter: add_edge_recursive_iter, - search_terms, - } - } - - pub fn get_archetype_by_id(&self, id: ArchetypeId) -> Option<&Archetype> - { - Some(self.graph.get_node_by_id(id)?.archetype()) - } - - pub fn create_entity(&mut self, uid: Uid) -> Result<(), EntityAlreadyExistsError> - { - debug_assert_eq!(uid.kind(), UidKind::Entity); - - if self.entity_archetype_lookup.contains_key(&uid) { - return Err(EntityAlreadyExistsError); - } - - let empty_archetype_id = ArchetypeId::new_empty(); - - let archetype_node = self.graph.get_or_create_node(empty_archetype_id, &[]); - - archetype_node - .archetype_mut() - .push_entity(ArchetypeEntity::new(uid, [])); - - self.entity_archetype_lookup.insert(uid, empty_archetype_id); - - Ok(()) - } - - pub fn remove_entity(&mut self, entity_uid: Uid) -> Result<ArchetypeEntity, Error> - { - let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { - return Err(Error::EntityDoesNotExist(entity_uid)); - }; - - let archetype_node = self - .graph - .get_node_by_id_mut(*archetype_id) - .expect("Archetype should exist"); - - let entity = archetype_node - .archetype_mut() - .remove_entity(entity_uid) - .expect("Entity should exist in archetype"); - - self.entity_archetype_lookup.remove(&entity_uid); - - Ok(entity) - } - - pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype> - { - let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; - - self.get_archetype_by_id(*archetype_id) - } - - pub fn add_entity_component( - &mut self, - entity_uid: Uid, - (component_id, component_name, component): (Uid, &'static str, Box<dyn Any>), - ) -> Result<(), Error> - { - let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { - return Err(Error::EntityDoesNotExist(entity_uid)); - }; - - let archetype_id = *archetype_id; - - let archetype_node = self - .graph - .get_node_by_id_mut(archetype_id) - .expect("Archetype should exist"); - - if archetype_node - .archetype() - .contains_component_with_exact_id(component_id) - { - return Err(Error::ComponentAlreadyInEntity { - entity: entity_uid, - component: component_id, - }); - } - - let add_edge_archetype_id = if let Some(add_edge_id) = archetype_node - .get_or_insert_edges(component_id, ArchetypeEdges::default) - .add - { - if !self.graph.contains_archetype(add_edge_id) { - let (_, add_edge_comp_ids) = self - .graph - .get_node_by_id(archetype_id) - .expect("Archetype should exist") - .make_add_edge(component_id); - - self.graph.create_node(add_edge_id, &add_edge_comp_ids); - } - - add_edge_id - } else { - let archetype_node = self - .graph - .get_node_by_id(archetype_id) - .expect("Archetype should exist"); - - let (add_edge_id, add_edge_comp_ids) = - archetype_node.make_add_edge(component_id); - - if !self.graph.contains_archetype(add_edge_id) { - self.graph.create_node(add_edge_id, &add_edge_comp_ids); - } - - add_edge_id - }; - - let archetype_node = self - .graph - .get_node_by_id_mut(archetype_id) - .expect("Archetype should exist"); - - let mut entity = archetype_node - .archetype_mut() - .remove_entity(entity_uid) - .expect("Entity should exist in archetype"); - - let add_edge_archetype = self - .graph - .get_node_by_id_mut(add_edge_archetype_id) - .expect("Add edge archetype should exist") - .archetype_mut(); - - entity.insert_component( - component_id, - ArchetypeEntityComponent::new(component, component_name), - add_edge_archetype, - ); - - add_edge_archetype.push_entity(entity); - - self.entity_archetype_lookup - .insert(entity_uid, add_edge_archetype_id); - - Ok(()) - } - - pub fn remove_entity_component( - &mut self, - entity_uid: Uid, - component_id: Uid, - ) -> Result<(), Error> - { - let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { - return Err(Error::EntityDoesNotExist(entity_uid)); - }; - - let archetype_id = *archetype_id; - - let archetype_node = self - .graph - .get_node_by_id_mut(archetype_id) - .expect("Archetype should exist"); - - if !archetype_node - .archetype() - .contains_component_with_exact_id(component_id) - { - return Err(Error::ComponentNotFoundInEntity { - entity: entity_uid, - component: component_id, - }); - } - - let remove_edge_id = archetype_node - .get_or_insert_edges(component_id, ArchetypeEdges::default) - .remove - .unwrap_or_else(|| { - let archetype_node = self - .graph - .get_node_by_id_mut(archetype_id) - .expect("Archetype should exist"); - - let (remove_edge_id, remove_edge_comp_ids) = - archetype_node.make_remove_edge(component_id); - - if !self.graph.contains_archetype(remove_edge_id) { - self.graph - .create_node(remove_edge_id, &remove_edge_comp_ids); - } - - remove_edge_id - }); - - let archetype_node = self - .graph - .get_node_by_id_mut(archetype_id) - .expect("Archetype should exist"); - - let mut entity = archetype_node - .archetype_mut() - .remove_entity(entity_uid) - .expect("Entity should exist in archetype"); - - let removed_component = - entity.remove_component(component_id, archetype_node.archetype()); - - self.graph - .get_node_by_id_mut(remove_edge_id) - .expect("Remove edge archetype should exist") - .archetype_mut() - .push_entity(entity); - - self.entity_archetype_lookup - .insert(entity_uid, remove_edge_id); - - tracing::debug!( - entity_id = %entity_uid, - component_id = %component_id, - component_name = removed_component.name(), - "Removed component from entity" - ); - - 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, - search_terms: &ArchetypeSearchTerms<'_>, - ) -> Vec<ArchetypeId> - { - let Some(mut search_iter) = - self.graph.dfs_archetype_add_edges(ArchetypeId::new_empty()) - else { - // If the root archetype doesn't exist, no other archetype can exist either - // - // TODO: The above comment is not true. Cases where imaginary archetypes have - // been created should be handled as well - return Vec::new(); - }; - - let mut found = Vec::<ArchetypeId>::new(); - - while let Some(node_id) = search_iter.streaming_next() { - let ArchetypeAddEdgeDfsIterResult::AddEdge { - add_edge_archetype_id: node_id, - add_edge_component_id, - } = node_id - else { - continue; - }; - - if search_terms.excluded_contains(add_edge_component_id) { - search_iter.pop(); - 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() < search_terms.required_components.len() { - continue; - } - - if !search_terms.archetype_contains_all_required(node.archetype()) { - continue; - } - - found.push(node.archetype().id()); - - search_iter.pop(); - } - - found - } -} - -#[cfg(feature = "vizoxide")] -impl Storage -{ - pub fn create_vizoxide_archetype_graph( - &self, - graph_name: impl AsRef<str>, - params: VizoxideArchetypeGraphParams, - ) -> Result<vizoxide::Graph, vizoxide::GraphvizError> - { - let viz_graph = vizoxide::Graph::builder(graph_name.as_ref()) - .strict(true) - .directed(true) - .build()?; - - let mut viz_node_lookup = HashMap::new(); - - for node in self.graph.iter_nodes() { - let id = node.archetype().id(); - - if !viz_node_lookup.contains_key(&id) { - let node = self.graph.get_node_by_id(id).unwrap(); - - let viz_node = (params.create_node_cb)( - node.archetype(), - ArchetypeMetadata { is_imaginary: false }, - viz_graph.create_node(&(params.create_node_name)( - node.archetype(), - ArchetypeMetadata { is_imaginary: false }, - )), - ) - .build()?; - - viz_node_lookup.insert(id, viz_node); - } - - for (edge_comp_id, edges) in node.iter_edges() { - if let Some(add_edge) = edges.add { - if !viz_node_lookup.contains_key(&add_edge) { - let viz_node = self.create_vizoxide_archetype_graph_edge_node( - &viz_graph, - node, - add_edge, - *edge_comp_id, - ¶ms, - )?; - - viz_node_lookup.insert(add_edge, viz_node); - } - - (params.create_edge_cb)( - node.archetype(), - *edge_comp_id, - VizoxideArchetypeGraphEdgeKind::Add, - viz_graph.create_edge( - viz_node_lookup.get(&id).unwrap(), - viz_node_lookup.get(&add_edge).unwrap(), - Some(&format!("Add {}", edge_comp_id.id())), - ), - ) - .build()?; - } - - if let Some(remove_edge) = edges.remove { - if !viz_node_lookup.contains_key(&remove_edge) { - let viz_node = self.create_vizoxide_archetype_graph_edge_node( - &viz_graph, - node, - remove_edge, - *edge_comp_id, - ¶ms, - )?; - - viz_node_lookup.insert(remove_edge, viz_node); - } - - (params.create_edge_cb)( - node.archetype(), - *edge_comp_id, - VizoxideArchetypeGraphEdgeKind::Remove, - viz_graph.create_edge( - viz_node_lookup.get(&id).unwrap(), - viz_node_lookup.get(&remove_edge).unwrap(), - Some(&format!("Remove {}", edge_comp_id.id())), - ), - ) - .build()?; - } - } - } - - drop(viz_node_lookup); - - Ok(viz_graph) - } - - fn create_vizoxide_archetype_graph_edge_node<'vizoxide_graph>( - &self, - viz_graph: &'vizoxide_graph vizoxide::Graph, - node: &graph::ArchetypeNode, - edge_id: ArchetypeId, - edge_comp_id: Uid, - params: &VizoxideArchetypeGraphParams, - ) -> Result<vizoxide::Node<'vizoxide_graph>, vizoxide::GraphvizError> - { - match self.graph.get_node_by_id(edge_id) { - Some(edge_node) => (params.create_node_cb)( - edge_node.archetype(), - ArchetypeMetadata { is_imaginary: false }, - viz_graph.create_node(&(params.create_node_name)( - edge_node.archetype(), - ArchetypeMetadata { is_imaginary: false }, - )), - ) - .build(), - None => { - let mut comp_ids = - node.archetype().component_ids_sorted().collect::<Vec<_>>(); - - let insert_index = comp_ids.partition_point(|cid| *cid <= edge_comp_id); - - comp_ids.insert(insert_index, edge_comp_id); - - let imaginary_edge_archetype = Archetype::new(edge_id, comp_ids); - - (params.create_node_cb)( - &imaginary_edge_archetype, - ArchetypeMetadata { is_imaginary: true }, - viz_graph.create_node(&(params.create_node_name)( - &imaginary_edge_archetype, - ArchetypeMetadata { is_imaginary: true }, - )), - ) - .build() - } - } - } -} - -#[cfg(feature = "vizoxide")] -pub struct VizoxideArchetypeGraphParams -{ - pub create_node_name: fn(&Archetype, ArchetypeMetadata) -> std::borrow::Cow<'_, str>, - pub create_node_cb: for<'storage, 'graph> fn( - &'storage Archetype, - ArchetypeMetadata, - vizoxide::NodeBuilder<'graph>, - ) -> vizoxide::NodeBuilder<'graph>, - pub create_edge_cb: for<'storage, 'graph> fn( - &'storage Archetype, - Uid, - VizoxideArchetypeGraphEdgeKind, - vizoxide::EdgeBuilder<'graph>, - ) -> vizoxide::EdgeBuilder<'graph>, -} - -#[cfg(feature = "vizoxide")] -#[derive(Debug, Clone)] -pub struct ArchetypeMetadata -{ - pub is_imaginary: bool, -} - -#[cfg(feature = "vizoxide")] -#[derive(Debug, Clone, Copy)] -pub enum VizoxideArchetypeGraphEdgeKind -{ - Add, - Remove, -} - -#[derive(Debug)] -pub struct ArchetypeRefIter<'storage, 'search_terms> -{ - storage: &'storage Storage, - pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>, - dfs_iter: ArchetypeAddEdgeDfsIter<'storage>, - search_terms: ArchetypeSearchTerms<'search_terms>, -} - -impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> -{ - type Item = &'component_storage Archetype; - - 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"), - ); - } - - let archetype_id = loop { - match self.dfs_iter.streaming_find(|res| { - matches!( - res, - ArchetypeAddEdgeDfsIterResult::AddEdge { .. } - | ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { .. } - ) - })? { - ArchetypeAddEdgeDfsIterResult::AddEdge { - add_edge_archetype_id, - add_edge_component_id, - } => { - if self.search_terms.excluded_contains(add_edge_component_id) { - self.dfs_iter.pop(); - continue; - } - - break add_edge_archetype_id; - } - ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { - archetype, - add_edge_archetype_id, - add_edge_component_id, - } => { - if self.search_terms.excluded_contains(add_edge_component_id) { - continue; - } - - let mut add_edge_archetype_comps = - archetype.component_ids_sorted().collect::<Vec<_>>(); - - add_edge_archetype_comps - .insert_at_part_pt_by_key(add_edge_component_id, |comp_id| { - comp_id - }); - - self.storage.imaginary_archetypes.borrow_mut().push( - ImaginaryArchetype { - id: add_edge_archetype_id, - component_ids: add_edge_archetype_comps.clone(), - }, - ); - - 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.clone(), - )), - found.into_iter(), - )); - } - _ => { - unreachable!(); - } - } - }; - - Some( - self.storage - .get_archetype_by_id(archetype_id) - .expect("Archetype should exist"), - ) - } -} - -impl ArchetypeRefIter<'_, '_> -{ - fn find_edges_of_imaginary_archetype( - &self, - imaginary_archetype_comps: &[Uid], - ) -> Vec<(Uid, ArchetypeEdges)> - { - self.storage - .find_all_archetype_with_comps(&ArchetypeSearchTerms { - required_components: imaginary_archetype_comps, - excluded_components: &[], - }) - .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(|found_archetype_comp_id| { - !imaginary_archetype_comps.iter().any( - |imaginary_archetype_comp_id| { - *imaginary_archetype_comp_id == *found_archetype_comp_id - }, - ) - }) - .expect("Oh noooo"); - - let mut add_edge_comp_ids = imaginary_archetype_comps.to_vec(); - - add_edge_comp_ids.insert_at_part_pt_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<_>>() - } -} - -#[derive(Debug, thiserror::Error)] -pub enum Error -{ - #[error("Entity with ID {0:?} does not exist")] - EntityDoesNotExist(Uid), - - #[error("Entity with ID {entity:?} already has component with ID {component:?}")] - ComponentAlreadyInEntity - { - entity: Uid, component: Uid - }, - - #[error("Entity with ID {entity:?} does not have component with ID {component:?}")] - ComponentNotFoundInEntity - { - entity: Uid, component: Uid - }, -} - -#[derive(Debug, thiserror::Error)] -#[error("Entity with already exists")] -pub struct EntityAlreadyExistsError; - -#[derive(Debug)] -struct ImaginaryArchetype -{ - id: ArchetypeId, - component_ids: Vec<Uid>, -} - -#[cfg(test)] -mod tests -{ - use crate::component::storage::Storage; - use crate::component::storage::archetype::Id as ArchetypeId; - use crate::uid::{Kind as UidKind, Uid}; - - #[test] - fn create_entity_works() - { - let mut new_storage = Storage::default(); - - let uid = Uid::new_unique(UidKind::Entity); - - new_storage.create_entity(uid).expect("Expected Ok"); - - let archetype_node = new_storage - .graph - .get_node_by_id(ArchetypeId::new_empty()) - .expect("Archetype for entities with no component doesn't exist"); - - assert_eq!(archetype_node.archetype().component_cnt(), 0); - assert_eq!(archetype_node.archetype().entity_cnt(), 1); - - assert_eq!( - new_storage.entity_archetype_lookup.get(&uid).copied(), - Some(ArchetypeId::new_empty()) - ); - } -} |
