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::Hill => 14,
58        TerrainKindView::Bog => 25,
59        TerrainKindView::ShallowWater => 40,
60        TerrainKindView::DeepWater => u16::MAX,
61        TerrainKindView::Trail => 8,
62        TerrainKindView::Road => 5,
63        TerrainKindView::Rock => u16::MAX,
64    }
65}
66
67pub fn collides_player_at(x: f32, y: f32, world: &NavWorld) -> bool {
68    if world.circles.iter().any(|o| {
69        circle_overlap(x, y, PLAYER_RADIUS_M, o.x, o.y, o.radius_m)
70    }) {
71        return true;
72    }
73    let pad = PLAYER_RADIUS_M;
74    world.buildings.iter().any(|b| {
75        let hw = b.width_m / 2.0 + pad;
76        let hd = b.depth_m / 2.0 + pad;
77        x >= b.x - hw && x <= b.x + hw && y >= b.y - hd && y <= b.y + hd
78    })
79}
80
81fn circle_overlap(ax: f32, ay: f32, ar: f32, bx: f32, by: f32, br: f32) -> bool {
82    let dx = ax - bx;
83    let dy = ay - by;
84    let min_dist = ar + br;
85    dx * dx + dy * dy < min_dist * min_dist
86}
87
88pub(crate) fn block_circle(blocked: &mut [bool], width: i16, height: i16, cx: f32, cy: f32, radius_m: f32) {
89    let block_r = radius_m + PLAYER_RADIUS_M + PATH_CLEARANCE_M;
90    let r = block_r.ceil() as i16;
91    let ix = cx.floor() as i16;
92    let iy = cy.floor() as i16;
93    for dy in -r..=r {
94        for dx in -r..=r {
95            let cell_x = ix + dx;
96            let cell_y = iy + dy;
97            if cell_x < 0 || cell_y < 0 || cell_x >= width || cell_y >= height {
98                continue;
99            }
100            let cell_cx = cell_x as f32 + 0.5;
101            let cell_cy = cell_y as f32 + 0.5;
102            if (cell_cx - cx).hypot(cell_cy - cy) <= block_r {
103                let idx = (cell_y as usize) * (width as usize) + (cell_x as usize);
104                blocked[idx] = true;
105            }
106        }
107    }
108}
109
110pub(crate) fn mark_building_footprint(blocked: &mut [bool], width: i16, height: i16, building: &BuildingView) {
111    let pad = PLAYER_RADIUS_M + PATH_CLEARANCE_M;
112    let hw = building.width_m / 2.0;
113    let hd = building.depth_m / 2.0;
114    let x0 = (building.x - hw - pad).floor() as i16;
115    let y0 = (building.y - hd - pad).floor() as i16;
116    let x1 = (building.x + hw + pad).ceil() as i16 - 1;
117    let y1 = (building.y + hd + pad).ceil() as i16 - 1;
118    if x1 < x0 || y1 < y0 {
119        return;
120    }
121    for x in x0..=x1 {
122        for y in y0..=y1 {
123            if x >= 0 && y >= 0 && x < width && y < height {
124                let idx = (y as usize) * (width as usize) + (x as usize);
125                blocked[idx] = true;
126            }
127        }
128    }
129}
130
131pub(crate) fn clear_door_cells(blocked: &mut [bool], width: i16, height: i16, doors: &[DoorView]) {
132    for door in doors {
133        if door.open {
134            let (x, y) = world_to_cell(door.x, door.y);
135            for dx in -1i16..=1 {
136                for dy in -1i16..=1 {
137                    if dx.abs() + dy.abs() <= 1 {
138                        let cx = x + dx;
139                        let cy = y + dy;
140                        if cx >= 0 && cy >= 0 && cx < width && cy < height {
141                            let idx = (cy as usize) * (width as usize) + (cx as usize);
142                            blocked[idx] = false;
143                        }
144                    }
145                }
146            }
147        }
148    }
149}
150
151pub(crate) fn world_to_cell(x: f32, y: f32) -> (i16, i16) {
152    (x.floor() as i16, y.floor() as i16)
153}
154
155pub(crate) fn cell_center(x: i16, y: i16) -> (f32, f32) {
156    (x as f32 + 0.5, y as f32 + 0.5)
157}
158
159/// Build blocking circles from protocol views (resource nodes + living NPCs).
160pub fn circles_from_views(
161    resource_nodes: &[flatland_protocol::ResourceNodeView],
162    npcs: &[flatland_protocol::NpcView],
163) -> Vec<NavBlockingCircle> {
164    let mut circles = Vec::new();
165    for node in resource_nodes {
166        if node.blocking
167            && matches!(
168                node.state,
169                ResourceNodeState::Available | ResourceNodeState::Harvesting
170            )
171        {
172            let radius = if node.blocking_radius_m > 0.0 {
173                node.blocking_radius_m
174            } else {
175                0.8
176            };
177            circles.push(NavBlockingCircle {
178                x: node.x,
179                y: node.y,
180                radius_m: radius,
181            });
182        }
183    }
184    for npc in npcs {
185        let alive =
186            npc.life_state != Some(LifeState::Dead) && npc.hp_pct.is_none_or(|h| h > 0.0);
187        if alive {
188            circles.push(NavBlockingCircle {
189                x: npc.x,
190                y: npc.y,
191                radius_m: 0.55,
192            });
193        }
194    }
195    circles
196}
flatland_pathfinding/grid.rs

flatland_pathfinding/
grid.rs
