Relational Queries

[alice-i-cecile]

Goal Description

Accessing related entities (parents, children, ancestors) is a common demand when writing more complex logic in the ECS (particularly when working with scenes or UI). Our existing solutions are insufficiently ergonomic and challenging to discover, and inadequately composable. Without the use of multiple queries, boilerplate logic or exclusive systems, users should be able to:

• fetch the value of a given component on the entity's parent
• fetch the value of a given component from the first encountered ancestor on an entity, if such an entity is found
• fetch the entity ID of the first encountered sibling entity with the given component
• find the first child or grand-child with the given component
• check if the values of a given component on any of the (recursive) children have changed
• perform all of these operations but using arbitrary tree-like relationships instead of Children/ChildOf

Relational queries which involve value-checking are out-of-scope: only existing query filters need to be supported.

Previously: #17647

Goal Status

This is a potential Bevy Project Goal. Its state on the Project Goals Board determines if it is Proposed, Postponed, Blocked (Approved), Inactive (Approved), Active (Approved), Completed, or Declined.

• Staffing SMEs: Not yet staffed
• Working Group Link: Working Group not yet formed
• Design Documents: Design documents not yet written

[alice-i-cecile]

@SanderMertens chimes in with advice on common patterns and use cases:

I think the things that have been discussed most often are:

// find spaceships docked to anything
SpaceShip($this), DockedTo($this, *)

// find all spaceships docked to a planet
SpaceShip($this), DockedTo($this, $thing), Planet($thing)

// find all entities with networked components
Networked($component), $component($this)

// find all entities with Position & a parent with Position
Position($this), Position(up ChildOf)

[alice-i-cecile]

@james-j-obrien remarks:

Ive just been working on a query engine that supports most of the queries that Sander mentioned although the internals are quite different to bevys atm.

One API wrinkle is it becomes hard to support Query implementing IntoIterator as each match can access components on multiple entities, if you want to mutate anything across a relationship (which could therefore be shared with another entity) you can't be "collectable" like an iterator is. It becomes a lending iterator

[SanderMertens]

Useful tutorial on how to read prolog-style queries (first 30min basically go over everything you need to know): https://www.youtube.com/watch?t=358&v=SykxWpFwMGs&feature=youtu.be

Good video with example use cases & explanation on how to implement prolog-style backtracking: https://www.youtube.com/watch?v=b04n6JfDano

Another example of where prolog-style queries are used in the wild: https://docs.larian.game/Osiris_Overview

List of prerequisites & hurdles you'll encounter for relational queries (written for fragmenting relationships but applies to other kinds of storages as well): https://ajmmertens.medium.com/a-roadmap-to-entity-relationships-5b1d11ebb4eb

[james-j-obrien]

To expand on my meaning above: There are some restrictions placed on the type of API that can be provided for relational queries while still allowing it to implement std::iter::IntoIterator/having QueryIter implement Iterator.

If I wanted to query for &mut Transform of my entity and my entity's parent, even though we are not going to alias in that fetch, we can no longer implement Iterator for QueryIter as sibling entities would produce aliasing if we were to, for example, collect the iterator.

let mut query = world.query::<(&mut Transform, Parent<&mut Transform>>();
let vec = query.iter_mut().collect();
// Oh no vec[0].1 aliases with vec[1].1 as they share a parent

Depending on the design there are other cases that can cause this, if I query for (&mut Transform, (ChildOf, *)) a prolog style solver would typically return one match per child that could take the place of *, but then those transforms would alias if collected, despite not even accessing another entity mutably.

TL;DR: In order to maintain Query: IntoIterator during iteration the design needs to

1. keep accesses to related entities read only
2. only match target entities mutably once

#21557 does this by only supporting iteration for a subset of QueryData and only matching once per entity.
Lending/StreamingIterator are options to try and bring some of the Iterator functionality back to problematic queries without manually implementing iterator methods, but there are complexity tradeoffs.