diff options
Diffstat (limited to 'ecs/src/component')
| -rw-r--r-- | ecs/src/component/local.rs | 61 | ||||
| -rw-r--r-- | ecs/src/component/storage.rs | 798 | ||||
| -rw-r--r-- | ecs/src/component/storage/archetype.rs | 300 | ||||
| -rw-r--r-- | ecs/src/component/storage/graph.rs | 420 |
4 files changed, 0 insertions, 1579 deletions
diff --git a/ecs/src/component/local.rs b/ecs/src/component/local.rs deleted file mode 100644 index 0f6f641..0000000 --- a/ecs/src/component/local.rs +++ /dev/null @@ -1,61 +0,0 @@ -use std::ops::{Deref, DerefMut}; - -use crate::component::{Component, HandleMut as ComponentHandleMut}; -use crate::system::{Param as SystemParam, System}; -use crate::World; - -/// Holds a component which is local to a single system. -#[derive(Debug)] -pub struct Local<'world, LocalComponent: Component> -{ - local_component: ComponentHandleMut<'world, LocalComponent>, -} - -impl<'world, LocalComponent> SystemParam<'world> for Local<'world, LocalComponent> -where - LocalComponent: Component, -{ - type Input = LocalComponent; - - fn initialize<SystemImpl>( - system: &mut impl System<'world, SystemImpl>, - input: Self::Input, - ) - { - system.set_local_component(input); - } - - fn new<SystemImpl>( - system: &'world impl System<'world, SystemImpl>, - _world: &'world World, - ) -> Self - { - let local_component = system - .get_local_component_mut::<LocalComponent>() - .expect("Local component is uninitialized"); - - Self { local_component } - } -} - -impl<LocalComponent> Deref for Local<'_, LocalComponent> -where - LocalComponent: Component, -{ - type Target = LocalComponent; - - fn deref(&self) -> &Self::Target - { - &self.local_component - } -} - -impl<LocalComponent> DerefMut for Local<'_, LocalComponent> -where - LocalComponent: Component, -{ - fn deref_mut(&mut self) -> &mut Self::Target - { - &mut self.local_component - } -} diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs deleted file mode 100644 index 40909fb..0000000 --- a/ecs/src/component/storage.rs +++ /dev/null @@ -1,798 +0,0 @@ -use std::any::type_name; -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::component::Component; -use crate::type_name::TypeName; -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, uid: Uid) -> bool - { - self.excluded_components.binary_search(&uid).is_ok() - } - - fn required_contains(&self, uid: Uid) -> bool - { - self.required_components.binary_search(&uid).is_ok() - } -} - -#[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 - .excluded_components - .iter() - .any(|excluded_comp_id| search_terms.required_contains(*excluded_comp_id)) - { - 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: archetype_id, - component_ids: search_terms.required_components.to_vec(), - }); - - 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<(), Error> - { - debug_assert_eq!(uid.kind(), UidKind::Entity); - - if self.entity_archetype_lookup.contains_key(&uid) { - return Err(Error::EntityAlreadyExists(uid)); - } - - let empty_archetype_id = ArchetypeId::from_components_metadata(&[]); - - 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: (Uid, Box<dyn Component>), - ) -> Result<(), Error> - { - let (component_id, component) = component; - - debug_assert!( - !component.self_is_optional(), - "Adding a optional component to a entity is not supported" - ); - - 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() - .has_component_with_id(component_id) - { - return Err(Error::ComponentAlreadyInEntity { - entity: entity_uid, - component: component_id, - }); - } - - let add_edge_archetype_id = match archetype_node - .get_or_insert_edges(component_id, ArchetypeEdges::default) - .add - { - Some(add_edge_id) => { - 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 - } - None => { - let archetype_node = self - .graph - .get_node_by_id_mut(archetype_id) - .expect("Archetype should exist"); - - let (add_edge_id, add_edge_comp_ids) = - archetype_node.make_add_edge(component_id); - - archetype_node - .get_edges_mut(component_id) - .expect("Edges for component in archetype should exist") - .add = Some(add_edge_id); - - if !self.graph.contains_archetype(add_edge_id) { - self.graph.create_node(add_edge_id, &add_edge_comp_ids); - } - - add_edge_id - } - }; - - { - let add_edge_archetype_node = self - .graph - .get_node_by_id_mut(add_edge_archetype_id) - .expect("Add edge archetype should exist"); - - let add_edge_archetype_edges = add_edge_archetype_node - .get_or_insert_edges(component_id, ArchetypeEdges::default); - - add_edge_archetype_edges.remove = Some(archetype_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), - 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() - .has_component_with_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); - - archetype_node - .get_edges_mut(component_id) - .expect("Edges for component in archetype should exist") - .remove = Some(remove_edge_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"); - - 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); - - 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(&[])) - 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 { - 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 - .required_components - .iter() - .all(|comp_id| node.archetype().has_component_with_id(*comp_id)) - { - continue; - } - - found.push(node.archetype().id()); - - search_iter.pop(); - } - - found - } -} - -impl TypeName for Storage -{ - fn type_name(&self) -> &'static str - { - type_name::<Self>() - } -} - -#[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, 'search_terms> Iterator - for ArchetypeRefIter<'component_storage, 'search_terms> -{ - 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_partition_point_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 - .iter() - .map(|comp_id| *comp_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.clone(), - )), - found.into_iter(), - )); - - continue; - } - _ => { - 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_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<_>>() - } -} - -#[derive(Debug, thiserror::Error)] -pub enum Error -{ - #[error("Entity with ID {0:?} already exists")] - EntityAlreadyExists(Uid), - - #[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)] -struct ImaginaryArchetype -{ - id: ArchetypeId, - component_ids: Vec<Uid>, -} - -#[cfg(test)] -mod tests -{ - use crate::component::storage::archetype::Id as ArchetypeId; - use crate::component::storage::Storage; - 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::from_components_metadata(&[])) - .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::from_components_metadata(&[])) - ); - } -} diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs deleted file mode 100644 index 5306cf9..0000000 --- a/ecs/src/component/storage/archetype.rs +++ /dev/null @@ -1,300 +0,0 @@ -use std::hash::{DefaultHasher, Hash, Hasher}; -use std::slice::Iter as SliceIter; - -use hashbrown::HashMap; - -use crate::component::{Component, Metadata as ComponentMetadata}; -use crate::lock::Lock; -use crate::uid::{Kind as UidKind, Uid}; -use crate::util::HashMapExt; - -#[derive(Debug)] -pub struct Archetype -{ - id: Id, - entities: Vec<Entity>, - entity_index_lookup: HashMap<Uid, usize>, - component_index_lookup: HashMap<Uid, usize>, - component_ids: Vec<Uid>, -} - -impl Archetype -{ - pub fn new(id: Id, component_ids: impl AsRef<[Uid]>) -> Self - { - Self { - id, - entities: Vec::new(), - entity_index_lookup: HashMap::new(), - component_index_lookup: component_ids - .as_ref() - .iter() - .enumerate() - .map(|(index, id)| (*id, index)) - .collect(), - component_ids: component_ids.as_ref().to_vec(), - } - } - - pub fn id(&self) -> Id - { - self.id - } - - pub fn is_superset(&self, other: &Self) -> bool - { - self.component_index_lookup - .keys_is_superset(&other.component_index_lookup) - } - - pub fn is_subset(&self, other: &Self) -> bool - { - self.component_index_lookup - .keys_is_subset(&other.component_index_lookup) - } - - pub fn get_entity_by_id(&self, entity_uid: Uid) -> Option<&Entity> - { - let index = *self.entity_index_lookup.get(&entity_uid)?; - - Some(self.entities.get(index).unwrap_or_else(|| { - panic!( - "In invalid state! Index of entity with ID {entity_uid:?} is out of bounds" - ); - })) - } - - pub fn push_entity(&mut self, entity: Entity) - { - self.entity_index_lookup - .insert(entity.uid, self.entities.len()); - - self.entities.push(entity); - } - - pub fn remove_entity(&mut self, entity_uid: Uid) -> Option<Entity> - { - //debug_assert_eq!(entity_uid.kind(), UidKind::Entity); - - let entity_index = self.entity_index_lookup.remove(&entity_uid)?; - - if self.entities.len() == 1 { - return Some(self.entities.remove(entity_index)); - } - - let last_entity_uid = self - .entities - .last() - .expect(concat!( - "Invalid state. No entities in archetype but entry was ", - "removed successfully from entity index lookup" - )) - .uid; - - // By using swap_remove, no memory reallocation occurs and only one index in the - // entity lookup needs to be updated - let removed_entity = self.entities.swap_remove(entity_index); - - self.entity_index_lookup - .insert(last_entity_uid, entity_index); - - Some(removed_entity) - } - - pub fn entities(&self) -> EntityIter<'_> - { - 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() - } - - pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize> - { - self.component_index_lookup.get(&component_id).copied() - } - - pub fn component_ids_unsorted(&self) -> impl Iterator<Item = Uid> + '_ - { - self.component_index_lookup.keys().copied() - } - - pub fn component_ids_sorted(&self) -> impl Iterator<Item = Uid> + '_ - { - self.component_ids.iter().copied() - } - - pub fn has_component_with_id(&self, component_id: Uid) -> bool - { - debug_assert_eq!(component_id.kind(), UidKind::Component); - - self.component_index_lookup.contains_key(&component_id) - } -} - -#[derive(Debug)] -pub struct EntityIter<'archetype> -{ - iter: SliceIter<'archetype, Entity>, -} - -impl<'archetype> Iterator for EntityIter<'archetype> -{ - type Item = &'archetype Entity; - - fn next(&mut self) -> Option<Self::Item> - { - self.iter.next() - } -} - -#[derive(Debug)] -pub struct Entity -{ - uid: Uid, - components: Vec<EntityComponent>, -} - -impl Entity -{ - pub fn new(uid: Uid, components: impl IntoIterator<Item = EntityComponent>) -> Self - { - Self { - uid, - components: components.into_iter().collect(), - } - } - - pub fn uid(&self) -> Uid - { - self.uid - } - - pub fn components(&self) -> &[EntityComponent] - { - &self.components - } - - pub fn remove_component(&mut self, component_id: Uid, archetype: &Archetype) - { - let index = archetype - .get_index_for_component(component_id) - .expect("Archetype should contain component"); - - self.components.remove(index); - } - - pub fn insert_component( - &mut self, - component_id: Uid, - component: EntityComponent, - archetype: &Archetype, - ) - { - let index = archetype - .get_index_for_component(component_id) - .expect("Archetype should contain component"); - - self.components.insert(index, component); - } -} - -#[derive(Debug)] -pub struct EntityComponent -{ - name: &'static str, - component: Lock<Box<dyn Component>>, -} - -impl EntityComponent -{ - pub fn new(component: Box<dyn Component>) -> Self - { - Self { - name: component.type_name(), - component: Lock::new(component), - } - } - - pub fn name(&self) -> &str - { - self.name - } - - pub fn component(&self) -> &Lock<Box<dyn Component>> - { - &self.component - } -} - -/// Archetype ID. -#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)] -pub struct Id -{ - hash: u64, -} - -impl Id -{ - pub fn new(component_ids: &impl AsRef<[Uid]>) -> Self - { - if component_ids.as_ref().is_empty() { - return Self { hash: 0 }; - } - - debug_assert!( - component_ids.as_ref().is_sorted(), - "Cannot create archetype ID from unsorted component IDs" - ); - - let mut hasher = DefaultHasher::new(); - - for component_id in component_ids.as_ref() { - component_id.hash(&mut hasher); - } - - Self { hash: hasher.finish() } - } - - pub fn from_components_metadata<'a>( - components_metadata: impl IntoIterator<Item = &'a ComponentMetadata>, - ) -> Self - { - let mut hasher = DefaultHasher::new(); - - let mut prev_component_id: Option<Uid> = None; - - let mut comp_metadata_iter = components_metadata.into_iter().peekable(); - - if comp_metadata_iter.peek().is_none() { - return Self { hash: 0 }; - } - - for comp_metadata in comp_metadata_iter { - if prev_component_id - .is_some_and(|prev_comp_id| comp_metadata.id < prev_comp_id) - { - panic!( - "Cannot create archetype ID from a unsorted component metadata list" - ); - } - - prev_component_id = Some(comp_metadata.id); - - if comp_metadata.is_optional { - continue; - } - - comp_metadata.id.hash(&mut hasher); - } - - Self { hash: hasher.finish() } - } -} diff --git a/ecs/src/component/storage/graph.rs b/ecs/src/component/storage/graph.rs deleted file mode 100644 index 11160e7..0000000 --- a/ecs/src/component/storage/graph.rs +++ /dev/null @@ -1,420 +0,0 @@ -use std::vec::IntoIter as VecIntoIter; - -use hashbrown::{HashMap, HashSet}; - -use crate::component::storage::archetype::{Archetype, Id as ArchetypeId}; -use crate::uid::{Kind as UidKind, Uid}; -use crate::util::{BorrowedOrOwned, StreamingIterator}; - -#[derive(Debug, Default)] -pub struct Graph -{ - nodes: Vec<ArchetypeNode>, - archetype_index_lookup: HashMap<ArchetypeId, usize>, -} - -impl Graph -{ - pub fn create_node(&mut self, id: ArchetypeId, component_ids: &impl AsRef<[Uid]>) - { - debug_assert!(!self.contains_archetype(id)); - - let _ = self.get_or_create_node(id, component_ids); - } - - pub fn get_or_create_node( - &mut self, - id: ArchetypeId, - component_ids: &impl AsRef<[Uid]>, - ) -> &mut ArchetypeNode - { - let exists_before = self.archetype_index_lookup.contains_key(&id); - - let index = *self.archetype_index_lookup.entry(id).or_insert_with(|| { - self.nodes.push(ArchetypeNode { - archetype: Archetype::new(id, component_ids.as_ref()), - edges: HashMap::new(), - }); - - self.nodes.len() - 1 - }); - - if !exists_before { - self.create_missing_edges(id); - } - - self.nodes - .get_mut(index) - .expect("Archetype index from lookup is out of bounds") - } - - pub fn contains_archetype(&self, id: ArchetypeId) -> bool - { - self.archetype_index_lookup.contains_key(&id) - } - - pub fn get_node_by_id(&self, id: ArchetypeId) -> Option<&ArchetypeNode> - { - let index = self.archetype_index_lookup.get(&id)?; - - Some(self.nodes.get(*index).unwrap_or_else(|| { - panic!("In invalid state! Index of archetype with ID {id:?} is out of bounds") - })) - } - - pub fn get_node_by_id_mut(&mut self, id: ArchetypeId) -> Option<&mut ArchetypeNode> - { - let index = self.archetype_index_lookup.get(&id)?; - - Some(self.nodes.get_mut(*index).unwrap_or_else(|| { - panic!("In invalid state! Index of archetype with ID {id:?} is out of bounds") - })) - } - - #[cfg(feature = "vizoxide")] - pub fn iter_nodes(&self) -> impl Iterator<Item = &ArchetypeNode> - { - self.nodes.iter() - } - - pub fn dfs_archetype_add_edges( - &self, - archetype_id: ArchetypeId, - ) -> Option<ArchetypeAddEdgeDfsIter> - { - let node = self.get_node_by_id(archetype_id)?; - - Some(ArchetypeAddEdgeDfsIter { - graph: self, - stack: vec![( - BorrowedOrOwned::Borrowned(node.archetype()), - node.edges - .iter() - .map(|(comp_id, edges)| (*comp_id, edges.clone())) - .collect::<Vec<_>>() - .into_iter(), - )], - visited: HashSet::new(), - }) - } - - fn create_missing_edges(&mut self, archetype_id: ArchetypeId) - { - let archetype_node_index = *self - .archetype_index_lookup - .get(&archetype_id) - .expect("Archetype should exist"); - - let (nodes_before, nodes_rest) = self.nodes.split_at_mut(archetype_node_index); - - let ([archetype_node], nodes_after) = nodes_rest.split_at_mut(1) else { - unreachable!(); - }; - - for other_archetype_node in nodes_before.iter_mut().chain(nodes_after.iter_mut()) - { - if archetype_node.archetype().component_cnt() - > other_archetype_node.archetype().component_cnt() - && other_archetype_node - .archetype() - .is_subset(archetype_node.archetype()) - { - Self::create_missing_subset_node_edges( - archetype_node, - other_archetype_node, - ); - - continue; - } - - if other_archetype_node - .archetype() - .is_superset(archetype_node.archetype()) - { - Self::create_missing_superset_node_edges( - archetype_node, - other_archetype_node, - ); - } - } - } - - fn create_missing_subset_node_edges( - target_node: &ArchetypeNode, - subset_node: &mut ArchetypeNode, - ) - { - let uniq_comp_id = target_node - .archetype() - .component_ids_sorted() - .find(|id| !subset_node.archetype().has_component_with_id(*id)) - .unwrap(); - - subset_node - .get_or_insert_edges(uniq_comp_id, ArchetypeEdges::default) - .add = Some(subset_node.make_add_edge(uniq_comp_id).0); - } - - fn create_missing_superset_node_edges( - target_node: &mut ArchetypeNode, - superset_node: &mut ArchetypeNode, - ) - { - if superset_node.archetype().component_cnt() - > target_node.archetype().component_cnt() + 1 - { - let first_unique_comp_id = superset_node - .archetype() - .component_ids_sorted() - .find(|other_archetype_comp_id| { - !target_node - .archetype() - .has_component_with_id(*other_archetype_comp_id) - }) - .or_else(|| { - if target_node.archetype().component_cnt() != 0 { - return None; - } - - superset_node.archetype().component_ids_sorted().next() - }) - .expect("Not possible"); - - target_node - .get_or_insert_edges(first_unique_comp_id, ArchetypeEdges::default) - .add = Some(target_node.make_add_edge(first_unique_comp_id).0); - - return; - } - - if superset_node.archetype().component_cnt() - != target_node.archetype().component_cnt() + 1 - { - return; - } - - let extra_comp_id = superset_node - .archetype() - .component_ids_unsorted() - .find(|comp_id| !target_node.archetype().has_component_with_id(*comp_id)) - .expect("Archetype should contain one extra component ID"); - - superset_node - .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) - .remove = Some(target_node.archetype().id()); - - target_node - .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) - .add = Some(superset_node.archetype().id()); - } -} - -#[derive(Debug)] -pub struct ArchetypeNode -{ - archetype: Archetype, - edges: HashMap<Uid, ArchetypeEdges>, -} - -impl ArchetypeNode -{ - pub fn archetype(&self) -> &Archetype - { - &self.archetype - } - - pub fn archetype_mut(&mut self) -> &mut Archetype - { - &mut self.archetype - } - - pub fn get_or_insert_edges( - &mut self, - component_id: Uid, - insert_fn: impl FnOnce() -> ArchetypeEdges, - ) -> &mut ArchetypeEdges - { - debug_assert_eq!(component_id.kind(), UidKind::Component); - - self.edges.entry(component_id).or_insert_with(insert_fn) - } - - #[cfg(feature = "vizoxide")] - pub fn iter_edges(&self) -> impl Iterator<Item = (&Uid, &ArchetypeEdges)> - { - self.edges.iter() - } - - pub fn get_edges_mut(&mut self, component_id: Uid) -> Option<&mut ArchetypeEdges> - { - debug_assert_eq!(component_id.kind(), UidKind::Component); - - self.edges.get_mut(&component_id) - } - - pub fn make_add_edge(&self, component_id: Uid) -> (ArchetypeId, Vec<Uid>) - { - let mut edge_comp_ids = self - .archetype() - .component_ids_unsorted() - .chain([component_id]) - .collect::<Vec<_>>(); - - edge_comp_ids.sort(); - - let add_edge_id = ArchetypeId::new(&edge_comp_ids); - - (add_edge_id, edge_comp_ids) - } - - pub fn make_remove_edge(&self, component_id: Uid) -> (ArchetypeId, Vec<Uid>) - { - let mut edge_comp_ids = self - .archetype() - .component_ids_unsorted() - .filter(|id| *id != component_id) - .collect::<Vec<_>>(); - - edge_comp_ids.sort(); - - let remove_edge_id = ArchetypeId::new(&edge_comp_ids); - - (remove_edge_id, edge_comp_ids) - } -} - -#[derive(Debug, Default, Clone)] -pub struct ArchetypeEdges -{ - pub add: Option<ArchetypeId>, - pub remove: Option<ArchetypeId>, -} - -type ArchetypeAddEdgeDfsIterStackElem<'graph> = ( - BorrowedOrOwned<'graph, Archetype>, - VecIntoIter<(Uid, ArchetypeEdges)>, -); - -#[derive(Debug)] -pub struct ArchetypeAddEdgeDfsIter<'graph> -{ - graph: &'graph Graph, - stack: Vec<ArchetypeAddEdgeDfsIterStackElem<'graph>>, - visited: HashSet<ArchetypeId>, -} - -impl<'graph> ArchetypeAddEdgeDfsIter<'graph> -{ - pub fn new(graph: &'graph Graph, start_nodes: &[ArchetypeId]) -> Self - { - Self { - graph, - stack: start_nodes - .iter() - .map(|start_node_id| { - let start_node = graph - .get_node_by_id(*start_node_id) - .expect("Start node does not exist"); - - ( - BorrowedOrOwned::Borrowned(start_node.archetype()), - start_node - .edges - .iter() - .map(|(comp_id, edges)| (*comp_id, edges.clone())) - .collect::<Vec<_>>() - .into_iter(), - ) - }) - .collect(), - visited: start_nodes.iter().copied().collect::<HashSet<_>>(), - } - } - - pub fn push( - &mut self, - item: ( - BorrowedOrOwned<'graph, Archetype>, - VecIntoIter<(Uid, ArchetypeEdges)>, - ), - ) - { - self.stack.push(item); - } - - pub fn pop(&mut self) - { - self.stack.pop(); - } -} - -impl<'graph> StreamingIterator for ArchetypeAddEdgeDfsIter<'graph> -{ - type Item<'a> - = ArchetypeAddEdgeDfsIterResult<'graph, 'a> - where - Self: 'a; - - fn streaming_next(&mut self) -> Option<Self::Item<'_>> - { - let (_, edges_iter) = self.stack.last_mut()?; - - let Some((component_id, edges)) = edges_iter.next() else { - self.stack.pop(); - - return Some(ArchetypeAddEdgeDfsIterResult::NoEdgesLeftForArchetype); - }; - - let Some(add_edge) = edges.add else { - return Some(ArchetypeAddEdgeDfsIterResult::NoAddEdge); - }; - - if self.visited.contains(&add_edge) { - return Some(ArchetypeAddEdgeDfsIterResult::AddEdgeAlreadyVisited); - } - - self.visited.insert(add_edge); - - let Some(add_edge_archetype) = self.graph.get_node_by_id(add_edge) else { - return Some(ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { - archetype: &self.stack.last().unwrap().0, - add_edge_archetype_id: add_edge, - add_edge_component_id: component_id, - }); - }; - - self.stack.push(( - BorrowedOrOwned::Borrowned(add_edge_archetype.archetype()), - add_edge_archetype - .edges - .iter() - .map(|(comp_id, edges)| (*comp_id, edges.clone())) - .collect::<Vec<_>>() - .into_iter(), - )); - - Some(ArchetypeAddEdgeDfsIterResult::AddEdge { - add_edge_archetype_id: add_edge, - add_edge_component_id: component_id, - }) - } -} - -#[derive(Debug)] -pub enum ArchetypeAddEdgeDfsIterResult<'graph, 'iter> -{ - AddEdge - { - add_edge_archetype_id: ArchetypeId, - add_edge_component_id: Uid, - }, - NoEdgesLeftForArchetype, - NoAddEdge, - AddEdgeAlreadyVisited, - AddEdgeArchetypeNotFound - { - archetype: &'iter BorrowedOrOwned<'graph, Archetype>, - add_edge_archetype_id: ArchetypeId, - add_edge_component_id: Uid, - }, -} |