Send only what each player can see

For Rust developers whose plaza world is bigger than one player's screen and who want to know what each piece of interest management saves

You will build a yard of 2,000 crates with three players walking through it. First a spatial grid cuts each player's frame down to the crates within view. Then the view is streamed as deltas against what each client has acknowledged, with a mirror on the client that checks it still agrees with the server. Then packets are dropped to show why the acknowledged baseline matters. Last, an aggregate tree gives each player a coarse picture of the rest of the world. Every step prints the bytes it costs.

Before you start

You need Rust with Cargo. plaza comes from crates.io:

plaza = "0"

Set up the project#

Start a new binary crate.

cargo new crateyard
cd crateyard

Add the two utility crates. plaza_server_utils holds the server half: the spatial grid, the delta baseline and the aggregate tree. plaza_client_utils holds the client half, the delta mirror, plus the slot keys and digests both halves share. Your [dependencies] section should look like this:

Cargo.toml

[dependencies]
plaza_server_utils = "0"
plaza_client_utils = "0"

Neither crate needs an async runtime. Everything in this tutorial is plain data structures driven from a loop, so the server and the three clients run side by side in one function. In a plaza app the server half runs in your StateLogic's TimeStep arm and each packet travels as one of your ops. The crates are scattered with a fixed seed and the players walk fixed paths, so every run prints the same numbers.

Send each player only what is near it#

Relevance means telling each client about the entities near it and nothing else. SpatialGrid buckets entity ids into square cells. query_radius returns every id in the cells that overlap a square around the viewer. That is a superset of the circle, so an exact distance test afterwards drops the extras. A cell about a third of the view radius wide is what plaza's examples use.

The crates never move, so the grid is filled once. A world whose entities move clears and refills it every tick, which costs less than tracking which cell each entity left.

Replace src/main.rs with this:

src/main.rs

use std::f32::consts::TAU;

use plaza_server_utils::relevance::{GridQuantizer, SpatialGrid};

const WORLD: f32 = 1000.0;
const CRATES: usize = 2000;
const PLAYERS: usize = 3;
const VIEW: f32 = 100.0;
const CELL: f32 = 32.0;
const TICKS: u64 = 200;
const ENTRY_BYTES: usize = 16;
const SEED: u64 = 0xc0ffee;

#[derive(Clone, Copy, Debug)]
struct Crate {
    x: f32,
    y: f32,
}

fn scatter(count: usize, mut seed: u64) -> Vec<Crate> {
    let mut next = move || {
        seed ^= seed << 13;
        seed ^= seed >> 7;
        seed ^= seed << 17;
        (seed % 1_000_000) as f32 / 1_000_000.0 * WORLD
    };
    (0..count)
        .map(|_| Crate {
            x: next(),
            y: next(),
        })
        .collect()
}

fn player_at(player: usize, tick: u64) -> (f32, f32) {
    let angle = tick as f32 * 0.01 + player as f32 * TAU / PLAYERS as f32;
    (500.0 + 300.0 * angle.cos(), 500.0 + 300.0 * angle.sin())
}

fn main() {
    let crates = scatter(CRATES, SEED);
    let mut grid = SpatialGrid::new(GridQuantizer::new((0.0, 0.0), CELL));
    for (index, c) in crates.iter().enumerate() {
        grid.insert(index as u32, c.x, c.y);
    }

    let mut candidates = Vec::new();
    for player in 0..PLAYERS {
        let (mut examined, mut visible) = (0, 0);
        for tick in 0..TICKS {
            let (px, py) = player_at(player, tick);
            candidates.clear();
            grid.query_radius(px, py, VIEW, &mut candidates);
            examined += candidates.len();
            visible += candidates
                .iter()
                .map(|index| crates[*index as usize])
                .filter(|c| (c.x - px).hypot(c.y - py) <= VIEW)
                .count();
        }
        let ticks = TICKS as usize;
        println!(
            "player {player}: grid returned {} crates a tick, {} in view, {} bytes a tick against {} for the whole world",
            examined / ticks,
            visible / ticks,
            visible * ENTRY_BYTES / ticks,
            CRATES * ENTRY_BYTES
        );
    }
}

Each entry costs 16 bytes in this tutorial's accounting: an 8-byte key and two 4-byte coordinates. The players walk a circle of radius 300 around the middle of the yard, a third of a turn apart, for 200 ticks.

Run it:

$ cargo run
player 0: grid returned 158 crates a tick, 61 in view, 990 bytes a tick against 32000 for the whole world
player 1: grid returned 169 crates a tick, 63 in view, 1021 bytes a tick against 32000 for the whole world
player 2: grid returned 158 crates a tick, 62 in view, 1003 bytes a tick against 32000 for the whole world

The grid hands back about 160 candidates a tick and the distance test keeps about 62 of them. Sending only those costs around 1,000 bytes a tick instead of 32,000 for the whole yard.

Stream the view as deltas#

Most of a player's view is the same from one tick to the next. Sending only what entered and what left is far cheaper, but it is only correct when the client really holds what the server thinks it holds. If the server diffs against what it last sent, one lost packet leaves the client short for good, because nothing ever mentions those crates again.

DeltaBaseline diffs against what the client has acknowledged instead. Keep one per client. Each tick you give plan the set of keys the client should hold now and a sequence number. It returns a DeltaPlan: the keys that entered, the keys that left and full_baseline when the client must clear its copy first. The client applies the packet to a DeltaMirror, which tracks which sequence numbers arrived. It sends back an acknowledgement and the digest of what it holds. observe_ack takes those and moves the server's baseline forward.

The keys are SlotKeys from a SlotAllocator, encoded as a u64 of index and generation. The server and the client fold the same encoded keys into a SetDigest, so a digest from one end means the same set at the other. Each packet carries the digest of the set the client should hold after applying it. settle compares the mirror against it and counts a mismatch.

Replace src/main.rs with the full program:

src/main.rs

use std::collections::BTreeSet;
use std::f32::consts::TAU;

use plaza_client_utils::{DeltaMirror, SetDigest, SlotAllocator, SlotKey};
use plaza_server_utils::DeltaBaseline;
use plaza_server_utils::relevance::{GridQuantizer, SpatialGrid};

const WORLD: f32 = 1000.0;
const CRATES: usize = 2000;
const PLAYERS: usize = 3;
const VIEW: f32 = 100.0;
const CELL: f32 = 32.0;
const TICKS: u64 = 200;
const HISTORY: usize = 32;
const ENTRY_BYTES: usize = 16;
const LEFT_BYTES: usize = 8;
const HEADER_BYTES: usize = 25;
const SEED: u64 = 0xc0ffee;

#[derive(Clone, Copy, Debug)]
struct Crate {
    x: f32,
    y: f32,
}

fn scatter(count: usize, mut seed: u64) -> Vec<Crate> {
    let mut next = move || {
        seed ^= seed << 13;
        seed ^= seed >> 7;
        seed ^= seed << 17;
        (seed % 1_000_000) as f32 / 1_000_000.0 * WORLD
    };
    (0..count)
        .map(|_| Crate {
            x: next(),
            y: next(),
        })
        .collect()
}

fn player_at(player: usize, tick: u64) -> (f32, f32) {
    let angle = tick as f32 * 0.01 + player as f32 * TAU / PLAYERS as f32;
    (500.0 + 300.0 * angle.cos(), 500.0 + 300.0 * angle.sin())
}

struct World {
    crates: Vec<Crate>,
    keys: Vec<SlotKey>,
    grid: SpatialGrid<u32>,
}

impl World {
    fn new() -> Self {
        let crates = scatter(CRATES, SEED);
        let mut slots = SlotAllocator::with_capacity(CRATES);
        let keys = crates.iter().map(|_| slots.alloc()).collect();
        let mut grid = SpatialGrid::new(GridQuantizer::new((0.0, 0.0), CELL));
        for (index, c) in crates.iter().enumerate() {
            grid.insert(index as u32, c.x, c.y);
        }
        World { crates, keys, grid }
    }

    fn visible(&self, (px, py): (f32, f32), candidates: &mut Vec<u32>) -> BTreeSet<u64> {
        candidates.clear();
        self.grid.query_radius(px, py, VIEW, candidates);
        candidates
            .iter()
            .map(|index| *index as usize)
            .filter(|index| {
                let c = self.crates[*index];
                (c.x - px).hypot(c.y - py) <= VIEW
            })
            .map(|index| self.keys[index].encode())
            .collect()
    }
}

struct Packet {
    seq: u64,
    full_baseline: bool,
    entered: Vec<(u64, Crate)>,
    left: Vec<u64>,
    digest: u64,
}

impl Packet {
    fn bytes(&self) -> usize {
        HEADER_BYTES + self.entered.len() * ENTRY_BYTES + self.left.len() * LEFT_BYTES
    }
}

fn build(world: &World, baseline: &mut DeltaBaseline, current: &BTreeSet<u64>, seq: u64) -> Packet {
    let plan = baseline.plan(current, seq);
    Packet {
        seq,
        full_baseline: plan.full_baseline,
        entered: plan
            .entered
            .iter()
            .map(|key| (*key, world.crates[SlotKey::decode(*key).index as usize]))
            .collect(),
        left: plan.left,
        digest: SetDigest::from_keys(current.iter().copied()).digest(),
    }
}

fn apply(mirror: &mut DeltaMirror<Crate>, packet: &Packet) {
    mirror.begin(packet.seq, packet.full_baseline);
    for (key, c) in &packet.entered {
        mirror.insert(SlotKey::decode(*key), *c);
    }
    for key in &packet.left {
        mirror.remove(SlotKey::decode(*key));
    }
    mirror.settle(packet.digest);
}

fn main() {
    let world = World::new();
    let mut candidates = Vec::new();

    for player in 0..PLAYERS {
        let mut baseline = DeltaBaseline::new(HISTORY);
        let mut mirror: DeltaMirror<Crate> = DeltaMirror::new();
        let (mut relevance_bytes, mut delta_bytes) = (0, 0);
        let mut current = BTreeSet::new();

        for tick in 0..TICKS {
            current = world.visible(player_at(player, tick), &mut candidates);
            relevance_bytes += current.len() * ENTRY_BYTES;

            let packet = build(&world, &mut baseline, &current, tick + 1);
            delta_bytes += packet.bytes();
            apply(&mut mirror, &packet);

            if let Some((newest, mask)) = mirror.acks().encode() {
                baseline.observe_ack(newest, mask, mirror.digest());
            }
        }

        let gap = mirror.divergence_from(current.iter().copied());
        println!(
            "player {player}: relevance {} bytes a tick, deltas {} bytes a tick, {} full baselines, {} digest mismatches, mirror off by {}",
            relevance_bytes / TICKS as usize,
            delta_bytes / TICKS as usize,
            baseline.full_rebuilds(),
            mirror.divergences(),
            gap.missing.len() + gap.extra.len()
        );
    }
}

World::visible is the query from the last step, returning encoded keys in a BTreeSet, which is what plan takes. build turns the plan into a packet by looking up each entering crate. apply is the whole client side: begin opens the packet, the entries go in, the departures come out and settle checks the result. The acknowledgement goes back the same tick here. On a real link it arrives a round trip later and the server keeps planning against the last one it has. A delta packet has a 25-byte header in this accounting (sequence, baseline sequence, digest and a flag) and a departure costs 8 bytes.

Run it:

$ cargo run
player 0: relevance 990 bytes a tick, deltas 57 bytes a tick, 1 full baselines, 0 digest mismatches, mirror off by 0
player 1: relevance 1021 bytes a tick, deltas 58 bytes a tick, 1 full baselines, 0 digest mismatches, mirror off by 0
player 2: relevance 1003 bytes a tick, deltas 58 bytes a tick, 1 full baselines, 0 digest mismatches, mirror off by 0

Deltas bring each player down to under 60 bytes a tick. The one full baseline per player is the first packet: before the first acknowledgement the server cannot know what the client holds, so it sends the whole view. mirror off by compares each mirror with the server's own set at the end using divergence_from, which names the keys that are missing or extra. Both checks read zero.

Lose packets and recover#

A real link loses packets. This step drops one packet in ten for each player and runs the stream twice. RecoveryPolicy::Naive diffs against what was last sent and RecoveryPolicy::AckRecovery, the default, diffs against what was acknowledged. The acknowledgements still get through, so the server learns which packets arrived.

Add RecoveryPolicy to the plaza_server_utils import, then add the loss rule:

src/main.rs

fn lost(player: usize, seq: u64) -> bool {
    (seq + player as u64) % 10 == 0
}

Replace the body of main with this:

src/main.rs

let world = World::new();
let mut candidates = Vec::new();

for policy in [RecoveryPolicy::Naive, RecoveryPolicy::AckRecovery] {
    println!("{policy:?}");
    for player in 0..PLAYERS {
        let mut baseline = DeltaBaseline::new(HISTORY).with_policy(policy);
        let mut mirror: DeltaMirror<Crate> = DeltaMirror::new();
        let mut delta_bytes = 0;
        let mut should_hold = BTreeSet::new();

        for tick in 0..TICKS {
            let current = world.visible(player_at(player, tick), &mut candidates);
            let packet = build(&world, &mut baseline, &current, tick + 1);
            delta_bytes += packet.bytes();
            if !lost(player, packet.seq) {
                apply(&mut mirror, &packet);
                should_hold = current;
            }

            if let Some((newest, mask)) = mirror.acks().encode() {
                baseline.observe_ack(newest, mask, mirror.digest());
            }
        }

        let gap = mirror.divergence_from(should_hold.iter().copied());
        println!(
            "  player {player}: {} bytes a tick, {} packets lost, {} full baselines, {} digest mismatches, mirror missing {} extra {}",
            delta_bytes / TICKS as usize,
            mirror.frames_lost(),
            baseline.full_rebuilds(),
            mirror.divergences(),
            gap.missing.len(),
            gap.extra.len()
        );
    }
}

should_hold is the view as of the last packet that arrived, which is what the mirror ought to match.

Run it:

$ cargo run
Naive
  player 0: 57 bytes a tick, 19 packets lost, 1 full baselines, 171 digest mismatches, mirror missing 6 extra 23
  player 1: 58 bytes a tick, 20 packets lost, 1 full baselines, 172 digest mismatches, mirror missing 9 extra 19
  player 2: 58 bytes a tick, 20 packets lost, 1 full baselines, 173 digest mismatches, mirror missing 4 extra 18
AckRecovery
  player 0: 426 bytes a tick, 19 packets lost, 5 full baselines, 0 digest mismatches, mirror missing 0 extra 0
  player 1: 451 bytes a tick, 20 packets lost, 5 full baselines, 0 digest mismatches, mirror missing 0 extra 0
  player 2: 436 bytes a tick, 20 packets lost, 6 full baselines, 0 digest mismatches, mirror missing 0 extra 0

The naive stream stays at about 58 bytes a tick and is wrong. Every lost packet takes its entries and departures with it, so each mirror ends up missing crates it should show and holding crates that walked out of view long ago. The digest disagrees on almost every packet after the first loss and nothing in the stream can repair it.

The acknowledged stream ends with every mirror correct and no digest mismatches. Its baseline is the newest contiguous acknowledgement. After a loss the server diffs against the last state before the gap until that state ages out of the HISTORY window of 32 sent states. The next plan is then a full baseline, which is where the extra full baselines in the output come from. At this loss rate the stream averages about 440 bytes a tick.

full_rebuilds and frames_lost are worth putting on a debug panel. Here about 20 lost packets per player led to 5 or 6 full baselines, because one rebuild clears every gap inside the window it replaces.

Summarise the rest of the world#

Relevance is all or nothing: a crate outside the view does not exist for that client. That is fine for things a client only draws. It is wrong for things a client computes with, such as a minimap of where the crowds are or a force that adds up over everything. AggregateTree keeps those distant crates at lower resolution. It replaces a distant group with one stand-in at its weighted centroid and keeps near crates exact.

Add AggregateTree and WeightedPoint to the plaza_server_utils import and const SUMMARY_BYTES: usize = 12; beside the other sizes. Then add this function:

src/main.rs

fn whole_world_summary(world: &World, (px, py): (f32, f32)) {
    let points: Vec<WeightedPoint> = world
        .crates
        .iter()
        .map(|c| WeightedPoint::new(c.x, c.y, 1.0))
        .collect();
    let tree = AggregateTree::build_in(&points, (WORLD / 2.0, WORLD / 2.0), WORLD, 10);
    let mut out = Vec::new();
    for theta in [0.0, 0.5, 1.0] {
        tree.summarize(px, py, theta, &mut out);
        let groups = out.iter().filter(|s| s.count > 1).count();
        let crates: u32 = out.iter().map(|s| s.count).sum();
        println!(
            "  theta {theta}: {crates} crates as {} entries, {groups} of them stand-ins for a group, {} bytes",
            out.len(),
            out.len() * SUMMARY_BYTES
        );
    }
}

Call it at the end of main:

src/main.rs

println!("whole world from player 0");
whole_world_summary(&world, player_at(0, 0));

The weight of each crate is 1.0, so a stand-in's weight is the number of crates it covers. build_in fixes the root cell to the yard rather than to the crates' current extent, which keeps the clusters stable when the tree is rebuilt every tick. summarize walks the tree from the viewer and accepts a whole cell when its width divided by its distance is below theta. A summary entry costs 12 bytes here: two coordinates and a weight.

Run it:

$ cargo run
Naive
  player 0: 57 bytes a tick, 19 packets lost, 1 full baselines, 171 digest mismatches, mirror missing 6 extra 23
  player 1: 58 bytes a tick, 20 packets lost, 1 full baselines, 172 digest mismatches, mirror missing 9 extra 19
  player 2: 58 bytes a tick, 20 packets lost, 1 full baselines, 173 digest mismatches, mirror missing 4 extra 18
AckRecovery
  player 0: 426 bytes a tick, 19 packets lost, 5 full baselines, 0 digest mismatches, mirror missing 0 extra 0
  player 1: 451 bytes a tick, 20 packets lost, 5 full baselines, 0 digest mismatches, mirror missing 0 extra 0
  player 2: 436 bytes a tick, 20 packets lost, 6 full baselines, 0 digest mismatches, mirror missing 0 extra 0
whole world from player 0
  theta 0: 2000 crates as 1996 entries, 4 of them stand-ins for a group, 23952 bytes
  theta 0.5: 2000 crates as 122 entries, 93 of them stand-ins for a group, 1464 bytes
  theta 1: 2000 crates as 38 entries, 36 of them stand-ins for a group, 456 bytes

theta 0 accepts no cell, so it is aggregation switched off through the same code path. The four stand-ins there are crates that share a leaf at the tree's maximum depth of 10. At 0.5 the whole yard fits in 122 entries and at 1.0 in 38. How coarse you can go depends on what the client does with the entries. A drawing tolerates more than a simulation. Past about 1.0 the walk starts accepting cells the viewer is standing close to.

Where to go next#

The crates here never move, so the delta stream is the whole story. When entities move, the set membership still travels as deltas and the positions of the entities in view travel beside it. PriorityAccumulator fits those updates into a byte budget without starving anyone, RestDetector skips what has stopped moving and TierBoundary keeps an entity on the edge of view from flickering in and out. Told sends only changed values on a reliable stream where acknowledgements are not needed. For a world with known bounds, CellSpace and DenseGrid replace the hashed grid with a flat table. PlayoutBuffer on the client and DeltaBaseline::with_flow on the server handle a tab that stops reading and comes back.

Chapter 11 of the plaza guide, Keeping the pipe small, covers relevance, deltas, aggregation and priority with numbers from the examples. The plaza_server_utils usage guide and the plaza_client_utils usage guide on GitHub cover both halves of the stream.

The full API references are on docs.rs: plaza_server_utils and plaza_client_utils.