//! The read side of the behavior engine: a per-pass owned snapshot of enemy state plus the
//! broad-phase grid and the `SpatialQuery` that behaviors use to *know* about entities they
//! aren't directly touching. Behaviors that *act* go through the command buffer instead.
use macroquad::math::Vec2;
use crate::enemy::Enemy;
use crate::world::EntityId;
fn dist2(a: Vec2, b: Vec2) -> f32 {
let d = a - b;
d.x * d.x + d.y * d.y
}
pub struct Grid {
cell_size: f32,
cols: i32,
rows: i32,
cells: Vec<Vec<u32>>, // each cell holds indices INTO the snapshot slice, not EntityIds
}
impl Grid {
pub fn new(width: f32, height: f32, cell_size: f32) -> Grid {
// cell_size ≈ a typical query radius: too small and one query touches many cells,
// too large and every enemy lands in one cell, degrading back toward O(n²).
let cols = (width / cell_size).ceil() as i32;
let rows = (height / cell_size).ceil() as i32;
Grid {
cell_size,
cols,
rows,
cells: vec![Vec::new(); (cols * rows) as usize],
}
}
fn coords(&self, p: Vec2) -> (i32, i32) {
((p.x / self.cell_size) as i32, (p.y / self.cell_size) as i32)
}
/// Clear and re-bucket every snapshot row. Called once per pass, before any query.
/// `clear()` keeps capacity, so the only steady-state cost is the re-insert walk.
pub fn rebuild(&mut self, snapshot: &[EnemySnapshot]) {
for c in &mut self.cells {
c.clear();
}
for (i, e) in snapshot.iter().enumerate() {
let (cx, cy) = self.coords(e.pos);
let cx = cx.clamp(0, self.cols - 1);
let cy = cy.clamp(0, self.rows - 1);
self.cells[(cy * self.cols + cx) as usize].push(i as u32);
}
}
/// Snapshot indices from every cell overlapping the box `center ± r`. Each enemy lives
/// in exactly one cell and the cells are disjoint, so no index is yielded twice — the
/// caller still does the exact circle test, this just narrows the field.
fn candidates_in_box(&self, center: Vec2, r: f32) -> impl Iterator<Item = u32> + '_ {
let (x0, y0) = self.coords(Vec2 {
x: center.x - r,
y: center.y - r,
});
let (x1, y1) = self.coords(Vec2 {
x: center.x + r,
y: center.y + r,
});
let x0 = x0.max(0);
let y0 = y0.max(0);
let x1 = x1.min(self.cols - 1);
let y1 = y1.min(self.rows - 1);
(y0..=y1)
.flat_map(move |cy| (x0..=x1).map(move |cx| (cx, cy)))
.flat_map(move |(cx, cy)| self.cells[(cy * self.cols + cx) as usize].iter().copied())
}
}
#[derive(Clone, Copy)]
pub struct EnemySnapshot {
pub id: EntityId,
pub pos: Vec2,
pub hp: f32,
pub radius: f32,
}
impl EnemySnapshot {
/// Built once per pass. In practice this also feeds the broad-phase grid that the
/// collision step needs anyway, so the snapshot is nearly free — we're reusing work.
pub fn collect(enemies: &[Enemy]) -> Vec<EnemySnapshot> {
enemies
.iter()
.map(|e| EnemySnapshot {
id: e.id,
pos: e.pos,
hp: e.hp,
radius: e.radius,
})
.collect()
}
}
/// A handle returned BY queries. It's a snapshot row, not a borrow — so a behavior can
/// hold it, then act on it by id through the command buffer (`cmd.damage(r.id, …)`).
/// Read by snapshot, write by id: that's how a behavior affects an enemy it never
/// physically collided with.
#[derive(Clone, Copy)]
pub struct EnemyRef {
pub id: EntityId,
pub pos: Vec2,
pub hp: f32,
}
impl From<&EnemySnapshot> for EnemyRef {
fn from(s: &EnemySnapshot) -> Self {
EnemyRef {
id: s.id,
pos: s.pos,
hp: s.hp,
}
}
}
/// Read-only spatial index handed to behaviors via the context. Backed by the owned
/// snapshot slice + the world's broad-phase grid.
///
/// Staleness note: this view is up to one frame old (a just-killed enemy may still be
/// listed). That's invisible for "nearest"/"in radius" decisions and not worth the cost
/// of keeping it perfectly live — behaviors that *act* go through `cmd`, which applies
/// against the real, current world.
pub struct SpatialQuery<'a> {
enemies: &'a [EnemySnapshot],
grid: &'a Grid,
}
impl<'a> SpatialQuery<'a> {
pub fn new(enemies: &'a [EnemySnapshot], grid: &'a Grid) -> Self {
SpatialQuery { enemies, grid }
}
/// Nearest enemy to `from`, excluding one id. A search box of half-extent `r` only
/// *guarantees* coverage out to distance `r` (its inscribed circle), so a candidate
/// found at distance `d > r` could still be beaten by one sitting in a cell just
/// outside the box. Widen until the best found is within the guaranteed radius (or the
/// grid is exhausted), so the result is the true nearest, not merely the nearest in the
/// first box scanned.
pub fn nearest_enemy(&self, from: Vec2, exclude: EntityId) -> Option<EnemyRef> {
let reach = self.grid.cell_size * self.grid.cols.max(self.grid.rows) as f32;
let mut r = self.grid.cell_size;
loop {
let best = self
.grid
.candidates_in_box(from, r)
.map(|i| &self.enemies[i as usize])
.filter(|s| s.id != exclude)
.map(|s| (dist2(s.pos, from), s))
.min_by(|a, b| a.0.total_cmp(&b.0));
match best {
Some((d2, s)) if d2.sqrt() <= r || r >= reach => return Some(EnemyRef::from(s)),
None if r >= reach => return None,
_ => r += self.grid.cell_size,
}
}
}
/// Enemies whose centre lies within `r` of `center`. Gathers only the cells the
/// circle's bounding box touches, then applies the exact distance test.
pub fn enemies_in_radius(&self, center: Vec2, r: f32) -> impl Iterator<Item = EnemyRef> + '_ {
let enemies = self.enemies;
self.grid
.candidates_in_box(center, r)
.map(move |i| &enemies[i as usize])
.filter(move |s| dist2(s.pos, center) <= r * r)
.map(EnemyRef::from)
}
/// Collision narrow-phase: the nearest enemy whose body overlaps a circle of `radius`
/// at `pos`. Unlike `enemies_in_radius` this accounts for each enemy's own radius, so
/// it needs the snapshot's `radius` field (which `EnemyRef` omits) — hence it returns
/// an id. The box is padded by one cell so an enemy whose centre sits in a neighbour
/// cell but whose body reaches `pos` is still found (holds while enemy radius ≤ cell_size).
pub fn first_hit(&self, pos: Vec2, radius: f32) -> Option<EntityId> {
let reach = radius + self.grid.cell_size;
self.grid
.candidates_in_box(pos, reach)
.map(|i| &self.enemies[i as usize])
.filter(|s| dist2(s.pos, pos) <= (radius + s.radius) * (radius + s.radius))
.min_by(|a, b| dist2(a.pos, pos).total_cmp(&dist2(b.pos, pos)))
.map(|s| s.id)
}
}