rustsim_spaces/
grid.rs

1//! 2D grid spaces with integer coordinates.
2//!
3//! Two variants are provided:
4//!
5//! - [`Grid2D`] - multi-occupancy: each cell can hold any number of agents.
6//! - [`Grid2DSingle`] - single-occupancy: each cell holds at most one agent.
7//!
8//! Both support periodic (toroidal) and non-periodic (bounded) boundaries.
9//! Neighbor queries use Chebyshev distance (8-connected / square neighborhood).
10//!
11//! Mirrors Julia Agents.jl `GridSpace` and `GridSpaceSingle`.
12
13use rand::Rng;
14use rustsim_core::{
15    interaction::{PositionedAgent, SpaceInteraction},
16    space::Space,
17    types::AgentId,
18};
19use thiserror::Error;
20
21/// Position on a 2D grid: `(x, y)` with `0 ? x < width`, `0 ? y < height`.
22pub type GridPos2 = (usize, usize);
23
24/// Errors returned by grid space operations.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
26pub enum GridError {
27    /// The position is outside the grid bounds (and the grid is not periodic).
28    #[error("position ({}, {}) is out of bounds", .0.0, .0.1)]
29    OutOfBounds(GridPos2),
30    /// The cell is already occupied (single-occupancy grid only).
31    #[error("position ({}, {}) is already occupied", .0.0, .0.1)]
32    Occupied(GridPos2),
33}
34
35/// Multi-occupancy 2D grid space.
36///
37/// Each cell can hold an arbitrary number of agents. Backed by a flat
38/// `Vec<Vec<AgentId>>` of size `width x height`.
39///
40/// # Boundary modes
41///
42/// - `periodic = true` - toroidal wrapping (positions are taken modulo grid size).
43/// - `periodic = false` - bounded (out-of-bounds positions return an error).
44#[derive(Debug, Clone)]
45pub struct Grid2D {
46    width: usize,
47    height: usize,
48    periodic: bool,
49    cells: Vec<Vec<AgentId>>,
50}
51
52impl Grid2D {
53    /// Create a new multi-occupancy grid.
54    ///
55    /// # Panics
56    ///
57    /// Panics if `width` or `height` is zero.
58    pub fn new(width: usize, height: usize, periodic: bool) -> Self {
59        assert!(width > 0 && height > 0, "grid dimensions must be positive");
60        let cells = vec![Vec::new(); width * height];
61        Self {
62            width,
63            height,
64            periodic,
65            cells,
66        }
67    }
68
69    /// Grid dimensions as `(width, height)`.
70    pub fn dimensions(&self) -> (usize, usize) {
71        (self.width, self.height)
72    }
73
74    /// Whether the grid wraps around (toroidal boundaries).
75    pub fn periodic(&self) -> bool {
76        self.periodic
77    }
78
79    /// Check whether a position is within the grid bounds.
80    pub fn is_in_bounds(&self, pos: GridPos2) -> bool {
81        pos.0 < self.width && pos.1 < self.height
82    }
83
84    /// Check whether a cell has no agents.
85    pub fn is_empty(&self, pos: GridPos2) -> bool {
86        match self.normalize_pos(pos) {
87            Some(pos) => self.cells[self.index(pos)].is_empty(),
88            None => true,
89        }
90    }
91
92    /// Return the agent IDs at a given position, or `None` if out of bounds.
93    pub fn ids_in_position(&self, pos: GridPos2) -> Option<&[AgentId]> {
94        let pos = self.normalize_pos(pos)?;
95        Some(&self.cells[self.index(pos)])
96    }
97
98    /// Register an agent at a position.
99    pub fn add_agent(&mut self, pos: GridPos2, id: AgentId) -> Result<(), GridError> {
100        let pos = self.normalize_pos(pos).ok_or(GridError::OutOfBounds(pos))?;
101        let index = self.index(pos);
102        self.cells[index].push(id);
103        Ok(())
104    }
105
106    /// Deregister an agent from a position. Returns `Ok(true)` if found and removed.
107    pub fn remove_agent(&mut self, pos: GridPos2, id: AgentId) -> Result<bool, GridError> {
108        let pos = self.normalize_pos(pos).ok_or(GridError::OutOfBounds(pos))?;
109        let index = self.index(pos);
110        let cell = &mut self.cells[index];
111        if let Some(index) = cell.iter().position(|value| *value == id) {
112            cell.swap_remove(index);
113            Ok(true)
114        } else {
115            Ok(false)
116        }
117    }
118
119    fn normalize_pos(&self, pos: GridPos2) -> Option<GridPos2> {
120        if self.periodic {
121            Some((pos.0 % self.width, pos.1 % self.height))
122        } else if self.is_in_bounds(pos) {
123            Some(pos)
124        } else {
125            None
126        }
127    }
128
129    fn index(&self, pos: GridPos2) -> usize {
130        pos.1 * self.width + pos.0
131    }
132}
133
134impl Space for Grid2D {}
135
136impl<A> SpaceInteraction<A> for Grid2D
137where
138    A: PositionedAgent<Position = GridPos2>,
139{
140    type Error = GridError;
141
142    fn random_position<R: rand::RngCore>(&self, rng: &mut R) -> A::Position {
143        let x = rng.gen_range(0..self.width);
144        let y = rng.gen_range(0..self.height);
145        (x, y)
146    }
147
148    fn add_agent(&mut self, agent: &A) -> Result<(), Self::Error> {
149        self.add_agent(*agent.position(), agent.id())
150    }
151
152    fn remove_agent(&mut self, agent: &A) -> Result<(), Self::Error> {
153        self.remove_agent(*agent.position(), agent.id()).map(|_| ())
154    }
155
156    fn nearby_ids(&self, position: &A::Position, radius: usize) -> Vec<AgentId> {
157        let mut ids = Vec::new();
158        let radius = radius as i32;
159        let (cx, cy) = (position.0 as i32, position.1 as i32);
160        for dy in -radius..=radius {
161            for dx in -radius..=radius {
162                let x = cx + dx;
163                let y = cy + dy;
164                let pos = if self.periodic {
165                    let px = ((x % self.width as i32) + self.width as i32) % self.width as i32;
166                    let py = ((y % self.height as i32) + self.height as i32) % self.height as i32;
167                    Some((px as usize, py as usize))
168                } else if x >= 0 && y >= 0 && x < self.width as i32 && y < self.height as i32 {
169                    Some((x as usize, y as usize))
170                } else {
171                    None
172                };
173
174                if let Some(pos) = pos {
175                    ids.extend(self.cells[self.index(pos)].iter().copied());
176                }
177            }
178        }
179        ids
180    }
181}
182
183/// Single-occupancy 2D grid space.
184///
185/// Each cell holds at most one agent. Attempting to add an agent to an
186/// occupied cell returns [`GridError::Occupied`].
187///
188/// Backed by a flat `Vec<Option<AgentId>>` of size `width x height`.
189#[derive(Debug, Clone)]
190pub struct Grid2DSingle {
191    width: usize,
192    height: usize,
193    periodic: bool,
194    cells: Vec<Option<AgentId>>,
195}
196
197impl Grid2DSingle {
198    /// Create a new single-occupancy grid.
199    ///
200    /// # Panics
201    ///
202    /// Panics if `width` or `height` is zero.
203    pub fn new(width: usize, height: usize, periodic: bool) -> Self {
204        assert!(width > 0 && height > 0, "grid dimensions must be positive");
205        let cells = vec![None; width * height];
206        Self {
207            width,
208            height,
209            periodic,
210            cells,
211        }
212    }
213
214    /// Grid dimensions as `(width, height)`.
215    pub fn dimensions(&self) -> (usize, usize) {
216        (self.width, self.height)
217    }
218
219    /// Whether the grid wraps around (toroidal boundaries).
220    pub fn periodic(&self) -> bool {
221        self.periodic
222    }
223
224    /// Check whether a position is within the grid bounds.
225    pub fn is_in_bounds(&self, pos: GridPos2) -> bool {
226        pos.0 < self.width && pos.1 < self.height
227    }
228
229    /// Check whether a cell is unoccupied.
230    pub fn is_empty(&self, pos: GridPos2) -> bool {
231        match self.normalize_pos(pos) {
232            Some(pos) => self.cells[self.index(pos)].is_none(),
233            None => true,
234        }
235    }
236
237    /// Return the agent ID at a given position, or `None` if empty or out of bounds.
238    pub fn id_in_position(&self, pos: GridPos2) -> Option<AgentId> {
239        let pos = self.normalize_pos(pos)?;
240        self.cells[self.index(pos)]
241    }
242
243    /// Register an agent at a position. Returns [`GridError::Occupied`] if the cell is taken.
244    pub fn add_agent(&mut self, pos: GridPos2, id: AgentId) -> Result<(), GridError> {
245        let pos = self.normalize_pos(pos).ok_or(GridError::OutOfBounds(pos))?;
246        let index = self.index(pos);
247        let cell = &mut self.cells[index];
248        if cell.is_some() {
249            return Err(GridError::Occupied(pos));
250        }
251        *cell = Some(id);
252        Ok(())
253    }
254
255    /// Deregister an agent from a position. Returns `Ok(true)` if found and removed.
256    pub fn remove_agent(&mut self, pos: GridPos2, id: AgentId) -> Result<bool, GridError> {
257        let pos = self.normalize_pos(pos).ok_or(GridError::OutOfBounds(pos))?;
258        let index = self.index(pos);
259        let cell = &mut self.cells[index];
260        if cell == &Some(id) {
261            *cell = None;
262            Ok(true)
263        } else {
264            Ok(false)
265        }
266    }
267
268    fn normalize_pos(&self, pos: GridPos2) -> Option<GridPos2> {
269        if self.periodic {
270            Some((pos.0 % self.width, pos.1 % self.height))
271        } else if self.is_in_bounds(pos) {
272            Some(pos)
273        } else {
274            None
275        }
276    }
277
278    fn index(&self, pos: GridPos2) -> usize {
279        pos.1 * self.width + pos.0
280    }
281}
282
283impl Space for Grid2DSingle {}
284
285impl<A> SpaceInteraction<A> for Grid2DSingle
286where
287    A: PositionedAgent<Position = GridPos2>,
288{
289    type Error = GridError;
290
291    fn random_position<R: rand::RngCore>(&self, rng: &mut R) -> A::Position {
292        let x = rng.gen_range(0..self.width);
293        let y = rng.gen_range(0..self.height);
294        (x, y)
295    }
296
297    fn add_agent(&mut self, agent: &A) -> Result<(), Self::Error> {
298        self.add_agent(*agent.position(), agent.id())
299    }
300
301    fn remove_agent(&mut self, agent: &A) -> Result<(), Self::Error> {
302        self.remove_agent(*agent.position(), agent.id()).map(|_| ())
303    }
304
305    fn nearby_ids(&self, position: &A::Position, radius: usize) -> Vec<AgentId> {
306        let mut ids = Vec::new();
307        let radius = radius as i32;
308        let (cx, cy) = (position.0 as i32, position.1 as i32);
309        for dy in -radius..=radius {
310            for dx in -radius..=radius {
311                let x = cx + dx;
312                let y = cy + dy;
313                let pos = if self.periodic {
314                    let px = ((x % self.width as i32) + self.width as i32) % self.width as i32;
315                    let py = ((y % self.height as i32) + self.height as i32) % self.height as i32;
316                    Some((px as usize, py as usize))
317                } else if x >= 0 && y >= 0 && x < self.width as i32 && y < self.height as i32 {
318                    Some((x as usize, y as usize))
319                } else {
320                    None
321                };
322
323                if let Some(pos) = pos {
324                    if let Some(id) = self.cells[self.index(pos)] {
325                        ids.push(id);
326                    }
327                }
328            }
329        }
330        ids
331    }
332}
rustsim_spaces/grid.rs

rustsim_spaces/
grid.rs
