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::Beach => 18,
63        TerrainKindView::ShallowWater => 40,
64        TerrainKindView::DeepWater => u16::MAX,
65        TerrainKindView::Trail => 8,
66        TerrainKindView::Road => 5,
67        TerrainKindView::Rock => u16::MAX,
68    }
69}
70
71pub fn collides_player_at(x: f32, y: f32, world: &NavWorld) -> bool {
72    if world.circles.iter().any(|o| {
73        circle_overlap(x, y, PLAYER_RADIUS_M, o.x, o.y, o.radius_m)
74    }) {
75        return true;
76    }
77    let pad = PLAYER_RADIUS_M;
78    world.buildings.iter().any(|b| {
79        let hw = b.width_m / 2.0 + pad;
80        let hd = b.depth_m / 2.0 + pad;
81        x >= b.x - hw && x <= b.x + hw && y >= b.y - hd && y <= b.y + hd
82    })
83}
84
85fn circle_overlap(ax: f32, ay: f32, ar: f32, bx: f32, by: f32, br: f32) -> bool {
86    let dx = ax - bx;
87    let dy = ay - by;
88    let min_dist = ar + br;
89    dx * dx + dy * dy < min_dist * min_dist
90}
91
92pub(crate) fn block_circle(blocked: &mut [bool], width: i16, height: i16, cx: f32, cy: f32, radius_m: f32) {
93    let block_r = radius_m + PLAYER_RADIUS_M + PATH_CLEARANCE_M;
94    let r = block_r.ceil() as i16;
95    let ix = cx.floor() as i16;
96    let iy = cy.floor() as i16;
97    for dy in -r..=r {
98        for dx in -r..=r {
99            let cell_x = ix + dx;
100            let cell_y = iy + dy;
101            if cell_x < 0 || cell_y < 0 || cell_x >= width || cell_y >= height {
102                continue;
103            }
104            let cell_cx = cell_x as f32 + 0.5;
105            let cell_cy = cell_y as f32 + 0.5;
106            if (cell_cx - cx).hypot(cell_cy - cy) <= block_r {
107                let idx = (cell_y as usize) * (width as usize) + (cell_x as usize);
108                blocked[idx] = true;
109            }
110        }
111    }
112}
113
114pub(crate) fn mark_building_footprint(blocked: &mut [bool], width: i16, height: i16, building: &BuildingView) {
115    let pad = PLAYER_RADIUS_M + PATH_CLEARANCE_M;
116    let hw = building.width_m / 2.0;
117    let hd = building.depth_m / 2.0;
118    let x0 = (building.x - hw - pad).floor() as i16;
119    let y0 = (building.y - hd - pad).floor() as i16;
120    let x1 = (building.x + hw + pad).ceil() as i16 - 1;
121    let y1 = (building.y + hd + pad).ceil() as i16 - 1;
122    if x1 < x0 || y1 < y0 {
123        return;
124    }
125    for x in x0..=x1 {
126        for y in y0..=y1 {
127            if x >= 0 && y >= 0 && x < width && y < height {
128                let idx = (y as usize) * (width as usize) + (x as usize);
129                blocked[idx] = true;
130            }
131        }
132    }
133}
134
135pub(crate) fn clear_door_cells(blocked: &mut [bool], width: i16, height: i16, doors: &[DoorView]) {
136    for door in doors {
137        if door.open {
138            let (x, y) = world_to_cell(door.x, door.y);
139            for dx in -1i16..=1 {
140                for dy in -1i16..=1 {
141                    if dx.abs() + dy.abs() <= 1 {
142                        let cx = x + dx;
143                        let cy = y + dy;
144                        if cx >= 0 && cy >= 0 && cx < width && cy < height {
145                            let idx = (cy as usize) * (width as usize) + (cx as usize);
146                            blocked[idx] = false;
147                        }
148                    }
149                }
150            }
151        }
152    }
153}
154
155pub(crate) fn world_to_cell(x: f32, y: f32) -> (i16, i16) {
156    (x.floor() as i16, y.floor() as i16)
157}
158
159pub(crate) fn cell_center(x: i16, y: i16) -> (f32, f32) {
160    (x as f32 + 0.5, y as f32 + 0.5)
161}
162
163/// Default nav radius when a placed prop has `blocking: true` but radius 0 in data.
164pub const DEFAULT_PLACED_PROP_BLOCK_RADIUS_M: f32 = 0.7;
165
166/// Blocking circles for placed props that have `blocking` on the item template (AOI view).
167pub fn circles_from_placed_containers(
168    containers: &[flatland_protocol::PlacedContainerView],
169) -> Vec<NavBlockingCircle> {
170    containers
171        .iter()
172        .filter(|c| c.blocking)
173        .map(|c| {
174            let radius_m = if c.blocking_radius_m > 0.0 {
175                c.blocking_radius_m
176            } else {
177                DEFAULT_PLACED_PROP_BLOCK_RADIUS_M
178            };
179            NavBlockingCircle {
180                x: c.x,
181                y: c.y,
182                radius_m,
183            }
184        })
185        .collect()
186}
187
188/// Outdoor travel goal snapped clear of buildings, trees, NPCs, and placed props.
189pub fn snap_nav_goal(world: &NavWorld, gx: f32, gy: f32) -> (f32, f32) {
190    if !nav_position_blocked(world, gx, gy, PATH_CLEARANCE_M) {
191        return (gx, gy);
192    }
193    for step in 1..=40 {
194        let d = step as f32 * 0.35;
195        for (dx, dy) in [
196            (0.0, -d),
197            (0.0, d),
198            (d, 0.0),
199            (-d, 0.0),
200            (d, -d),
201            (d, d),
202            (-d, -d),
203            (-d, d),
204        ] {
205            let nx = gx + dx;
206            let ny = gy + dy;
207            if !nav_position_blocked(world, nx, ny, PATH_CLEARANCE_M) {
208                return (nx, ny);
209            }
210        }
211    }
212    (gx, gy)
213}
214
215fn nav_position_blocked(world: &NavWorld, x: f32, y: f32, extra_pad_m: f32) -> bool {
216    let body = PLAYER_RADIUS_M + extra_pad_m.max(0.0);
217    if world.circles.iter().any(|o| {
218        circle_overlap(x, y, body, o.x, o.y, o.radius_m + extra_pad_m.max(0.0))
219    }) {
220        return true;
221    }
222    world.buildings.iter().any(|b| {
223        let hw = b.width_m / 2.0 + body;
224        let hd = b.depth_m / 2.0 + body;
225        x >= b.x - hw && x <= b.x + hw && y >= b.y - hd && y <= b.y + hd
226    })
227}
228
229/// Build blocking circles from protocol views (resource nodes + living NPCs).
230pub fn circles_from_views(
231    resource_nodes: &[flatland_protocol::ResourceNodeView],
232    npcs: &[flatland_protocol::NpcView],
233) -> Vec<NavBlockingCircle> {
234    let mut circles = Vec::new();
235    for node in resource_nodes {
236        if node.blocking
237            && matches!(
238                node.state,
239                ResourceNodeState::Available | ResourceNodeState::Harvesting
240            )
241        {
242            let radius = if node.blocking_radius_m > 0.0 {
243                node.blocking_radius_m
244            } else {
245                0.8
246            };
247            circles.push(NavBlockingCircle {
248                x: node.x,
249                y: node.y,
250                radius_m: radius,
251            });
252        }
253    }
254    for npc in npcs {
255        let alive =
256            npc.life_state != Some(LifeState::Dead) && npc.hp_pct.is_none_or(|h| h > 0.0);
257        if alive {
258            circles.push(NavBlockingCircle {
259                x: npc.x,
260                y: npc.y,
261                radius_m: 0.55,
262            });
263        }
264    }
265    circles
266}
flatland_pathfinding/grid.rs

flatland_pathfinding/
grid.rs
