Hierarchy optimized systems and storage
- Dominant language
- Rust
- Stars
- 48.2k
- Forks
- 4.8k
- Avg merge
- 3d 22h
- Merged PRs (30d)
- 161
Description
## 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: #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.
- #3329
- #3340
- #2277
Other issues brought up about the hierarchy:
- #2758
- #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.
```rust
#[derive(Component)]
pub struct HierarchicalRelations {
first_child: Option,
prev_sibling: Option,
next_sibling: Option,
parent: Option,
}
```
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::iter_all_in_descendants` or `HierarchyQuery::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` 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 , 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?
Contributor guide
Assessment
This issue has not been assessed yet.