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.

[alice-i-cecile]

that we support loading resources from scenes

FYI, #3580 does this.

[james7132]

FYI, #3580 does this.

IIRC that PR doesn't support merging resources with one in a scene. We'd likely need a specialized solution that handles merging and unmerging the resource upon scene load and unload. Though admittedly, so would any scene load/unload that directly handles Entity references in components.

[alice-i-cecile]

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.

We could add a Hierarchy component for this, but then this results in another synchronization problem...

[james7132]

Instead of Parent(Option<Entity>) we could use the following components

#[derive(Component)]
pub struct Parent(Entity);

#[derive(Component)]
pub struct FirstChild(Entity);

#[derive(Component)]
pub struct PrevSibling(Entity);

#[derive(Component)]
pub struct NextSibling(Entity);

Pros

• This works based on component presence., so it works with filters like Changed<Parent> or Without<FirstChild>. Root queries still work as expected without any additional resource to maintain it.
• This relies on Commands to work properly, but that delays consistency until the next command buffer flush (i.e. stage boundaries, exclusive systems) instead of relying on a singular maintenance system.
  • Could be a reasonable compromise here given both engine systems and developers being used to the idea of delaying changes to a common synchronization point.
• This still guarantees O(1) hierarchy updates.
• Addition/removal costs can be eased with SparseSet storage for these links.

Cons

• This complicates the code for managing the operations on the hierarchy quite a bit, but can be mitigated via query wrappers and custom SystemParams.
• Structural changes are not visible until the next command buffer flush. Any mutative changes will be inconsistent until then. For example: a new child onto a parent will update FirstChild and the Sibling components respectively, but Parent nor the Sibling components are not going to be there until the command buffer flush). This might not be a good idea if we stack multiple changes in the same system. This definitely needs to be explored more.
• Will cause pretty hefty archetype fragmentation. These 4 alone cause each "normal" archetype to be split into 16 potential combinations.
• This does not address the issues of cache-friendly iteration, just consistency.

[alice-i-cecile]

The archetype fragmentation could be addressed down the line with archetype invariants. In practice, I'm not sure that users will be manually building these things, and we'll only get fragmentation if we're inserting this one component at a time.

[maniwani]

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

• It's 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" and "everything else queries" disjoint (and therefore they can exist at the same time).

I do think we lose a lot of valuable functionality by moving to the "Hierarchy left/right/parent" approach.

Isn't this something we can deal with by either using resources that wrap HashSet (i.e. Root(HashSet<Entity>) and Leaves(HashSet<Entity>)) or marker ZSTs?

What if we have both the HierarchicalRelations component for general hierarchy traversal and IsParent and IsChild markers for cheap root-finding? AFAIK there's nothing Parent and Children do better except iterate the children faster (edit: Changed<Children> signaling could be emulated with Changed<IsParent>).

I'd vote against splitting HierarchicalRelations into separate components (Transform all over again).

[james7132]

One more note: edited the description to include the previous attempt to split the hierarchy from bevy_transform. Not sure if it's doable given these new proposals.

[maniwani]

The way I interpreted #2789 was that the transform systems are too special since they involve two components (Transform and GlobalTransform). We could add a bevy_hierarchy crate for general hierarchies and have bevy_transform stay the same.

I did like the suggestion in there to parameterize Parent and Children into Parent<T> and Children<T> since it does seem like Parent and Children get (mis)used for things that aren't transforms. Same could be applied here.

#[derive(Component)]
pub struct Hierarchy<T> {
  parent: Option<Entity>,
  first_child: Option<Entity>, // should there be a `last_child` field as well?
  prev_sibling: Option<Entity>,
  next_sibling: Option<Entity>,
  _phantom: PhantomData<T>,
}

#[derive(Component)]
pub struct IsParent<T>(PhantomData<T>);

#[derive(Component)]
pub struct IsChild<T>(PhantomData<T>);

[james7132]

The way I interpreted #2789 was that the transform systems are too special since they involve two components (Transform and GlobalTransform). We could add a bevy_hierarchy crate for general hierarchies and have bevy_transform stay the same.

Arguably, the same parenting structure for transforms should be used for the others, since it's the logical expectation here. Not too keen on the idea of multiple overlapping and conflicting hierarchies, particularly when it comes to showing it to users in an editor. We could split it out so that the hierarchy exists separately from a "f32-based Transform system operating in Euclidean space" that bevy_transform currently provides. It would allow others to implement their own transform systems like a f64 backed one, a fixed point transform system, a UI-focused rect-based transform system, or internal efforts for a dedicated 2D one too, but also leverage the parent-sibling-child relationships that seem endemic to all of them.

[maniwani]

Arguably, the same parenting structure for transforms should be used for the others, since it's the logical expectation here.

Honestly, I would parameterize the types "just for the heck of it" since it would help clarify how the components are used. That way, coupling other stuff to the transform hierarchy becomes an intentional choice, instead of users just accidentally using the same components not knowing they're for transforms (bike-shedding, but renaming the types to something like IsParentTransform and IsChildTransform is also an option).

And there are clearly hierarchies people want to express that have nothing to do with transforms.

[alice-i-cecile]

Arguably, the same parenting structure for transforms should be used for the others, since it's the logical expectation here

This was @cart's take: we should try to have a single hierarchy that we use for everything (if feasible).

I'm not sure I personally agree, but I'm willing to explore the direction the design takes. However, I think it's critical to support the inheritance of other properties (hopefully even user-defined properties), and to be able to control what is and isn't inherited (translation? scale? visibility?) at an entity-level.

[james7132]

I think I would rather just provide the tools for managing, traversing, and querying the hierarchy. Operations like dirtying, propagation, and inheritance may be too use case specific to make generic systems for.

[maniwani]

Getting mixed signals here. Is this issue about hierarchies in general or specifically the transform hierarchy (since you mentioned animation, visibility, and working in an editor)?

A tree of linked nodes would be useful in general (in the same way ECS relations would be), but I see no reason to discuss splitting bevy_transform here if we're only going to talk about the transform hierarchy and properties that have to inherit from it.

Anyway, I was just saying that people misuse Parent and Children for non-transform-related things, so we should do something to clarify (edit: when) components are coupled to the transform hierarchy.

[alice-i-cecile]

Anyway, I was just saying that people misuse Parent and Children for non-transform-related things, so we should do something to clarify that all these components are coupled to the transform hierarchy.

Agreed: we should either do this, or allow people to opt-out of this coupling.

[cart]

Not fully caught up yet: but I'd like to first state that hierarchy is already decoupled from Transforms. Transforms just choose to use it for transform propagation. The only real coupling is "the crate these things live in". Opting out does seem like a reasonable feature request, but I'd want real motivating use cases before adding that complexity.

I also agree that how Transforms relate to the "generic hierarchy" should be a separate conversation.

[alice-i-cecile]

The only real coupling is "the crate these things live in"

@cart are you okay with me redoing #2789 and splitting the crates apart? Regardless of the rest of the details, I think this is a necessary split and will seriously reduce user and developer confusion about the intended design.

[james7132]

Whipped up a summary of the discussions here as an RFC: bevyengine/rfcs/pull/53. Please take a look!

[cart]

@cart are you okay with me redoing #2789 and splitting the crates apart? Regardless of the rest of the details, I think this is a necessary split and will seriously reduce user and developer confusion about the intended design.

Yeah I'm cool with this. Thanks for checking.

[Shatur]

What I found inconvenient about the current system is that when I store a scene, I have to store Parent and Children in order to restore the hierarchy later. And the same for replication over the network.