proof_engine/netcode/
snapshot.rs

1//! World state snapshots with delta compression and relevancy filtering.
2
3use std::collections::HashMap;
4
5/// Unique identifier for a snapshot in time.
6#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
7pub struct SnapshotId(pub u64);
8
9impl SnapshotId {
10    pub fn next(self) -> Self {
11        SnapshotId(self.0.wrapping_add(1))
12    }
13
14    pub fn distance(self, other: SnapshotId) -> u64 {
15        if self.0 >= other.0 {
16            self.0 - other.0
17        } else {
18            other.0 - self.0
19        }
20    }
21
22    pub fn zero() -> Self {
23        SnapshotId(0)
24    }
25}
26
27/// Strongly-typed entity identifier within the netcode layer.
28#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
29pub struct NetEntityId(pub u32);
30
31/// Individual component data stored as a type-tagged byte buffer.
32/// Components are identified by a numeric type ID for serialization.
33#[derive(Debug, Clone)]
34pub struct ComponentData {
35    pub type_id: u16,
36    pub data: Vec<u8>,
37    pub version: u32,
38}
39
40impl ComponentData {
41    pub fn new(type_id: u16, data: Vec<u8>) -> Self {
42        Self {
43            type_id,
44            data,
45            version: 1,
46        }
47    }
48
49    pub fn with_version(type_id: u16, data: Vec<u8>, version: u32) -> Self {
50        Self {
51            type_id,
52            data,
53            version,
54        }
55    }
56
57    pub fn size(&self) -> usize {
58        self.data.len() + 6 // type_id(2) + version(4)
59    }
60
61    /// Compute a simple FNV-1a hash of the data for change detection.
62    pub fn content_hash(&self) -> u64 {
63        let mut hash: u64 = 0xcbf29ce484222325;
64        for &byte in &self.data {
65            hash ^= byte as u64;
66            hash = hash.wrapping_mul(0x100000001b3);
67        }
68        hash
69    }
70
71    /// Produce a delta between this component and another of the same type.
72    /// Returns None if data is identical.
73    pub fn delta_against(&self, baseline: &ComponentData) -> Option<ComponentDelta> {
74        if self.type_id != baseline.type_id {
75            return Some(ComponentDelta {
76                type_id: self.type_id,
77                kind: DeltaKind::Replaced(self.data.clone()),
78                new_version: self.version,
79            });
80        }
81
82        if self.data == baseline.data {
83            return None;
84        }
85
86        // XOR delta for same-length data
87        if self.data.len() == baseline.data.len() {
88            let mut xor_data = Vec::with_capacity(self.data.len());
89            let mut has_diff = false;
90            for i in 0..self.data.len() {
91                let x = self.data[i] ^ baseline.data[i];
92                if x != 0 {
93                    has_diff = true;
94                }
95                xor_data.push(x);
96            }
97
98            if !has_diff {
99                return None;
100            }
101
102            // Run-length encode the XOR data for compression
103            let rle = rle_encode(&xor_data);
104            if rle.len() < xor_data.len() {
105                return Some(ComponentDelta {
106                    type_id: self.type_id,
107                    kind: DeltaKind::XorRle(rle),
108                    new_version: self.version,
109                });
110            }
111
112            return Some(ComponentDelta {
113                type_id: self.type_id,
114                kind: DeltaKind::XorRaw(xor_data),
115                new_version: self.version,
116            });
117        }
118
119        // Different lengths: full replacement
120        Some(ComponentDelta {
121            type_id: self.type_id,
122            kind: DeltaKind::Replaced(self.data.clone()),
123            new_version: self.version,
124        })
125    }
126
127    /// Apply a delta to produce a new ComponentData.
128    pub fn apply_delta(&self, delta: &ComponentDelta) -> ComponentData {
129        let new_data = match &delta.kind {
130            DeltaKind::Replaced(data) => data.clone(),
131            DeltaKind::XorRaw(xor) => {
132                let mut result = self.data.clone();
133                for i in 0..result.len().min(xor.len()) {
134                    result[i] ^= xor[i];
135                }
136                result
137            }
138            DeltaKind::XorRle(rle) => {
139                let xor = rle_decode(rle, self.data.len());
140                let mut result = self.data.clone();
141                for i in 0..result.len().min(xor.len()) {
142                    result[i] ^= xor[i];
143                }
144                result
145            }
146        };
147        ComponentData {
148            type_id: delta.type_id,
149            data: new_data,
150            version: delta.new_version,
151        }
152    }
153}
154
155/// Run-length encode: pairs of (count, value).
156fn rle_encode(data: &[u8]) -> Vec<u8> {
157    let mut result = Vec::new();
158    if data.is_empty() {
159        return result;
160    }
161    let mut current = data[0];
162    let mut count: u8 = 1;
163    for &byte in &data[1..] {
164        if byte == current && count < 255 {
165            count += 1;
166        } else {
167            result.push(count);
168            result.push(current);
169            current = byte;
170            count = 1;
171        }
172    }
173    result.push(count);
174    result.push(current);
175    result
176}
177
178/// Decode RLE data back to original size.
179fn rle_decode(rle: &[u8], expected_len: usize) -> Vec<u8> {
180    let mut result = Vec::with_capacity(expected_len);
181    let mut i = 0;
182    while i + 1 < rle.len() && result.len() < expected_len {
183        let count = rle[i] as usize;
184        let value = rle[i + 1];
185        for _ in 0..count {
186            if result.len() >= expected_len {
187                break;
188            }
189            result.push(value);
190        }
191        i += 2;
192    }
193    while result.len() < expected_len {
194        result.push(0);
195    }
196    result
197}
198
199/// Snapshot of a single entity's state at a point in time.
200#[derive(Debug, Clone)]
201pub struct EntitySnapshot {
202    pub entity_id: NetEntityId,
203    pub components: Vec<ComponentData>,
204    pub position: [f32; 3],
205    pub rotation: [f32; 4],
206    pub velocity: [f32; 3],
207    pub flags: u32,
208}
209
210impl EntitySnapshot {
211    pub fn new(entity_id: NetEntityId) -> Self {
212        Self {
213            entity_id,
214            components: Vec::new(),
215            position: [0.0; 3],
216            rotation: [0.0, 0.0, 0.0, 1.0],
217            velocity: [0.0; 3],
218            flags: 0,
219        }
220    }
221
222    pub fn with_position(mut self, x: f32, y: f32, z: f32) -> Self {
223        self.position = [x, y, z];
224        self
225    }
226
227    pub fn with_rotation(mut self, x: f32, y: f32, z: f32, w: f32) -> Self {
228        self.rotation = [x, y, z, w];
229        self
230    }
231
232    pub fn with_velocity(mut self, x: f32, y: f32, z: f32) -> Self {
233        self.velocity = [x, y, z];
234        self
235    }
236
237    pub fn add_component(&mut self, component: ComponentData) {
238        // Replace if same type_id exists
239        if let Some(existing) = self.components.iter_mut().find(|c| c.type_id == component.type_id) {
240            *existing = component;
241        } else {
242            self.components.push(component);
243        }
244    }
245
246    pub fn get_component(&self, type_id: u16) -> Option<&ComponentData> {
247        self.components.iter().find(|c| c.type_id == type_id)
248    }
249
250    pub fn remove_component(&mut self, type_id: u16) -> bool {
251        let len_before = self.components.len();
252        self.components.retain(|c| c.type_id != type_id);
253        self.components.len() < len_before
254    }
255
256    pub fn total_size(&self) -> usize {
257        let base = 4 + 12 + 16 + 12 + 4; // id + pos + rot + vel + flags
258        let comp_size: usize = self.components.iter().map(|c| c.size()).sum();
259        base + comp_size
260    }
261
262    /// Compute delta between this snapshot and a baseline of the same entity.
263    pub fn delta_against(&self, baseline: &EntitySnapshot) -> EntityDelta {
264        let mut changed_components = Vec::new();
265        let mut added_components = Vec::new();
266        let mut removed_component_types = Vec::new();
267
268        // Check for changed/added components
269        for comp in &self.components {
270            if let Some(base_comp) = baseline.get_component(comp.type_id) {
271                if let Some(delta) = comp.delta_against(base_comp) {
272                    changed_components.push(delta);
273                }
274            } else {
275                added_components.push(comp.clone());
276            }
277        }
278
279        // Check for removed components
280        for base_comp in &baseline.components {
281            if self.get_component(base_comp.type_id).is_none() {
282                removed_component_types.push(base_comp.type_id);
283            }
284        }
285
286        // Position delta
287        let pos_changed = (self.position[0] - baseline.position[0]).abs() > f32::EPSILON
288            || (self.position[1] - baseline.position[1]).abs() > f32::EPSILON
289            || (self.position[2] - baseline.position[2]).abs() > f32::EPSILON;
290
291        let rot_changed = (self.rotation[0] - baseline.rotation[0]).abs() > f32::EPSILON
292            || (self.rotation[1] - baseline.rotation[1]).abs() > f32::EPSILON
293            || (self.rotation[2] - baseline.rotation[2]).abs() > f32::EPSILON
294            || (self.rotation[3] - baseline.rotation[3]).abs() > f32::EPSILON;
295
296        let vel_changed = (self.velocity[0] - baseline.velocity[0]).abs() > f32::EPSILON
297            || (self.velocity[1] - baseline.velocity[1]).abs() > f32::EPSILON
298            || (self.velocity[2] - baseline.velocity[2]).abs() > f32::EPSILON;
299
300        EntityDelta {
301            entity_id: self.entity_id,
302            position: if pos_changed { Some(self.position) } else { None },
303            rotation: if rot_changed { Some(self.rotation) } else { None },
304            velocity: if vel_changed { Some(self.velocity) } else { None },
305            flags_changed: self.flags != baseline.flags,
306            new_flags: self.flags,
307            changed_components,
308            added_components,
309            removed_component_types,
310        }
311    }
312
313    /// Apply a delta to produce an updated snapshot.
314    pub fn apply_delta(&self, delta: &EntityDelta) -> EntitySnapshot {
315        let mut result = self.clone();
316
317        if let Some(pos) = delta.position {
318            result.position = pos;
319        }
320        if let Some(rot) = delta.rotation {
321            result.rotation = rot;
322        }
323        if let Some(vel) = delta.velocity {
324            result.velocity = vel;
325        }
326        if delta.flags_changed {
327            result.flags = delta.new_flags;
328        }
329
330        // Apply component changes
331        for comp_delta in &delta.changed_components {
332            if let Some(existing) = result.components.iter_mut().find(|c| c.type_id == comp_delta.type_id) {
333                let original = existing.clone();
334                *existing = original.apply_delta(comp_delta);
335            }
336        }
337
338        // Add new components
339        for added in &delta.added_components {
340            result.add_component(added.clone());
341        }
342
343        // Remove components
344        for &type_id in &delta.removed_component_types {
345            result.remove_component(type_id);
346        }
347
348        result
349    }
350}
351
352/// Delta for a single component.
353#[derive(Debug, Clone)]
354pub struct ComponentDelta {
355    pub type_id: u16,
356    pub kind: DeltaKind,
357    pub new_version: u32,
358}
359
360impl ComponentDelta {
361    pub fn size(&self) -> usize {
362        2 + 4 + match &self.kind {
363            DeltaKind::Replaced(data) => data.len() + 1,
364            DeltaKind::XorRaw(data) => data.len() + 1,
365            DeltaKind::XorRle(data) => data.len() + 1,
366        }
367    }
368}
369
370/// How a component changed between snapshots.
371#[derive(Debug, Clone)]
372pub enum DeltaKind {
373    Replaced(Vec<u8>),
374    XorRaw(Vec<u8>),
375    XorRle(Vec<u8>),
376}
377
378/// Delta for a single entity between two snapshots.
379#[derive(Debug, Clone)]
380pub struct EntityDelta {
381    pub entity_id: NetEntityId,
382    pub position: Option<[f32; 3]>,
383    pub rotation: Option<[f32; 4]>,
384    pub velocity: Option<[f32; 3]>,
385    pub flags_changed: bool,
386    pub new_flags: u32,
387    pub changed_components: Vec<ComponentDelta>,
388    pub added_components: Vec<ComponentData>,
389    pub removed_component_types: Vec<u16>,
390}
391
392impl EntityDelta {
393    pub fn is_empty(&self) -> bool {
394        self.position.is_none()
395            && self.rotation.is_none()
396            && self.velocity.is_none()
397            && !self.flags_changed
398            && self.changed_components.is_empty()
399            && self.added_components.is_empty()
400            && self.removed_component_types.is_empty()
401    }
402
403    pub fn estimated_size(&self) -> usize {
404        let mut size = 4; // entity_id
405        if self.position.is_some() { size += 12; }
406        if self.rotation.is_some() { size += 16; }
407        if self.velocity.is_some() { size += 12; }
408        if self.flags_changed { size += 4; }
409        for cd in &self.changed_components { size += cd.size(); }
410        for ac in &self.added_components { size += ac.size(); }
411        size += self.removed_component_types.len() * 2;
412        size
413    }
414}
415
416/// A complete snapshot of the world at a given tick.
417#[derive(Debug, Clone)]
418pub struct WorldSnapshot {
419    pub id: SnapshotId,
420    pub tick: u64,
421    pub timestamp_ms: u64,
422    pub entities: HashMap<NetEntityId, EntitySnapshot>,
423}
424
425impl WorldSnapshot {
426    pub fn new(id: SnapshotId, tick: u64, timestamp_ms: u64) -> Self {
427        Self {
428            id,
429            tick,
430            timestamp_ms,
431            entities: HashMap::new(),
432        }
433    }
434
435    pub fn add_entity(&mut self, snapshot: EntitySnapshot) {
436        self.entities.insert(snapshot.entity_id, snapshot);
437    }
438
439    pub fn remove_entity(&mut self, id: NetEntityId) -> Option<EntitySnapshot> {
440        self.entities.remove(&id)
441    }
442
443    pub fn get_entity(&self, id: NetEntityId) -> Option<&EntitySnapshot> {
444        self.entities.get(&id)
445    }
446
447    pub fn entity_count(&self) -> usize {
448        self.entities.len()
449    }
450
451    pub fn total_size(&self) -> usize {
452        let header = 8 + 8 + 8; // id + tick + timestamp
453        let entity_size: usize = self.entities.values().map(|e| e.total_size()).sum();
454        header + entity_size
455    }
456
457    /// Compute a delta from a baseline snapshot.
458    pub fn delta_from(&self, baseline: &WorldSnapshot) -> SnapshotDelta {
459        let mut entity_deltas = Vec::new();
460        let mut spawned_entities = Vec::new();
461        let mut despawned_entities = Vec::new();
462
463        // Find changed and new entities
464        for (id, entity) in &self.entities {
465            if let Some(base_entity) = baseline.entities.get(id) {
466                let delta = entity.delta_against(base_entity);
467                if !delta.is_empty() {
468                    entity_deltas.push(delta);
469                }
470            } else {
471                spawned_entities.push(entity.clone());
472            }
473        }
474
475        // Find despawned entities
476        for id in baseline.entities.keys() {
477            if !self.entities.contains_key(id) {
478                despawned_entities.push(*id);
479            }
480        }
481
482        SnapshotDelta {
483            baseline_id: baseline.id,
484            target_id: self.id,
485            baseline_tick: baseline.tick,
486            target_tick: self.tick,
487            timestamp_ms: self.timestamp_ms,
488            entity_deltas,
489            spawned_entities,
490            despawned_entities,
491        }
492    }
493
494    /// Apply a delta to produce a new WorldSnapshot.
495    pub fn apply_delta(&self, delta: &SnapshotDelta) -> WorldSnapshot {
496        let mut result = WorldSnapshot::new(delta.target_id, delta.target_tick, delta.timestamp_ms);
497
498        // Copy all existing entities
499        for (id, entity) in &self.entities {
500            result.entities.insert(*id, entity.clone());
501        }
502
503        // Apply entity deltas
504        for ed in &delta.entity_deltas {
505            if let Some(existing) = self.entities.get(&ed.entity_id) {
506                let updated = existing.apply_delta(ed);
507                result.entities.insert(ed.entity_id, updated);
508            }
509        }
510
511        // Add spawned entities
512        for spawned in &delta.spawned_entities {
513            result.entities.insert(spawned.entity_id, spawned.clone());
514        }
515
516        // Remove despawned entities
517        for &id in &delta.despawned_entities {
518            result.entities.remove(&id);
519        }
520
521        result
522    }
523
524    /// Merge another snapshot into this one (union of entities, preferring other on conflict).
525    pub fn merge_from(&mut self, other: &WorldSnapshot) {
526        for (id, entity) in &other.entities {
527            self.entities.insert(*id, entity.clone());
528        }
529        if other.tick > self.tick {
530            self.tick = other.tick;
531            self.id = other.id;
532            self.timestamp_ms = other.timestamp_ms;
533        }
534    }
535}
536
537/// Delta between two world snapshots.
538#[derive(Debug, Clone)]
539pub struct SnapshotDelta {
540    pub baseline_id: SnapshotId,
541    pub target_id: SnapshotId,
542    pub baseline_tick: u64,
543    pub target_tick: u64,
544    pub timestamp_ms: u64,
545    pub entity_deltas: Vec<EntityDelta>,
546    pub spawned_entities: Vec<EntitySnapshot>,
547    pub despawned_entities: Vec<NetEntityId>,
548}
549
550impl SnapshotDelta {
551    pub fn is_empty(&self) -> bool {
552        self.entity_deltas.is_empty()
553            && self.spawned_entities.is_empty()
554            && self.despawned_entities.is_empty()
555    }
556
557    pub fn estimated_size(&self) -> usize {
558        let header = 8 + 8 + 8 + 8 + 8;
559        let deltas: usize = self.entity_deltas.iter().map(|d| d.estimated_size()).sum();
560        let spawns: usize = self.spawned_entities.iter().map(|e| e.total_size()).sum();
561        let despawns = self.despawned_entities.len() * 4;
562        header + deltas + spawns + despawns
563    }
564
565    pub fn delta_count(&self) -> usize {
566        self.entity_deltas.len() + self.spawned_entities.len() + self.despawned_entities.len()
567    }
568}
569
570/// Ring buffer for storing recent world snapshots.
571/// Supports efficient lookup by snapshot ID and tick number.
572pub struct SnapshotRingBuffer {
573    buffer: Vec<Option<WorldSnapshot>>,
574    capacity: usize,
575    head: usize,
576    count: usize,
577    latest_id: SnapshotId,
578    id_to_index: HashMap<SnapshotId, usize>,
579    tick_to_id: HashMap<u64, SnapshotId>,
580}
581
582impl SnapshotRingBuffer {
583    pub fn new(capacity: usize) -> Self {
584        let capacity = capacity.max(4);
585        let mut buffer = Vec::with_capacity(capacity);
586        for _ in 0..capacity {
587            buffer.push(None);
588        }
589        Self {
590            buffer,
591            capacity,
592            head: 0,
593            count: 0,
594            latest_id: SnapshotId(0),
595            id_to_index: HashMap::new(),
596            tick_to_id: HashMap::new(),
597        }
598    }
599
600    pub fn push(&mut self, snapshot: WorldSnapshot) {
601        // Evict the old entry at this position
602        if let Some(ref old) = self.buffer[self.head] {
603            self.id_to_index.remove(&old.id);
604            self.tick_to_id.remove(&old.tick);
605        }
606
607        let id = snapshot.id;
608        let tick = snapshot.tick;
609        self.id_to_index.insert(id, self.head);
610        self.tick_to_id.insert(tick, id);
611        self.buffer[self.head] = Some(snapshot);
612
613        if id.0 > self.latest_id.0 {
614            self.latest_id = id;
615        }
616
617        self.head = (self.head + 1) % self.capacity;
618        if self.count < self.capacity {
619            self.count += 1;
620        }
621    }
622
623    pub fn get(&self, id: SnapshotId) -> Option<&WorldSnapshot> {
624        self.id_to_index.get(&id).and_then(|&idx| self.buffer[idx].as_ref())
625    }
626
627    pub fn get_by_tick(&self, tick: u64) -> Option<&WorldSnapshot> {
628        self.tick_to_id.get(&tick).and_then(|id| self.get(*id))
629    }
630
631    pub fn latest(&self) -> Option<&WorldSnapshot> {
632        if self.count == 0 {
633            return None;
634        }
635        self.get(self.latest_id)
636    }
637
638    pub fn latest_id(&self) -> SnapshotId {
639        self.latest_id
640    }
641
642    pub fn len(&self) -> usize {
643        self.count
644    }
645
646    pub fn is_empty(&self) -> bool {
647        self.count == 0
648    }
649
650    pub fn capacity(&self) -> usize {
651        self.capacity
652    }
653
654    pub fn is_full(&self) -> bool {
655        self.count >= self.capacity
656    }
657
658    /// Get the N most recent snapshots, ordered oldest to newest.
659    pub fn recent(&self, n: usize) -> Vec<&WorldSnapshot> {
660        let n = n.min(self.count);
661        let mut result = Vec::with_capacity(n);
662        let start = if self.head >= n {
663            self.head - n
664        } else {
665            self.capacity - (n - self.head)
666        };
667        for i in 0..n {
668            let idx = (start + i) % self.capacity;
669            if let Some(ref snap) = self.buffer[idx] {
670                result.push(snap);
671            }
672        }
673        result
674    }
675
676    /// Find the closest snapshot to a given tick.
677    pub fn closest_to_tick(&self, tick: u64) -> Option<&WorldSnapshot> {
678        let mut best: Option<&WorldSnapshot> = None;
679        let mut best_dist = u64::MAX;
680        for entry in &self.buffer {
681            if let Some(ref snap) = entry {
682                let dist = if snap.tick > tick {
683                    snap.tick - tick
684                } else {
685                    tick - snap.tick
686                };
687                if dist < best_dist {
688                    best_dist = dist;
689                    best = Some(snap);
690                }
691            }
692        }
693        best
694    }
695
696    /// Compute delta between two stored snapshots.
697    pub fn compute_delta(&self, baseline_id: SnapshotId, target_id: SnapshotId) -> Option<SnapshotDelta> {
698        let baseline = self.get(baseline_id)?;
699        let target = self.get(target_id)?;
700        Some(target.delta_from(baseline))
701    }
702
703    /// Remove all snapshots older than the given tick.
704    pub fn prune_before(&mut self, tick: u64) {
705        for i in 0..self.capacity {
706            if let Some(ref snap) = self.buffer[i] {
707                if snap.tick < tick {
708                    let id = snap.id;
709                    let t = snap.tick;
710                    self.id_to_index.remove(&id);
711                    self.tick_to_id.remove(&t);
712                    self.buffer[i] = None;
713                    if self.count > 0 {
714                        self.count -= 1;
715                    }
716                }
717            }
718        }
719    }
720
721    pub fn clear(&mut self) {
722        for i in 0..self.capacity {
723            self.buffer[i] = None;
724        }
725        self.id_to_index.clear();
726        self.tick_to_id.clear();
727        self.head = 0;
728        self.count = 0;
729    }
730
731    /// Collect all snapshot IDs currently stored, in no particular order.
732    pub fn stored_ids(&self) -> Vec<SnapshotId> {
733        self.id_to_index.keys().copied().collect()
734    }
735}
736
737/// Priority and relevancy information for a single entity relative to a client.
738#[derive(Debug, Clone)]
739pub struct RelevancyEntry {
740    pub entity_id: NetEntityId,
741    pub priority: f32,
742    pub distance_sq: f32,
743    pub is_relevant: bool,
744    pub last_sent_tick: u64,
745    pub update_frequency: f32,
746    pub accumulated_priority: f32,
747}
748
749impl RelevancyEntry {
750    pub fn new(entity_id: NetEntityId) -> Self {
751        Self {
752            entity_id,
753            priority: 1.0,
754            distance_sq: 0.0,
755            is_relevant: true,
756            last_sent_tick: 0,
757            update_frequency: 1.0,
758            accumulated_priority: 0.0,
759        }
760    }
761}
762
763/// A spatial region used for area-of-interest filtering.
764#[derive(Debug, Clone)]
765pub struct RelevancyRegion {
766    pub center: [f32; 3],
767    pub radius: f32,
768    pub priority_falloff: f32,
769    pub min_priority: f32,
770}
771
772impl RelevancyRegion {
773    pub fn new(center: [f32; 3], radius: f32) -> Self {
774        Self {
775            center,
776            radius,
777            priority_falloff: 1.0,
778            min_priority: 0.0,
779        }
780    }
781
782    pub fn contains(&self, pos: [f32; 3]) -> bool {
783        let dx = pos[0] - self.center[0];
784        let dy = pos[1] - self.center[1];
785        let dz = pos[2] - self.center[2];
786        dx * dx + dy * dy + dz * dz <= self.radius * self.radius
787    }
788
789    pub fn distance_sq(&self, pos: [f32; 3]) -> f32 {
790        let dx = pos[0] - self.center[0];
791        let dy = pos[1] - self.center[1];
792        let dz = pos[2] - self.center[2];
793        dx * dx + dy * dy + dz * dz
794    }
795
796    pub fn priority_at(&self, pos: [f32; 3]) -> f32 {
797        let dist_sq = self.distance_sq(pos);
798        let radius_sq = self.radius * self.radius;
799        if dist_sq >= radius_sq {
800            return self.min_priority;
801        }
802        let t = 1.0 - (dist_sq / radius_sq).sqrt();
803        let p = t.powf(self.priority_falloff);
804        self.min_priority + (1.0 - self.min_priority) * p
805    }
806}
807
808/// Client identifier for relevancy tracking.
809#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
810pub struct ClientId(pub u32);
811
812/// Per-client relevancy filter that determines which entities
813/// should be sent and at what priority/frequency.
814pub struct RelevancyFilter {
815    client_id: ClientId,
816    region: RelevancyRegion,
817    entries: HashMap<NetEntityId, RelevancyEntry>,
818    max_entities_per_update: usize,
819    bandwidth_budget_bytes: usize,
820    always_relevant: Vec<NetEntityId>,
821    never_relevant: Vec<NetEntityId>,
822    priority_bias: HashMap<u16, f32>,
823    current_tick: u64,
824}
825
826impl RelevancyFilter {
827    pub fn new(client_id: ClientId, region: RelevancyRegion) -> Self {
828        Self {
829            client_id,
830            region,
831            entries: HashMap::new(),
832            max_entities_per_update: 64,
833            bandwidth_budget_bytes: 16384,
834            always_relevant: Vec::new(),
835            never_relevant: Vec::new(),
836            priority_bias: HashMap::new(),
837            current_tick: 0,
838        }
839    }
840
841    pub fn client_id(&self) -> ClientId {
842        self.client_id
843    }
844
845    pub fn set_region(&mut self, region: RelevancyRegion) {
846        self.region = region;
847    }
848
849    pub fn region(&self) -> &RelevancyRegion {
850        &self.region
851    }
852
853    pub fn set_max_entities(&mut self, max: usize) {
854        self.max_entities_per_update = max;
855    }
856
857    pub fn set_bandwidth_budget(&mut self, bytes: usize) {
858        self.bandwidth_budget_bytes = bytes;
859    }
860
861    pub fn add_always_relevant(&mut self, id: NetEntityId) {
862        if !self.always_relevant.contains(&id) {
863            self.always_relevant.push(id);
864        }
865    }
866
867    pub fn remove_always_relevant(&mut self, id: NetEntityId) {
868        self.always_relevant.retain(|&x| x != id);
869    }
870
871    pub fn add_never_relevant(&mut self, id: NetEntityId) {
872        if !self.never_relevant.contains(&id) {
873            self.never_relevant.push(id);
874        }
875    }
876
877    pub fn remove_never_relevant(&mut self, id: NetEntityId) {
878        self.never_relevant.retain(|&x| x != id);
879    }
880
881    pub fn set_component_priority_bias(&mut self, component_type: u16, bias: f32) {
882        self.priority_bias.insert(component_type, bias);
883    }
884
885    /// Update the filter with a new world snapshot. Recomputes relevancy for all entities.
886    pub fn update(&mut self, snapshot: &WorldSnapshot, tick: u64) {
887        self.current_tick = tick;
888
889        // Remove entries for entities no longer in the world
890        self.entries.retain(|id, _| snapshot.entities.contains_key(id));
891
892        for (id, entity) in &snapshot.entities {
893            // Skip never-relevant entities
894            if self.never_relevant.contains(id) {
895                if let Some(entry) = self.entries.get_mut(id) {
896                    entry.is_relevant = false;
897                    entry.priority = 0.0;
898                }
899                continue;
900            }
901
902            let entry = self.entries.entry(*id).or_insert_with(|| RelevancyEntry::new(*id));
903            let dist_sq = self.region.distance_sq(entity.position);
904            entry.distance_sq = dist_sq;
905
906            if self.always_relevant.contains(id) {
907                entry.is_relevant = true;
908                entry.priority = 10.0;
909            } else {
910                entry.is_relevant = self.region.contains(entity.position);
911                entry.priority = self.region.priority_at(entity.position);
912            }
913
914            // Apply component-based priority bias
915            for comp in &entity.components {
916                if let Some(&bias) = self.priority_bias.get(&comp.type_id) {
917                    entry.priority *= bias;
918                }
919            }
920
921            // Accumulate priority based on time since last sent
922            let ticks_since_sent = if tick > entry.last_sent_tick {
923                tick - entry.last_sent_tick
924            } else {
925                0
926            };
927            entry.accumulated_priority = entry.priority * (1.0 + ticks_since_sent as f32 * 0.1);
928        }
929    }
930
931    /// Get entities that should be included in the next update,
932    /// sorted by accumulated priority (highest first), limited by bandwidth and count.
933    pub fn select_entities(&mut self, snapshot: &WorldSnapshot) -> Vec<NetEntityId> {
934        let mut candidates: Vec<(NetEntityId, f32)> = self.entries.iter()
935            .filter(|(_, entry)| entry.is_relevant)
936            .map(|(&id, entry)| (id, entry.accumulated_priority))
937            .collect();
938
939        // Sort by accumulated priority descending
940        candidates.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
941
942        let mut selected = Vec::new();
943        let mut budget_remaining = self.bandwidth_budget_bytes;
944
945        for (id, _priority) in candidates {
946            if selected.len() >= self.max_entities_per_update {
947                break;
948            }
949
950            // Estimate the size of this entity's data
951            if let Some(entity) = snapshot.get_entity(id) {
952                let est_size = entity.total_size();
953                if est_size > budget_remaining && !selected.is_empty() {
954                    continue;
955                }
956                budget_remaining = budget_remaining.saturating_sub(est_size);
957                selected.push(id);
958
959                // Mark as sent
960                if let Some(entry) = self.entries.get_mut(&id) {
961                    entry.last_sent_tick = self.current_tick;
962                    entry.accumulated_priority = 0.0;
963                }
964            }
965        }
966
967        selected
968    }
969
970    /// Create a filtered world snapshot containing only relevant entities for this client.
971    pub fn filter_snapshot(&mut self, snapshot: &WorldSnapshot) -> WorldSnapshot {
972        let selected = self.select_entities(snapshot);
973        let mut filtered = WorldSnapshot::new(snapshot.id, snapshot.tick, snapshot.timestamp_ms);
974        for id in selected {
975            if let Some(entity) = snapshot.get_entity(id) {
976                filtered.add_entity(entity.clone());
977            }
978        }
979        filtered
980    }
981
982    /// Get the current relevancy entry for an entity.
983    pub fn get_entry(&self, id: NetEntityId) -> Option<&RelevancyEntry> {
984        self.entries.get(&id)
985    }
986
987    /// Number of entities currently tracked.
988    pub fn tracked_count(&self) -> usize {
989        self.entries.len()
990    }
991
992    /// Number of entities currently considered relevant.
993    pub fn relevant_count(&self) -> usize {
994        self.entries.values().filter(|e| e.is_relevant).count()
995    }
996
997    /// Reset accumulated priorities for all entries.
998    pub fn reset_priorities(&mut self) {
999        for entry in self.entries.values_mut() {
1000            entry.accumulated_priority = 0.0;
1001        }
1002    }
1003}
1004
1005/// Quantize a float to a fixed number of bits for bandwidth reduction.
1006pub fn quantize_f32(value: f32, min: f32, max: f32, bits: u32) -> u32 {
1007    let range = max - min;
1008    if range <= f32::EPSILON {
1009        return 0;
1010    }
1011    let normalized = ((value - min) / range).clamp(0.0, 1.0);
1012    let max_val = (1u32 << bits) - 1;
1013    (normalized * max_val as f32) as u32
1014}
1015
1016/// Dequantize back to float.
1017pub fn dequantize_f32(quantized: u32, min: f32, max: f32, bits: u32) -> f32 {
1018    let max_val = (1u32 << bits) - 1;
1019    if max_val == 0 {
1020        return min;
1021    }
1022    let normalized = quantized as f32 / max_val as f32;
1023    min + normalized * (max - min)
1024}
1025
1026/// Pack three quantized position components into bytes.
1027pub fn pack_position(pos: [f32; 3], bounds_min: [f32; 3], bounds_max: [f32; 3], bits_per_axis: u32) -> Vec<u8> {
1028    let qx = quantize_f32(pos[0], bounds_min[0], bounds_max[0], bits_per_axis);
1029    let qy = quantize_f32(pos[1], bounds_min[1], bounds_max[1], bits_per_axis);
1030    let qz = quantize_f32(pos[2], bounds_min[2], bounds_max[2], bits_per_axis);
1031
1032    let mut bytes = Vec::new();
1033    bytes.extend_from_slice(&qx.to_le_bytes());
1034    bytes.extend_from_slice(&qy.to_le_bytes());
1035    bytes.extend_from_slice(&qz.to_le_bytes());
1036    bytes
1037}
1038
1039/// Unpack position from bytes.
1040pub fn unpack_position(data: &[u8], bounds_min: [f32; 3], bounds_max: [f32; 3], bits_per_axis: u32) -> [f32; 3] {
1041    if data.len() < 12 {
1042        return [0.0; 3];
1043    }
1044    let qx = u32::from_le_bytes([data[0], data[1], data[2], data[3]]);
1045    let qy = u32::from_le_bytes([data[4], data[5], data[6], data[7]]);
1046    let qz = u32::from_le_bytes([data[8], data[9], data[10], data[11]]);
1047
1048    [
1049        dequantize_f32(qx, bounds_min[0], bounds_max[0], bits_per_axis),
1050        dequantize_f32(qy, bounds_min[1], bounds_max[1], bits_per_axis),
1051        dequantize_f32(qz, bounds_min[2], bounds_max[2], bits_per_axis),
1052    ]
1053}
1054
1055/// Smallest-three quaternion compression: store only the 3 smallest components
1056/// and the index of the largest.
1057pub fn compress_quaternion(q: [f32; 4]) -> [u16; 3] {
1058    let mut largest_idx = 0;
1059    let mut largest_val = q[0].abs();
1060    for i in 1..4 {
1061        if q[i].abs() > largest_val {
1062            largest_val = q[i].abs();
1063            largest_idx = i;
1064        }
1065    }
1066
1067    // Ensure the largest component is positive (negate all if needed)
1068    let sign = if q[largest_idx] < 0.0 { -1.0 } else { 1.0 };
1069
1070    let mut small = Vec::with_capacity(3);
1071    for i in 0..4 {
1072        if i != largest_idx {
1073            let val = q[i] * sign;
1074            // Quaternion components are in [-1/sqrt(2), 1/sqrt(2)] range
1075            let normalized = (val * std::f32::consts::FRAC_1_SQRT_2.recip() + 1.0) * 0.5;
1076            let quantized = (normalized.clamp(0.0, 1.0) * 65535.0) as u16;
1077            small.push(quantized);
1078        }
1079    }
1080
1081    // Pack largest index into top 2 bits of first value
1082    let idx_bits = (largest_idx as u16) << 14;
1083    small[0] = (small[0] & 0x3FFF) | idx_bits;
1084
1085    [small[0], small[1], small[2]]
1086}
1087
1088/// Decompress a quaternion from smallest-three representation.
1089pub fn decompress_quaternion(packed: [u16; 3]) -> [f32; 4] {
1090    let largest_idx = ((packed[0] >> 14) & 0x03) as usize;
1091    let inv_sqrt2 = std::f32::consts::FRAC_1_SQRT_2;
1092
1093    let a_norm = (packed[0] & 0x3FFF) as f32 / 16383.0;
1094    let b_norm = packed[1] as f32 / 65535.0;
1095    let c_norm = packed[2] as f32 / 65535.0;
1096
1097    let a = (a_norm * 2.0 - 1.0) * inv_sqrt2;
1098    let b = (b_norm * 2.0 - 1.0) * inv_sqrt2;
1099    let c = (c_norm * 2.0 - 1.0) * inv_sqrt2;
1100
1101    let sum_sq = a * a + b * b + c * c;
1102    let largest = (1.0 - sum_sq).max(0.0).sqrt();
1103
1104    let mut result = [0.0f32; 4];
1105    let mut small_idx = 0;
1106    let smalls = [a, b, c];
1107    for i in 0..4 {
1108        if i == largest_idx {
1109            result[i] = largest;
1110        } else {
1111            result[i] = smalls[small_idx];
1112            small_idx += 1;
1113        }
1114    }
1115
1116    // Normalize
1117    let len = (result[0] * result[0] + result[1] * result[1]
1118        + result[2] * result[2] + result[3] * result[3]).sqrt();
1119    if len > f32::EPSILON {
1120        for v in &mut result {
1121            *v /= len;
1122        }
1123    }
1124
1125    result
1126}
1127
1128#[cfg(test)]
1129mod tests {
1130    use super::*;
1131
1132    #[test]
1133    fn test_snapshot_id() {
1134        let id = SnapshotId(5);
1135        assert_eq!(id.next(), SnapshotId(6));
1136        assert_eq!(id.distance(SnapshotId(10)), 5);
1137    }
1138
1139    #[test]
1140    fn test_component_delta_identical() {
1141        let c1 = ComponentData::new(1, vec![1, 2, 3, 4]);
1142        let c2 = ComponentData::new(1, vec![1, 2, 3, 4]);
1143        assert!(c1.delta_against(&c2).is_none());
1144    }
1145
1146    #[test]
1147    fn test_component_delta_changed() {
1148        let c1 = ComponentData::new(1, vec![1, 2, 3, 4]);
1149        let c2 = ComponentData::new(1, vec![1, 2, 5, 4]);
1150        let delta = c1.delta_against(&c2);
1151        assert!(delta.is_some());
1152        let reconstructed = c2.apply_delta(&delta.unwrap());
1153        assert_eq!(reconstructed.data, c1.data);
1154    }
1155
1156    #[test]
1157    fn test_world_snapshot_delta() {
1158        let mut ws1 = WorldSnapshot::new(SnapshotId(1), 1, 100);
1159        let mut e1 = EntitySnapshot::new(NetEntityId(1));
1160        e1.position = [1.0, 2.0, 3.0];
1161        e1.add_component(ComponentData::new(1, vec![10, 20]));
1162        ws1.add_entity(e1);
1163
1164        let mut ws2 = WorldSnapshot::new(SnapshotId(2), 2, 200);
1165        let mut e1b = EntitySnapshot::new(NetEntityId(1));
1166        e1b.position = [4.0, 5.0, 6.0];
1167        e1b.add_component(ComponentData::new(1, vec![10, 20]));
1168        ws2.add_entity(e1b);
1169
1170        let delta = ws2.delta_from(&ws1);
1171        assert_eq!(delta.entity_deltas.len(), 1);
1172        assert!(delta.entity_deltas[0].position.is_some());
1173    }
1174
1175    #[test]
1176    fn test_ring_buffer() {
1177        let mut rb = SnapshotRingBuffer::new(4);
1178        for i in 0..6 {
1179            let snap = WorldSnapshot::new(SnapshotId(i), i, i * 100);
1180            rb.push(snap);
1181        }
1182        assert_eq!(rb.len(), 4);
1183        assert!(rb.get(SnapshotId(0)).is_none());
1184        assert!(rb.get(SnapshotId(1)).is_none());
1185        assert!(rb.get(SnapshotId(2)).is_some());
1186        assert!(rb.get(SnapshotId(5)).is_some());
1187    }
1188
1189    #[test]
1190    fn test_quantize_roundtrip() {
1191        let val = 3.14;
1192        let q = quantize_f32(val, 0.0, 10.0, 16);
1193        let dq = dequantize_f32(q, 0.0, 10.0, 16);
1194        assert!((dq - val).abs() < 0.001);
1195    }
1196
1197    #[test]
1198    fn test_relevancy_region() {
1199        let region = RelevancyRegion::new([0.0, 0.0, 0.0], 100.0);
1200        assert!(region.contains([50.0, 0.0, 0.0]));
1201        assert!(!region.contains([150.0, 0.0, 0.0]));
1202        let p = region.priority_at([0.0, 0.0, 0.0]);
1203        assert!((p - 1.0).abs() < 0.01);
1204    }
1205
1206    #[test]
1207    fn test_rle_roundtrip() {
1208        let data = vec![0, 0, 0, 5, 5, 0, 0, 7];
1209        let encoded = rle_encode(&data);
1210        let decoded = rle_decode(&encoded, data.len());
1211        assert_eq!(decoded, data);
1212    }
1213}
proof_engine/netcode/snapshot.rs

proof_engine/netcode/
snapshot.rs
