Hierarchy optimized systems and storage

[james7132]

What problem does this solve or what need does it fill?

Several common entity hierarchy based systems have started to crop up in multiple upcoming and current focus areas.

• Current: Transform propagation is reliant on a depth-first traversal of the Transform hierarchy.
• Current: Make Visibility affect children entities #3874 - ComputedVisbility should be inherited from parents/ancestors.
• Upcoming: Animation bone binding maintenance require querying a path of named descendants. For example, root/hips/chest/shoulder_L is a top-down hierarchy query based on the Name components of each entity.

There are also several existing cases where the current Transform based hierarchy is either buggy or unwieldy to manage the need to wait for the consistency of the system to settle.

• GlobalTransform not being updated #3329
• Ensure GlobalTransform consistency when Parent is spawned without Children #3340
• Child's Transform component ignored when parent does not have the GlobalTransform/Transform components #2277

Other issues brought up about the hierarchy:

• Should bevy-transform be two crates? #2758
• Transform hierarchy split #2789

What solution would you like?

This will require additional design but it'd be best to have a hierarchy structure that is:

• Agnostic to the ECS data that is being stored at each Entity, but enables querying for ECS components as well as it's position within a hierarchy.
• Performant to traverse: primarily in both a top-down depth first but also linear manner.
• Minimize deferred/time based delays between hierarchy updates and the results appearing in the final output.
• Constant time updates to local changes in the hierarchy itself, primarily these operations:
  • Parenting an Entity to a child
  • Unparenting an Entity to a child.
  • Re-parenting an Entity between two different parents.
  • These should not require a secondary maintenance system to keep it correct.
• Easy to detect, deduplicate, and propagate dirtying. Think transitive change detection at the hierarchy level.
• Optionally: dedicated hierarchy-optimized ECS storage. This may be a huge stretch goal, but it would speed up any hierarchy traversals by cutting out some of the cache misses.

What alternative(s) have you considered?

Using the current Parent and Children components as is.

Possible Ideas

One of the potential options that doesn't rock the boat that hard is using a tree-based linked list approach.

#[derive(Component)]
pub struct HierarchicalRelations {
  first_child: Option<Entity>,
  prev_sibling: Option<Entity>,
  next_sibling: Option<Entity>,
  parent: Option<Entity>,
}

This has a few benefits/drawbacks over the current Parent/Children component approach:

• This component exposes an interface that would encapsulate both Parent and Children as well as let users query for the siblings
  of a given Entity without a reference to the parent.
• This creates a tree/forest of linked entities where each set of children forms a doubly-linked list. This can be used to traverse the tree in many different ways.
• This could be split into 4 different components if we need the cache locality, though the random access may negate any cache based perf gains seen there.
• Custom iterators and SystemParams can be built on top of queries for this component(s) to more easily query for ECS data based on the hierarchy (i.e. HierarchyQuery<T>::iter_all_in_descendants or HierarchyQuery<T>::iter_all_in_ancestors)
• Updating these pointers just requires Query<&mut HierarchicalRelations>. Query::get_multiple or something similar can be used to update multiple relations at the same time to "atomically" update each of them. Removes the reliance on a secondary system to keep Children up to date.
• Ignoring change detection, this would actually have a smaller memory footprint as both Children and Parent, assuming we have Option<Entity> niched. SmallVec<[Entity; 8]> is 64 bytes in ECS storage, and more if it overflows, and Parent is 8 bytes. This single component is only 32 bytes.
• The main downside to this is that counting the number of children of an entity is O(n), though this could be fixed via caching.
• This loses cache locality of child references, becoming a linked list with random lookups. However, since both this component and the current Children solution are both more or less useless without a secondary Query::get to fetch corresponding components, this might not be a big loss.
• This loses the ergonomics of using a for loop over the children of a given Entity. Could be handled with a custom iterator though.

This is an approach seen in bitsquid http://bitsquid.blogspot.com/2014/10/building-data-oriented-entity-system.html, where dedicated storage for the hierarchy was also used.

Additional context

• This likely requires a lot of design and RFC around this if we decide to go down this route.
• Is it possible to handle this with ECS relations?

[alice-i-cecile]

Related discussion of current limitations, with a focus on bugs and usability: #2572.

This is effectively a more-scoped version of #3742.

[alice-i-cecile]

Is it possible to handle this with ECS relations?

Yes: this is one of the core use cases. However, as you see, there's a huge level of design and benchmarking required. This may be a good starting point to allow us to build-out a generalizable solution.

This loses the ergonomics of using a for loop over the children of a given Entity. Could be handled with a custom iterator though.

IMO this is required.

[alice-i-cecile]

Alternative proposal: Hierarchy as a resource

Rather than storing Parent and Child components, simply store a Hierarchy resource.

Benefits

• cache locality and efficient, easily tweaked data structures for lookup
• no coordination challenges: simply hook into an event emitted when entities are despawned to make sure that you don't go out of sync
• instant modification
• easy to extend with helpful APIs due to simple data model
• easy to extend to user-created variants

Drawbacks

• information about "is this entity part of the hierarchy" is harder to discover, as it's no longer part of the hierarchy

Limitations

• actual information of interest (i.e. Transform) will still require fragmented query.get call

[james7132]

Rather than storing Parent and Child components, simply store a Hierarchy resource.

One downsidde to this is that this blocks any concurrent editing of the hierarchy, at least not without a RwLock of some kind. Though that might be desirable for determinism purposes, and arguably Query<&mut HierarhicalRelations> when using Query::get_multiple is in a similar boat.

---

However, mutation, beyond the local scope is probably not something we should be optimizing for here, since the heaviest operations involve traversing and reading the hierarchy. It's probably best to think of the ways we want to be querying this structure what other non-mutative operations we want on it.

• Dirtying. Think of this as hierarchical change detection. A good number of these cases benefit from finding changes to the hierarchy. This should be used in tandem with normal change detection to seed the dirtying.
  • Value dirtying - This is a change in an ECS component that causes a propagating change in it's children or ancestors. A great example of this is visibility inheritance. If an entity is no longer visible, it's children aren't visible either. This may require a form of deduplication to prevent an exponential number of tree traverals.
  • Structural dirtying - This is a result of changing the hierarchy itself. Structural dirtying implies value dirtying here.
  • As suggested by this article, mutating the internals of a hierarchy structure can optimize these use cases.
• Path queries. These utilize some criteria (i.e. Name components), to find one or more descendants of a ancestor.
• Blanket traversals. These could be breadth-first or depth first depending on the use case. Needed for the dirtying use cases.

Some additional observations:

• Unless we have dedicated hierarchical ECS storage for component data, fragmented Query::get calls are unavoidable. Even then the question of hierarchy maintenance requires quite a bit of swapping and shifting of storage, so the gains here might be quickly negated outside of simple toy examples.
• Solutions that aren't in ECS storage (i.e. resources) will require a mapping back to Entity of some sort, be it HashMap, BTreeMap, or SparseSet. All 3 arguably lose out a bit in terms of cache performance, and require a bit more memory. Entity itself cannot contain hierarchical data in it as of now, though some bit-mangled version of it might be able to.
• Relations, AFAIK, only solves the issues of representing, updating, and maintaining one level of the hierarchy's relationship with it's immediate neighbors. The resource or hierarchical ECS storage solutions targets the problem globally and might be able to be optimized more aggressively.

[alice-i-cecile]

One downsidde to this is that this blocks any concurrent editing of the hierarchy, at least not without a RwLock of some kind

I will note that this is currently the case with commands, but this is a limitation.

Unless we have dedicated hierarchical ECS storage for component data, fragmented Query::get calls are unavoidable. Even then the question of hierarchy maintenance requires quite a bit of swapping and shifting of storage, so the gains here might be quickly negated outside of simple toy examples.

Yep: however by storing e.g. a Transform in this hierarchical storage we're losing performance on linear iteration instead (which is also quite common), unless we're duplicating data across both storages.

Relations, AFAIK, only solves the issues of representing, updating, and maintaining one level of the hierarchy's relationship with it's immediate neighbors. The resource or hierarchical ECS storage solutions targets the problem globally and might be able to be optimized more aggressively.

This is correct for some but not all of the potential designs :) The index-backed solutions can be custom-optimized for these situations.

[cart]

@alice-i-cecile another big drawback to "hierarchy as a resource" is that it is not particularly scene friendly. It assumes (1) that we support loading resources from scenes and (2) that each time we load a scene's instance of the hierarchy resource, we "merge" that with the global version.

I do think a Hierarchy / left+right pointer based approach is worth considering (note that I read the bitsquid article linked above way back when I was first deciding how hierarchy would work in Bevy). The ability to update the hierarchy "transactionally" is really nice (although this could be accomplished with split components, with the right scoping). I also really like the O(1) entity deparenting.

The main reasons I opted for split components vs "Hierarchy left+right":

• it made it easy and cheap to query for "hierarchy roots" (just do Query<Entity, Without<Parent>>), things with parents (With<Parent>), and things with children (With<Children>). Doing a full scan of all Hierarchy components every time a root is needed (ex: propagating transforms, updating UI layouts, etc) isn't ideal.
• You can query for Changed<Children> to detect when a child has been added / removed from a specific entity.
• you can make "root queries" vs "everything else queries" disjoint (and therefore they can exist at the same time).

However during this early decision making process, I very clearly undervalued "always consistent" hierarchies. Given how central hierarchy can be to game logic, being able to trust it at a given point in time (and not just after the Hierarchy sync) is pretty important. The "consistency problem" must be solved, but I do think we lose a lot of valuable functionality by moving to the "Hierarchy left/right/parent" approach.

[james7132]

Yep: however by storing e.g. a Transform in this hierarchical storage we're losing performance on linear iteration instead (which is also quite common), unless we're duplicating data across both storages.

As suggested by the bitsquid article, which has been referenced several times in this thread already, you can keep what is effectively a Vec<Transform> around. Iteration is still 100% linear, and better yet, it enforces that parents are iterated before their children. The main issue here is that such a storage aggressively swaps the data stored within it upon dirtying any of the components held within: could be a very write-heavy solution for large pieces of data and should generally be used in cases only when mutations are a very small subset of the available entities.

[cart]

Also for "hierarchy as a resource", it creates a "garbage collection" problem. Every time an entity is despawned, we now need to check if it exists in the hierarchy. You can't know ahead of time, so you need to check every despawned entity.

[james7132]

it made it easy and cheap to query for "hierarchy roots" (just do Query<Entity, Without>), things with parents (With), and things with children (With). Doing a full scan of all Hierarchy components every time a root is needed (ex: propagating transforms, updating UI layouts, etc) isn't ideal.

Is this something we can't deal with using either Resources that wrap HashSet (i.e. Root(HashSet<Entity>) and Leaves(HashSet<Entity>)) or marker ZSTs? Both of which can be enforced in O(1) time and can have linear iteration time. For cases where we load/unload large masses of entities, we can have a one-shot system patch up these resources afterwards to enforce correctness.

You can query for Changed to detect when a child has been added / removed from a specific entity.

Wouldn't a inverted filter work here too (i.e. Changed<Parent> where Parent(Option<Entity>) and a corresponding query for the parent's components) also suffice? This is less ergonomic, but IMO this is resolvable with a custom SystemParam.

you can make "root queries" vs "everything else queries" disjoint (and therefore they can exist at the same time).

Can you explain this more? Read-only queries should be easy enough to work with without clashes.

---

Overall, I don't think the underlying representation here is something we should encourage users to directly query, much like ECS itself, but rather provide solid wrappers and abstractions (i.e. custom SystemParams, dedicated hierarchical query types) that provide the ergonomics needed.