steel_core/chunk/chunk_tracker/
mod.rs

1//! Incremental eight-neighbor ticket propagation shared by loading and simulation.
2//!
3//! Mirrors Vanilla's `ChunkTracker` / `DynamicGraphMinFixedPoint`. Each domain
4//! retains its own sources and levels; the const limit selects its outer boundary.
5use std::mem;
6
7use rustc_hash::FxHashMap;
8use steel_utils::ChunkPos;
9
10use super::{chunk_ticket_manager::ChunkTicketLevel, chunk_ticket_storage::SourceLevelUpdate};
11
12/// Vanilla-style level buckets for pending graph corrections.
13#[derive(Debug)]
14struct LeveledPropagationQueue {
15    buckets: Vec<Vec<ChunkPos>>,
16    first_queued_level: u8,
17}
18
19impl LeveledPropagationQueue {
20    fn new(level_count: u8) -> Self {
21        Self {
22            buckets: (0..usize::from(level_count)).map(|_| Vec::new()).collect(),
23            first_queued_level: level_count,
24        }
25    }
26
27    fn enqueue(&mut self, pos: ChunkPos, level: u8) {
28        self.buckets[usize::from(level)].push(pos);
29        self.first_queued_level = self.first_queued_level.min(level);
30    }
31
32    fn pop(&mut self) -> Option<(ChunkPos, u8)> {
33        while usize::from(self.first_queued_level) < self.buckets.len() {
34            let bucket = &mut self.buckets[usize::from(self.first_queued_level)];
35            if let Some(pos) = bucket.pop() {
36                return Some((pos, self.first_queued_level));
37            }
38            self.first_queued_level += 1;
39        }
40        None
41    }
42
43    const fn is_empty(&self) -> bool {
44        self.first_queued_level as usize == self.buckets.len()
45    }
46}
47
48/// A propagated loading or simulation level change.
49#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub struct ChunkLevelChange {
51    /// Chunk whose propagated level changed.
52    pub pos: ChunkPos,
53    /// `Some(level)` if the level changed or was added, `None` if it was removed.
54    pub new_level: Option<ChunkTicketLevel>,
55}
56
57/// Tracks sources and their minimum propagated levels through `MAX_LEVEL`.
58#[derive(Debug)]
59pub struct ChunkTracker<const MAX_LEVEL: u8> {
60    source_levels: FxHashMap<ChunkPos, u8>,
61    pending_source_levels: FxHashMap<ChunkPos, u8>,
62    levels: FxHashMap<ChunkPos, ChunkTicketLevel>,
63    pending_levels: FxHashMap<ChunkPos, u8>,
64    propagation_queue: LeveledPropagationQueue,
65    changes: Vec<ChunkLevelChange>,
66}
67
68impl<const MAX_LEVEL: u8> Default for ChunkTracker<MAX_LEVEL> {
69    fn default() -> Self {
70        Self::new()
71    }
72}
73
74impl<const MAX_LEVEL: u8> ChunkTracker<MAX_LEVEL> {
75    const ABSENT_LEVEL: u8 = MAX_LEVEL + 1;
76    /// Creates an empty tracker for this domain.
77    #[must_use]
78    pub fn new() -> Self {
79        assert!(
80            MAX_LEVEL <= ChunkTicketLevel::MAX.raw(),
81            "tracker limit exceeds supported ticket levels"
82        );
83        Self {
84            source_levels: FxHashMap::default(),
85            pending_source_levels: FxHashMap::default(),
86            levels: FxHashMap::default(),
87            pending_levels: FxHashMap::default(),
88            propagation_queue: LeveledPropagationQueue::new(Self::ABSENT_LEVEL + 1),
89            changes: Vec::new(),
90        }
91    }
92
93    /// Applies the latest effective ticket source level at one position.
94    pub(crate) fn apply_source_update(&mut self, update: SourceLevelUpdate) {
95        assert!(
96            update.level.is_none_or(|level| level.raw() <= MAX_LEVEL),
97            "source level exceeds tracker limit"
98        );
99        let new_level = update
100            .level
101            .map_or(Self::ABSENT_LEVEL, ChunkTicketLevel::raw);
102
103        let old_level = self.source_level(update.pos);
104        if old_level == new_level {
105            return;
106        }
107
108        let original_level = *self
109            .pending_source_levels
110            .entry(update.pos)
111            .or_insert(old_level);
112        if new_level == Self::ABSENT_LEVEL {
113            self.source_levels.remove(&update.pos);
114        } else {
115            self.source_levels.insert(update.pos, new_level);
116        }
117
118        if original_level == new_level {
119            self.pending_source_levels.remove(&update.pos);
120        }
121    }
122
123    /// Applies effective source updates in iterator order.
124    pub(crate) fn apply_source_updates(
125        &mut self,
126        updates: impl IntoIterator<Item = SourceLevelUpdate>,
127    ) {
128        for update in updates {
129            self.apply_source_update(update);
130        }
131    }
132
133    /// Applies pending source changes with minimum 8-neighbor propagation.
134    /// The returned changes include additions, updates, and removals.
135    pub fn run_all_updates(&mut self) -> &[ChunkLevelChange] {
136        self.changes.clear();
137
138        if self.pending_source_levels.is_empty() {
139            return &self.changes;
140        }
141
142        debug_assert!(self.pending_levels.is_empty());
143        debug_assert!(self.propagation_queue.is_empty());
144
145        let source_changes = mem::take(&mut self.pending_source_levels);
146        let mut original_levels = FxHashMap::default();
147        for (pos, old_level) in source_changes {
148            let new_level = self.source_level(pos);
149            self.check_edge(None, pos, new_level, new_level < old_level);
150        }
151
152        while let Some((pos, queued_priority)) = self.propagation_queue.pop() {
153            let Some(computed_level) = self.pending_levels.get(&pos).copied() else {
154                continue;
155            };
156            if self.level(pos).min(computed_level) != queued_priority {
157                continue;
158            }
159            self.pending_levels.remove(&pos);
160            self.apply_pending_level(pos, computed_level, &mut original_levels);
161        }
162
163        for (pos, old_level) in original_levels {
164            let new_level = self.levels.get(&pos).copied();
165            if old_level != new_level {
166                self.changes.push(ChunkLevelChange { pos, new_level });
167            }
168        }
169        self.changes
170            .sort_unstable_by_key(|change| (change.pos.0.x, change.pos.0.y));
171
172        &self.changes
173    }
174
175    /// Takes the change buffer produced by the last propagation pass.
176    pub(crate) fn take_changes(&mut self) -> Vec<ChunkLevelChange> {
177        mem::take(&mut self.changes)
178    }
179
180    /// Reuses a drained change buffer on the next propagation pass.
181    pub(crate) fn recycle_changes(&mut self, mut changes: Vec<ChunkLevelChange>) {
182        debug_assert_eq!(self.changes, []);
183        changes.clear();
184        self.changes = changes;
185    }
186
187    /// Returns the last propagated ticket level at `pos`.
188    #[must_use]
189    pub fn get_level(&self, pos: ChunkPos) -> Option<ChunkTicketLevel> {
190        self.levels.get(&pos).copied()
191    }
192
193    #[cfg(test)]
194    pub(super) fn is_dirty(&self) -> bool {
195        !self.pending_source_levels.is_empty()
196    }
197
198    fn source_level(&self, pos: ChunkPos) -> u8 {
199        self.source_levels
200            .get(&pos)
201            .copied()
202            .unwrap_or(Self::ABSENT_LEVEL)
203    }
204
205    fn level(&self, pos: ChunkPos) -> u8 {
206        self.levels
207            .get(&pos)
208            .copied()
209            .map_or(Self::ABSENT_LEVEL, ChunkTicketLevel::raw)
210    }
211
212    fn apply_pending_level(
213        &mut self,
214        pos: ChunkPos,
215        computed_level: u8,
216        original_levels: &mut FxHashMap<ChunkPos, Option<ChunkTicketLevel>>,
217    ) {
218        let current_level = self.level(pos);
219        if computed_level < current_level {
220            self.set_level(pos, computed_level, original_levels);
221            self.check_neighbors_after_update(pos, computed_level, true);
222        } else if computed_level > current_level {
223            self.set_level(pos, Self::ABSENT_LEVEL, original_levels);
224            if computed_level != Self::ABSENT_LEVEL {
225                self.schedule_level(pos, computed_level);
226            }
227            self.check_neighbors_after_update(pos, current_level, false);
228        }
229    }
230
231    fn set_level(
232        &mut self,
233        pos: ChunkPos,
234        level: u8,
235        original_levels: &mut FxHashMap<ChunkPos, Option<ChunkTicketLevel>>,
236    ) {
237        original_levels
238            .entry(pos)
239            .or_insert_with(|| self.levels.get(&pos).copied());
240
241        if level == Self::ABSENT_LEVEL {
242            self.levels.remove(&pos);
243            return;
244        }
245
246        let Some(level) = ChunkTicketLevel::new(level) else {
247            panic!("propagated ticket level exceeds ChunkTicketLevel::MAX");
248        };
249        self.levels.insert(pos, level);
250    }
251
252    fn check_neighbors_after_update(&mut self, pos: ChunkPos, level: u8, only_decrease: bool) {
253        if only_decrease && level >= MAX_LEVEL {
254            return;
255        }
256
257        for neighbor in pos.neighbors() {
258            self.check_neighbor(pos, neighbor, level, only_decrease);
259        }
260    }
261
262    fn check_neighbor(
263        &mut self,
264        from: ChunkPos,
265        to: ChunkPos,
266        from_level: u8,
267        only_decrease: bool,
268    ) {
269        let propagated_level = from_level.saturating_add(1).min(Self::ABSENT_LEVEL);
270        if only_decrease {
271            self.check_edge(Some(from), to, propagated_level, true);
272            return;
273        }
274
275        let old_computed_level = self
276            .pending_levels
277            .get(&to)
278            .copied()
279            .unwrap_or_else(|| self.level(to));
280        if propagated_level == old_computed_level {
281            self.check_edge(Some(from), to, Self::ABSENT_LEVEL, false);
282        }
283    }
284
285    fn check_edge(
286        &mut self,
287        known_parent: Option<ChunkPos>,
288        pos: ChunkPos,
289        level_from_parent: u8,
290        only_decrease: bool,
291    ) {
292        let current_level = self.level(pos);
293        let old_computed_level = self
294            .pending_levels
295            .get(&pos)
296            .copied()
297            .unwrap_or(current_level);
298        let new_computed_level = if only_decrease {
299            old_computed_level.min(level_from_parent)
300        } else {
301            self.compute_level(pos, known_parent, level_from_parent)
302        };
303
304        self.replace_pending_level(pos, current_level, new_computed_level);
305    }
306
307    fn compute_level(
308        &self,
309        pos: ChunkPos,
310        known_parent: Option<ChunkPos>,
311        level_from_parent: u8,
312    ) -> u8 {
313        let mut computed_level = level_from_parent.min(self.source_level(pos));
314        for neighbor in pos.neighbors() {
315            if Some(neighbor) == known_parent {
316                continue;
317            }
318
319            computed_level = computed_level.min(self.level(neighbor).saturating_add(1));
320            if computed_level == 0 {
321                break;
322            }
323        }
324        computed_level.min(Self::ABSENT_LEVEL)
325    }
326
327    fn replace_pending_level(&mut self, pos: ChunkPos, current_level: u8, computed_level: u8) {
328        if current_level == computed_level {
329            self.pending_levels.remove(&pos);
330        } else {
331            self.pending_levels.insert(pos, computed_level);
332            self.propagation_queue
333                .enqueue(pos, current_level.min(computed_level));
334        }
335    }
336
337    fn schedule_level(&mut self, pos: ChunkPos, computed_level: u8) {
338        let current_level = self.level(pos);
339        debug_assert!(!self.pending_levels.contains_key(&pos));
340        self.pending_levels.insert(pos, computed_level);
341        self.propagation_queue
342            .enqueue(pos, current_level.min(computed_level));
343    }
344}
345
346#[cfg(test)]
347mod tests;
steel_core/chunk/chunk_tracker/mod.rs

steel_core/chunk/chunk_tracker/
mod.rs
