psx_residency_sim/
world.rs

1//! Region graphs and routes for the simulator.
2
3use alloc::collections::BinaryHeap;
4use alloc::vec;
5use alloc::vec::Vec;
6use core::cmp::Reverse;
7
8/// Ticks per second the simulator's clocks run at (60 Hz NTSC).
9pub const TICKS_PER_SECOND: u32 = 60;
10
11/// One region: how big it is and where the cooker put it on the disc.
12#[derive(Copy, Clone, Debug, PartialEq, Eq)]
13pub struct SimRegion {
14    /// Sectors (and pages: one page per sector).
15    pub sectors: u32,
16    /// First sector on the disc.
17    pub lba: u32,
18}
19
20/// Regions, the walk distance between neighbours, and for each region the set
21/// of regions that must be resident while the player is in it (the cooker's
22/// closure `V(R)`).
23#[derive(Clone, Debug, Default)]
24pub struct RegionGraph {
25    regions: Vec<SimRegion>,
26    edges: Vec<Vec<(u32, u32)>>,
27    needs: Vec<Vec<u32>>,
28}
29
30impl RegionGraph {
31    /// An empty graph.
32    pub fn new() -> Self {
33        Self::default()
34    }
35
36    /// A chain of `count` regions of `sectors` sectors, neighbours `length`
37    /// units apart, each needing itself only until [`Self::needs_with_neighbors`].
38    pub fn chain(count: u32, sectors: u32, length: u32) -> Self {
39        let mut graph = Self::new();
40        for _ in 0..count {
41            graph.add_region(sectors);
42        }
43        for region in 1..count {
44            graph.connect(region - 1, region, length);
45        }
46        graph.layout_in_order(0, 0);
47        graph
48    }
49
50    /// A `width` x `height` grid, row-major on disc, neighbours `length` apart.
51    pub fn grid(width: u32, height: u32, sectors: u32, length: u32) -> Self {
52        let mut graph = Self::new();
53        for _ in 0..width * height {
54            graph.add_region(sectors);
55        }
56        for y in 0..height {
57            for x in 0..width {
58                let here = y * width + x;
59                if x + 1 < width {
60                    graph.connect(here, here + 1, length);
61                }
62                if y + 1 < height {
63                    graph.connect(here, here + width, length);
64                }
65            }
66        }
67        graph.layout_in_order(0, 0);
68        graph
69    }
70
71    /// Add a region; returns its id (ids are dense from 0). Its disc position
72    /// is set by [`Self::layout_in_order`] or [`Self::place`].
73    pub fn add_region(&mut self, sectors: u32) -> u32 {
74        self.regions.push(SimRegion { sectors, lba: 0 });
75        self.edges.push(Vec::new());
76        let id = self.regions.len() as u32 - 1;
77        self.needs.push(vec![id]);
78        id
79    }
80
81    /// Put `region` at sector `lba`.
82    pub fn place(&mut self, region: u32, lba: u32) {
83        self.regions[region as usize].lba = lba;
84    }
85
86    /// Lay regions out in id order from `start_lba`, `gap` sectors apart.
87    pub fn layout_in_order(&mut self, start_lba: u32, gap: u32) {
88        let mut lba = start_lba;
89        for region in &mut self.regions {
90            region.lba = lba;
91            lba += region.sectors + gap;
92        }
93    }
94
95    /// Connect two regions both ways, `length` units apart.
96    pub fn connect(&mut self, a: u32, b: u32, length: u32) {
97        self.edges[a as usize].push((b, length));
98        self.edges[b as usize].push((a, length));
99    }
100
101    /// Set the regions that must be resident while the player is in `region`.
102    pub fn set_needs(&mut self, region: u32, needs: &[u32]) {
103        self.needs[region as usize] = needs.to_vec();
104    }
105
106    /// Every region needs itself and its direct neighbours.
107    pub fn needs_with_neighbors(&mut self) {
108        for region in 0..self.regions.len() {
109            let mut needs = vec![region as u32];
110            needs.extend(self.edges[region].iter().map(|&(to, _)| to));
111            self.needs[region] = needs;
112        }
113    }
114
115    /// Number of regions.
116    pub fn region_count(&self) -> usize {
117        self.regions.len()
118    }
119
120    /// Region `id`.
121    pub fn region(&self, id: u32) -> SimRegion {
122        self.regions[id as usize]
123    }
124
125    /// Regions needed while the player is in `region`.
126    pub fn needs(&self, region: u32) -> &[u32] {
127        &self.needs[region as usize]
128    }
129
130    /// Edge length between two neighbours.
131    pub fn edge_length(&self, a: u32, b: u32) -> Option<u32> {
132        self.edges[a as usize]
133            .iter()
134            .find(|&&(to, _)| to == b)
135            .map(|&(_, length)| length)
136    }
137
138    /// Total sectors of all regions.
139    pub fn total_sectors(&self) -> u64 {
140        self.regions.iter().map(|r| r.sectors as u64).sum()
141    }
142
143    /// Walk distance from `from` to every region (Dijkstra over edge
144    /// lengths); `u32::MAX` for unreachable regions.
145    pub fn distances_from(&self, from: u32) -> Vec<u32> {
146        let mut best = vec![u32::MAX; self.regions.len()];
147        let mut heap = BinaryHeap::new();
148        best[from as usize] = 0;
149        heap.push(Reverse((0u32, from)));
150        while let Some(Reverse((distance, region))) = heap.pop() {
151            if distance > best[region as usize] {
152                continue;
153            }
154            for &(to, length) in &self.edges[region as usize] {
155                let next = distance.saturating_add(length);
156                if next < best[to as usize] {
157                    best[to as usize] = next;
158                    heap.push(Reverse((next, to)));
159                }
160            }
161        }
162        best
163    }
164}
165
166/// The player is in `region` from `tick` on.
167#[derive(Copy, Clone, Debug, PartialEq, Eq)]
168pub struct RouteSample {
169    /// Tick the player enters the region.
170    pub tick: u32,
171    /// The region.
172    pub region: u32,
173}
174
175/// Positions over time: a list of region entries in tick order.
176#[derive(Clone, Debug, Default)]
177pub struct Route {
178    samples: Vec<RouteSample>,
179    end_tick: u32,
180}
181
182impl Route {
183    /// A route from explicit samples (sorted by tick) ending at `end_tick`.
184    pub fn from_samples(samples: Vec<RouteSample>, end_tick: u32) -> Self {
185        debug_assert!(samples.windows(2).all(|w| w[0].tick <= w[1].tick));
186        Self { samples, end_tick }
187    }
188
189    /// Walk `path` (consecutive regions must be neighbours) at
190    /// `units_per_second`, entering each region when the previous edge is
191    /// covered; the route ends one second after the last entry.
192    pub fn walk(graph: &RegionGraph, path: &[u32], units_per_second: u32) -> Self {
193        let mut samples = Vec::new();
194        let mut distance = 0u64;
195        for (index, &region) in path.iter().enumerate() {
196            if index > 0 {
197                distance += graph
198                    .edge_length(path[index - 1], region)
199                    .expect("route steps must follow edges") as u64;
200            }
201            let tick = distance * TICKS_PER_SECOND as u64 / units_per_second.max(1) as u64;
202            samples.push(RouteSample {
203                tick: tick as u32,
204                region,
205            });
206        }
207        let end_tick = samples.last().map_or(0, |s| s.tick) + TICKS_PER_SECOND;
208        Self { samples, end_tick }
209    }
210
211    /// The samples.
212    pub fn samples(&self) -> &[RouteSample] {
213        &self.samples
214    }
215
216    /// Last tick (exclusive).
217    pub fn end_tick(&self) -> u32 {
218        self.end_tick
219    }
220
221    /// The region the player is in at `tick`.
222    pub fn region_at(&self, tick: u32) -> Option<u32> {
223        let at = self.samples.partition_point(|s| s.tick <= tick);
224        at.checked_sub(1).map(|i| self.samples[i].region)
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231
232    #[test]
233    fn dijkstra_follows_edge_lengths() {
234        let mut graph = RegionGraph::new();
235        for _ in 0..4 {
236            graph.add_region(1);
237        }
238        graph.connect(0, 1, 10);
239        graph.connect(1, 2, 10);
240        graph.connect(0, 2, 50);
241        let distances = graph.distances_from(0);
242        assert_eq!(&distances[..3], &[0, 10, 20]);
243        assert_eq!(distances[3], u32::MAX);
244    }
245
246    #[test]
247    fn grid_and_layout() {
248        let mut graph = RegionGraph::grid(3, 2, 8, 100);
249        assert_eq!(graph.region_count(), 6);
250        assert_eq!(graph.region(4).lba, 32);
251        graph.layout_in_order(1000, 2);
252        assert_eq!(graph.region(1).lba, 1010);
253        graph.needs_with_neighbors();
254        assert_eq!(graph.needs(0), &[0, 1, 3]);
255        assert_eq!(graph.distances_from(0)[5], 300);
256    }
257
258    #[test]
259    fn a_walk_enters_regions_at_the_right_ticks() {
260        let graph = RegionGraph::chain(4, 4, 300);
261        // 300 units/s: one edge per second.
262        let route = Route::walk(&graph, &[0, 1, 2, 3], 300);
263        let ticks: Vec<u32> = route.samples().iter().map(|s| s.tick).collect();
264        assert_eq!(ticks, [0, 60, 120, 180]);
265        assert_eq!(route.region_at(59), Some(0));
266        assert_eq!(route.region_at(60), Some(1));
267        assert_eq!(route.region_at(10_000), Some(3));
268        assert_eq!(route.end_tick(), 240);
269    }
270}
psx_residency_sim/world.rs

psx_residency_sim/
world.rs
