summaryrefslogtreecommitdiff
path: root/ecs/src/component
diff options
context:
space:
mode:
Diffstat (limited to 'ecs/src/component')
-rw-r--r--ecs/src/component/local.rs13
-rw-r--r--ecs/src/component/storage.rs1118
-rw-r--r--ecs/src/component/storage/archetype.rs387
-rw-r--r--ecs/src/component/storage/graph.rs432
4 files changed, 1467 insertions, 483 deletions
diff --git a/ecs/src/component/local.rs b/ecs/src/component/local.rs
index 20627bf..0f6f641 100644
--- a/ecs/src/component/local.rs
+++ b/ecs/src/component/local.rs
@@ -1,21 +1,20 @@
use std::ops::{Deref, DerefMut};
-use crate::component::Component;
-use crate::system::{ComponentRefMut, Param as SystemParam, System};
+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: ComponentRefMut<'world, LocalComponent>,
+ local_component: ComponentHandleMut<'world, LocalComponent>,
}
-unsafe impl<'world, LocalComponent> SystemParam<'world> for Local<'world, LocalComponent>
+impl<'world, LocalComponent> SystemParam<'world> for Local<'world, LocalComponent>
where
LocalComponent: Component,
{
- type Flags = ();
type Input = LocalComponent;
fn initialize<SystemImpl>(
@@ -39,7 +38,7 @@ where
}
}
-impl<'world, LocalComponent> Deref for Local<'world, LocalComponent>
+impl<LocalComponent> Deref for Local<'_, LocalComponent>
where
LocalComponent: Component,
{
@@ -51,7 +50,7 @@ where
}
}
-impl<'world, LocalComponent> DerefMut for Local<'world, LocalComponent>
+impl<LocalComponent> DerefMut for Local<'_, LocalComponent>
where
LocalComponent: Component,
{
diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs
index ffd682e..b27b552 100644
--- a/ecs/src/component/storage.rs
+++ b/ecs/src/component/storage.rs
@@ -1,621 +1,787 @@
-use std::any::type_name;
-use std::borrow::Borrow;
+use std::any::Any;
+use std::array::IntoIter as ArrayIter;
use std::cell::RefCell;
-use std::collections::{HashMap, HashSet};
-use std::slice::Iter as SliceIter;
-use std::vec::IntoIter as OwnedVecIter;
-
-use crate::archetype::Id as ArchetypeId;
-use crate::component::{
- Component,
- IsOptional as ComponentIsOptional,
- Metadata as ComponentMetadata,
+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::type_name::TypeName;
-use crate::uid::Uid;
-use crate::util::Sortable;
-use crate::EntityComponent;
+use crate::component::storage::graph::{
+ ArchetypeAddEdgeDfsIter,
+ ArchetypeAddEdgeDfsIterResult,
+ ArchetypeEdges,
+ Graph,
+};
+use crate::uid::{Kind as UidKind, Uid};
+use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt};
-#[derive(Debug, Default)]
-pub struct Storage
+pub mod archetype;
+
+mod graph;
+
+#[derive(Debug)]
+pub struct ArchetypeSearchTerms<'a>
{
- archetypes: Vec<Archetype>,
- archetype_lookup: RefCell<HashMap<ArchetypeId, ArchetypeLookupEntry>>,
- entity_archetype_lookup: HashMap<Uid, ArchetypeId>,
+ pub required_components: &'a [Uid],
+ pub excluded_components: &'a [Uid],
}
-impl Storage
+impl ArchetypeSearchTerms<'_>
{
- pub fn find_entities<CompMetadataList>(
- &self,
- mut components_metadata: CompMetadataList,
- ) -> ArchetypeRefIter<'_>
- where
- CompMetadataList: Sortable<Item = ComponentMetadata>,
- CompMetadataList: AsRef<[ComponentMetadata]>,
+ fn excluded_contains(&self, comp_id: Uid) -> bool
{
- components_metadata.sort_by_key_b(|component_metadata| component_metadata.id);
+ let comp_id_kind = comp_id.kind();
- let archetype_id = ArchetypeId::from_components_metadata(&components_metadata);
+ debug_assert!(
+ comp_id_kind == UidKind::Component
+ || (comp_id_kind == UidKind::Pair
+ && comp_id.target_component() != Uid::wildcard())
+ );
- // This looks stupid but the borrow checker complains otherwise
- if self.archetype_lookup.borrow().contains_key(&archetype_id) {
- return self.iter_archetypes_by_lookup(archetype_id);
- }
+ let is_found = self.excluded_components.binary_search(&comp_id).is_ok();
- let comp_ids_set = create_non_opt_component_id_set(components_metadata.as_ref());
+ 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()
+ });
+ }
- let matching_archetype_indices = self
- .archetypes
- .iter()
- .enumerate()
- .filter_map(|(index, archetype)| {
- if archetype.component_ids_is_superset(&comp_ids_set) {
- return Some(index);
- }
+ is_found
+ }
- None
- })
- .collect();
-
- self.archetype_lookup.borrow_mut().insert(
- archetype_id,
- ArchetypeLookupEntry {
- component_ids: comp_ids_set,
- archetype_indices: matching_archetype_indices,
- },
- );
+ fn contains_conflicting(&self) -> bool
+ {
+ self.excluded_components.iter().any(|excluded_comp_id| {
+ self.required_components
+ .binary_search(excluded_comp_id)
+ .is_ok()
+ })
+ }
- self.iter_archetypes_by_lookup(archetype_id)
+ fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool
+ {
+ self.required_components
+ .iter()
+ .all(|comp_id| archetype.contains_matching_component(*comp_id))
}
+}
- pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype>
+#[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 = self.entity_archetype_lookup.get(&entity_uid)?;
+ 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 archetype_index =
- self.find_archetype_index_with_entity(*archetype_id, entity_uid)?;
+ 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,
+ };
+ };
- self.archetypes.get(archetype_index)
+ ArchetypeRefIter {
+ storage: self,
+ pre_iter: Either::A([archetype_id].into_iter()),
+ dfs_iter: add_edge_recursive_iter,
+ search_terms,
+ }
}
- #[cfg_attr(feature = "debug", tracing::instrument(skip_all))]
- pub fn push_entity(
- &mut self,
- entity_uid: Uid,
- mut components: Vec<Box<dyn Component>>,
- ) -> Result<(ArchetypeId, Uid), Error>
+ pub fn get_archetype_by_id(&self, id: ArchetypeId) -> Option<&Archetype>
{
- if self.entity_archetype_lookup.contains_key(&entity_uid) {
- return Err(Error::EntityAlreadyExists(entity_uid));
+ 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));
}
- components.sort_by_key(|component| component.self_id());
+ let empty_archetype_id = ArchetypeId::new_empty();
- #[cfg(feature = "debug")]
- tracing::debug!(
- "Pushing entity with components: ({})",
- components
- .iter()
- .map(|component| component.type_name())
- .collect::<Vec<_>>()
- .join(", ")
- );
+ let archetype_node = self.graph.get_or_create_node(empty_archetype_id, &[]);
- let archetype_id = ArchetypeId::from_components_metadata(
- &components
- .iter()
- .map(|component| ComponentMetadata::get(&**component))
- .collect::<Vec<_>>(),
- );
+ archetype_node
+ .archetype_mut()
+ .push_entity(ArchetypeEntity::new(uid, []));
- let comp_ids_set = create_non_opt_component_id_set(
- components
- .iter()
- .map(|component| ComponentMetadata::get(&**component)),
- );
+ self.entity_archetype_lookup.insert(uid, empty_archetype_id);
- let archetype_index =
- self.get_or_create_archetype(archetype_id, &comp_ids_set, &components);
+ Ok(())
+ }
- self.populate_matching_archetype_lookup_entries(&comp_ids_set, archetype_index);
+ 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 = self
- .archetypes
- .get_mut(archetype_index)
- .expect("Archetype is gone");
+ let archetype_node = self
+ .graph
+ .get_node_by_id_mut(*archetype_id)
+ .expect("Archetype should exist");
- archetype.push_entity(entity_uid, components);
+ let entity = archetype_node
+ .archetype_mut()
+ .remove_entity(entity_uid)
+ .expect("Entity should exist in archetype");
- archetype
- .entity_lookup
- .insert(entity_uid, archetype.entities.len() - 1);
+ self.entity_archetype_lookup.remove(&entity_uid);
- self.entity_archetype_lookup
- .insert(entity_uid, archetype_id);
+ Ok(entity)
+ }
- Ok((archetype_id, entity_uid))
+ 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_components_to_entity(
+ pub fn add_entity_component(
&mut self,
entity_uid: Uid,
- components: Vec<Box<dyn Component>>,
- ) -> Option<()>
+ (component_id, component_name, component): (Uid, &'static str, Box<dyn Any>),
+ ) -> Result<(), Error>
{
- let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?;
+ 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 archetype_index =
- self.find_archetype_index_with_entity(*archetype_id, entity_uid)?;
+ 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);
+ }
- let archetype = self.archetypes.get_mut(archetype_index)?;
+ add_edge_id
+ } else {
+ let archetype_node = self
+ .graph
+ .get_node_by_id(archetype_id)
+ .expect("Archetype should exist");
- let contains_component_already = components
- .iter()
- .any(|component| archetype.component_ids.contains_key(&component.self_id()));
-
- if contains_component_already {
- let component_cnt = components.len();
-
- // TODO: return error
- panic!(
- "Entity with UID {:?} already contains one or more component(s) ({})",
- entity_uid,
- components
- .iter()
- .flat_map(|component| [component.type_name(), ", "])
- .enumerate()
- .take_while(|(index, _)| { *index < (component_cnt * 2) - 1 })
- .map(|(_, component)| component)
- .collect::<String>()
- );
- }
+ let (add_edge_id, add_edge_comp_ids) =
+ archetype_node.make_add_edge(component_id);
- let entity = archetype.take_entity(entity_uid)?;
+ if !self.graph.contains_archetype(add_edge_id) {
+ self.graph.create_node(add_edge_id, &add_edge_comp_ids);
+ }
- self.entity_archetype_lookup.remove(&entity_uid);
+ 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_id, component_name),
+ add_edge_archetype,
+ );
- self.push_entity(
- entity_uid,
- entity
- .components
- .into_iter()
- .map(|component| component.component.into_inner())
- .chain(components)
- .collect(),
- )
- .expect("Not supposed to return Err since the entity is removed");
+ add_edge_archetype.push_entity(entity);
- Some(())
+ self.entity_archetype_lookup
+ .insert(entity_uid, add_edge_archetype_id);
+
+ Ok(())
}
- pub fn remove_components_from_entity(
+ pub fn remove_entity_component(
&mut self,
entity_uid: Uid,
- component_ids: impl IntoIterator<Item = Uid>,
- ) -> Option<()>
+ component_id: Uid,
+ ) -> Result<(), Error>
{
- let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?;
+ 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 archetype_index =
- self.find_archetype_index_with_entity(*archetype_id, entity_uid)?;
+ 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);
+ }
- let archetype = self.archetypes.get_mut(archetype_index)?;
+ remove_edge_id
+ });
- let entity = archetype.take_entity(entity_uid)?;
+ let archetype_node = self
+ .graph
+ .get_node_by_id_mut(archetype_id)
+ .expect("Archetype should exist");
- let component_ids_set = component_ids.into_iter().collect::<HashSet<_>>();
+ let mut entity = archetype_node
+ .archetype_mut()
+ .remove_entity(entity_uid)
+ .expect("Entity should exist in archetype");
- self.entity_archetype_lookup.remove(&entity_uid);
+ entity.remove_component(component_id, archetype_node.archetype());
- self.push_entity(
- entity_uid,
- entity
- .components
- .into_iter()
- .map(|component| component.component.into_inner())
- .filter(|component| !component_ids_set.contains(&component.self_id()))
- .collect(),
- )
- .expect("Not supposed to return Err since the entity is removed");
+ self.graph
+ .get_node_by_id_mut(remove_edge_id)
+ .expect("Remove edge archetype should exist")
+ .archetype_mut()
+ .push_entity(entity);
- Some(())
+ self.entity_archetype_lookup
+ .insert(entity_uid, remove_edge_id);
+
+ Ok(())
}
- fn populate_matching_archetype_lookup_entries(
- &mut self,
- comp_ids_set: &HashSet<Uid>,
- archetype_index: usize,
- )
+ pub fn create_imaginary_archetypes(&mut self)
{
- let mut archetype_lookup = self.archetype_lookup.borrow_mut();
-
- for (_, lookup_entry) in archetype_lookup.iter_mut() {
- if &lookup_entry.component_ids == comp_ids_set {
+ for imaginary_archetype in self.imaginary_archetypes.get_mut().drain(..) {
+ if self.graph.contains_archetype(imaginary_archetype.id) {
continue;
}
- // There shouldn't be duplicate archetype indices in the lookup entry
- if lookup_entry.archetype_indices.contains(&archetype_index) {
- continue;
- }
-
- if lookup_entry.component_ids.is_subset(comp_ids_set) {
- lookup_entry.archetype_indices.push(archetype_index);
- }
+ self.graph
+ .create_node(imaginary_archetype.id, &imaginary_archetype.component_ids);
}
}
- fn get_or_create_archetype(
- &mut self,
- archetype_id: ArchetypeId,
- comp_ids_set: &HashSet<Uid>,
- components: &[Box<dyn Component>],
- ) -> usize
+ fn find_all_archetype_with_comps(
+ &self,
+ search_terms: &ArchetypeSearchTerms<'_>,
+ ) -> Vec<ArchetypeId>
{
- let mut archetype_lookup = self.archetype_lookup.borrow_mut();
+ 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;
+ };
- let lookup_entry = archetype_lookup.entry(archetype_id).or_insert_with(|| {
- ArchetypeLookupEntry {
- component_ids: comp_ids_set.clone(),
- archetype_indices: Vec::with_capacity(1),
+ 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;
}
- });
- if lookup_entry.archetype_indices.is_empty() {
- self.archetypes.push(Archetype::new(
- components.iter().map(|component| component.self_id()),
- ));
+ found.push(node.archetype().id());
- lookup_entry
- .archetype_indices
- .push(self.archetypes.len() - 1);
+ search_iter.pop();
}
- // SAFETY: Above, we push a archetype index if archetype_indices is empty so this
- // cannot fail
- unsafe { *lookup_entry.archetype_indices.first().unwrap_unchecked() }
+ found
}
+}
- fn find_archetype_index_with_entity(
+#[cfg(feature = "vizoxide")]
+impl Storage
+{
+ pub fn create_vizoxide_archetype_graph(
&self,
- archetype_id: ArchetypeId,
- entity_uid: Uid,
- ) -> Option<usize>
+ graph_name: impl AsRef<str>,
+ params: VizoxideArchetypeGraphParams,
+ ) -> Result<vizoxide::Graph, vizoxide::GraphvizError>
{
- let archetype_lookup = self.archetype_lookup.borrow_mut();
+ 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);
+ }
- let archetype_lookup_entry = archetype_lookup.get(&archetype_id)?;
+ 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,
+ &params,
+ )?;
+
+ 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()?;
+ }
- // TODO: Also have a hashmap for precise archetype ID -> archetype index lookup.
- // This way is slow
- archetype_lookup_entry
- .archetype_indices
- .iter()
- .find(|archetype_index| {
- let Some(archetype) = self.archetypes.get(**archetype_index) else {
- return false;
- };
+ 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,
+ &params,
+ )?;
+
+ 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()?;
+ }
+ }
+ }
- archetype.has_entity(entity_uid)
- })
- .copied()
+ drop(viz_node_lookup);
+
+ Ok(viz_graph)
}
- fn iter_archetypes_by_lookup(&self, archetype_id: ArchetypeId)
- -> ArchetypeRefIter<'_>
+ 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>
{
- let archetype_lookup = self.archetype_lookup.borrow();
-
- // The archetype indices have to be cloned to prevent a panic when query
- // iterations are nested. The panic happens because the archetype_lookup RefCell
- // is borrowed and it tries to mutably borrow it
- let archetype_indices = archetype_lookup
- .get(&archetype_id)
- .unwrap()
- .archetype_indices
- .clone();
-
- ArchetypeRefIter {
- indices: archetype_indices.into_iter(),
- archetypes: &self.archetypes,
+ 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()
+ }
}
}
}
-/// Component storage error
-#[derive(Debug, Clone, thiserror::Error)]
-pub enum Error
+#[cfg(feature = "vizoxide")]
+pub struct VizoxideArchetypeGraphParams
{
- #[error("Entity already exists")]
- EntityAlreadyExists(Uid),
+ 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>,
}
-impl TypeName for Storage
+#[cfg(feature = "vizoxide")]
+#[derive(Debug, Clone)]
+pub struct ArchetypeMetadata
{
- fn type_name(&self) -> &'static str
- {
- type_name::<Self>()
- }
+ pub is_imaginary: bool,
}
-#[derive(Debug)]
-struct ArchetypeLookupEntry
+#[cfg(feature = "vizoxide")]
+#[derive(Debug, Clone, Copy)]
+pub enum VizoxideArchetypeGraphEdgeKind
{
- component_ids: HashSet<Uid>,
- archetype_indices: Vec<usize>,
+ Add,
+ Remove,
}
#[derive(Debug)]
-pub struct Archetype
+pub struct ArchetypeRefIter<'storage, 'search_terms>
{
- component_ids: HashMap<Uid, usize>,
- entity_lookup: HashMap<Uid, usize>,
- entities: Vec<ArchetypeEntity>,
+ storage: &'storage Storage,
+ pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>,
+ dfs_iter: ArchetypeAddEdgeDfsIter<'storage>,
+ search_terms: ArchetypeSearchTerms<'search_terms>,
}
-impl Archetype
+impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_>
{
- fn new(component_ids: impl IntoIterator<Item = Uid>) -> Self
- {
- Self {
- component_ids: component_ids
- .into_iter()
- .enumerate()
- .map(|(index, component_id)| (component_id, index))
- .collect(),
- entity_lookup: HashMap::new(),
- entities: Vec::new(),
- }
- }
+ type Item = &'component_storage Archetype;
- pub fn component_ids_is_superset(&self, other_component_ids: &HashSet<Uid>) -> bool
+ fn next(&mut self) -> Option<Self::Item>
{
- if other_component_ids.len() <= self.component_ids.len() {
- other_component_ids
- .iter()
- .all(|v| self.component_ids.contains_key(v))
- } else {
- false
+ 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"),
+ );
}
- }
-
- pub fn get_entity(&self, entity_uid: Uid) -> Option<&ArchetypeEntity>
- {
- let entity_index = *self.entity_lookup.get(&entity_uid)?;
-
- self.entities.get(entity_index)
- }
-
- pub fn entities(&self) -> EntityIter<'_>
- {
- EntityIter { iter: self.entities.iter() }
- }
-
- pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize>
- {
- self.component_ids.get(&component_id).copied()
- }
-
- fn push_entity(
- &mut self,
- entity_uid: Uid,
- components: impl IntoIterator<Item = Box<dyn Component>>,
- )
- {
- self.entities.push(ArchetypeEntity {
- uid: entity_uid,
- components: components.into_iter().map(Into::into).collect(),
- });
- }
-
- pub fn take_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity>
- {
- let entity_index = self.entity_lookup.remove(&entity_uid)?;
-
- let entity = self.entities.remove(entity_index);
- for index in self.entity_lookup.values_mut() {
- if *index > entity_index {
- *index -= 1;
+ 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.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(entity)
- }
-
- fn has_entity(&self, entity_uid: Uid) -> bool
- {
- self.entity_lookup.contains_key(&entity_uid)
+ Some(
+ self.storage
+ .get_archetype_by_id(archetype_id)
+ .expect("Archetype should exist"),
+ )
}
}
-#[derive(Debug)]
-pub struct ArchetypeEntity
+impl ArchetypeRefIter<'_, '_>
{
- uid: Uid,
- components: Vec<EntityComponent>,
-}
-
-impl ArchetypeEntity
-{
- pub fn uid(&self) -> Uid
+ fn find_edges_of_imaginary_archetype(
+ &self,
+ imaginary_archetype_comps: &[Uid],
+ ) -> Vec<(Uid, ArchetypeEdges)>
{
- self.uid
- }
+ 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();
- pub fn components(&self) -> &[EntityComponent]
- {
- &self.components
- }
+ if found_archetype.component_cnt() < imaginary_archetype_comps.len() + 1 {
+ return None;
+ }
- pub fn get_component(&self, index: usize) -> Option<&EntityComponent>
- {
- self.components.get(index)
- }
-}
+ 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");
-#[derive(Debug)]
-pub struct ArchetypeRefIter<'component_storage>
-{
- indices: OwnedVecIter<usize>,
- archetypes: &'component_storage [Archetype],
-}
+ let mut add_edge_comp_ids = imaginary_archetype_comps.to_vec();
-impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage>
-{
- type Item = &'component_storage Archetype;
+ add_edge_comp_ids
+ .insert_at_partition_point_by_key(unique_comp_id, |id| *id);
- fn next(&mut self) -> Option<Self::Item>
- {
- let archetype_index = self.indices.next()?;
+ let add_edge = ArchetypeId::new(&add_edge_comp_ids);
- Some(
- self.archetypes
- .get(archetype_index)
- .expect("Archetype index in archetype lookup entry was not found"),
- )
+ Some((
+ unique_comp_id,
+ ArchetypeEdges { add: Some(add_edge), remove: None },
+ ))
+ })
+ .collect::<Vec<_>>()
}
}
-#[derive(Debug)]
-pub struct EntityIter<'archetype>
+#[derive(Debug, thiserror::Error)]
+pub enum Error
{
- iter: SliceIter<'archetype, ArchetypeEntity>,
-}
+ #[error("Entity with ID {0:?} already exists")]
+ EntityAlreadyExists(Uid),
-impl<'archetype> Iterator for EntityIter<'archetype>
-{
- type Item = &'archetype ArchetypeEntity;
+ #[error("Entity with ID {0:?} does not exist")]
+ EntityDoesNotExist(Uid),
- fn next(&mut self) -> Option<Self::Item>
+ #[error("Entity with ID {entity:?} already has component with ID {component:?}")]
+ ComponentAlreadyInEntity
{
- self.iter.next()
- }
+ entity: Uid, component: Uid
+ },
+
+ #[error("Entity with ID {entity:?} does not have component with ID {component:?}")]
+ ComponentNotFoundInEntity
+ {
+ entity: Uid, component: Uid
+ },
}
-fn create_non_opt_component_id_set<Item>(
- component_metadata_iter: impl IntoIterator<Item = Item>,
-) -> HashSet<Uid>
-where
- Item: Borrow<ComponentMetadata>,
+#[derive(Debug)]
+struct ImaginaryArchetype
{
- component_metadata_iter
- .into_iter()
- .filter_map(|item| {
- let component_metadata = item.borrow();
-
- if component_metadata.is_optional == ComponentIsOptional::Yes {
- return None;
- }
-
- Some(component_metadata.id)
- })
- .collect::<HashSet<_>>()
+ id: ArchetypeId,
+ component_ids: Vec<Uid>,
}
#[cfg(test)]
mod tests
{
-
- use ecs_macros::Component;
-
- use super::Storage;
- use crate::archetype::Id as ArchetypeId;
- use crate::component::{
- Component,
- IsOptional as ComponentIsOptional,
- Metadata as ComponentMetadata,
- };
+ use crate::component::storage::archetype::Id as ArchetypeId;
+ use crate::component::storage::Storage;
use crate::uid::{Kind as UidKind, Uid};
- #[derive(Debug, Component)]
- struct HealthPotion
- {
- _hp_restoration: u32,
- }
-
- #[derive(Debug, Component)]
- struct Hookshot
- {
- _range: u32,
- }
-
- #[derive(Debug, Component)]
- struct DekuNut
- {
- _throwing_damage: u32,
- }
-
- #[derive(Debug, Component)]
- struct Bow
- {
- _damage: u32,
- }
-
- #[derive(Debug, Component)]
- struct IronBoots;
-
#[test]
- fn push_entity_works()
+ fn create_entity_works()
{
- let mut component_storage = Storage::default();
-
- component_storage
- .push_entity(
- Uid::new_unique(UidKind::Entity),
- vec![
- Box::new(HealthPotion { _hp_restoration: 12 }),
- Box::new(Hookshot { _range: 50 }),
- ],
- )
- .expect("Expected Ok");
-
- assert_eq!(component_storage.archetypes.len(), 1);
-
- let archetype = component_storage
- .archetypes
- .first()
- .expect("Expected a archetype in archetypes Vec");
-
- assert_eq!(archetype.component_ids.len(), 2);
+ let mut new_storage = Storage::default();
- // One entity
- assert_eq!(archetype.entities.len(), 1);
+ let uid = Uid::new_unique(UidKind::Entity);
- let entity_components = archetype
- .entities
- .first()
- .expect("Expected a entity in archetype");
+ new_storage.create_entity(uid).expect("Expected Ok");
- assert_eq!(entity_components.components.len(), 2);
+ 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!(component_storage.archetype_lookup.borrow().len(), 1);
+ assert_eq!(archetype_node.archetype().component_cnt(), 0);
+ assert_eq!(archetype_node.archetype().entity_cnt(), 1);
- let mut components_metadata = [
- ComponentMetadata {
- id: HealthPotion::id(),
- is_optional: ComponentIsOptional::No,
- },
- ComponentMetadata {
- id: Hookshot::id(),
- is_optional: ComponentIsOptional::No,
- },
- ];
-
- components_metadata.sort_by_key(|comp_metadata| comp_metadata.id);
-
- let archetype_lookup = component_storage.archetype_lookup.borrow();
-
- let lookup_entry = archetype_lookup
- .get(&ArchetypeId::from_components_metadata(&components_metadata))
- .expect("Expected entry in archetype lookup map");
-
- let first_archetype_index = lookup_entry
- .archetype_indices
- .first()
- .expect("Expected archetype lookup to contain a archetype reference");
-
- assert_eq!(*first_archetype_index, 0);
+ assert_eq!(
+ new_storage.entity_archetype_lookup.get(&uid).copied(),
+ Some(ArchetypeId::new_empty())
+ );
}
}
diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs
new file mode 100644
index 0000000..bb29701
--- /dev/null
+++ b/ecs/src/component/storage/archetype.rs
@@ -0,0 +1,387 @@
+use std::any::Any;
+use std::array::IntoIter as ArrayIntoIter;
+use std::hash::{DefaultHasher, Hash, Hasher};
+use std::iter::{Enumerate, Filter, Map, RepeatN, Zip};
+use std::option::IntoIter as OptionIntoIter;
+use std::slice::Iter as SliceIter;
+
+use hashbrown::HashMap;
+
+use crate::lock::Lock;
+use crate::uid::{Kind as UidKind, Uid};
+use crate::util::{Either, 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_matching_component_indices(
+ &self,
+ component_id: Uid,
+ ) -> MatchingComponentIter
+ {
+ assert!(
+ component_id.kind() == UidKind::Component
+ || component_id.kind() == UidKind::Pair
+ );
+
+ if component_id.kind() == UidKind::Pair
+ && component_id.target_component() == Uid::wildcard()
+ {
+ return MatchingComponentIter {
+ inner: Either::A(
+ self.component_ids
+ .iter()
+ .enumerate()
+ .zip(std::iter::repeat_n(component_id, self.component_ids.len()))
+ .filter(
+ (|((_, other_comp_id), component_id)| {
+ other_comp_id.kind() == UidKind::Pair
+ && other_comp_id.has_same_relation_as(*component_id)
+ })
+ as MatchingComponentIterFilterFn,
+ )
+ .map(|((index, other_comp_id), _)| (*other_comp_id, index)),
+ ),
+ };
+ }
+
+ MatchingComponentIter {
+ inner: Either::B(
+ [component_id]
+ .into_iter()
+ .zip(self.get_index_for_component(component_id)),
+ ),
+ }
+ }
+
+ pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize>
+ {
+ assert!(
+ component_id.kind() == UidKind::Component
+ || (component_id.kind() == UidKind::Pair
+ && component_id.target_component() != Uid::wildcard())
+ );
+
+ 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 contains_matching_component(&self, component_id: Uid) -> bool
+ {
+ let component_id_kind = component_id.kind();
+
+ debug_assert!(
+ component_id_kind == UidKind::Component || component_id_kind == UidKind::Pair
+ );
+
+ if component_id.kind() == UidKind::Pair
+ && component_id.target_component() == Uid::wildcard()
+ {
+ return self.component_ids.iter().any(|other_comp_id| {
+ other_comp_id.kind() == UidKind::Pair
+ && other_comp_id.has_same_relation_as(component_id)
+ });
+ }
+
+ self.contains_component_with_exact_id(component_id)
+ }
+
+ pub fn contains_component_with_exact_id(&self, component_id: Uid) -> bool
+ {
+ let component_id_kind = component_id.kind();
+
+ debug_assert!(
+ component_id_kind == UidKind::Component
+ || (component_id_kind == UidKind::Pair
+ && component_id.target_component() != Uid::wildcard())
+ );
+
+ self.component_index_lookup.contains_key(&component_id)
+ }
+}
+
+type MatchingComponentIterFilterFn = fn(&((usize, &Uid), Uid)) -> bool;
+
+type MatchingComponentIterMapFn = fn(((usize, &Uid), Uid)) -> (Uid, usize);
+
+type InnerMatchingComponentIterA<'archetype> = Map<
+ Filter<
+ Zip<Enumerate<SliceIter<'archetype, Uid>>, RepeatN<Uid>>,
+ MatchingComponentIterFilterFn,
+ >,
+ MatchingComponentIterMapFn,
+>;
+
+type InnerMatchingComponentIterB = Zip<ArrayIntoIter<Uid, 1>, OptionIntoIter<usize>>;
+
+#[derive(Debug)]
+pub struct MatchingComponentIter<'archetype>
+{
+ inner: Either<InnerMatchingComponentIterA<'archetype>, InnerMatchingComponentIterB>,
+}
+
+impl Iterator for MatchingComponentIter<'_>
+{
+ type Item = (Uid, usize);
+
+ fn next(&mut self) -> Option<Self::Item>
+ {
+ self.inner.next()
+ }
+}
+
+#[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
+{
+ id: Uid,
+ component: Lock<Box<dyn Any>>,
+}
+
+impl EntityComponent
+{
+ pub fn new(
+ component: Box<dyn Any>,
+ component_id: Uid,
+ component_name: &'static str,
+ ) -> Self
+ {
+ Self {
+ id: component_id,
+ component: Lock::new(component, component_name),
+ }
+ }
+
+ #[allow(dead_code)]
+ pub fn id(&self) -> Uid
+ {
+ self.id
+ }
+
+ pub fn component(&self) -> &Lock<Box<dyn Any>>
+ {
+ &self.component
+ }
+}
+
+/// Archetype ID.
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
+pub struct Id
+{
+ hash: u64,
+}
+
+impl Id
+{
+ pub fn new_empty() -> Self
+ {
+ Self { hash: 0 }
+ }
+
+ pub fn new<'a>(component_ids: impl IntoIterator<Item = &'a Uid>) -> Self
+ {
+ let mut hasher = DefaultHasher::new();
+
+ let mut prev_component_id: Option<Uid> = None;
+
+ let mut component_id_iter = component_ids.into_iter().peekable();
+
+ if component_id_iter.peek().is_none() {
+ return Self::new_empty();
+ }
+
+ for comp_id in component_id_iter {
+ if prev_component_id.is_some_and(|prev_comp_id| *comp_id < prev_comp_id) {
+ panic!(
+ "Cannot create archetype ID from a unsorted component metadata list"
+ );
+ }
+
+ prev_component_id = Some(*comp_id);
+
+ comp_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..29fa937
--- /dev/null
+++ b/ecs/src/component/storage/graph.rs
@@ -0,0 +1,432 @@
+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: &mut ArchetypeNode,
+ subset_node: &mut ArchetypeNode,
+ )
+ {
+ let uniq_comp_id = target_node
+ .archetype()
+ .component_ids_sorted()
+ .find(|id| {
+ !subset_node
+ .archetype()
+ .contains_component_with_exact_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);
+
+ if target_node.archetype().component_cnt()
+ == subset_node.archetype().component_cnt() + 1
+ {
+ target_node
+ .get_or_insert_edges(uniq_comp_id, ArchetypeEdges::default)
+ .remove = Some(subset_node.archetype().id());
+ }
+ }
+
+ 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()
+ .contains_component_with_exact_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()
+ .contains_component_with_exact_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!(matches!(
+ component_id.kind(),
+ UidKind::Component | UidKind::Pair
+ ));
+
+ 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 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,
+ },
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-01 13:29:44 +0000