Compare commits
No commits in common. 'wip/graph' and 'main' have entirely different histories.
9 changed files with 89 additions and 543 deletions
@ -1,323 +0,0 @@ |
||||
use std::alloc::Layout; |
||||
use std::collections::{HashMap, HashSet}; |
||||
|
||||
use super::archetable::{Archetable, EntityRow}; |
||||
use super::archetype::Archetype; |
||||
use super::component::Component; |
||||
use super::entity::Entity; |
||||
use super::world::World; |
||||
|
||||
/// Graph of [`Archetable`]s contained within [`Node`]s.
|
||||
///
|
||||
/// Allows for traversal by of `Archetables` by their [`Archetype`], one
|
||||
/// [`Component`] at a time. For example to get all [`entities`][`Entity`] with
|
||||
/// both `Position` and `Velocity` you would start at `root()`, then traverse
|
||||
/// to `Position`, then `Velocity`, or the other way around, since you end up
|
||||
/// at the same `Node` either way. You can then `iter()` all `Archetables` that
|
||||
/// have those same components.
|
||||
pub struct Archegraph { |
||||
node_count: usize, |
||||
node_storage: Vec<Option<NodeData>>, |
||||
archetable_storage: Vec<Option<Archetable>>, |
||||
// unused_indices: Vec<NodeIndex>,
|
||||
type_lookup: HashMap<Archetype, NodeIndex>, |
||||
} |
||||
|
||||
pub type GraphEntityIndex = super::entity_index::EntityIndex<(NodeIndex, EntityRow)>; |
||||
|
||||
type NodeIndex = usize; |
||||
|
||||
pub struct Node<'a> { |
||||
archegraph: &'a Archegraph, |
||||
node_index: NodeIndex, |
||||
} |
||||
|
||||
pub struct NodeMut<'a> { |
||||
archegraph: &'a mut Archegraph, |
||||
node_index: NodeIndex, |
||||
} |
||||
|
||||
#[derive(Default)] |
||||
struct NodeData { |
||||
add: HashMap<Component, NodeIndex>, |
||||
remove: HashMap<Component, NodeIndex>, |
||||
} |
||||
|
||||
impl Archegraph { |
||||
pub fn new() -> Self { |
||||
// Empty archetable is added in `World::bootstrap_archetable`.
|
||||
Self { |
||||
node_count: 0, |
||||
node_storage: Vec::new(), |
||||
archetable_storage: Vec::new(), |
||||
// unused_indices: Vec::new(),
|
||||
type_lookup: HashMap::new(), |
||||
} |
||||
} |
||||
|
||||
pub fn bootstrap(&mut self, pairs: Vec<(Entity, Layout)>) { |
||||
// Inner function is just so call to `bootstrap` is prettier.
|
||||
fn inner(graph: &mut Archegraph, pairs: Vec<(Entity, Layout)>, mut start_index: usize) { |
||||
// Iterate all the subsets of the pairs and initialize them, first.
|
||||
// The `start_index` should ensure that no subset is bootstrapped twice.
|
||||
for i in start_index..pairs.len() { |
||||
let mut pairs_subset = pairs.clone(); |
||||
pairs_subset.remove(i); |
||||
inner(graph, pairs_subset, start_index); |
||||
start_index += 1; |
||||
} |
||||
|
||||
let layouts = pairs.iter().map(|p| Some(p.1)).collect(); |
||||
let archetype = Archetype::new(pairs.iter().map(|p| p.0)); |
||||
let archetable = Archetable::new(archetype, layouts); |
||||
|
||||
// No entity lookups necessary during bootstrapping.
|
||||
graph.insert(archetable, &GraphEntityIndex::EMPTY); |
||||
} |
||||
inner(self, pairs, 0); |
||||
} |
||||
|
||||
#[inline] |
||||
#[must_use] |
||||
pub fn node_count(&self) -> usize { |
||||
self.node_count |
||||
} |
||||
|
||||
#[must_use] |
||||
pub fn root(&self) -> &NodeData { |
||||
self.node_storage[0].as_ref().unwrap() |
||||
} |
||||
|
||||
#[must_use] |
||||
pub fn root_mut(&mut self) -> &mut NodeData { |
||||
self.node_storage[0].as_mut().unwrap() |
||||
} |
||||
|
||||
#[must_use] |
||||
pub fn get(&self, index: NodeIndex) -> Option<&NodeData> { |
||||
self.node_storage.get(index).and_then(Option::as_ref) |
||||
} |
||||
|
||||
#[must_use] |
||||
pub fn get_mut(&mut self, index: NodeIndex) -> Option<&mut NodeData> { |
||||
self.node_storage.get_mut(index).and_then(Option::as_mut) |
||||
} |
||||
|
||||
#[must_use] |
||||
pub fn lookup_or_create( |
||||
&mut self, |
||||
archetype: &Archetype, |
||||
entity_index: &GraphEntityIndex, |
||||
) -> NodeMut { |
||||
if let Some(index) = self.type_lookup.get(&archetype) { |
||||
// SAFETY: `type_lookup` is guaranteed to point to a valid archetable.
|
||||
self.node_storage[*index].as_mut().unwrap() |
||||
} else { |
||||
let layouts = self.get_layouts(archetype, entity_index); |
||||
let archetable = Archetable::new(archetype.clone(), layouts); |
||||
self.insert(archetable, entity_index) |
||||
} |
||||
} |
||||
|
||||
pub fn insert(&mut self, archetable: Archetable, entity_index: &GraphEntityIndex) -> NodeMut { |
||||
let archetype = archetable.archetype().clone(); |
||||
let index = self.reserve_archetable_index(); |
||||
|
||||
let mut node = Default::default(); |
||||
self.fill_edges(&mut node, entity_index); |
||||
|
||||
self.node_storage[index] = Some(node); |
||||
self.archetable_storage[index] = Some(archetable); |
||||
self.type_lookup.insert(archetype, index); |
||||
|
||||
() |
||||
} |
||||
|
||||
fn get_layout(&self, component: Component, entity_index: &GraphEntityIndex) -> Option<Layout> { |
||||
// FIXME: Relations can be components too.
|
||||
let entity: Entity = component.try_into().ok()?; |
||||
let (node_index, row) = entity_index.get(entity.id())?.data; |
||||
let archetable = self.get(node_index).unwrap().get(); |
||||
let component_index = archetable.archetype().position(World::LAYOUT)?; |
||||
let column = archetable.column_by_index(component_index).unwrap(); |
||||
let column = unsafe { column.as_typed_slice::<Layout>() }; |
||||
Some(column[row]) |
||||
} |
||||
|
||||
fn get_layouts( |
||||
&self, |
||||
archetype: &Archetype, |
||||
entity_index: &GraphEntityIndex, |
||||
) -> Vec<Option<Layout>> { |
||||
let iter = archetype.components().iter(); |
||||
iter.map(|c| self.get_layout(*c, entity_index)).collect() |
||||
} |
||||
|
||||
#[must_use] |
||||
fn reserve_archetable_index(&mut self) -> usize { |
||||
self.node_count += 1; |
||||
// self.unused_indices.pop().unwrap_or_else(|| {
|
||||
self.node_storage.push(None); |
||||
self.node_storage.len() - 1 |
||||
// })
|
||||
} |
||||
|
||||
fn fill_edges(&mut self, node: &mut NodeData, entity_index: &GraphEntityIndex) { |
||||
let archetype = node.archetable.archetype(); |
||||
for component in archetype.components() { |
||||
let other_archetype = archetype.clone().without(*component); |
||||
let other_node = self.lookup_or_create(&other_archetype, entity_index); |
||||
node.remove.insert(*component, other_node.index); |
||||
other_node.add.insert(*component, node.index); |
||||
} |
||||
} |
||||
} |
||||
|
||||
impl<'a> Node<'a> { |
||||
#[must_use] |
||||
pub fn iter(&'a self) -> impl Iterator<Item = &Archetable> { |
||||
let storage = &self.archegraph.archetable_storage; |
||||
GraphIter::new(&self.archegraph.node_storage, self.node_index) |
||||
.map(|index| storage[index].as_ref().unwrap()) |
||||
} |
||||
|
||||
#[must_use] |
||||
pub fn get(&self) -> &Archetable { |
||||
let storage = &self.archegraph.archetable_storage; |
||||
storage[self.node_index].as_ref().unwrap() |
||||
} |
||||
} |
||||
|
||||
impl<'a> NodeMut<'a> { |
||||
#[must_use] |
||||
pub fn iter(&'a mut self) -> impl Iterator<Item = &'a mut Archetable> { |
||||
let node_storage = &self.archegraph.node_storage; |
||||
let archetable_storage = &mut self.archegraph.archetable_storage; |
||||
GraphIter::new(node_storage, self.node_index) |
||||
.map(|index| archetable_storage[index].as_mut().unwrap()) |
||||
} |
||||
|
||||
#[must_use] |
||||
pub fn get(&mut self) -> &mut Archetable { |
||||
let storage = &mut self.archegraph.archetable_storage; |
||||
storage[self.node_index].as_mut().unwrap() |
||||
} |
||||
} |
||||
|
||||
struct GraphIter<'a> { |
||||
node_storage: &'a Vec<Option<NodeData>>, |
||||
stack: Vec<NodeIndex>, |
||||
visited: HashSet<NodeIndex>, |
||||
} |
||||
|
||||
impl GraphIter<'_> { |
||||
fn new(node_storage: &Vec<Option<NodeData>>, start_index: NodeIndex) -> GraphIter { |
||||
GraphIter { |
||||
node_storage, |
||||
stack: vec![start_index], |
||||
visited: HashSet::new(), |
||||
} |
||||
} |
||||
} |
||||
|
||||
impl<'a> Iterator for GraphIter<'a> { |
||||
type Item = NodeIndex; |
||||
|
||||
fn next(&mut self) -> Option<Self::Item> { |
||||
while let Some(index) = self.stack.pop() { |
||||
if !self.visited.contains(&index) { |
||||
let node = self.archegraph.get(index).unwrap(); |
||||
self.stack.extend(node.add.values()); |
||||
self.visited.insert(index); |
||||
return Some(index); |
||||
} |
||||
} |
||||
None |
||||
} |
||||
} |
||||
|
||||
impl NodeData { |
||||
#[must_use] |
||||
fn new(archetable: Archetable) -> Self { |
||||
Self { |
||||
archetable, |
||||
add: HashMap::new(), |
||||
remove: HashMap::new(), |
||||
} |
||||
} |
||||
} |
||||
|
||||
#[cfg(test)] |
||||
mod tests { |
||||
use super::*; |
||||
|
||||
#[test] |
||||
fn bootstrap() { |
||||
let mut archegraph = Archegraph::new(); |
||||
|
||||
let a = Entity::new_checked(1, 0).unwrap(); |
||||
let b = Entity::new_checked(2, 0).unwrap(); |
||||
let c = Entity::new_checked(10, 0).unwrap(); |
||||
let d = Entity::new_checked(2000, 0).unwrap(); |
||||
|
||||
archegraph.bootstrap(vec![ |
||||
(a, Layout::new::<u8>()), |
||||
(b, Layout::new::<u16>()), |
||||
(c, Layout::new::<u32>()), |
||||
(d, Layout::new::<u64>()), |
||||
]); |
||||
|
||||
// {a, b, c, d} has 16 subsets including {} (the empty root archetype)
|
||||
// and {a, b, c, d} (archetype containing all components at the same time).
|
||||
assert_eq!(16, archegraph.node_count()); |
||||
|
||||
let mut archetypes = archegraph |
||||
.root() |
||||
.iter(&archegraph) |
||||
.map(Archetable::archetype) |
||||
.map(Archetype::components) |
||||
.collect::<Vec<_>>(); |
||||
|
||||
// Not guaranteed to iter in any specific order.
|
||||
archetypes.sort(); |
||||
|
||||
assert_eq!( |
||||
vec![ |
||||
vec![], |
||||
vec![a], |
||||
vec![a, b], |
||||
vec![a, b, c], |
||||
vec![a, b, c, d], |
||||
vec![a, b, d], |
||||
vec![a, c], |
||||
vec![a, c, d], |
||||
vec![a, d], |
||||
vec![b], |
||||
vec![b, c], |
||||
vec![b, c, d], |
||||
vec![b, d], |
||||
vec![c], |
||||
vec![c, d], |
||||
vec![d], |
||||
], |
||||
archetypes |
||||
); |
||||
|
||||
// Ensure the columns' layouts are correct for a given Archetype.
|
||||
let archetype = Archetype::new([a, c, d]); |
||||
let index = &GraphEntityIndex::EMPTY; |
||||
let table = &archegraph.lookup_or_create(&archetype, index).get(); |
||||
assert_eq!( |
||||
Layout::new::<u8>(), |
||||
table.column_by_index(0).unwrap().layout() |
||||
); |
||||
assert_eq!( |
||||
Layout::new::<u32>(), |
||||
table.column_by_index(1).unwrap().layout() |
||||
); |
||||
assert_eq!( |
||||
Layout::new::<u64>(), |
||||
table.column_by_index(2).unwrap().layout() |
||||
); |
||||
} |
||||
} |
||||
Loading…
Reference in new issue