diff options
Diffstat (limited to 'ecs/src/component/storage')
| -rw-r--r-- | ecs/src/component/storage/archetype.rs | 216 | ||||
| -rw-r--r-- | ecs/src/component/storage/graph.rs | 269 |
2 files changed, 485 insertions, 0 deletions
diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs new file mode 100644 index 0000000..ee3d7f8 --- /dev/null +++ b/ecs/src/component/storage/archetype.rs @@ -0,0 +1,216 @@ +use std::borrow::Borrow; +use std::hash::{DefaultHasher, Hash, Hasher}; +use std::slice::Iter as SliceIter; + +use hashbrown::HashMap; + +use crate::component::Metadata as ComponentMetadata; +use crate::uid::{Kind as UidKind, Uid}; +use crate::util::HashMapExt; +use crate::EntityComponent; + +#[derive(Debug)] +pub struct Archetype +{ + id: Id, + entities: Vec<ArchetypeEntity>, + entity_index_lookup: HashMap<Uid, usize>, + component_index_lookup: HashMap<Uid, usize>, +} + +impl Archetype +{ + pub fn new(id: Id, component_ids: impl IntoIterator<Item: Borrow<Uid>>) -> Self + { + Self { + id, + entities: Vec::new(), + entity_index_lookup: HashMap::new(), + component_index_lookup: component_ids + .into_iter() + .enumerate() + .map(|(index, id)| (*id.borrow(), index)) + .collect(), + } + } + + 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 get_entity_by_id(&self, entity_uid: Uid) -> Option<&ArchetypeEntity> + { + 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: ArchetypeEntity) + { + self.entity_index_lookup + .insert(entity.uid, self.entities.len()); + + self.entities.push(entity); + } + + pub fn remove_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity> + { + //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 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, ArchetypeEntity>, +} + +impl<'archetype> Iterator for EntityIter<'archetype> +{ + type Item = &'archetype ArchetypeEntity; + + fn next(&mut self) -> Option<Self::Item> + { + self.iter.next() + } +} + +#[derive(Debug)] +pub struct ArchetypeEntity +{ + pub uid: Uid, + pub components: Vec<EntityComponent>, +} + +/// 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().len() == 0 { + 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( + components_metadata: &impl AsRef<[ComponentMetadata]>, + ) -> Self + { + if components_metadata.as_ref().len() == 0 { + return Self { hash: 0 }; + } + + debug_assert!( + components_metadata + .as_ref() + .is_sorted_by_key(|comp_metadata| comp_metadata.id), + "Cannot create archetype ID from a unsorted component metadata list" + ); + + let component_ids = + components_metadata + .as_ref() + .iter() + .filter_map(|component_metadata| { + if component_metadata.is_optional { + return None; + } + + Some(component_metadata.id) + }); + + let mut hasher = DefaultHasher::new(); + + for component_id in component_ids { + component_id.hash(&mut hasher); + } + + Self { hash: hasher.finish() } + } +} diff --git a/ecs/src/component/storage/graph.rs b/ecs/src/component/storage/graph.rs new file mode 100644 index 0000000..fe97933 --- /dev/null +++ b/ecs/src/component/storage/graph.rs @@ -0,0 +1,269 @@ +use hashbrown::hash_map::Values as HashMapValueIter; +use hashbrown::HashMap; + +use crate::component::storage::archetype::{Archetype, Id as ArchetypeId}; +use crate::uid::{Kind as UidKind, Uid}; + +#[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 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 + }); + + 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") + })) + } + + pub fn recurse_archetype_add_edges( + &self, + archetype_id: ArchetypeId, + ) -> Option<ArchetypeAddEdgeRecursiveIter> + { + Some(ArchetypeAddEdgeRecursiveIter { + graph: self, + stack: vec![self.get_node_by_id(archetype_id)?.edges.values()], + }) + } + + fn create_missing_edges(&mut self, archetype_id: ArchetypeId) + { + let archetype_node = self + .get_node_by_id(archetype_id) + .expect("Archetype should exist"); + + let mut comp_ids = archetype_node + .archetype() + .component_ids_unsorted() + .collect::<Vec<_>>(); + + comp_ids.sort(); + + for component_id_index in 0..archetype_node.archetype().component_cnt() { + let mut comp_ids_without_comp = comp_ids.clone(); + + let removed_comp_id = comp_ids_without_comp.remove(component_id_index); + + let archetype_without_comp_id = ArchetypeId::new(&comp_ids_without_comp); + + let Some(archetype_node_without_comp) = + self.get_node_by_id_mut(archetype_without_comp_id) + else { + continue; + }; + + archetype_node_without_comp + .get_or_insert_edges(removed_comp_id, ArchetypeEdges::default) + .add = Some(archetype_id); + + let archetype_node = self + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + archetype_node + .get_or_insert_edges(removed_comp_id, ArchetypeEdges::default) + .remove = Some(archetype_without_comp_id); + } + + 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!(); + }; + + let expected_component_cnt = archetype_node.archetype().component_cnt() + 1; + + for other_archetype_node in nodes_before.iter_mut().chain(nodes_after.iter_mut()) + { + if other_archetype_node.archetype().component_cnt() != expected_component_cnt + || !other_archetype_node + .archetype() + .is_superset(&archetype_node.archetype()) + { + continue; + } + + let extra_comp_id = other_archetype_node + .archetype() + .component_ids_unsorted() + .find(|comp_id| { + !archetype_node.archetype().has_component_with_id(*comp_id) + }) + .expect("Archetype should contain one extra component ID"); + + other_archetype_node + .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) + .remove = Some(archetype_id); + + archetype_node + .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) + .add = Some(other_archetype_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) + } + + 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)] +pub struct ArchetypeEdges +{ + pub add: Option<ArchetypeId>, + pub remove: Option<ArchetypeId>, +} + +#[derive(Debug)] +pub struct ArchetypeAddEdgeRecursiveIter<'graph> +{ + graph: &'graph Graph, + stack: Vec<HashMapValueIter<'graph, Uid, ArchetypeEdges>>, +} + +impl<'graph> Iterator for ArchetypeAddEdgeRecursiveIter<'graph> +{ + type Item = Option<ArchetypeId>; + + fn next(&mut self) -> Option<Self::Item> + { + let iter = self.stack.last_mut()?; + + let Some(edges) = iter.next() else { + self.stack.pop(); + + return Some(None); + }; + + let Some(add_edge) = edges.add else { + return Some(None); + }; + + let add_edge_archetype = self + .graph + .get_node_by_id(add_edge) + .expect("Add edge archetype not found"); + + self.stack.push(add_edge_archetype.edges.values()); + + Some(Some(add_edge)) + } +} |