banished_core/
scheduler.rs

1//! Game time, and the entity manager's update buckets.
2//!
3//! **Time.** The engine counts time in integer microseconds (`System::Time`). [`ticks`] and
4//! [`seconds`] convert as the original does: through `f64`, truncating to time and rounding to
5//! `f32` seconds.
6//!
7//! **Buckets.** A town has tens of thousands of entities, so the game does not update all of them
8//! in every simulation iteration. [`EntityScheduler`] keeps them in five buckets, and each
9//! iteration visits at most [`QUOTAS`] entities of each bucket, starting where the last visit
10//! stopped. Each entity receives the time since its own last visit, so no time is lost.
11//!
12//! ```
13//! use banished_core::scheduler::{seconds, ticks};
14//!
15//! assert_eq!(ticks(1.5), 1_500_000);
16//! assert_eq!(seconds(ticks(1.5)), 1.5);
17//! ```
18//!
19//! The port's handles are stable indices; the engine uses object pointers. Removing an entity
20//! still swaps it with the last one of its bucket, as in the engine.
21//!
22//! Original: `FUN_1400c9460`, `FUN_1400c9560`, `FUN_1400c9d70`.
23
24/// The length of one tick of game time, in seconds: the engine's timer counts 1,000,000 ticks per
25/// second.
26///
27/// Original: `System::Timer::Startup`, Runtime `0x1800cd030`.
28pub const SECONDS_PER_TICK: f64 = 1e-6;
29
30/// Seconds to game time: through `f64`, truncated.
31///
32/// Original: constructing a `System::Time`, Runtime `0x1800078c0`.
33pub fn ticks(seconds: f32) -> i64 {
34    (seconds as f64 / SECONDS_PER_TICK) as i64
35}
36
37/// Game time to seconds: through `f64`, rounded to `f32`.
38///
39/// Original: `System::Time::AsSeconds`, Runtime `0x180007900`.
40pub fn seconds(time: i64) -> f32 {
41    (time as f64 * SECONDS_PER_TICK) as f32
42}
43
44// The entity manager's +0xa8..+0xb8.
45/// How many entities of each bucket one iteration visits, for buckets 0 to 4.
46///
47/// Original: `FUN_1400c9460`.
48pub const QUOTAS: [usize; 5] = [50, 15, 8, 5, 2];
49
50struct Entity<T> {
51    value: T,
52    bucket: usize,
53    slot: usize,
54    last_time: i64,
55    live: bool,
56}
57
58/// Handles of entities registered with [`EntityScheduler::register_extra`] start here, so that
59/// a placed entity's handle stays its index. The game gives such entities values from here too:
60/// citizens `EXTRA + citizen`, and entities the town does not model (the map ambience, a
61/// saved game's entities of templates it skips) from [`FOREIGN`].
62pub const EXTRA: usize = 1 << 30;
63/// Values of scheduled entities with no behaviour in the port (visited for the cursors' sake).
64pub const FOREIGN: usize = EXTRA + (1 << 29);
65
66/// The entity manager's buckets: which entities are visited in each simulation iteration, and
67/// the time each one has had since its last visit. `T` is the caller's value for an entity.
68pub struct EntityScheduler<T> {
69    /// The current game time.
70    pub time: i64,
71    entities: Vec<Entity<T>>,
72    /// Entities outside the placed index space (handles from [`EXTRA`]).
73    extra: Vec<Entity<T>>,
74    buckets: [Vec<usize>; 5],
75    cursors: [usize; 5],
76    /// This iteration's visits, in order: the value and the time since its last visit.
77    visited: Vec<(T, i64)>,
78}
79
80impl<T: Copy> Default for EntityScheduler<T> {
81    fn default() -> Self {
82        Self {
83            time: 0,
84            entities: Vec::new(),
85            extra: Vec::new(),
86            buckets: std::array::from_fn(|_| Vec::new()),
87            cursors: [0; 5],
88            visited: Vec::new(),
89        }
90    }
91}
92
93impl<T: Copy> EntityScheduler<T> {
94    /// Register an entity in a bucket, at the end, with its last visit set to now. Returns its
95    /// handle. Bucket 6 means "not scheduled": the entity is registered but never visited.
96    ///
97    /// Original: `FUN_1400c9d70`.
98    pub fn register(&mut self, value: T, bucket: usize) -> usize {
99        assert!(
100            bucket < 5 || bucket == 6,
101            "invalid component-description bucket"
102        );
103        let id = self.entities.len();
104        let slot = if bucket < 5 {
105            let slot = self.buckets[bucket].len();
106            self.buckets[bucket].push(id);
107            slot
108        } else {
109            0
110        };
111        self.entities.push(Entity {
112            value,
113            bucket,
114            slot,
115            last_time: self.time,
116            live: true,
117        });
118        id
119    }
120
121    /// [`register`](Self::register) in the extra handle space (from [`EXTRA`]): the same
122    /// buckets, cursors and timing, without taking a placed entity's index.
123    pub fn register_extra(&mut self, value: T, bucket: usize) -> usize {
124        let id = EXTRA + self.extra.len();
125        let slot = if bucket < 5 {
126            let slot = self.buckets[bucket].len();
127            self.buckets[bucket].push(id);
128            slot
129        } else {
130            0
131        };
132        self.extra.push(Entity {
133            value,
134            bucket,
135            slot,
136            last_time: self.time,
137            live: true,
138        });
139        id
140    }
141
142    fn entity_mut(&mut self, id: usize) -> &mut Entity<T> {
143        if id >= EXTRA {
144            &mut self.extra[id - EXTRA]
145        } else {
146            &mut self.entities[id]
147        }
148    }
149
150    /// Whether `handle` was registered.
151    pub fn contains(&self, handle: usize) -> bool {
152        if handle >= EXTRA {
153            handle - EXTRA < self.extra.len()
154        } else {
155            handle < self.entities.len()
156        }
157    }
158
159    /// A bucket's handles in visiting order.
160    pub fn bucket(&self, bucket: usize) -> &[usize] {
161        &self.buckets[bucket]
162    }
163
164    // +0xbc
165    /// A bucket's cursor, the slot its next visit starts at.
166    pub fn cursor(&self, bucket: usize) -> usize {
167        self.cursors[bucket]
168    }
169
170    /// An entity's bucket (6: none) and last visit time.
171    pub fn schedule(&self, handle: usize) -> (usize, i64) {
172        let e = if handle >= EXTRA {
173            &self.extra[handle - EXTRA]
174        } else {
175            &self.entities[handle]
176        };
177        (e.bucket, e.last_time)
178    }
179
180    /// A saved game's bucket lists, cursors and schedules: `order` lists each bucket's handles
181    /// in its saved order, `saved` each saved entity's bucket (6: none) and last visit time.
182    /// Registered entities the save does not know keep their bucket and follow its listed ones.
183    pub fn restore(
184        &mut self,
185        order: &[Vec<usize>; 5],
186        cursors: [usize; 5],
187        saved: &[(usize, usize, i64)],
188    ) {
189        let listed: std::collections::HashSet<usize> = order
190            .iter()
191            .flatten()
192            .copied()
193            .chain(saved.iter().map(|s| s.0))
194            .collect();
195        let mut lists: [Vec<usize>; 5] = std::array::from_fn(|b| {
196            order[b]
197                .iter()
198                .copied()
199                .filter(|&h| self.contains(h))
200                .collect()
201        });
202        for b in 0..5 {
203            for &h in &self.buckets[b] {
204                if !listed.contains(&h) {
205                    lists[b].push(h);
206                }
207            }
208        }
209        for (b, list) in lists.iter().enumerate() {
210            for (slot, &h) in list.iter().enumerate() {
211                let e = self.entity_mut(h);
212                e.bucket = b;
213                e.slot = slot;
214            }
215        }
216        self.buckets = lists;
217        self.cursors = cursors;
218        let in_lists: std::collections::HashSet<usize> =
219            self.buckets.iter().flatten().copied().collect();
220        for &(h, bucket, t) in saved {
221            if !self.contains(h) {
222                continue;
223            }
224            let e = self.entity_mut(h);
225            e.last_time = t;
226            if !in_lists.contains(&h) {
227                e.bucket = if bucket < 5 { 6 } else { bucket };
228            }
229        }
230    }
231
232    /// The values visited since the last call, each with the time since its previous visit,
233    /// in visiting order (the bucket pass's scheduled components run for these).
234    pub fn take_visits(&mut self) -> Vec<(T, i64)> {
235        std::mem::take(&mut self.visited)
236    }
237
238    /// Advance the clock by `dt` seconds. Then the caller visits each bucket, then removes the
239    /// entities that were deleted.
240    ///
241    /// Original: `FUN_1400c9560` (the clock).
242    pub fn advance(&mut self, dt: f32) {
243        self.time += ticks(dt);
244    }
245
246    /// Visit one bucket: from its cursor, at most its quota of entities or one full round. Each
247    /// visit gives the entity's handle, value and the time since its own last visit. Entities
248    /// registered during the visits wait until the next iteration.
249    ///
250    /// Original: `FUN_1400c9560`.
251    pub fn visit_bucket(&mut self, bucket: usize) -> Vec<(usize, T, i64)> {
252        let list = &self.buckets[bucket];
253        let count = list.len();
254        if count == 0 {
255            return Vec::new();
256        }
257        let mut cursor = if self.cursors[bucket] < count {
258            self.cursors[bucket]
259        } else {
260            0
261        };
262        let mut visits = Vec::with_capacity(QUOTAS[bucket].min(count));
263        let time = self.time;
264        for _ in 0..QUOTAS[bucket].min(count) {
265            let id = self.buckets[bucket][cursor];
266            let entity = self.entity_mut(id);
267            let dt = time - entity.last_time;
268            if entity.live && dt > 0 {
269                entity.last_time = time;
270                let value = entity.value;
271                visits.push((id, value, dt));
272                self.visited.push((value, dt));
273            }
274            cursor = (cursor + 1) % count;
275        }
276        self.cursors[bucket] = cursor;
277        visits
278    }
279
280    /// Remove an entity: it swaps places with the last entity of its bucket, and the cursor does
281    /// not move. Call it after all visits of the iteration, as the original deletes late.
282    ///
283    /// Original: `FUN_1400c8db0`.
284    pub fn remove(&mut self, id: usize) {
285        let entity = self.entity_mut(id);
286        if !entity.live {
287            return;
288        }
289        let (bucket, slot) = (entity.bucket, entity.slot);
290        if bucket < 5 {
291            self.buckets[bucket].swap_remove(slot);
292            if let Some(&moved) = self.buckets[bucket].get(slot) {
293                self.entity_mut(moved).slot = slot;
294            }
295        }
296        self.entity_mut(id).live = false;
297    }
298}
299
300#[cfg(test)]
301mod tests {
302    use super::*;
303
304    #[test]
305    fn quotas_elapsed_time_and_registration() {
306        let mut scheduler = EntityScheduler::default();
307        for i in 0..11 {
308            scheduler.register(i, 3);
309        }
310        scheduler.register(99, 6);
311        scheduler.advance(0.5);
312        let first = scheduler.visit_bucket(3);
313        assert_eq!(
314            first.iter().map(|v| v.1).collect::<Vec<_>>(),
315            [0, 1, 2, 3, 4]
316        );
317        assert!(first.iter().all(|v| v.2 == ticks(0.5)));
318        scheduler.advance(0.5);
319        let second = scheduler.visit_bucket(3);
320        assert_eq!(
321            second.iter().map(|v| v.1).collect::<Vec<_>>(),
322            [5, 6, 7, 8, 9]
323        );
324        assert!(second.iter().all(|v| v.2 == 2 * ticks(0.5)));
325        scheduler.advance(0.5);
326        let third = scheduler.visit_bucket(3);
327        assert_eq!(
328            third.iter().map(|v| v.1).collect::<Vec<_>>(),
329            [10, 0, 1, 2, 3]
330        );
331        assert_eq!(third[0].2, 3 * ticks(0.5));
332        assert_eq!(third[1].2, 2 * ticks(0.5));
333    }
334
335    #[test]
336    fn deletion_preserves_swap_order_and_zero_delta_skips_callbacks() {
337        let mut scheduler = EntityScheduler::default();
338        let ids: Vec<_> = (0..4).map(|i| scheduler.register(i, 4)).collect();
339        assert!(scheduler.visit_bucket(4).is_empty());
340        // Even zero-delta visits move the cursor; the next live visit starts with 2, 3.
341        scheduler.advance(1.0);
342        scheduler.visit_bucket(4);
343        scheduler.remove(ids[1]); // [0, 3, 2], cursor still 0
344        scheduler.advance(1.0);
345        assert_eq!(
346            scheduler
347                .visit_bucket(4)
348                .iter()
349                .map(|v| v.1)
350                .collect::<Vec<_>>(),
351            [0, 3]
352        );
353        scheduler.remove(ids[3]);
354        scheduler.advance(1.0);
355        assert_eq!(
356            scheduler
357                .visit_bucket(4)
358                .iter()
359                .map(|v| v.1)
360                .collect::<Vec<_>>(),
361            [0, 2]
362        );
363    }
364}
banished_core/scheduler.rs

banished_core/
scheduler.rs
