rpfm_extensions/startpos/
vision.rs

1//---------------------------------------------------------------------------//
2// Copyright (c) 2017-2026 Ismael Gutiérrez González. All rights reserved.
3//
4// This file is part of the Rusted PackFile Manager (RPFM) project,
5// which can be found here: https://github.com/Frodo45127/rpfm.
6//
7// This file is licensed under the MIT license, which can be found here:
8// https://github.com/Frodo45127/rpfm/blob/master/LICENSE.
9//---------------------------------------------------------------------------//
10
11//! Vision areas of a startpos (`LINE_OF_SIGHT` and `CAMPAIGN_SHROUD` records) and their quad tree encoding.
12//!
13//! Vision lives on a square grid of half world units over the campaign map, rounded to whole cells (1357x1112 cells
14//! in Attila; both sides are stretched to fit the map exactly). The startpos stores an area as a quad tree over a power-of-two square that
15//! covers the grid, with its rows counted from the top:
16//!
17//! - A node with children is a byte with the code of each child in two bits, the first child in the lowest bits
18//!   (1: mixed, 2: empty, 3: full), followed by its mixed children. Children are the top-left, top-right,
19//!   bottom-left and bottom-right quarters.
20//! - A node without children (the 8x8 cells at the bottom of the tree) is a 0 byte followed by 8 bytes, one per row
21//!   from the bottom, with the leftmost cell in the lowest bit. An empty area is a single such node.
22
23use std::collections::HashSet;
24
25#[cfg(test)] #[path = "vision_test.rs"] pub(crate) mod vision_test;
26
27/// World units per vision cell, horizontally.
28const CELL_SIZE: f32 = 0.5;
29
30/// Cells per side of a quad tree leaf.
31const LEAF_SIZE: u32 = 8;
32
33/// Child codes of a quad tree node.
34const MIXED: u8 = 1;
35const EMPTY: u8 = 2;
36const FULL: u8 = 3;
37
38//---------------------------------------------------------------------------//
39//                              Types
40//---------------------------------------------------------------------------//
41
42/// World bounds of an area: its corner closest to the origin and the opposite one.
43pub type WorldBounds = ((f32, f32), (f32, f32));
44
45/// The vision grid of a campaign map.
46#[derive(Debug, Clone, Copy, PartialEq)]
47pub struct VisionGrid {
48
49    /// Columns.
50    width: u32,
51
52    /// Rows.
53    height: u32,
54
55    /// World units per cell, horizontally and vertically.
56    cell_size: (f32, f32),
57
58    /// Size of the map in world units.
59    world_size: (f32, f32),
60
61    /// Side of the quad tree square.
62    tree_size: u32,
63}
64
65/// An area of the vision grid: a set of cells (column, row from the bottom).
66#[derive(Debug, Clone, PartialEq, Eq, Default)]
67pub struct Vision {
68    cells: HashSet<(u32, u32)>,
69}
70
71//---------------------------------------------------------------------------//
72//                              Implementations
73//---------------------------------------------------------------------------//
74
75impl VisionGrid {
76
77    /// Creates the vision grid of a map of the given size in world units.
78    pub fn new(world_size: (f32, f32)) -> Self {
79        let width = (world_size.0 / CELL_SIZE).round().max(1.0) as u32;
80        let height = (world_size.1 / CELL_SIZE).round().max(1.0) as u32;
81        Self {
82            width,
83            height,
84            cell_size: (world_size.0 / width as f32, world_size.1 / height as f32),
85            world_size,
86            tree_size: width.max(height).max(LEAF_SIZE).next_power_of_two(),
87        }
88    }
89
90    /// Returns the columns, rows and quad tree side, as the `QUAD_TREE_BIT_ARRAY` records store them.
91    pub fn dimensions(&self) -> (u32, u32, u32) {
92        (self.width, self.height, self.tree_size)
93    }
94
95    /// Returns the cell containing a world position.
96    pub fn cell_at(&self, position: (f32, f32)) -> (u32, u32) {
97        ((position.0 / self.cell_size.0).max(0.0) as u32, (position.1 / self.cell_size.1).max(0.0) as u32)
98    }
99
100    /// Returns the world position of a cell's corner closest to the origin: the cell times the map size, over the
101    /// cells of the grid. This gives the game's floats horizontally, and vertically in 3 of 4 cases.
102    pub fn cell_position(&self, cell: (u32, u32)) -> (f32, f32) {
103        ((cell.0 as f32 * self.world_size.0) / self.width as f32, (cell.1 as f32 * self.world_size.1) / self.height as f32)
104    }
105
106    /// Returns what a character sees: the cells within its sight radius around its cell, counting the radius in
107    /// horizontal cells. A cell `(dx, dy)` away is in if `dx² + dy² <= r * (r + 1)`.
108    pub fn disk(&self, position: (f32, f32), radius: f32) -> Vision {
109        let (cx, cy) = self.cell_at(position);
110        let r = (radius / self.cell_size.0).round() as i64;
111        let limit = r * (r + 1);
112        let mut cells = HashSet::new();
113        for dx in -r..=r {
114            for dy in -r..=r {
115                let (x, y) = (i64::from(cx) + dx, i64::from(cy) + dy);
116                if dx * dx + dy * dy <= limit && self.contains(x, y) {
117                    cells.insert((x as u32, y as u32));
118                }
119            }
120        }
121        Vision { cells }
122    }
123
124    /// Returns the cells whose centre is within a radius of any of the given world positions.
125    pub fn around(&self, positions: &[(f32, f32)], radius: f32) -> Vision {
126        let mut cells = HashSet::new();
127        for &(px, py) in positions {
128            let (x0, y0) = self.cell_at((px - radius, py - radius));
129            let (x1, y1) = self.cell_at((px + radius, py + radius));
130            for x in x0..=x1 {
131                for y in y0..=y1 {
132                    let (cx, cy) = ((x as f32 + 0.5) * self.cell_size.0, (y as f32 + 0.5) * self.cell_size.1);
133                    if (cx - px).powi(2) + (cy - py).powi(2) <= radius * radius && self.contains(i64::from(x), i64::from(y)) {
134                        cells.insert((x, y));
135                    }
136                }
137            }
138        }
139        Vision { cells }
140    }
141
142    /// Returns the cells of a world rectangle whose corner closest to the origin passes a test. The rectangle is
143    /// snapped outwards to the grid, as the game does.
144    ///
145    /// # Arguments
146    ///
147    /// * `min` - Corner of the rectangle closest to the origin.
148    /// * `max` - Opposite corner of the rectangle.
149    /// * `keep` - Test on the world position of each cell's corner.
150    ///
151    /// # Returns
152    ///
153    /// The area, and the world bounds of the snapped rectangle.
154    pub fn cells_where(&self, min: (f32, f32), max: (f32, f32), mut keep: impl FnMut((f32, f32)) -> bool) -> (Vision, WorldBounds) {
155        let first = self.cell_at(min);
156        let last = self.cell_at(max);
157        let last = (last.0.min(self.width - 1), last.1.min(self.height - 1));
158        let mut cells = HashSet::new();
159        for x in first.0..=last.0 {
160            for y in first.1..=last.1 {
161                if keep(self.cell_position((x, y))) {
162                    cells.insert((x, y));
163                }
164            }
165        }
166        (Vision { cells }, (self.cell_position(first), self.cell_position((last.0 + 1, last.1 + 1))))
167    }
168
169    /// Returns if a cell is inside the grid.
170    fn contains(&self, x: i64, y: i64) -> bool {
171        (0..i64::from(self.width)).contains(&x) && (0..i64::from(self.height)).contains(&y)
172    }
173}
174
175impl Vision {
176
177    /// Returns if the area has no cells.
178    pub fn is_empty(&self) -> bool {
179        self.cells.is_empty()
180    }
181
182    /// Returns if the area has a cell.
183    pub fn contains(&self, cell: (u32, u32)) -> bool {
184        self.cells.contains(&cell)
185    }
186
187    /// Adds the cells of another area to this one.
188    pub fn extend(&mut self, other: &Vision) {
189        self.cells.extend(other.cells.iter().copied());
190    }
191
192    /// Returns the world bounds of the area: the corner of its first cell and the far corner of its last one.
193    pub fn bounds(&self, grid: &VisionGrid) -> Option<WorldBounds> {
194        let min_x = self.cells.iter().map(|cell| cell.0).min()?;
195        let min_y = self.cells.iter().map(|cell| cell.1).min()?;
196        let max_x = self.cells.iter().map(|cell| cell.0).max()?;
197        let max_y = self.cells.iter().map(|cell| cell.1).max()?;
198        Some((grid.cell_position((min_x, min_y)), grid.cell_position((max_x + 1, max_y + 1))))
199    }
200
201    /// Encodes the area as the quad tree of a `QUAD_TREE_BIT_ARRAY` record (see the module docs).
202    pub fn encode(&self, grid: &VisionGrid) -> Vec<u8> {
203        let mut bytes = vec![];
204        let cells = self.cells.iter().map(|&(x, y)| (x, grid.tree_size - 1 - y)).collect::<Vec<_>>();
205        if cells.is_empty() {
206            bytes.resize(1 + LEAF_SIZE as usize, 0);
207        } else {
208            encode_node((0, 0, grid.tree_size), cells, &mut bytes);
209        }
210        bytes
211    }
212}
213
214/// Encodes a mixed node of the quad tree: (column, row from the top, side), with its cells (also counted from the
215/// top). Each node splits its cells among its children, so the whole tree takes one pass per level.
216fn encode_node((x, y, size): (u32, u32, u32), cells: Vec<(u32, u32)>, bytes: &mut Vec<u8>) {
217    if size == LEAF_SIZE {
218        let mut rows = [0u8; LEAF_SIZE as usize];
219        for (cell_x, cell_y) in cells {
220            rows[(cell_y - y) as usize] |= 1 << (cell_x - x);
221        }
222        bytes.push(0);
223        bytes.extend(rows.iter().rev());
224        return;
225    }
226
227    let half = size / 2;
228    let mut children = [(x, y, vec![]), (x + half, y, vec![]), (x, y + half, vec![]), (x + half, y + half, vec![])];
229    for cell in cells {
230        let index = usize::from(cell.0 >= x + half) + 2 * usize::from(cell.1 >= y + half);
231        children[index].2.push(cell);
232    }
233
234    let code = |count: usize| match count {
235        0 => EMPTY,
236        count if count == (half * half) as usize => FULL,
237        _ => MIXED,
238    };
239    bytes.push(children.iter().enumerate().fold(0, |byte, (index, child)| byte | code(child.2.len()) << (2 * index)));
240    for (child_x, child_y, child_cells) in children {
241        if code(child_cells.len()) == MIXED {
242            encode_node((child_x, child_y, half), child_cells, bytes);
243        }
244    }
245}
rpfm_extensions/startpos/vision.rs

rpfm_extensions/startpos/
vision.rs
