Interest management

Deep dive

How it works

Parts:

• Spatial index — grid or tree of entities, rebuilt or updated per tick.
• Relevancy filter — per client: radius, visibility (PVS, ray tests), always-relevant lists.
• Priority accumulators — per (client, entity), grow each tick the entity is not sent.
• Packet filler — sends highest acc first until the byte budget is spent.

1. Spatial index: entities are bucketed into grid cells each tick (or on move). For dense, uneven worlds use a quadtree/octree or per-zone lists.
2. Relevancy per client: candidates = entities in neighbouring cells within radius R (plus always-relevant: own team, own projectiles, game-state singletons), minus those failing visibility (PVS from the level's BSP/cells, or ray tests for important entities).
3. Enter/leave: entities entering the set are sent with full state ("create"); entities leaving get a "destroy" or are left to time out on the client.
4. Priority: per (client, entity) keep an accumulator. Base priority by type and distance (closer, larger, faster, recently interacted, in view cone → higher). Each tick acc += base × dt.
5. Packet fill: sort candidates by acc (or partial-select the top k), serialize until the budget (e.g. 1200 bytes) is full, reset sent entities' accumulators. Unsent ones keep growing and win later.

 +---+---+---+---+
 |   | e |   |   |     viewer V queries the 3x3 block around its cell;
 +---+---+---+---+     cell size >= R guarantees every entity within R is inside it
 |   | V | e |   |
 +---+---+---+---+
 | e |   |   | x |  <- x is never even looked at
 +---+---+---+---+

Code

use std::collections::HashMap;

#[derive(Clone, Copy)]
pub struct Entity { pub id: u32, pub x: f32, pub y: f32, pub base_priority: f32, pub bytes: usize }

pub struct Grid { cell: f32, cells: HashMap<(i32, i32), Vec<usize>> } // indices into the entity slice

impl Grid {
    pub fn build(ents: &[Entity], cell: f32) -> Self {
        let mut cells: HashMap<(i32, i32), Vec<usize>> = HashMap::new();
        for (i, e) in ents.iter().enumerate() {
            cells.entry(((e.x / cell).floor() as i32, (e.y / cell).floor() as i32)).or_default().push(i);
        }
        Grid { cell, cells }
    }
    /// All entities within `r` of (x, y); requires r <= cell.
    pub fn query(&self, ents: &[Entity], x: f32, y: f32, r: f32, out: &mut Vec<usize>) {
        debug_assert!(r <= self.cell);
        let (cx, cy) = ((x / self.cell).floor() as i32, (y / self.cell).floor() as i32);
        for dx in -1..=1 {
            for dy in -1..=1 {
                if let Some(v) = self.cells.get(&(cx + dx, cy + dy)) {
                    for &i in v {
                        let (ex, ey) = (ents[i].x - x, ents[i].y - y);
                        if ex * ex + ey * ey <= r * r { out.push(i); }
                    }
                }
            }
        }
    }
}

/// Per-client relevancy state.
pub struct ClientView { pub x: f32, pub y: f32, acc: HashMap<u32, f32>, relevant: HashMap<u32, ()> }

impl ClientView {
    pub fn new(x: f32, y: f32) -> Self { ClientView { x, y, acc: HashMap::new(), relevant: HashMap::new() } }

    /// Returns ids to serialize this tick, highest accumulated priority first, within `budget` bytes.
    pub fn select(&mut self, ents: &[Entity], grid: &Grid, r_enter: f32, r_leave: f32,
                  dt: f32, budget: usize) -> Vec<u32> {
        let mut near = Vec::new();
        grid.query(ents, self.x, self.y, r_leave, &mut near);
        let mut cands: Vec<(f32, usize)> = Vec::new();
        let mut still = HashMap::new();
        for i in near {
            let e = &ents[i];
            let d2 = (e.x - self.x).powi(2) + (e.y - self.y).powi(2);
            // Hysteresis: new entities need to come within r_enter; known ones stay until r_leave.
            if d2 > r_enter * r_enter && !self.relevant.contains_key(&e.id) { continue; }
            still.insert(e.id, ());
            let dist_factor = 1.0 / (1.0 + d2.sqrt() / 10.0); // closer = more often
            let a = self.acc.entry(e.id).or_insert(0.0);
            *a += e.base_priority * dist_factor * dt;
            cands.push((*a, i));
        }
        self.acc.retain(|id, _| still.contains_key(id)); // left the area: forget (client destroys it)
        self.relevant = still;
        cands.sort_unstable_by(|a, b| b.0.total_cmp(&a.0));
        let (mut used, mut out) = (0, Vec::new());
        for (_, i) in cands {
            let e = &ents[i];
            if used + e.bytes > budget { continue; } // smaller ones may still fit
            used += e.bytes;
            out.push(e.id);
            self.acc.insert(e.id, 0.0); // sent: start accumulating again
        }
        out
    }
}

#[test]
fn far_entities_are_not_starved() {
    let ents: Vec<Entity> = (0..50)
        .map(|i| Entity { id: i, x: i as f32 * 2.0, y: 0.0, base_priority: 1.0, bytes: 100 })
        .collect();
    let grid = Grid::build(&ents, 120.0);
    let mut view = ClientView::new(0.0, 0.0);
    let mut sent = vec![0; 50];
    for _ in 0..600 {                            // 10 s at 60 Hz, room for 5 of 50 entities per tick
        for id in view.select(&ents, &grid, 100.0, 110.0, 1.0 / 60.0, 500) { sent[id as usize] += 1; }
    }
    assert!(sent[0] > sent[49] && sent[49] > 0, "{sent:?}");
}

Complexity and constants

• Brute force: clients × entities distance checks per tick; 100 × 50 000 = 5M checks, too slow at 30 Hz on one core. Grid: clients × (entities in 9 cells), typically 100s per client.
• Grid rebuild: O(entities) per tick, or incremental updates only when an entity changes cell.
• Priority selection: O(c log c) sort for c candidates, or O(c) with partial selection (select_nth_unstable) when only the top k fit.
• Budget: packet budget ≈ 1200 bytes × send rate; at 30 Hz that is about 290 kbit/s per client upper bound.
• Fortnite-scale: Epic built Unreal's Replication Graph for about 100 players and order of 50 000 replicated actors per server.

Efficiency

Cost: brute force is clients × entities distance checks per tick: 100 × 50 000 = 5M, too slow at 30 Hz on one core. A grid checks clients × entities in 9 cells, typically 100s per client; rebuild is O(entities) per tick. The budget of about 1200 bytes per packet at 30 Hz is 290 kbit/s per client at most. Bound: CPU for filtering, bandwidth for the packet budget.

Levers:

• Uniform grid with cell size ≥ radius — turns O(entities) into O(nearby) per client — uneven or dense worlds use a quadtree.
• Partial selection of the top k (select_nth_unstable) instead of a full sort — O(c) instead of O(c log c) (Rust docs) — when only the top k fit in a packet.
• Compute per-cell lists once and share across clients (Replication Graph spatial nodes, Epic) — avoids per-client scans — many clients in one cell.
• Priority accumulators — guarantees far entities still update (Fiedler) — bandwidth-capped links.
• Hysteresis, enter at R and leave at 1.1-1.2 R — avoids repeated full-state creates — entities on the border.

Naive → standard → state of the art:

• Send everything to everyone · O(clients × entities) bandwidth and checks
• Grid relevancy plus priority accumulators under a byte budget · 100s of candidates per client
• Replication graph with shared per-cell lists plus visibility culling · Fortnite: about 100 players and order of 50 000 replicated actors per server

Implementation notes

• Share work across clients: rebuild the spatial index once per tick, and group clients in the same cell (Replication Graph's spatial grid nodes) so per-cell lists are computed once.
• Update frequencies by class: player characters every tick, distant props every second or two; implement as base priority, not separate timers.
• Visibility: precomputed PVS for static geometry is cheap; per-pair ray tests are costly, so limit them to enemy players near the edge of visibility and test a few points (head, feet). Send enemies slightly before they become visible (predict movement by latency) to avoid pop-in.
• Audio-relevant entities (footsteps, gunfire) need a larger radius than visual ones; add an "audible" relevancy class.
• Clients must handle entities disappearing and reappearing: destroy on leave or keep a grace period, and treat re-entry as a full-state create.

Pitfalls

• Cell size smaller than the query radius: entities near cell borders are missed.
• Border flicker: entities on the radius boundary enter and leave every tick, each time costing a full-state create. Hysteresis fixes it.
• Starvation with pure distance priority: far entities never get a slot. Accumulators guarantee eventual updates.
• Leaking hidden info through other channels: sounds, kill feed, minimap, or "relevancy" itself (an entity appearing tells the client something is there).
• Per-client per-entity state grows as clients × entities; store accumulators only for candidates and drop them on leave.

Variants and alternatives

In production

• Games: Unreal Engine (NetCullDistanceSquared, NetPriority, Replication Graph used by Fortnite), Valve Source (PVS-based transmit), VALORANT (server-side fog of war), Unity Netcode for Entities (ghost relevancy and importance scaling), Gaffer On Games priority accumulators.
• Distributed simulation: HLA's Data Distribution Management filters data exchange by intersecting update and subscription regions; Morse and Zyda study multicast grouping for it.
• Messaging: publish/subscribe systems deliver only events that match a subscription (Eugster et al. survey).
• Anti-cheat: server-side visibility culling removes the positions wallhacks need (Riot, VALORANT).

Implementations

Sources

• Fiedler, State Synchronization (priority accumulator), gafferongames.com, 2015. post
• Epic Games, Replication Graph documentation, Unreal Engine docs. docs
• Riot Games Technology, Demolishing Wallhacks with VALORANT's Fog of War, 2020. post
• Boulanger, Kienzle, Verbrugge, Comparing Interest Management Algorithms for Massively Multiplayer Games, ACM NetGames, 2006. paper
• Morse, Zyda, Multicast grouping for data distribution management, Simulation Practice and Theory, 2002. paper
• Eugster, Felber, Guerraoui, Kermarrec, The many faces of publish/subscribe, ACM Computing Surveys, 2003. paper