diff options
Diffstat (limited to 'engine-ecs/src/component/storage.rs')
| -rw-r--r-- | engine-ecs/src/component/storage.rs | 795 |
1 files changed, 795 insertions, 0 deletions
diff --git a/engine-ecs/src/component/storage.rs b/engine-ecs/src/component/storage.rs new file mode 100644 index 0000000..dc38b6a --- /dev/null +++ b/engine-ecs/src/component/storage.rs @@ -0,0 +1,795 @@ +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()) + ); + } +} |