feat(engine-ecs): add traversal query termHEADmaster

9 files changed, 805 insertions, 354 deletions

diff --git a/engine-ecs/src/component/storage.rs b/engine-ecs/src/component/storage.rs
index a4944c7..4a1c035 100644
--- a/engine-ecs/src/component/storage.rs
+++ b/engine-ecs/src/component/storage.rs
@@ -17,7 +17,8 @@ use crate::component::storage::graph::{
     ArchetypeEdges,
     Graph,
 };
-use crate::uid::Uid;
+use crate::uid::{PairParams, Uid};
+use crate::util::array_vec::ArrayVec;
 use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt};
 
 pub mod archetype;
@@ -25,13 +26,56 @@ pub mod archetype;
 mod graph;
 
 #[derive(Debug)]
-pub struct ArchetypeSearchTerms<'a>
+pub struct SearchTerms<const TERM_CAP: usize>
 {
-    pub present: &'a [Uid],
-    pub absent: &'a [Uid],
+    pub(crate) present: ArrayVec<Uid, TERM_CAP>,
+    pub(crate) absent: ArrayVec<Uid, TERM_CAP>,
+    pub(crate) traverse: ArrayVec<Traversal<TERM_CAP>, TERM_CAP>,
 }
 
-impl ArchetypeSearchTerms<'_>
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub struct TermMetadata
+{
+    pub level: u32,
+    pub index: u32,
+}
+
+#[derive(Debug, Clone)]
+pub struct Traversal<const TERM_CAP: usize>
+{
+    pub kind: TraversalKind,
+    pub relation: Uid,
+    pub terms: fn(&Self) -> SearchTerms<TERM_CAP>,
+    pub term_metadata: TermMetadata,
+}
+
+impl<const TERM_CAP: usize> Traversal<TERM_CAP>
+{
+    fn relationship(&self) -> Uid
+    {
+        Uid::new_pair(&PairParams {
+            relation: self.relation,
+            target: Uid::wildcard(),
+        })
+    }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[non_exhaustive]
+pub enum TraversalKind
+{
+    Up,
+}
+
+#[derive(Debug)]
+pub struct TraversalResult
+{
+    pub relation: Uid,
+    pub term_metadata: TermMetadata,
+    pub found_ent: Uid,
+}
+
+impl<const TERM_CAP: usize> SearchTerms<TERM_CAP>
 {
     fn excluded_contains(&self, comp_id: Uid) -> bool
     {
@@ -55,11 +99,9 @@ impl ArchetypeSearchTerms<'_>
 
     fn contains_conflicting(&self) -> bool
     {
-        self.absent.iter().any(|excluded_comp_id| {
-            self.present
-                .binary_search(excluded_comp_id)
-                .is_ok()
-        })
+        self.absent
+            .iter()
+            .any(|excluded_comp_id| self.present.binary_search(excluded_comp_id).is_ok())
     }
 
     fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool
@@ -80,12 +122,12 @@ pub struct Storage
 
 impl Storage
 {
-    pub fn search_archetypes<'search_terms>(
+    pub fn search_archetypes<'search_terms, const TERM_CAP: usize>(
         &self,
-        search_terms: ArchetypeSearchTerms<'search_terms>,
-    ) -> ArchetypeRefIter<'_, 'search_terms>
+        search_terms: &'search_terms SearchTerms<TERM_CAP>,
+    ) -> ArchetypeRefIter<'_, 'search_terms, TERM_CAP>
     {
-        let archetype_id = ArchetypeId::new(search_terms.present);
+        let archetype_id = ArchetypeId::new(search_terms.present.iter());
 
         if search_terms.contains_conflicting() {
             return ArchetypeRefIter {
@@ -370,9 +412,9 @@ impl Storage
         }
     }
 
-    fn find_all_archetype_with_comps(
+    fn find_all_archetype_with_comps<const TERM_CAP: usize>(
         &self,
-        search_terms: &ArchetypeSearchTerms<'_>,
+        search_terms: &SearchTerms<TERM_CAP>,
     ) -> Vec<ArchetypeId>
     {
         let Some(mut search_iter) =
@@ -594,29 +636,52 @@ pub enum VizoxideArchetypeGraphEdgeKind
 }
 
 #[derive(Debug)]
-pub struct ArchetypeRefIter<'storage, 'search_terms>
+pub struct ArchetypeRefIter<'storage, 'search_terms, const TERM_CAP: usize>
 {
     storage: &'storage Storage,
     pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>,
     dfs_iter: ArchetypeAddEdgeDfsIter<'storage>,
-    search_terms: ArchetypeSearchTerms<'search_terms>,
+    search_terms: &'search_terms SearchTerms<TERM_CAP>,
 }
 
-impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_>
+impl<'component_storage, const TERM_CAP: usize> Iterator
+    for ArchetypeRefIter<'component_storage, '_, TERM_CAP>
 {
-    type Item = &'component_storage Archetype;
+    type Item = (
+        &'component_storage Archetype,
+        ArrayVec<TraversalResult, TERM_CAP>,
+    );
 
     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"),
-            );
+        if let Some((pre_iter_archetype, pre_iter_traversal_results)) =
+            self.pre_iter.find_map(|archetype_id| {
+                let archetype = self
+                    .storage
+                    .get_archetype_by_id(archetype_id)
+                    .expect("Archetype should exist");
+
+                let mut traversal_results =
+                    ArrayVec::<TraversalResult, TERM_CAP>::default();
+
+                if do_traversals(
+                    self.storage,
+                    archetype,
+                    &self.search_terms.traverse,
+                    &mut traversal_results,
+                )
+                .is_none()
+                {
+                    return None;
+                };
+
+                Some((archetype, traversal_results))
+            })
+        {
+            return Some((pre_iter_archetype, pre_iter_traversal_results));
         }
 
-        let archetype_id = loop {
+        let (archetype, traversal_results) = loop {
             match self.dfs_iter.streaming_find(|res| {
                 matches!(
                     res,
@@ -633,7 +698,27 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_>
                         continue;
                     }
 
-                    break add_edge_archetype_id;
+                    let add_edge_archetype = self
+                        .storage
+                        .get_archetype_by_id(add_edge_archetype_id)
+                        .expect("Archetype should exist");
+
+                    let mut traversal_results =
+                        ArrayVec::<TraversalResult, TERM_CAP>::default();
+
+                    if do_traversals(
+                        self.storage,
+                        add_edge_archetype,
+                        &self.search_terms.traverse,
+                        &mut traversal_results,
+                    )
+                    .is_none()
+                    {
+                        self.dfs_iter.pop();
+                        continue;
+                    };
+
+                    break (add_edge_archetype, traversal_results);
                 }
                 ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound {
                     archetype,
@@ -644,8 +729,9 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_>
                         continue;
                     }
 
-                    let mut add_edge_archetype_comps =
-                        archetype.component_ids_sorted().collect::<Vec<_>>();
+                    let mut add_edge_archetype_comps = archetype
+                        .component_ids_sorted()
+                        .collect::<ArrayVec<_, 32>>();
 
                     add_edge_archetype_comps
                         .insert_at_part_pt_by_key(add_edge_component_id, |comp_id| {
@@ -659,13 +745,14 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_>
                         },
                     );
 
-                    let found =
-                        self.find_edges_of_imaginary_archetype(&add_edge_archetype_comps);
+                    let found = self.find_edges_of_imaginary_archetype(
+                        add_edge_archetype_comps.clone(),
+                    );
 
                     self.dfs_iter.push((
                         BorrowedOrOwned::Owned(Archetype::new(
                             add_edge_archetype_id,
-                            add_edge_archetype_comps.clone(),
+                            add_edge_archetype_comps,
                         )),
                         found.into_iter(),
                     ));
@@ -676,25 +763,22 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_>
             }
         };
 
-        Some(
-            self.storage
-                .get_archetype_by_id(archetype_id)
-                .expect("Archetype should exist"),
-        )
+        Some((archetype, traversal_results))
     }
 }
 
-impl ArchetypeRefIter<'_, '_>
+impl<const TERM_CAP: usize> ArchetypeRefIter<'_, '_, TERM_CAP>
 {
     fn find_edges_of_imaginary_archetype(
         &self,
-        imaginary_archetype_comps: &[Uid],
+        imaginary_archetype_comps: ArrayVec<Uid, 32>,
     ) -> Vec<(Uid, ArchetypeEdges)>
     {
         self.storage
-            .find_all_archetype_with_comps(&ArchetypeSearchTerms {
-                present: imaginary_archetype_comps,
-                absent: &[],
+            .find_all_archetype_with_comps(&SearchTerms {
+                present: imaginary_archetype_comps.clone(),
+                absent: ArrayVec::default(),
+                traverse: ArrayVec::default(),
             })
             .into_iter()
             .filter_map(|found_id| {
@@ -757,7 +841,75 @@ pub struct EntityAlreadyExistsError;
 struct ImaginaryArchetype
 {
     id: ArchetypeId,
-    component_ids: Vec<Uid>,
+    component_ids: ArrayVec<Uid, 32>,
+}
+
+fn do_traversals<const TERM_CAP: usize>(
+    storage: &Storage,
+    archetype: &Archetype,
+    traversals: &[Traversal<TERM_CAP>],
+    results: &mut ArrayVec<TraversalResult, TERM_CAP>,
+) -> Option<()>
+{
+    // TODO: Optimize traversals. Caching is needed especially
+
+    for traversal in traversals {
+        if traversal.kind == TraversalKind::Up {
+            archetype
+                .get_matching_component_ids(traversal.relationship())
+                .find_map(|relationship| {
+                    traverse_dfs(
+                        storage,
+                        relationship.target(),
+                        traversal,
+                        &(traversal.terms)(traversal),
+                        results,
+                    )
+                })?;
+        } else {
+            unimplemented!();
+        }
+    }
+
+    Some(())
+}
+
+fn traverse_dfs<const TERM_CAP: usize>(
+    storage: &Storage,
+    ent_id: Uid,
+    traversal: &Traversal<TERM_CAP>,
+    terms: &SearchTerms<TERM_CAP>,
+    results: &mut ArrayVec<TraversalResult, TERM_CAP>,
+) -> Option<()>
+{
+    let ent_archetype = storage.get_entity_archetype(ent_id)?;
+
+    if terms
+        .absent
+        .iter()
+        .all(|absent_comp_id| !ent_archetype.contains_matching_component(*absent_comp_id))
+        && terms.archetype_contains_all_required(ent_archetype)
+        && do_traversals(storage, ent_archetype, &terms.traverse, results).is_some()
+    {
+        results.push(TraversalResult {
+            relation: traversal.relation,
+            term_metadata: traversal.term_metadata,
+            found_ent: ent_id,
+        });
+
+        return Some(());
+    }
+
+    for relationship in ent_archetype.get_matching_component_ids(traversal.relationship())
+    {
+        if traverse_dfs(storage, relationship.target(), traversal, terms, results)
+            .is_some()
+        {
+            return Some(());
+        }
+    }
+
+    None
 }
 
 #[cfg(test)]
diff --git a/engine-ecs/src/component/storage/archetype.rs b/engine-ecs/src/component/storage/archetype.rs
index c5cce10..236bf97 100644
--- a/engine-ecs/src/component/storage/archetype.rs
+++ b/engine-ecs/src/component/storage/archetype.rs
@@ -107,11 +107,6 @@ impl Archetype
         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()
@@ -182,6 +177,33 @@ impl Archetype
         self.contains_component_with_exact_id(component_id)
     }
 
+    pub fn get_matching_component_ids(
+        &self,
+        component_id: Uid,
+    ) -> impl Iterator<Item = Uid> + use<'_>
+    {
+        if component_id.is_pair() && component_id.target() == Uid::wildcard() {
+            return Either::A(
+                self.component_ids
+                    .iter()
+                    .filter(move |other_comp_id| {
+                        other_comp_id.is_pair()
+                            && other_comp_id.has_same_relation_as(component_id)
+                    })
+                    .copied(),
+            );
+        }
+
+        Either::B(
+            (if self.contains_component_with_exact_id(component_id) {
+                Some(component_id)
+            } else {
+                None
+            })
+            .into_iter(),
+        )
+    }
+
     pub fn contains_component_with_exact_id(&self, component_id: Uid) -> bool
     {
         debug_assert!(
diff --git a/engine-ecs/src/pair.rs b/engine-ecs/src/pair.rs
index 1168f67..00c6a72 100644
--- a/engine-ecs/src/pair.rs
+++ b/engine-ecs/src/pair.rs
@@ -14,11 +14,12 @@ use crate::entity::{
     MatchingComponentIter as EntityMatchingComponentIter,
 };
 use crate::query::{
+    SearchResult,
     Term as QueryTerm,
+    TermMetadata as QueryTermMetadata,
     TermsBuilder as QueryTermsBuilder,
     TermsBuilderInterface,
 };
-use crate::tuple::Tuple;
 use crate::uid::{PairParams as UidPairParams, Uid, With as WithUid};
 use crate::util::impl_multiple;
 use crate::{Component, EntityComponentRef, World};
@@ -192,121 +193,128 @@ where
     }
 }
 
-impl<'world, Relation, Target> QueryTerm<'world> for Pair<Relation, &Target>
+impl<'query, Relation, Target> QueryTerm<'query> for Pair<Relation, &Target>
 where
     Relation: Component,
     Target: Component,
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<ComponentHandle<'world, Target>>;
+    type Fields = (ComponentHandle<'query, Target>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: QueryTermMetadata,
     )
     {
         terms_builder.present([Pair::<Relation, Target>::uid()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: QueryTermMetadata,
+    ) -> Self::Fields
     {
-        let target_component = entity_handle
+        let target_component = search_result
+            .entity_handle
             .get_matching_components(Pair::<Relation, Target>::uid())
             .next()
             .expect("Not possible");
 
-        let target_component = match ComponentHandle::<Target>::from_entity_component_ref(&target_component) {
-            Ok(target_component) => target_component,
-            Err(err) => {
-                panic!(
-                    "Creating handle to target component {} failed: {err}",
-                    type_name::<Target>()
-                );
-            }
-        };
+        let target_component =
+            match ComponentHandle::<Target>::from_entity_component_ref(&target_component)
+            {
+                Ok(target_component) => target_component,
+                Err(err) => {
+                    panic!(
+                        "Creating handle to target component {} failed: {err}",
+                        type_name::<Target>()
+                    );
+                }
+            };
 
-        fields.with_elem(target_component)
+        (target_component,)
     }
 }
 
-impl<'world, Relation, Target> QueryTerm<'world> for Pair<Relation, &mut Target>
+impl<'query, Relation, Target> QueryTerm<'query> for Pair<Relation, &mut Target>
 where
     Relation: Component,
     Target: Component,
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<ComponentHandleMut<'world, Target>>;
+    type Fields = (ComponentHandleMut<'query, Target>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: QueryTermMetadata,
     )
     {
         terms_builder.present([Pair::<Relation, Target>::uid()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: QueryTermMetadata,
+    ) -> Self::Fields
     {
-        let target_component = entity_handle
+        let target_component = search_result
+            .entity_handle
             .get_matching_components(Pair::<Relation, Target>::uid())
             .next()
             .expect("Not possible");
 
-        let target_component = match ComponentHandleMut::<Target>::from_entity_component_ref(&target_component, world) {
-            Ok(target_component) => target_component,
-            Err(err) => {
-                panic!(
-                    "Creating mut handle to target component {} failed: {err}",
-                    type_name::<Target>()
-                );
-            }
-        };
+        let target_component =
+            match ComponentHandleMut::<Target>::from_entity_component_ref(
+                &target_component,
+                world,
+            ) {
+                Ok(target_component) => target_component,
+                Err(err) => {
+                    panic!(
+                        "Creating mut handle to target component {} failed: {err}",
+                        type_name::<Target>()
+                    );
+                }
+            };
 
-        fields.with_elem(target_component)
+        (target_component,)
     }
 }
 
 // TODO: implement QueryTerm for Pair<&Relation, Target> (or equivalent)
 // TODO: implement QueryTerm for Pair<&mut Relation, Target> (or equivalent)
 
-impl<'world, Relation> QueryTerm<'world> for Pair<Relation, Wildcard>
+impl<'query, Relation> QueryTerm<'query> for Pair<Relation, Wildcard>
 where
     Relation: Component,
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<WithWildcard<'world, Relation, Wildcard>>;
+    type Fields = (WithWildcard<'query, Relation, Wildcard>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: QueryTermMetadata,
     )
     {
         terms_builder.present([Self::uid()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: QueryTermMetadata,
+    ) -> Self::Fields
     {
-        let first_matching_comp = entity_handle
+        let first_matching_comp = search_result
+            .entity_handle
             .get_matching_components(Self::uid())
             .next()
             .expect("Not possible");
 
-        fields.with_elem(
-            WithWildcard {
-                world,
-                component_ref: first_matching_comp,
-                _pd: PhantomData,
-            }
-        )
+        (WithWildcard {
+            world,
+            component_ref: first_matching_comp,
+            _pd: PhantomData,
+        },)
     }
 }
 
@@ -337,45 +345,43 @@ where
     }
 }
 
-impl<'world, Relation> QueryTerm<'world> for &[Pair<Relation, Wildcard>]
+impl<'query, Relation> QueryTerm<'query> for &[Pair<Relation, Wildcard>]
 where
     Relation: Component,
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<MultipleWithWildcard<'world, Relation, Wildcard>>;
+    type Fields = (MultipleWithWildcard<'query, Relation, Wildcard>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         _terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: QueryTermMetadata,
     )
     {
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: QueryTermMetadata,
+    ) -> Self::Fields
     {
-        fields.with_elem(
-            MultipleWithWildcard {
-                entity_handle: entity_handle.clone(),
-                world,
-                _pd: PhantomData,
-            }
-        )
+        (MultipleWithWildcard {
+            entity_handle: search_result.entity_handle.clone(),
+            world,
+            _pd: PhantomData,
+        },)
     }
 }
 
 /// Reference to a pair with a wildcard relation/target.
 #[derive(Debug)]
-pub struct WithWildcard<'world, Relation, Target>
+pub struct WithWildcard<'query, Relation, Target>
 {
-    world: &'world World,
-    component_ref: EntityComponentRef<'world>,
+    world: &'query World,
+    component_ref: EntityComponentRef<'query>,
     _pd: PhantomData<(Relation, Target)>,
 }
 
-impl<'world, Relation, Target> WithWildcard<'world, Relation, Target>
+impl<'query, Relation, Target> WithWildcard<'query, Relation, Target>
 {
     /// Returns a new `WithWildcard`.
     ///
@@ -388,7 +394,7 @@ impl<'world, Relation, Target> WithWildcard<'world, Relation, Target>
     ///   component's ID
     /// - Both `Relation::uid()` and `Target::uid()` are wildcards
     /// - Neither `Relation::uid()` or `Target::uid()` are wildcards
-    pub fn new(world: &'world World, component_ref: EntityComponentRef<'world>) -> Self
+    pub fn new(world: &'query World, component_ref: EntityComponentRef<'query>) -> Self
     where
         Relation: ComponentOrWildcard,
         Target: ComponentOrWildcard,
@@ -480,13 +486,13 @@ impl<'world, Relation, Target> WithWildcard<'world, Relation, Target>
     }
 }
 
-impl<'world, Relation> WithWildcard<'world, Relation, Wildcard>
+impl<'query, Relation> WithWildcard<'query, Relation, Wildcard>
 where
     Relation: Component,
 {
     /// Attempts to retrieve the target as a entity, returning `None` if not found.
     #[must_use]
-    pub fn get_target_ent(&self) -> Option<EntityHandle<'world>>
+    pub fn get_target_ent(&self) -> Option<EntityHandle<'query>>
     {
         let archetype = self
             .world
@@ -562,7 +568,7 @@ pub struct MultipleWithWildcard<'a, Relation, Target>
     _pd: PhantomData<(Relation, Target)>,
 }
 
-impl<'world, Relation, Target> MultipleWithWildcard<'world, Relation, Target>
+impl<'query, Relation, Target> MultipleWithWildcard<'query, Relation, Target>
 {
     /// Returns a new `MultipleWithWildcard`.
     ///
@@ -570,7 +576,7 @@ impl<'world, Relation, Target> MultipleWithWildcard<'world, Relation, Target>
     /// This function will panic if:
     /// - Both `Relation::uid()` and `Target::uid()` are wildcards
     /// - Neither `Relation::uid()` or `Target::uid()` are wildcards
-    pub fn new(world: &'world World, entity_handle: EntityHandle<'world>) -> Self
+    pub fn new(world: &'query World, entity_handle: EntityHandle<'query>) -> Self
     where
         Relation: ComponentOrWildcard,
         Target: ComponentOrWildcard,
diff --git a/engine-ecs/src/query.rs b/engine-ecs/src/query.rs
index 8549411..10260f2 100644
--- a/engine-ecs/src/query.rs
+++ b/engine-ecs/src/query.rs
@@ -1,8 +1,8 @@
 use std::any::type_name;
 use std::marker::PhantomData;
 
-use seq_macro::seq;
 use paste::paste;
+use seq_macro::seq;
 use util_macros::sub;
 
 use crate::component::{
@@ -11,13 +11,27 @@ use crate::component::{
     HandleMut as ComponentHandleMut,
 };
 use crate::entity::Handle as EntityHandle;
+use crate::pair::Wildcard;
 use crate::query::flexible::{Iter as FlexibleQueryIter, Query as FlexibleQuery};
 use crate::system::{Metadata as SystemMetadata, Param as SystemParam};
-use crate::tuple::Tuple;
+use crate::tuple::{Concat, Tuple};
 use crate::uid::Uid;
 use crate::util::array_vec::ArrayVec;
 use crate::util::Array;
-use crate::World;
+use crate::{pair, World};
+
+mod reexports
+{
+    pub use crate::component::storage::{
+        SearchTerms as Terms,
+        TermMetadata,
+        Traversal,
+        TraversalKind,
+        TraversalResult,
+    };
+}
+
+pub use reexports::*;
 
 pub mod flexible;
 pub mod term;
@@ -27,23 +41,20 @@ pub const MAX_TERM_CNT: usize = 17;
 
 #[derive(Debug)]
 pub struct Query<'world, TermsT>
-where
-    TermsT: TermTuple<'world>,
 {
     inner: FlexibleQuery<'world, MAX_TERM_CNT>,
     _pd: PhantomData<TermsT>,
 }
 
 impl<'world, TermsT> Query<'world, TermsT>
-where
-    TermsT: TermTuple<'world>,
 {
     /// Iterates over the entities matching this query, the iterator item being the entity
     /// components.
     #[must_use]
-    pub fn iter<'this>(
-        &'this self,
-    ) -> Iter<'this, 'world, TermsT, FlexibleQueryIter<'this, 'world>>
+    pub fn iter<'this>(&'this self) -> Iter<'this, TermsT>
+    where
+        TermsT: TermTuple<'this>,
+        'world: 'this,
     {
         tracing::trace!("Searching for {}", std::any::type_name::<TermsT>());
 
@@ -57,44 +68,25 @@ where
     /// Iterates over the entities matching this query, the iterator item being the entity
     /// [`Uid`] and the matching entity components.
     #[must_use]
-    pub fn iter_with_euids<'this>(
-        &'this self,
-    ) -> ComponentAndEuidIter<'this, 'world, TermsT, FlexibleQueryIter<'this, 'world>>
-    {
-        tracing::trace!("Searching for {}", std::any::type_name::<TermsT>());
-
-        ComponentAndEuidIter {
-            world: self.inner.world(),
-            iter: self.inner.iter(),
-            comps_pd: PhantomData,
-        }
-    }
-
-    /// Iterates over the entities matching this query using the iterator returned by
-    /// `func`.
-    ///
-    /// This function exists so that a custom [`EntityHandle`] iterator can be given to
-    /// [`Iter`] without giving the user access to a reference to the [`World`].
-    #[must_use]
-    pub fn iter_with<'this, OutIter>(
-        &'this self,
-        func: impl FnOnce(FlexibleQueryIter<'this, 'world>) -> OutIter,
-    ) -> Iter<'this, 'world, TermsT, OutIter>
+    pub fn iter_with_euids<'this>(&'this self) -> ComponentAndEuidIter<'this, TermsT>
     where
-        OutIter: Iterator<Item = EntityHandle<'world>>,
+        TermsT: TermTuple<'this>,
+        'world: 'this,
     {
         tracing::trace!("Searching for {}", std::any::type_name::<TermsT>());
 
-        Iter {
+        ComponentAndEuidIter {
             world: self.inner.world(),
-            inner: func(self.inner.iter()),
+            inner: self.inner.iter(),
             comps_pd: PhantomData,
         }
     }
 
     /// Returns the UID of the entity at the given query iteration index.
     #[must_use]
-    pub fn get_entity_uid(&self, entity_index: usize) -> Option<Uid>
+    pub fn get_entity_uid<'this>(&'this self, entity_index: usize) -> Option<Uid>
+    where
+        TermsT: TermTuple<'this>,
     {
         Some(self.inner.iter().nth(entity_index)?.uid())
     }
@@ -124,10 +116,12 @@ where
     }
 
     pub(crate) fn new(world: &'world World) -> Self
+    where
+        TermsT: TermTuple<'world>,
     {
         let mut terms_builder = Terms::builder();
 
-        TermsT::apply_terms_to_builder(&mut terms_builder);
+        TermsT::apply_terms_to_builder(&mut terms_builder, 0);
 
         Self {
             inner: world.flexible_query(terms_builder.build()),
@@ -136,12 +130,12 @@ where
     }
 }
 
-impl<'query, 'world, TermsT> IntoIterator
-    for &'query Query<'world, TermsT>
+impl<'query, 'world, TermsT> IntoIterator for &'query Query<'world, TermsT>
 where
-    TermsT: TermTuple<'world>,
+    TermsT: TermTuple<'query>,
+    'world: 'query,
 {
-    type IntoIter = Iter<'query, 'world, TermsT, FlexibleQueryIter<'query, 'world>>;
+    type IntoIter = Iter<'query, TermsT>;
     type Item = TermsT::Fields;
 
     fn into_iter(self) -> Self::IntoIter
@@ -150,8 +144,7 @@ where
     }
 }
 
-impl<'world, TermsT> SystemParam<'world>
-    for Query<'world, TermsT>
+impl<'world, TermsT> SystemParam<'world> for Query<'world, TermsT>
 where
     TermsT: TermTuple<'world>,
 {
@@ -163,13 +156,6 @@ where
     }
 }
 
-#[derive(Debug)]
-pub struct Terms<const MAX_TERM_CNT: usize>
-{
-    present: ArrayVec<Uid, MAX_TERM_CNT>,
-    absent: ArrayVec<Uid, MAX_TERM_CNT>,
-}
-
 impl<const MAX_TERM_CNT: usize> Terms<MAX_TERM_CNT>
 {
     pub fn builder() -> TermsBuilder<MAX_TERM_CNT>
@@ -180,30 +166,33 @@ impl<const MAX_TERM_CNT: usize> Terms<MAX_TERM_CNT>
 
 #[derive(Debug, Default)]
 #[must_use]
-pub struct TermsBuilder<const MAX_TERM_CNT: usize>
+pub struct TermsBuilder<const TERM_CAP: usize>
 {
-    present: ArrayVec<Uid, MAX_TERM_CNT>,
-    absent: ArrayVec<Uid, MAX_TERM_CNT>,
+    present: ArrayVec<Uid, TERM_CAP>,
+    absent: ArrayVec<Uid, TERM_CAP>,
+    traverse: ArrayVec<Traversal<TERM_CAP>, TERM_CAP>,
 }
 
 #[allow(clippy::return_self_not_must_use)]
-pub trait TermsBuilderInterface
+pub trait TermsBuilderInterface<const TERM_CAP: usize>
 {
     fn present(self, ids: impl Array<Uid>) -> Self;
 
     fn absent(self, ids: impl Array<Uid>) -> Self;
+
+    fn traverse(self, traversals: impl Array<Traversal<TERM_CAP>> + Clone) -> Self;
 }
 
 macro_rules! impl_terms_builder {
     ($($impl_content: tt)*) => {
-        impl<const MAX_TERM_CNT: usize>
-            TermsBuilderInterface for TermsBuilder<MAX_TERM_CNT>
+        impl<const TERM_CAP: usize>
+            TermsBuilderInterface<TERM_CAP> for TermsBuilder<TERM_CAP>
         {
             $($impl_content)*
         }
 
-        impl<const MAX_TERM_CNT: usize>
-            TermsBuilderInterface for &mut TermsBuilder<MAX_TERM_CNT>
+        impl<const TERM_CAP: usize>
+            TermsBuilderInterface<TERM_CAP> for &mut TermsBuilder<TERM_CAP>
         {
             $($impl_content)*
         }
@@ -274,6 +263,17 @@ impl_terms_builder! {
 
         self
     }
+
+    #[allow(unused_mut)]
+    fn traverse(mut self, traversals: impl Array<Traversal<TERM_CAP>> + Clone) -> Self
+    {
+        self.traverse.extend(traversals.clone());
+
+        self.present(
+            traversals
+                .map(|traversal| pair!({ traversal.relation }, Wildcard).id())
+        )
+    }
 }
 
 impl<const MAX_TERM_CNT: usize> TermsBuilder<MAX_TERM_CNT>
@@ -287,45 +287,49 @@ impl<const MAX_TERM_CNT: usize> TermsBuilder<MAX_TERM_CNT>
         Terms {
             present: self.present,
             absent: self.absent,
+            traverse: self.traverse,
         }
     }
 }
 
-pub trait Term<'world>
+pub trait Term<'query>
 {
-    type AddField<Fields: Tuple>;
+    type Fields: Tuple;
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        term_metadata: TermMetadata,
     );
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>;
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
+    ) -> Self::Fields;
 }
 
-impl<'world, ComponentT: Component> Term<'world> for &ComponentT
+impl<'query, ComponentT: Component> Term<'query> for &ComponentT
 {
-    type AddField<Fields: Tuple> = Fields::WithElementAtEnd<ComponentHandle<'world, ComponentT>>;
+    type Fields = (ComponentHandle<'query, ComponentT>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
         terms_builder.present([ComponentT::id()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
         assert!(!ComponentT::id().is_pair());
 
-        let Some(component) = entity_handle
+        let Some(component) = search_result
+            .entity_handle
             .get_matching_components(ComponentT::id())
             .next()
         else {
@@ -335,44 +339,47 @@ impl<'world, ComponentT: Component> Term<'world> for &ComponentT
                     "is most likely a bug in the entity querying"
                 ),
                 type_name::<ComponentT>(),
-                entity_handle.uid()
+                search_result.entity_handle.uid()
             );
         };
 
-        let component = match ComponentHandle::<ComponentT>::from_entity_component_ref(&component) {
-            Ok(component) => component,
-            Err(err) => {
-                panic!(
-                    "Creating handle to component {} failed: {err}",
-                    type_name::<ComponentT>()
-                );
-            }
-        };
+        let component =
+            match ComponentHandle::<ComponentT>::from_entity_component_ref(&component) {
+                Ok(component) => component,
+                Err(err) => {
+                    panic!(
+                        "Creating handle to component {} failed: {err}",
+                        type_name::<ComponentT>()
+                    );
+                }
+            };
 
-        fields.with_elem(component)
+        (component,)
     }
 }
 
-impl<'world, ComponentT: Component> Term<'world> for &mut ComponentT
+impl<'query, ComponentT: Component> Term<'query> for &mut ComponentT
 {
-    type AddField<Fields: Tuple> = Fields::WithElementAtEnd<ComponentHandleMut<'world, ComponentT>>;
+    type Fields = (ComponentHandleMut<'query, ComponentT>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
         terms_builder.present([ComponentT::id()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
         assert!(!ComponentT::id().is_pair());
 
-        let Some(component) = entity_handle
+        let Some(component) = search_result
+            .entity_handle
             .get_matching_components(ComponentT::id())
             .next()
         else {
@@ -382,11 +389,13 @@ impl<'world, ComponentT: Component> Term<'world> for &mut ComponentT
                     "is most likely a bug in the entity querying"
                 ),
                 type_name::<ComponentT>(),
-                entity_handle.uid()
+                search_result.entity_handle.uid()
             );
         };
 
-        let component = match ComponentHandleMut::<ComponentT>::from_entity_component_ref(&component, world) {
+        let component = match ComponentHandleMut::<ComponentT>::from_entity_component_ref(
+            &component, world,
+        ) {
             Ok(component) => component,
             Err(err) => {
                 panic!(
@@ -396,57 +405,67 @@ impl<'world, ComponentT: Component> Term<'world> for &mut ComponentT
             }
         };
 
-        fields.with_elem(component)
+        (component,)
     }
 }
 
-impl<'world, TermT, FieldAcc> TermFieldSource<'world, FieldAcc> for TermT
-where 
-    TermT: Term<'world>,
-    TermT::AddField<FieldAcc>: Tuple,
-    FieldAcc: Tuple
+impl<'query, TermT, FieldAcc> TermFieldSource<'query, FieldAcc> for TermT
+where
+    TermT: Term<'query, Fields: Concat<FieldAcc>>,
+    FieldAcc: Tuple,
 {
-    type NewFieldAcc = TermT::AddField<FieldAcc>;
+    type NewFieldAcc = <TermT::Fields as Concat<FieldAcc>>::Output;
 
     fn collect_field(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
         fields: FieldAcc,
     ) -> Self::NewFieldAcc
     {
-        Self::add_field(entity_handle, world, fields)
+        <TermT::Fields as Concat<FieldAcc>>::concat(
+            Self::fields(world, search_result, term_metadata),
+            fields,
+        )
     }
 }
 
-pub trait TermTuple<'world>
+pub trait TermTuple<'query>
 {
-    type Fields;
+    type Fields: Tuple;
 
     fn apply_terms_to_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        term_level: u32,
     );
 
     fn get_fields(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_level: u32,
     ) -> Self::Fields;
 }
 
-pub struct Iter<'query, 'world, TermsT, EntityHandleIter>
+#[derive(Debug)]
+#[non_exhaustive]
+pub struct SearchResult<'query, 'temp>
+{
+    pub entity_handle: EntityHandle<'query>,
+    pub traversal_results: &'temp [TraversalResult],
+}
+
+pub struct Iter<'query, TermsT>
 where
-    TermsT: TermTuple<'world>,
-    EntityHandleIter: Iterator<Item = EntityHandle<'world>>,
+    TermsT: TermTuple<'query>,
 {
-    world: &'world World,
-    inner: EntityHandleIter,
-    comps_pd: PhantomData<(TermsT, &'query ())>,
+    world: &'query World,
+    inner: FlexibleQueryIter<'query, MAX_TERM_CNT>,
+    comps_pd: PhantomData<TermsT>,
 }
 
-impl<'query, 'world, TermsT, EntityHandleIter> Iterator
-    for Iter<'query, 'world, TermsT, EntityHandleIter>
+impl<'query, TermsT> Iterator for Iter<'query, TermsT>
 where
-    TermsT: TermTuple<'world>,
-    EntityHandleIter: Iterator<Item = EntityHandle<'world>>,
+    TermsT: TermTuple<'query>,
 {
     type Item = TermsT::Fields;
 
@@ -454,46 +473,58 @@ where
     {
         let entity_handle = self.inner.next()?;
 
-        Some(TermsT::get_fields(&entity_handle, self.world))
+        Some(TermsT::get_fields(
+            self.world,
+            &SearchResult {
+                entity_handle,
+                traversal_results: self.inner.traversal_results().unwrap(),
+            },
+            0,
+        ))
     }
 }
 
-pub struct ComponentAndEuidIter<'query, 'world, TermsT, EntityHandleIter>
+pub struct ComponentAndEuidIter<'query, TermsT>
 where
-    TermsT: TermTuple<'world>,
-    EntityHandleIter: Iterator<Item = EntityHandle<'world>>,
+    TermsT: TermTuple<'query>,
 {
-    world: &'world World,
-    iter: EntityHandleIter,
-    comps_pd: PhantomData<(TermsT, &'query ())>,
+    world: &'query World,
+    inner: FlexibleQueryIter<'query, MAX_TERM_CNT>,
+    comps_pd: PhantomData<TermsT>,
 }
 
-impl<'query, 'world, TermsT, EntityHandleIter> Iterator
-    for ComponentAndEuidIter<'query, 'world, TermsT, EntityHandleIter>
+impl<'query, TermsT> Iterator for ComponentAndEuidIter<'query, TermsT>
 where
-    TermsT: TermTuple<'world>,
-    EntityHandleIter: Iterator<Item = EntityHandle<'world>>,
+    TermsT: TermTuple<'query>,
 {
     type Item = (Uid, TermsT::Fields);
 
     fn next(&mut self) -> Option<Self::Item>
     {
-        let entity_handle = self.iter.next()?;
+        let entity_handle = self.inner.next()?;
 
         Some((
             entity_handle.uid(),
-            TermsT::get_fields(&entity_handle, self.world),
+            TermsT::get_fields(
+                self.world,
+                &SearchResult {
+                    entity_handle,
+                    traversal_results: self.inner.traversal_results().unwrap(),
+                },
+                0,
+            ),
         ))
     }
 }
 
-pub trait TermFieldSource<'world, FieldAcc>
+pub trait TermFieldSource<'query, FieldAcc>
 {
     type NewFieldAcc;
 
     fn collect_field(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
         fields: FieldAcc,
     ) -> Self::NewFieldAcc;
 }
@@ -513,11 +544,11 @@ macro_rules! term_field_source_new_field_acc {
 macro_rules! gen_term_tuple_impls {
     ($c: tt) => {
         seq!(I in 0..$c {
-            impl<'world, #(Term~I,)*> TermTuple<'world> for (#(Term~I,)*)
+            impl<'query, #(Term~I,)*> TermTuple<'query> for (#(Term~I,)*)
             where
                 #(
-                    Term~I: Term<'world> + TermFieldSource<
-                        'world,
+                    Term~I: Term<'query> + TermFieldSource<
+                        'query,
                         sub!(I - 1, term_field_source_new_field_acc),
                         NewFieldAcc: Tuple
                     >,
@@ -527,24 +558,40 @@ macro_rules! gen_term_tuple_impls {
 
                 #[allow(unused)]
                 fn apply_terms_to_builder<const MAX_TERM_CNT: usize>(
-                    terms_builder: &mut TermsBuilder<MAX_TERM_CNT>
+                    terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+                    term_level: u32,
                 )
                 {
                     #(
-                        Term~I::apply_to_terms_builder(terms_builder);
+                        Term~I::apply_to_terms_builder(
+                            terms_builder,
+                            TermMetadata {
+                                level: term_level,
+                                index: I
+                            },
+                        );
                     )*
                 }
 
                 #[allow(unused)]
                 fn get_fields(
-                    entity_handle: &EntityHandle<'world>,
-                    world: &'world World,
+                    world: &'query World,
+                    search_result: &SearchResult<'query, '_>,
+                    term_level: u32,
                 ) -> Self::Fields
                 {
                     let fields = ();
 
                     #(
-                        let fields = Term~I::collect_field(entity_handle, world, fields);
+                        let fields = Term~I::collect_field(
+                            world,
+                            search_result,
+                            TermMetadata {
+                                level: term_level,
+                                index: I
+                            },
+                            fields
+                        );
                     )*
 
                     fields
@@ -557,4 +604,3 @@ macro_rules! gen_term_tuple_impls {
 seq!(C in 0..17 {
     gen_term_tuple_impls!(C);
 });
-
diff --git a/engine-ecs/src/query/flexible.rs b/engine-ecs/src/query/flexible.rs
index fd1e30e..0198fb4 100644
--- a/engine-ecs/src/query/flexible.rs
+++ b/engine-ecs/src/query/flexible.rs
@@ -1,41 +1,34 @@
 //! Low-level querying.
-use std::iter::{repeat_n, FlatMap, RepeatN, Zip};
-
 use crate::component::storage::archetype::{Archetype, EntityIter};
-use crate::component::storage::{ArchetypeRefIter, ArchetypeSearchTerms};
+use crate::component::storage::{ArchetypeRefIter, TraversalResult};
 use crate::entity::Handle as EntityHandle;
 use crate::query::Terms;
+use crate::util::array_vec::ArrayVec;
 use crate::World;
 
 /// Low-level entity query structure.
 #[derive(Debug)]
-pub struct Query<'world, const MAX_TERM_CNT: usize>
+pub struct Query<'world, const TERM_CAP: usize>
 {
     world: &'world World,
-    terms: Terms<MAX_TERM_CNT>,
+    terms: Terms<TERM_CAP>,
 }
 
-impl<'world, const MAX_TERM_CNT: usize> Query<'world, MAX_TERM_CNT>
+impl<'world, const TERM_CAP: usize> Query<'world, TERM_CAP>
 {
     /// Iterates over the entities matching this query.
     #[must_use]
-    pub fn iter(&self) -> Iter<'_, 'world>
+    pub fn iter<'this>(&'this self) -> Iter<'this, TERM_CAP>
+    where
+        'world: 'this,
     {
         Iter {
-            iter: self
+            archetype_iter: self
                 .world
                 .data
                 .component_storage
-                .search_archetypes(ArchetypeSearchTerms {
-                    present: &self.terms.present,
-                    absent: &self.terms.absent
-                })
-                .flat_map(
-                    (|archetype| {
-                        repeat_n(archetype, archetype.entity_cnt())
-                            .zip(archetype.entities())
-                    }) as ComponentIterMapFn,
-                ),
+                .search_archetypes(&self.terms),
+            current: None,
             world: self.world,
         }
     }
@@ -46,16 +39,19 @@ impl<'world, const MAX_TERM_CNT: usize> Query<'world, MAX_TERM_CNT>
         self.world
     }
 
-    pub(crate) fn new(world: &'world World, terms: Terms<MAX_TERM_CNT>) -> Self
+    pub(crate) fn new(world: &'world World, terms: Terms<TERM_CAP>) -> Self
     {
         Self { world, terms }
     }
 }
 
-impl<'query, 'world, const MAX_TERM_CNT: usize> IntoIterator for &'query Query<'world, MAX_TERM_CNT>
+impl<'query, 'world, const TERM_CAP: usize> IntoIterator
+    for &'query Query<'world, TERM_CAP>
+where
+    'world: 'query,
 {
-    type IntoIter = Iter<'query, 'world>;
-    type Item = EntityHandle<'world>;
+    type IntoIter = Iter<'query, TERM_CAP>;
+    type Item = EntityHandle<'query>;
 
     fn into_iter(self) -> Self::IntoIter
     {
@@ -63,30 +59,43 @@ impl<'query, 'world, const MAX_TERM_CNT: usize> IntoIterator for &'query Query<'
     }
 }
 
-pub struct Iter<'query, 'world>
+pub struct Iter<'query, const TERM_CAP: usize>
 {
-    iter: QueryEntityIter<'query, 'world>,
-    world: &'world World,
+    archetype_iter: ArchetypeRefIter<'query, 'query, TERM_CAP>,
+    current: Option<(
+        &'query Archetype,
+        ArrayVec<TraversalResult, TERM_CAP>,
+        EntityIter<'query>,
+    )>,
+    world: &'query World,
 }
 
-impl<'query, 'world> Iterator for Iter<'query, 'world>
+impl<'query, const TERM_CAP: usize> Iter<'query, TERM_CAP>
 {
-    type Item = EntityHandle<'world>;
-
-    fn next(&mut self) -> Option<Self::Item>
+    pub fn traversal_results(&self) -> Option<&[TraversalResult]>
     {
-        let (archetype, entity) = self.iter.next()?;
-
-        Some(EntityHandle::new(archetype, entity, self.world))
+        self.current
+            .as_ref()
+            .map(|(_, traversal_results, _)| traversal_results.as_ref())
     }
 }
 
-type ComponentIterMapFnOutput<'a> = Zip<RepeatN<&'a Archetype>, EntityIter<'a>>;
+impl<'query, const TERM_CAP: usize> Iterator for Iter<'query, TERM_CAP>
+{
+    type Item = EntityHandle<'query>;
 
-type ComponentIterMapFn = for<'a> fn(&'a Archetype) -> ComponentIterMapFnOutput<'a>;
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        if let Some((archetype, _, entity_iter)) = self.current.as_mut() {
+            if let Some(entity) = entity_iter.next() {
+                return Some(EntityHandle::new(archetype, entity, self.world));
+            }
+        }
+
+        let (archetype, traversal_results) = self.archetype_iter.next()?;
 
-type QueryEntityIter<'query, 'world> = FlatMap<
-    ArchetypeRefIter<'world, 'query>,
-    ComponentIterMapFnOutput<'world>,
-    ComponentIterMapFn,
->;
+        self.current = Some((archetype, traversal_results, archetype.entities()));
+
+        self.next()
+    }
+}
diff --git a/engine-ecs/src/query/term.rs b/engine-ecs/src/query/term.rs
index 04bca1d..1bcb3dd 100644
--- a/engine-ecs/src/query/term.rs
+++ b/engine-ecs/src/query/term.rs
@@ -1,20 +1,23 @@
 use std::any::type_name;
 use std::marker::PhantomData;
 
-use crate::World;
 use crate::component::{
     Component,
     Handle as ComponentHandle,
     HandleMut as ComponentHandleMut,
 };
-use crate::entity::Handle as EntityHandle;
 use crate::query::{
+    SearchResult,
     Term,
+    TermMetadata,
+    TermTuple,
     TermsBuilder,
     TermsBuilderInterface,
+    Traversal,
+    TraversalKind,
 };
-use crate::tuple::Tuple;
 use crate::uid::With as WithUid;
+use crate::World;
 
 pub struct With<WithUidT>
 where
@@ -23,26 +26,27 @@ where
     _pd: PhantomData<WithUidT>,
 }
 
-impl<'world, WithUidT> Term<'world> for With<WithUidT>
+impl<'query, WithUidT> Term<'query> for With<WithUidT>
 where
     WithUidT: WithUid,
 {
-    type AddField<Fields: Tuple> = Fields;
+    type Fields = ();
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
         terms_builder.present([WithUidT::uid()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        _entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        _search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
-        fields
+        ()
     }
 }
 
@@ -53,48 +57,50 @@ where
     _pd: PhantomData<WithUidT>,
 }
 
-impl<'world, WithUidT> Term<'world> for Without<WithUidT>
+impl<'query, WithUidT> Term<'query> for Without<WithUidT>
 where
     WithUidT: WithUid,
 {
-    type AddField<Fields: Tuple> = Fields;
+    type Fields = ();
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
         terms_builder.absent([WithUidT::uid()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        _entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        _search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
-        fields
+        ()
     }
 }
 
-impl<'world, ComponentT: Component> Term<'world> for Option<&ComponentT>
+impl<'query, ComponentT: Component> Term<'query> for Option<&ComponentT>
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<Option<ComponentHandle<'world, ComponentT>>>;
+    type Fields = (Option<ComponentHandle<'query, ComponentT>>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
         let component = (|| {
-            let comp_ref = &entity_handle
+            let comp_ref = &search_result
+                .entity_handle
                 .get_matching_components(ComponentT::id())
                 .next()?;
 
@@ -109,33 +115,36 @@ impl<'world, ComponentT: Component> Term<'world> for Option<&ComponentT>
             }
         })();
 
-        fields.with_elem(component)
+        (component,)
     }
 }
 
-impl<'world, ComponentT: Component> Term<'world> for Option<&mut ComponentT>
+impl<'query, ComponentT: Component> Term<'query> for Option<&mut ComponentT>
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<Option<ComponentHandleMut<'world, ComponentT>>>;
+    type Fields = (Option<ComponentHandleMut<'query, ComponentT>>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
         let component = (|| {
-            let comp_ref = &entity_handle
+            let comp_ref = &search_result
+                .entity_handle
                 .get_matching_components(ComponentT::id())
                 .next()?;
 
-            match ComponentHandleMut::<ComponentT>::from_entity_component_ref(comp_ref, world) {
+            match ComponentHandleMut::<ComponentT>::from_entity_component_ref(
+                comp_ref, world,
+            ) {
                 Ok(component) => Some(component),
                 Err(err) => {
                     panic!(
@@ -146,6 +155,99 @@ impl<'world, ComponentT: Component> Term<'world> for Option<&mut ComponentT>
             }
         })();
 
-        fields.with_elem(component)
+        (component,)
+    }
+}
+
+pub struct Traverse<TermsT, Kind, Relation>
+{
+    _pd: PhantomData<(TermsT, Kind, Relation)>,
+}
+
+impl<'query, TermsT, Kind, Relation> Term<'query> for Traverse<TermsT, Kind, Relation>
+where
+    TermsT: TermTuple<'query>,
+    Kind: TraversalKindType,
+    Relation: Component,
+{
+    type Fields = TermsT::Fields;
+
+    fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
+        terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        term_metadata: TermMetadata,
+    )
+    {
+        terms_builder.traverse([Traversal {
+            kind: Kind::traversal_kind(),
+            relation: Relation::id(),
+            terms: |traversal| {
+                let mut terms_builder = TermsBuilder::default();
+
+                TermsT::apply_terms_to_builder(
+                    &mut terms_builder,
+                    traversal
+                        .term_metadata
+                        .level
+                        .checked_add(1)
+                        .expect("Too large term level. Would overflow"),
+                );
+
+                terms_builder.build()
+            },
+            term_metadata,
+        }]);
     }
+
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
+    ) -> Self::Fields
+    {
+        let Some(traversal_result) = search_result
+            .traversal_results
+            .iter()
+            .find(|traversal_result| traversal_result.term_metadata == term_metadata)
+        else {
+            unreachable!();
+        };
+
+        let Some(found_ent) = world.get_entity(traversal_result.found_ent) else {
+            unreachable!();
+        };
+
+        TermsT::get_fields(
+            world,
+            &SearchResult {
+                entity_handle: found_ent,
+                traversal_results: search_result.traversal_results,
+            },
+            term_metadata
+                .level
+                .checked_add(1)
+                .expect("Too large term level. Would overflow"),
+        )
+    }
+}
+
+pub trait TraversalKindType: sealed::Sealed
+{
+    fn traversal_kind() -> TraversalKind;
+}
+
+pub struct TraverseUp;
+
+impl TraversalKindType for TraverseUp
+{
+    fn traversal_kind() -> TraversalKind
+    {
+        TraversalKind::Up
+    }
+}
+
+impl sealed::Sealed for TraverseUp {}
+
+mod sealed
+{
+    pub trait Sealed {}
 }
diff --git a/engine-ecs/src/tuple.rs b/engine-ecs/src/tuple.rs
index 15e1719..a2073b1 100644
--- a/engine-ecs/src/tuple.rs
+++ b/engine-ecs/src/tuple.rs
@@ -1,4 +1,5 @@
-use std::{any::TypeId, convert::Infallible};
+use std::any::TypeId;
+use std::convert::Infallible;
 
 use paste::paste;
 use seq_macro::seq;
@@ -55,6 +56,32 @@ pub trait ReduceElement<Accumulator, Operation>
     type Return;
 }
 
+pub trait ElementConcat<Acc>
+{
+    type Output;
+
+    fn add_to(self, acc: Acc) -> Self::Output;
+}
+
+impl<Elem, Acc> ElementConcat<Acc> for Elem
+where
+    Acc: Tuple,
+{
+    type Output = Acc::WithElementAtEnd<Elem>;
+
+    fn add_to(self, acc: Acc) -> Self::Output
+    {
+        acc.with_elem(self)
+    }
+}
+
+pub trait Concat<Left>
+{
+    type Output;
+
+    fn concat(self, left: Left) -> Self::Output;
+}
+
 macro_rules! tuple_reduce_elem_tuple {
     (overflow) => {
         ()
@@ -67,6 +94,18 @@ macro_rules! tuple_reduce_elem_tuple {
     };
 }
 
+macro_rules! tuple_concat_elem_ouput {
+    (overflow) => {
+        Left
+    };
+
+    ($index: tt) => {
+        paste! {
+            [<Elem $index>]::Output
+        }
+    };
+}
+
 macro_rules! elem_type_by_index {
     (overflow) => {
         ()
@@ -148,6 +187,31 @@ macro_rules! impl_tuple_traits {
                 }
             }
 
+            paste! {
+                impl<Left, #(Elem~I,)*> Concat<Left> for (#(Elem~I,)*)
+                where
+                    Left: Tuple,
+                    #(
+                        Elem~I: ElementConcat<
+                            sub!(I - 1, tuple_concat_elem_ouput),
+                        >,
+                    )*
+                {
+                    type Output = sub!($cnt - 1, tuple_concat_elem_ouput);
+
+                    fn concat(self, left: Left) -> Self::Output
+                    {
+                        let out = left;
+
+                        #(
+                            let out = self.I.add_to(out);
+                        )*
+
+                        out
+                    }
+                }
+            }
+
             impl<#(Elem~I: 'static,)*> WithAllElemLtStatic for (#(Elem~I,)*)
             {
                 fn get_mut<Element: 'static>(&mut self, index: usize) -> Option<&mut Element>
diff --git a/engine-ecs/src/util.rs b/engine-ecs/src/util.rs
index f56a5c4..c52608a 100644
--- a/engine-ecs/src/util.rs
+++ b/engine-ecs/src/util.rs
@@ -34,6 +34,23 @@ impl<Item> VecExt<Item> for Vec<Item>
     }
 }
 
+impl<Item, const CAPACITY: usize> VecExt<Item> for ArrayVec<Item, CAPACITY>
+{
+    fn insert_at_part_pt_by_key<Key>(
+        &mut self,
+        item: Item,
+        mut func: impl FnMut(&Item) -> &Key,
+    ) where
+        Key: Ord,
+    {
+        let key = func(&item);
+
+        let insert_index = self.partition_point(|other_item| func(other_item) <= key);
+
+        self.insert(insert_index, item);
+    }
+}
+
 pub trait StreamingIterator
 {
     type Item<'a>
@@ -190,9 +207,16 @@ pub trait Array<Item>:
     + Sortable<Item = Item>
     + sealed::Sealed
 {
+    fn map<T>(self, func: impl FnMut(Item) -> T) -> impl Array<T>;
 }
 
-impl<Item, const CNT: usize> Array<Item> for [Item; CNT] {}
+impl<Item, const CNT: usize> Array<Item> for [Item; CNT]
+{
+    fn map<T>(self, func: impl FnMut(Item) -> T) -> impl Array<T>
+    {
+        self.map(func)
+    }
+}
 
 impl<Item, const CNT: usize> sealed::Sealed for [Item; CNT] {}
 
@@ -414,6 +438,8 @@ macro_rules! const_assert {
 
 pub(crate) use const_assert;
 
+use crate::util::array_vec::ArrayVec;
+
 mod sealed
 {
     pub trait Sealed {}
diff --git a/engine-ecs/src/util/array_vec.rs b/engine-ecs/src/util/array_vec.rs
index 5d0aac9..5863507 100644
--- a/engine-ecs/src/util/array_vec.rs
+++ b/engine-ecs/src/util/array_vec.rs
@@ -57,9 +57,23 @@ impl<Item, const CAPACITY: usize> ArrayVec<Item, CAPACITY>
     }
 }
 
+impl<Item, const CAPACITY: usize> FromIterator<Item> for ArrayVec<Item, CAPACITY>
+{
+    fn from_iter<IterT: IntoIterator<Item = Item>>(iter: IterT) -> Self
+    {
+        let mut new = Self::default();
+
+        for item in iter {
+            new.push(item);
+        }
+
+        new
+    }
+}
+
 impl<Item, const CAPACITY: usize> Extend<Item> for ArrayVec<Item, CAPACITY>
 {
-    fn extend<IntoIter: IntoIterator<Item = Item>>(&mut self, iter: IntoIter)
+    fn extend<Iter: IntoIterator<Item = Item>>(&mut self, iter: Iter)
     {
         for item in iter {
             self.push(item);
@@ -116,6 +130,16 @@ impl<Item, const CAPACITY: usize> Default for ArrayVec<Item, CAPACITY>
     }
 }
 
+impl<Item, const CAPACITY: usize> Clone for ArrayVec<Item, CAPACITY>
+where
+    Item: Clone,
+{
+    fn clone(&self) -> Self
+    {
+        Self::from_iter(self.iter().cloned())
+    }
+}
+
 impl<Item, const CAPACITY: usize> Drop for ArrayVec<Item, CAPACITY>
 {
     fn drop(&mut self)