dotzuki_engine/overworld/
npc_movement.rs

1//! Generic NPC movement system for the overworld.
2//!
3//! Implements NPC movement: per-frame sprite updates for all NPCs and the
4//! trainer-notice (emotion bubble) animation.
5//!
6//! All functions are generic over tileset and collision provider types.
7
8use alloc::collections::VecDeque;
9
10use crate::map::MapTrait;
11use crate::tileset::TilesetTrait;
12
13use super::collision::{CollisionProvider, SpritePosition};
14use super::player_movement::direction_delta;
15use super::types::{Direction, MapData, NpcMovementType, NpcWanderAxis};
16
17// ── NPC Runtime State ──────────────────────────────────────────────
18
19/// Runtime state for a single NPC on the current map.
20///
21/// Game-specific data (e.g., trainer flags, item drops) should be stored
22/// in a separate parallel array and looked up by `npc_index`.
23#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
24pub struct NpcRuntimeState {
25    pub npc_index: u8,
26    pub sprite_id: u8,
27    pub x: u16,
28    pub y: u16,
29    pub home_x: u16,
30    pub home_y: u16,
31    pub facing: Direction,
32    pub scripted_frame: Option<u8>,
33    pub movement_type: NpcMovementType,
34    /// Axis restriction for Wander NPCs (classic GB movement byte 2).
35    pub wander_axis: NpcWanderAxis,
36    pub range: u8,
37    pub walk_counter: u8,
38    pub delay_counter: u8,
39    pub text_id: u8,
40    pub defeated: bool,
41    pub visible: bool,
42    pub scripted_path: VecDeque<(u16, u16)>,
43}
44
45// ── Constants ──────────────────────────────────────────────────────
46
47/// Frames to walk one tile. The classic GB walkers take $10 frames per tile —
48/// HALF the player's speed (WALKANIMATIONCOUNTER = $10, movement.asm:296-339).
49pub const NPC_WALK_FRAMES: u8 = 16;
50/// Maximum delay between random NPC movements: `Random & $7F` ∈ 0..=127
51/// (movement.asm:352-361; a rolled 0 becomes 256 — that quirk is preserved
52/// by callers as an immediate re-roll, matching the original's wrap).
53pub const NPC_MAX_DELAY: u8 = 127;
54
55// ── Helpers ────────────────────────────────────────────────────────
56
57/// Determine direction from `from` toward `to`.
58///
59/// Uses the axial heuristic: if dx.abs() > dy.abs(), horizontal;
60/// otherwise vertical. Returns `None` if both positions are the same.
61pub fn direction_toward(from_x: u16, from_y: u16, to_x: u16, to_y: u16) -> Option<Direction> {
62    let dx = to_x as i32 - from_x as i32;
63    let dy = to_y as i32 - from_y as i32;
64    if dx == 0 && dy == 0 {
65        return None;
66    }
67    if dx.abs() > dy.abs() {
68        Some(if dx > 0 {
69            Direction::Right
70        } else {
71            Direction::Left
72        })
73    } else {
74        Some(if dy > 0 {
75            Direction::Down
76        } else {
77            Direction::Up
78        })
79    }
80}
81
82// ── Scripted Movement ──────────────────────────────────────────────
83
84/// Start an NPC walking a fixed path of tile coordinates.
85pub fn start_scripted_move(npc: &mut NpcRuntimeState, path: &[(u8, u8)]) {
86    npc.scripted_path.clear();
87    for &(x, y) in path {
88        npc.scripted_path.push_back((x as u16, y as u16));
89    }
90}
91
92/// Returns `true` when the NPC has finished its scripted path and is idle.
93pub fn is_scripted_move_done(npc: &NpcRuntimeState) -> bool {
94    npc.scripted_path.is_empty() && npc.walk_counter == 0
95}
96
97// ── Position Utilities ─────────────────────────────────────────────
98
99/// Collect tile positions of all visible NPCs for collision checks.
100pub fn get_npc_positions(npcs: &[NpcRuntimeState]) -> Vec<SpritePosition> {
101    npcs.iter()
102        .filter(|n| n.visible)
103        .map(|n| SpritePosition { x: n.x, y: n.y })
104        .collect()
105}
106
107// ── NPC Lookup ─────────────────────────────────────────────────────
108
109/// Find a visible NPC at the given tile position.
110pub fn npc_at_position(npcs: &[NpcRuntimeState], x: u16, y: u16) -> Option<&NpcRuntimeState> {
111    npcs.iter().find(|n| n.visible && n.x == x && n.y == y)
112}
113
114/// Mutable version of [`npc_at_position`].
115pub fn npc_at_position_mut(
116    npcs: &mut [NpcRuntimeState],
117    x: u16,
118    y: u16,
119) -> Option<&mut NpcRuntimeState> {
120    npcs.iter_mut().find(|n| n.visible && n.x == x && n.y == y)
121}
122
123// ── NPC Update Loop ────────────────────────────────────────────────
124
125/// Update all NPC movement for one frame.
126///
127/// This is the main entry point called every frame from the overworld loop
128/// (equivalent to `DoMovementForAllSprites` in the original game).
129///
130/// Each NPC that is visible, not mid-step, and not on a scripted path is
131/// updated based on its movement type (Stationary, Wander, FacePlayer, or FixedPath).
132///
133/// # Parameters
134/// - `npcs` — mutable slice of NPC runtime states
135/// - `player_x`, `player_y` — player's current tile position
136/// - `player_dest` — player's destination if mid-step (for collision avoidance)
137/// - `map_width_blocks`, `map_height_blocks` — map dimensions in blocks
138/// - `rng_value` — random value for wander direction/delay
139/// - `blocks` — block data for the current map
140/// - `tileset` — current tileset
141/// - `provider` — collision provider for tile passability
142pub fn update_npc_movement<T: TilesetTrait>(
143    npcs: &mut [NpcRuntimeState],
144    player_x: u16,
145    player_y: u16,
146    player_dest: Option<(u16, u16)>,
147    map_width_blocks: u8,
148    map_height_blocks: u8,
149    rng_value: u8,
150    blocks: &[u8],
151    tileset: T,
152    provider: &impl CollisionProvider<T>,
153) {
154    let max_x = (map_width_blocks as u16) * 2;
155    let max_y = (map_height_blocks as u16) * 2;
156
157    // Build the occupied-tile set: current position of each visible NPC,
158    // plus its destination if it is mid-step (to avoid inter-NPC collisions).
159    let occupied: Vec<(u16, u16)> = npcs
160        .iter()
161        .filter(|n| n.visible)
162        .flat_map(|n| {
163            let cur = (n.x, n.y);
164            if n.walk_counter > 0 {
165                let (dx, dy) = direction_delta(n.facing);
166                let dest = (
167                    (n.x as i32 + dx as i32).max(0) as u16,
168                    (n.y as i32 + dy as i32).max(0) as u16,
169                );
170                vec![cur, dest]
171            } else {
172                vec![cur]
173            }
174        })
175        .collect();
176
177    for i in 0..npcs.len() {
178        let npc = &mut npcs[i];
179        if !npc.visible {
180            continue;
181        }
182
183        // ── Finish current step ──────────────────────────────────
184        if npc.walk_counter > 0 {
185            npc.walk_counter -= 1;
186            if npc.walk_counter == 0 {
187                let (dx, dy) = direction_delta(npc.facing);
188                npc.x = (npc.x as i32 + dx as i32).max(0) as u16;
189                npc.y = (npc.y as i32 + dy as i32).max(0) as u16;
190
191                // Advance scripted path if we reached the next waypoint
192                if !npc.scripted_path.is_empty() {
193                    let &(tx, ty) = npc.scripted_path.front().unwrap();
194                    if npc.x == tx && npc.y == ty {
195                        npc.scripted_path.pop_front();
196                    }
197                    if let Some(&(ntx, nty)) = npc.scripted_path.front() {
198                        if let Some(dir) = direction_toward(npc.x, npc.y, ntx, nty) {
199                            npc.facing = dir;
200                            npc.walk_counter = NPC_WALK_FRAMES;
201                        }
202                    }
203                }
204            }
205            continue;
206        }
207
208        // ── Scripted path: start next step ───────────────────────
209        if !npc.scripted_path.is_empty() {
210            let &(tx, ty) = npc.scripted_path.front().unwrap();
211            if npc.x == tx && npc.y == ty {
212                npc.scripted_path.pop_front();
213                if npc.scripted_path.is_empty() {
214                    continue;
215                }
216                let &(tx, ty) = npc.scripted_path.front().unwrap();
217                if let Some(dir) = direction_toward(npc.x, npc.y, tx, ty) {
218                    npc.facing = dir;
219                    npc.walk_counter = NPC_WALK_FRAMES;
220                }
221            } else if let Some(dir) = direction_toward(npc.x, npc.y, tx, ty) {
222                npc.facing = dir;
223                npc.walk_counter = NPC_WALK_FRAMES;
224            }
225            continue;
226        }
227
228        // ── Autonomous movement by type ──────────────────────────
229        match npc.movement_type {
230            NpcMovementType::Stationary => {}
231            NpcMovementType::Wander => {
232                if npc.delay_counter > 0 {
233                    npc.delay_counter -= 1;
234                    continue;
235                }
236
237                // Pick a random direction from the lower 2 bits of rng_value,
238                // filtered by the classic axis byte (movement byte 2:
239                // UP_DOWN $01 → vertical only, LEFT_RIGHT $02 → horizontal
240                // only, ANY $00 → all four — movement.asm:195-251). An
241                // axis-off roll re-rolls the delay instead of moving.
242                let dir_bits = (rng_value.wrapping_add(i as u8)) & 0x03;
243                let dir = match dir_bits {
244                    0 => Direction::Down,
245                    1 => Direction::Up,
246                    2 => Direction::Left,
247                    3 => Direction::Right,
248                    _ => unreachable!(),
249                };
250                let axis_ok = match npc.wander_axis {
251                    NpcWanderAxis::Any => true,
252                    NpcWanderAxis::Vertical => {
253                        dir == Direction::Up || dir == Direction::Down
254                    }
255                    NpcWanderAxis::Horizontal => {
256                        dir == Direction::Left || dir == Direction::Right
257                    }
258                };
259                if !axis_ok {
260                    npc.delay_counter = rng_value & NPC_MAX_DELAY;
261                    continue;
262                }
263
264                let (dx, dy) = direction_delta(dir);
265                let tx = (npc.x as i32 + dx as i32) as u16;
266                let ty = (npc.y as i32 + dy as i32) as u16;
267
268                // Bounds check. (No radial leash: classic random walkers have
269                // none — they walk until blocked.)
270                if tx >= max_x || ty >= max_y {
271                    npc.facing = dir;
272                    npc.delay_counter = rng_value & NPC_MAX_DELAY;
273                    continue;
274                }
275
276                // Check occupied tiles (other NPCs)
277                let blocked = occupied
278                    .iter()
279                    .any(|&(ox, oy)| !(ox == npc.x && oy == npc.y) && ox == tx && oy == ty);
280                let player_blocked = (tx == player_x && ty == player_y)
281                    || player_dest.map_or(false, |(px, py)| tx == px && ty == py);
282
283                if blocked || player_blocked {
284                    npc.facing = dir;
285                    npc.delay_counter = rng_value & NPC_MAX_DELAY;
286                    continue;
287                }
288
289                // Check tile passability
290                let target_tile =
291                    provider.get_tile_at_position(tileset, blocks, map_width_blocks, tx, ty);
292                if !provider.is_tile_passable(tileset, target_tile) {
293                    npc.facing = dir;
294                    npc.delay_counter = rng_value & NPC_MAX_DELAY;
295                    continue;
296                }
297
298                npc.facing = dir;
299                npc.walk_counter = NPC_WALK_FRAMES;
300                npc.delay_counter = rng_value & NPC_MAX_DELAY;
301            }
302            NpcMovementType::FacePlayer => {
303                let dx = player_x as i32 - npc.x as i32;
304                let dy = player_y as i32 - npc.y as i32;
305
306                if dx.abs() >= dy.abs() {
307                    npc.facing = if dx > 0 {
308                        Direction::Right
309                    } else {
310                        Direction::Left
311                    };
312                } else {
313                    npc.facing = if dy > 0 {
314                        Direction::Down
315                    } else {
316                        Direction::Up
317                    };
318                }
319            }
320            NpcMovementType::FixedPath => {}
321        }
322    }
323}
324
325// ── NPC-in-Front Check ─────────────────────────────────────────────
326
327/// Find the NPC the player is facing, accounting for counter tiles.
328///
329/// In the original game, pressing A on a counter tile extends the
330/// interaction range by one tile to allow talking to NPCs across
331/// counters (e.g. shopkeepers in Poké Marts).
332pub fn npc_in_front_of_player<'a, M: MapTrait, T: TilesetTrait, Mus>(
333    npcs: &'a [NpcRuntimeState],
334    player_x: u16,
335    player_y: u16,
336    facing: Direction,
337    map: Option<&MapData<M, T, Mus>>,
338    provider: &impl CollisionProvider<T>,
339) -> Option<&'a NpcRuntimeState> {
340    let (dx, dy) = direction_delta(facing);
341    let target_x = (player_x as i32 + dx as i32) as u16;
342    let target_y = (player_y as i32 + dy as i32) as u16;
343
344    if let Some(npc) = npc_at_position(npcs, target_x, target_y) {
345        return Some(npc);
346    }
347
348    // Counter tile extension: if the tile in front is a counter,
349    // check one more tile in the same direction for an NPC behind it.
350    if let Some(map_data) = map {
351        let tile = provider.get_tile_at_position(
352            map_data.tileset,
353            &map_data.blocks,
354            map_data.width,
355            target_x,
356            target_y,
357        );
358        if provider.is_counter_tile(map_data.tileset, tile) {
359            let extended_x = (target_x as i32 + dx as i32) as u16;
360            let extended_y = (target_y as i32 + dy as i32) as u16;
361            return npc_at_position(npcs, extended_x, extended_y);
362        }
363    }
364
365    None
366}
dotzuki_engine/overworld/npc_movement.rs

dotzuki_engine/overworld/
npc_movement.rs
