Entity Indices

[cart]

I've been thinking a lot about "entity identities/indices" lately as there are a number of scenarios that are "suboptimal" right now:

1. More and more things are Entities these days (Windows just made the switch and in the near future we might do this for Assets). In both of those cases, we have a need for statically defined references to entities:
   • Windows: We have a "primary" window that might be created at startup. We need to be able to default to the primary window when spawning Cameras. Cameras must have default "constructable without inputs" impls for a variety of reasons (ergonomics, scenes, etc). Our currently solution is to use WindowRef::Primary and WindowRef::Entity(Entity), but this requires manually resolving the Primary window entity, which is cumbersome (this came up recently):

      fn system(primary: Query<Entity, With<PrimaryWindow>>, windows: Query<&Window>) {
          let entity = match some_window_ref {
              WindowRef::Primary => primary.single(),
              WindowRef::Entity(entity) => entity,
          };
          let window = windows.get(entity).unwrap();
      }

   • Assets: Assets must be able to have a "default handle" reference that we can use in Component Bundles (as the default value ... ex: a "default material", "default texture", "default mesh", etc). Currently this works because Assets are not entities and we have a separate UUID space. If we want assets to be entities, we need a solution to this problem. We could use a "WindowRef-style approach, but that would make handles cumbersome to use. And even without it, we still have a slight ergonomics issue when getting Asset entities using a Handle value: meshes.get(handle.entity()). Ideally we could just call meshes.get(&handle).
2. Some scenarios (such as networking) call for "stable" entity ids. Currently we encourage people to define custom NetworkId components and maintain a NetworkId -> Entity mapping, but looking up an entity based on its NetworkId is cumbersome because you first must look up the mapping resource, then feed the network id into the mapping resource to get the entity, then feed the final entity into your query.

Here is a rough idea for "entity indices", which feels like a reasonable solve for this problem:

First, we define an EntityIndex trait:

trait EntityIndex {
    type Param: ReadOnlySystemParam;
    fn entity_for_index(self, param: <Self::Param>::Item) -> Option<Entity>;
}

This reads arbitrary data from the ECS and uses it to map the given type's value to an Entity. It returns an option to allow for clean error handling.

We can implement EntityIndex for any of the types mentioned above.

WindowRef:

enum WindowRef {
    Primary,
    Entity(Entity),
}

impl EntityIndex for WindowRef {
    type Param = Query<Entity, With<PrimaryWindow>>;
    fn entity_for_index(self, primary: <Self::Param>::Item) -> Option<Entity> {
        match self {
            Primary => primary.get_single().ok(),
            Entity(entity) => entity
        } 
    }
}

Handle:

#[derive(Component)]
pub enum Handle<T> {   
    Default,
    Entity(StrongAssetEntityHandle<T>),
}

#[derive(Resource)]
pub struct DefaultAsset<T>(Entity);

impl<T> EntityIndex for Handle<T> {
    type Param = Res<DefaultAsset<T>>;
    fn entity_for_index(self, default_asset: <Self::Param>::Item) -> Option<Entity> {
        match self {
            Default => default_asset.0,
            Entity(strong_handle) => strong_handle.entity()
        } 
    }
}

NetworkId:

#[derive(Component)]
pub struct NetworkId(Uuid);

#[derive(Component)]
pub struct NetworkIds {
    ids: HashMap<Uuid, Entity>,
}

impl EntityIndex for NetworkId {
    type Param = Res<NetworkIds>;
    fn entity_for_index(self, network_ids: <Self::Param>::Item) -> Option<Entity> {
        network_ids.0.get(&self.0).copied()
    }
}

Now by hand waving a lot of internal implementation details, we can change query.get() to accept an impl EntityIndex instead of an Entity:

fn some_system(material_handles: Query<&Handle<Material>>, materials: Query<&Asset<Material>>) {
    let default_material = materials.get(&Handle::<Material>::Default);
    for handle in &material_handles {
        materials.get(handle);
    }
}

Note that Entity can trivially implement EntityIndex so the current "direct entity" query usage will continue to work.

Savvy ECS people will probably notice a problem with the code above though: the EntityIndex impl for Handle<Material> references Res<DefaultAsset<Material>>. Query<&Asset<Material>> does not reference that! Our system doesn't explicitly access it at all!

To resolve this problem, we add some new Component metadata:

#[derive(Component)]
#[component(indexed_by = "Handle<T>")]
pub struct Asset<T> {
    value: T,
    /* other asset stuff here */
}

This (statically) associates the Res<DefaultAsset<T>> param access with the Asset<T> Component. Any read access to that component implies access to the EntityIndex param. Conflicting access would be an error.

If you have a direct mutable World reference, you are free to use any EntityIndex impl at any time.

Now that the schedule is aware of this implied access, Query is free to do param lookups!

I've hand waved away a lot of implementation details:

• where is the index param information stored (on the query?)
• how is it kept up to date
• how is it accessed (i strongly suspect we'd need some sort of dynamic EntityIndexTypeId->SystemParamState map, which would incur per-entity-lookup overhead?)

This is also still a rough idea and its very possible I missed something. But I think in general this impl is reasonably scoped and opens the doors to a lot of new entity reference patterns. Worth considering?

Its also worth calling out that there are superficial similarities to relations. But I think entity indices have a very different purpose. They don't have the same functionality, their apis would look very different, and the perf characteristics are different. But its worth discussing overlap!

[alice-i-cecile]

Trying to parse this proposal: my initial thought went to #4513 and bevy_mod_index. Is it correct to say that this is an API that would implement these ideas?

I'm not sold on the complexity here vs the system param as in bevy_mod_index: this definitely seems like more indirection.

[cart]

I'd say its not really the #4513 problem space as it isn't really about "looking up entities by the values of their components". Its more about converting arbitrary data types to entity references based on ECS state. They do overlap slightly, but the methodology is very different. It doesn't require being particularly "smart" in the ECS. The mapping logic is fully externalized. We don't maintain any internal indices.

It is definitely in the vein of bevy_mod_index, but it intentionally takes the step further to abstract out the mapping logic when actually using indices. This whole proposal is motivated by UX. The act of doing the mapping lookup yourself is "too much work".

[maniwani]

I was thinking about where this fits in.

We already have something close to an entity index—Components—which maps TypeId values to ComponentId values. I say it's similar since I'm plotting to replace ComponentId with Entity. (We also map ArchetypeDef values to ArchetypeId values and Bundle TypeId values to BundleId values).

So to me your outline can be read like an admission that turning everything into entities is a good idea you're saying "make X be entities" just for arbitrary data values (instead of component and resource types).

For values, I propose a type-elided index like #7760 (or #7762). You can convert arbitrary values into unique keys and insert (UniqueValue, Entity) pairs in a map stored on World.

struct UniqueValue {
    type_id: TypeId,
    value_hash: u64,
}

impl UniqueValue {
    pub fn new<T: DynHash>(value: T) -> UniqueValue {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        value.dyn_hash(&mut hasher);
        let value_hash = hasher.finish();

        UniqueValue {
            type_id: std::any::TypeId::of::<T>(), 
            value_hash,
        }
    }
}

Since it's just one map, we can internalize it, no problem. And keeping it up-to-date would be easy to automate with "hooks" on structural changes to World, which will be included in my relations work.

The API could look something like:

world.register_entity(WindowRef::Primary, entity);
world.entity_ref_of(WindowRef::Primary);
world.entity_mut_of(WindowRef::Primary);
world.get_entity_ref_of(WindowRef::Primary);
world.get_entity_mut_of(WindowRef::Primary);
// queries can just wrap these
world.entity_of(WindowRef::Primary);
world.get_entity_of(WindowRef::Primary);

[cart]

So to me your outline can be read like an admission that turning everything into entities is a good idea you're saying "make X be entities" just for arbitrary data values (instead of component and resource types).

I do see the Typeid->ComponentId conceptual overlap. Presumably your proposed value->entity mapping api would look something like world.register_entity(TypeId, entity_of_component) in a World where components are entities?

So far for me this falls into the "yeah we could do it this way, but hashmaps already work quite well for this" category of thing. I'm on board for unifying things, but I want some motivating use cases that extend beyond "we can and its neat". A HashMap<TypeId, ComponentId> is super easy to understand and will already outperform a global hashmap with a key of (TypeId::of:<TypeId>(), hash_of(TypeId::of::<SomeComponent>()). This is probably just a lack of imagination on my part, but I can't see the use cases this unlocks (on its own ... components as entities generally does make some things nicer).

The API could look something like:

I don't hate the idea of internalizing this, but the WindowRef::Entity(entity) representation is notably missing (and we don't want to register each of those manually). So theres asymmetry when it comes to looking up one value vs the other.

This system also forces a specific lookup algorithm. With id schemes, some might be able to get away with array lookups, others will want hash maps (ex UUIDS), others are pass through (ex: WindowRef::Entity(Entity)). (edit: also some might just be direct reads from resources or components)

This also fully decouples lookup logic from actual ECS state. With the "internal value registration" approach WindowRef::Primary would need to be constantly synced with whatever Window component currently has the PrimaryWindow component. Why not just look that up from the ECS directly? A call to single() on a cached QueryState<Entity, With<PrimaryWindow>> will outperform the hashmap lookup. (although there is a good chance we'll need to do a Typeid hashmap lookup to find that cached querystate).

And keeping it up-to-date would be easy to automate with "hooks" on structural changes to World

This could work, but it requires (1) actually defining the hook-sync logic (more complexity) and (2) knowing where that sync point is in the schedule and working around it. Why do this at all when we can just read the actual "up to date" values directly from the ECS?

value_hash: u64,

We should probably be avoiding the "pre-hash and store to determine equality with future type" approach as much as possible (we do use it in a number of places but im trying to walk that back ... ex in the asset system rework im trying very hard not to do "asset path hash for cheap equality" . Theres a non-zero chance of collision here and apparently for arbitrary inputs + non-cryptographic hashes we shouldn't rely on this. Ideally we have the ability to fall back to actual value equality checks on collision.

https://users.rust-lang.org/t/using-ahash-non-cryptographic-hash-for-equality-comparison-considered-harmful/71701

[maniwani]

I do see the TypeId->ComponentId conceptual overlap.

A HashMap<TypeId, ComponentId> is super easy to understand and will already outperform a global hashmap with a key of (TypeId::of:<TypeId>(), hash_of(TypeId::of::<SomeComponent>()).

The Map<UniqueValue, Entity> and API I'm proposing is a separate thing from Components. I just wanted to point out how this is a form of 👻. I wasn't suggesting a new API for components, really just replacing ComponentId with Entity (so Components would have a Map<TypeId, Entity>), with some other dense index just for constructing the Access bitsets.

Why not just look that up from the ECS directly?

Is this not a discussion about mapping arbitrary data values to Entity values? If anything, I should be asking you this.

This system also forces a specific lookup algorithm.

If you don't already know the Entity, a map lookup is the most broadly applicable index we could provide internally.
You said:

This whole proposal is motivated by UX. The act of doing the mapping lookup yourself is "too much work".

But then also:

With ID schemes, some might be able to get away with array lookups, others will want hash maps (e.g. UUIDs), others are passthrough.

I think providing this internally is better UX. I don't want to design an ID scheme or maintain an index. I just want to register mappings with the ECS and have it manage them. Could your proposed API be available side-by-side for users that actually want to put in all that work to optimize?

WindowRef::Primary vs WindowRef::Entity(Entity)

(edit: paragraph) I'm not familiar enough with the context to know why we should place a lot of value on this being symmetrical. If you know the Entity value, you don't need to use the index lookup, right?

This could work, but it (1) requires hook-sync logic (more complexity).

True. However, structural change hooks are required to implement cleanup policies and inheritance for relationships (I realize that probably sounds like complete gibberish rn), which I am working on, so I tried to think of a solution assuming we'll have that capability.

(2) knowing where that sync point is in the schedule and working around it.

Users won't need to think about when it happens. Hooks would be called by the bevy_ecs code that performs structural changes. Any structural changes produced by the hooks themselves would be deferred as commands.

Basically, bevy_window would just register a function like update_index to be run by ComponentInserted and ComponentRemoved hooks when the component ID matches PrimaryWindow, and that's pretty much it.

Why do this at all when we can just read the actual "up to date" values directly from the ECS?

Again, I thought the premise of this discussion is that being able to lookup the Entity for a special value is useful, so I suggested a generic way to map arbitrary values to Entity values. Advantages are that keeping it in sync can be automated (I do admit that requires another feature that doesn't exist yet), it would be available in any context—system, exclusive system, command—and it would mirror a strategy for mapping labels to label IDs. Disadvantages are non-negotiable hash map overhead and the non-zero possibility of hash collisions.

I don't think those disadvantages are deal-breakers. IMO the overhead is fine since indirect lookups shouldn't be the norm.

[maniwani]

Forgot the last part.

Theres a non-zero chance of collision here and apparently for arbitrary inputs + non-cryptographic hashes we shouldn't rely on this.

There's always a non-zero chance of collision, right? There's a brand-new PR to extend TypeId to 128-bits and it only reduces the (already very small) likelihood of collisions. Even UUIDs have a non-zero (but practically infinitesimal) chance of collisions. I don't think you can guarantee zero collisions unless you allocate from some finite reserve (i.e. memory addresses, monotonically increasing counters, etc.), but then you can't repeatedly generate the same key from a given value.

We already use DynHash to tell different labels apart and that just hashes the TypeId and value, so the UniqueValue keys are at least not totally crazy. (edit: Maybe we need to use a fancier key derivation function, but I feel like there's probably a simple method that's fast and still has enough entropy for an extremely low collision probability.)

(edit: And maybe I'm reading the linked discussion incorrectly, but it seems that a hash function being cryptographic or not only says something about its collision resistance to specially crafted adversarial inputs. One poster did suggest that the OP should use universal hashing, but no need for cryptographic guarantees.)

[maniwani]

On the "stable entity IDs" point, it'd be cool if applications could reserve ranges of Entity (each range gets its own freelist basically) and manually allocate entities in those ranges, but IDK if that's compatible with the current recycling mechanism.

Requiring a layer of indirection for user-controlled IDs has always been lacking, and I think it'll seem worse in the future considering any entity relationship functionality we add is almost certainly only going to incorporate Entity identifiers.

[maniwani]

The World only knows about entities. And all talk of indexing and relationships only applies to Entity values, so it'd be better UX if everyone could use our handy-dandy Entity type directly instead of needing to provide their own.

If you could just reserve 1,000 Entity values, i.e. separate them from the pool the World uses for general spawning, then there would be no need for a layer of indirection. Everyone could use Entity.

Entity is like a pointer, so IMO users should be able to allocate entities like they can allocate memory. (edit: Unlike most allocators, we could even allow reserving specific ranges of Entity values).

Namespacing might be cleaner.

I'm not familiar with this. Can you explain?

[iiYese]

I haven't looked into how it works but in flecs users can lookup by entity name world.lookup("foo.bar") and they're just strings. Multiple entities can have the same "name" so long as they're in different parts of a hierarchy. So for the networking example users can generate names and not care about what World is doing.

You can also take "namespacing" more literally and expose a way for users to mask Entity IDs. You could decrease the current ID range and reserve bits for masking or increase the ID range and use the new bits for masking.

[SanderMertens]

That's right, one additional note: lookups by name are equivalent to lookups by type, since in Flecs the type registry and ECS are the same thing. As a result these two functions return the same entity:

flecs::entity e = world.lookup("foo::bar");
flecs::entity e = world.id<foo::bar>(); // faster, since it doesn't need the by name lookup

[maniwani]

Ah, OK. I see now. Sander just explained it to me.

flecs::entity p = world.lookup("assets::prefabs::buildings::Turret");
// or
flecs::entity p = world.id<assets::prefabs::buildings::Turret>();

Each element of the module path (assets, assets::prefabs, assets::prefabs::buildings, assets::prefabs::buildings::Turret) is an entity and they are related by ChildOf relationships. Pretty neat.

---

So for the networking example users can generate names and not care about what World is doing.

Oh, for sure. But since components commonly store Entity values, and relations are probably going to be identified with concatenated pairs of Entity indices, and scenes will store both, it seems like Entity should be as useful as possible.

I think it'd be best if most users never had to translate between Entity and some custom ID. Tracking multiple Entity free-list heads would probably have a performance cost, but reserving random or specific Entity values is possible, and I think it should be allowed.

Users would regardless be able to register any MyCustomId values in the type-elided index I described in the above thread (or using the externalized proposal in the OP), but then it would be the user's choice, totally opt-in.

[1mamute]

This is talked in this article by Sander Mertens (author of flecs):

He starts talking about how ComponentId's in flecs are just EntityIds and then talks about Id partitioning and its uses:

Id Partitioning
32 bits is a lot. I doubt there will ever be a game with 4 billion entities, and while it is good to know that the ECS library provides some headroom, this seems a bit excessive. It turns out we can still make good use of our id space, even if our game doesn’t have millions (or billions) of entities.

In flecs you can partition your id space. Partitioning basically means walling of a part of your ids for a specific purpose. There are a few ways in which this is useful. The first one is component identifiers.

Low Component Identifiers. While it is great to use entity identifiers for components, it can pose some challenges. For example, you can optimize your data structures if you know that you’ll never have more than 64 components, and avoid resorting to expensive(ish) alternatives such as maps. When components are entities however, we can’t make assumptions about the id range of those components, which makes it harder to do such optimizations.

Custom Entity Ranges. Flecs lets you set id ranges which configures the range in which ids are produced:

// Generate entities between 5000 and 6000
world.set_entity_range(5000, 6000);

This is useful in multiplayer games, where you may want to reserve id ranges for different services of your architecture. You may for example reserve ids 1000..5000 for clients, and everything above that (5000..0) for entities from a server. This makes it possible to receive ids from a server that don’t have to be mapped to local ids, saving CPU cycles on the client!