flatland_pathfinding/
grid.rs

1//! Navigation world snapshot for pathfinding.
2
3use flatland_protocol::{
4    BuildingView, DoorView, LifeState, ResourceNodeState, TerrainKindView, TerrainZoneView,
5    ZPlatformView, ZTransitionView,
6};
7
8pub const PLAYER_RADIUS_M: f32 = 0.45;
9/// Extra clearance so paths don't hug walls.
10pub const PATH_CLEARANCE_M: f32 = 0.35;
11/// Sample spacing when testing straight segments against circle obstacles.
12pub const SEGMENT_SAMPLE_M: f32 = 0.3;
13
14#[derive(Debug, Clone, Copy)]
15pub struct NavBlockingCircle {
16    pub x: f32,
17    pub y: f32,
18    pub radius_m: f32,
19}
20
21/// Static + dynamic obstacles for one path query.
22#[derive(Debug, Clone)]
23pub struct NavWorld {
24    pub world_width_m: f32,
25    pub world_height_m: f32,
26    pub terrain_zones: Vec<TerrainZoneView>,
27    pub z_platforms: Vec<ZPlatformView>,
28    pub z_transitions: Vec<ZTransitionView>,
29    pub buildings: Vec<BuildingView>,
30    pub doors: Vec<DoorView>,
31    pub circles: Vec<NavBlockingCircle>,
32}
33
34impl NavWorld {
35    pub fn elevation_at(&self, x: f32, y: f32) -> f32 {
36        terrain_at(&self.terrain_zones, x, y)
37            .map(|z| z.elevation)
38            .unwrap_or(0.0)
39    }
40
41    pub fn terrain_kind_at(&self, x: f32, y: f32) -> TerrainKindView {
42        terrain_at(&self.terrain_zones, x, y)
43            .map(|z| z.kind)
44            .unwrap_or(TerrainKindView::Grass)
45    }
46}
47
48fn terrain_at(zones: &[TerrainZoneView], x: f32, y: f32) -> Option<&TerrainZoneView> {
49    zones
50        .iter()
51        .find(|zone| x >= zone.x0 && x < zone.x1 && y >= zone.y0 && y < zone.y1)
52}
53
54pub(crate) fn terrain_cost(kind: TerrainKindView) -> u16 {
55    match kind {
56        TerrainKindView::Grass => 10,
57        TerrainKindView::Dirt => 11,
58        TerrainKindView::Tilled => 12,
59        TerrainKindView::Desert => 13,
60        TerrainKindView::Hill => 14,
61        TerrainKindView::Bog => 25,
62        TerrainKindView::ShallowWater => 40,
63        TerrainKindView::DeepWater => u16::MAX,
64        TerrainKindView::Trail => 8,
65        TerrainKindView::Road => 5,
66        TerrainKindView::Rock => u16::MAX,
67    }
68}
69
70pub fn collides_player_at(x: f32, y: f32, world: &NavWorld) -> bool {
71    if world.circles.iter().any(|o| {
72        circle_overlap(x, y, PLAYER_RADIUS_M, o.x, o.y, o.radius_m)
73    }) {
74        return true;
75    }
76    let pad = PLAYER_RADIUS_M;
77    world.buildings.iter().any(|b| {
78        let hw = b.width_m / 2.0 + pad;
79        let hd = b.depth_m / 2.0 + pad;
80        x >= b.x - hw && x <= b.x + hw && y >= b.y - hd && y <= b.y + hd
81    })
82}
83
84fn circle_overlap(ax: f32, ay: f32, ar: f32, bx: f32, by: f32, br: f32) -> bool {
85    let dx = ax - bx;
86    let dy = ay - by;
87    let min_dist = ar + br;
88    dx * dx + dy * dy < min_dist * min_dist
89}
90
91pub(crate) fn block_circle(blocked: &mut [bool], width: i16, height: i16, cx: f32, cy: f32, radius_m: f32) {
92    let block_r = radius_m + PLAYER_RADIUS_M + PATH_CLEARANCE_M;
93    let r = block_r.ceil() as i16;
94    let ix = cx.floor() as i16;
95    let iy = cy.floor() as i16;
96    for dy in -r..=r {
97        for dx in -r..=r {
98            let cell_x = ix + dx;
99            let cell_y = iy + dy;
100            if cell_x < 0 || cell_y < 0 || cell_x >= width || cell_y >= height {
101                continue;
102            }
103            let cell_cx = cell_x as f32 + 0.5;
104            let cell_cy = cell_y as f32 + 0.5;
105            if (cell_cx - cx).hypot(cell_cy - cy) <= block_r {
106                let idx = (cell_y as usize) * (width as usize) + (cell_x as usize);
107                blocked[idx] = true;
108            }
109        }
110    }
111}
112
113pub(crate) fn mark_building_footprint(blocked: &mut [bool], width: i16, height: i16, building: &BuildingView) {
114    let pad = PLAYER_RADIUS_M + PATH_CLEARANCE_M;
115    let hw = building.width_m / 2.0;
116    let hd = building.depth_m / 2.0;
117    let x0 = (building.x - hw - pad).floor() as i16;
118    let y0 = (building.y - hd - pad).floor() as i16;
119    let x1 = (building.x + hw + pad).ceil() as i16 - 1;
120    let y1 = (building.y + hd + pad).ceil() as i16 - 1;
121    if x1 < x0 || y1 < y0 {
122        return;
123    }
124    for x in x0..=x1 {
125        for y in y0..=y1 {
126            if x >= 0 && y >= 0 && x < width && y < height {
127                let idx = (y as usize) * (width as usize) + (x as usize);
128                blocked[idx] = true;
129            }
130        }
131    }
132}
133
134pub(crate) fn clear_door_cells(blocked: &mut [bool], width: i16, height: i16, doors: &[DoorView]) {
135    for door in doors {
136        if door.open {
137            let (x, y) = world_to_cell(door.x, door.y);
138            for dx in -1i16..=1 {
139                for dy in -1i16..=1 {
140                    if dx.abs() + dy.abs() <= 1 {
141                        let cx = x + dx;
142                        let cy = y + dy;
143                        if cx >= 0 && cy >= 0 && cx < width && cy < height {
144                            let idx = (cy as usize) * (width as usize) + (cx as usize);
145                            blocked[idx] = false;
146                        }
147                    }
148                }
149            }
150        }
151    }
152}
153
154pub(crate) fn world_to_cell(x: f32, y: f32) -> (i16, i16) {
155    (x.floor() as i16, y.floor() as i16)
156}
157
158pub(crate) fn cell_center(x: i16, y: i16) -> (f32, f32) {
159    (x as f32 + 0.5, y as f32 + 0.5)
160}
161
162/// Build blocking circles from protocol views (resource nodes + living NPCs).
163pub fn circles_from_views(
164    resource_nodes: &[flatland_protocol::ResourceNodeView],
165    npcs: &[flatland_protocol::NpcView],
166) -> Vec<NavBlockingCircle> {
167    let mut circles = Vec::new();
168    for node in resource_nodes {
169        if node.blocking
170            && matches!(
171                node.state,
172                ResourceNodeState::Available | ResourceNodeState::Harvesting
173            )
174        {
175            let radius = if node.blocking_radius_m > 0.0 {
176                node.blocking_radius_m
177            } else {
178                0.8
179            };
180            circles.push(NavBlockingCircle {
181                x: node.x,
182                y: node.y,
183                radius_m: radius,
184            });
185        }
186    }
187    for npc in npcs {
188        let alive =
189            npc.life_state != Some(LifeState::Dead) && npc.hp_pct.is_none_or(|h| h > 0.0);
190        if alive {
191            circles.push(NavBlockingCircle {
192                x: npc.x,
193                y: npc.y,
194                radius_m: 0.55,
195            });
196        }
197    }
198    circles
199}
flatland_pathfinding/grid.rs

flatland_pathfinding/
grid.rs
