Bevy Scoped Queries & Entities proposal.

[RylanYancey]

I have slowly been building up expertise around ECS for the past few years and contemplating about how I would implement a high-performance sandbox minecraft-like game. However, I run into a major problem.

The Problem

When there are many, many players on a single world, a majority of the checks that occur are between entities that are nowhere near each other. This problem becomes exponentially worse the larger the world and more spread out the players. For example, I have a system where I need to update whether enemies can see the player. This system might look like this:

fn can_enemy_see_player(
    enemies: Query<(&Transform, &mut PlayerTracker), With<Enemy>>,
    players: Query<(&Transform, &Player), ()>,
    world: Res<WorldChunks>,
) {
    for (enemy_transform, tracker) in enemies.iter() {
        for (player_transform, player) in players.iter() {
            if enemy_transform.distance_to(player_transform) < tracker.radius() {
                if world.has_ubroken_sightline(enemy_transform, player_transform) {
                    tracker.set_tracking(player);
                }
            }
        }
    }
}

The problem is that the number of checks is the enemy count times the player count, which is an O(n^2) operation and a major contributor to runtime performance, especially given that a majority of the checks are between enemies and players that are so far away that are too far away to interact with each other.

Minecraft handles this particular check by a combination of infrequently and randomly running visibility checks and basing visibility on whether the player is looking at the enemy, but this can result in strange behaviour where enemies take several seconds to notice a player right next to them, and becomes increasingly apparent the more players exist in a world.

Solution: Scoped Queries

When an entity is spawned, I want to assign it a scope based on its transform. Scope may be defined like so:

trait Scope {}

#[derive(Scope)]
struct Dimensional(u64);

#[derive(Scope)]
struct Regional {
    dimension: u64,
    region: Vec2<i64>,
}

/// Default scope.
#[derive(Scope)]
struct Global;

I could create a scoped entity with commands.

commands.spawn_scoped(
    Regional {
        dimension: 0,
        region: Vec2::new(0, 0),
    }
    (
        // ...components
    )
);

The Bevy ECS could then store the scope in the archetype table.

// Deep in the bevy ecs
pub struct Table {
    // ... other fields

    // a Map of scopes, where the associated
    // vector is a binary sorted Vec with indices
    // of entities that are in the scope. 
    // sorting the indices will help with cache locality
    // when iterating entities of a given scope.
    scopes: IndexMap<impl Scope, Vec<usize>>,
}

To iterate by scope, there could be a trait 'ScopeFilter', which could be used to implement scoped queries.

pub trait ScopeFilter<S: Scope> {
    fn matches(&self, other: &S) -> bool;
}

pub struct RegionInRadius {
    dim: u64,
    position: Vec3<f32>,
    radius: f32,
}

impl ScopeFilter<Regional> for RegionInRadius {
    fn matches(&self, other: &Regional) -> bool {
        // return true if 
        other.is_in_radius(self.dim, self.position, self.radius)
    }
}

Then I could create a system to update the scope based on changed transforms.

// pseudocode
fn update_scope(
    query: Query<Changed<Transform>, Scope<Regional>>,
) {
    for transform in query.iter() {
        let dim = transform.scope().dimension;
        transform.entity().update_scope(Regional::new(dim, transform));
    }
}

With all of this in place, our query can be changed to look like this:

fn can_enemy_see_player(
    // add the scope to the queries to only iterate archetypes with this particular scope.
    enemies: Query<(&Transform, &mut PlayerTracker), (With<Enemy>, Scope<Regional>)>,
    players: Query<(&Transform, &Player), Scope<Regional>>,
    world: Res<WorldChunks>,
) {
    for (enemy_transform, tracker) in enemies.iter() {
        // scopes can be accessed through the component like entity(). 
        let regional_scope_filter = RegionInRadius {
            dim: enemy_transform.scope().dim,
            position: enemy_transform.position(),
            radius: tracker.radius(),
        };

        // iterate over all player entities whose region is inside the provided radius.
        for (player_transform, player) in players.iter_scoped(regional_scope_filter) {
            // we still have to check if the enemy is close enough, 
            // the scoped iter only ballparks it. 
            if enemy_transform.distance_to(player_transform) < tracker.radius() {
                if world.has_ubroken_sightline(enemy_transform, player_transform) {
                    tracker.set_tracking(player);
                }
            }
        }
    }
}

This would drastically reduce the number of checks that have to be done, and allow for many more players, and entities, to exist on a single ECS instance.

[alice-i-cecile]

Generally I think that spatial partitioning strategies like quad trees are the way to go here :) Indexes (#4513) are currently possible, but not as reliable / well-integrated as I'd like. See that issue for more thoughts on how to improve this.

#13464 is also related, as you could use a space filling curve or a similar ordering to speed up checks.