From f8d95d074c36ec35eee8def73b8d9f2b83c922cb Mon Sep 17 00:00:00 2001
From: metamuffin <metamuffin@disroot.org>
Date: Mon, 20 Oct 2025 00:56:32 +0200
Subject: Pathfinding avoids chairs

---
 server/bot/src/algos/customer.rs |  9 ++++-----
 server/bot/src/algos/frank.rs    |  2 +-
 server/bot/src/algos/simple.rs   |  2 +-
 server/bot/src/algos/test.rs     |  2 +-
 server/bot/src/pathfinding.rs    | 24 +++++++++++++++++-------
 5 files changed, 24 insertions(+), 15 deletions(-)

(limited to 'server/bot')

diff --git a/server/bot/src/algos/customer.rs b/server/bot/src/algos/customer.rs
index 06dc373c..5a6f71f7 100644
--- a/server/bot/src/algos/customer.rs
+++ b/server/bot/src/algos/customer.rs
@@ -112,7 +112,7 @@ impl CustomerState {
                         .map(|(p, _)| *p)
                         .collect::<Vec<_>>();
                     if let Some(&chair) = chairs.get(random::<usize>(..) % chairs.len().max(1))
-                        && let Some(path) = find_path(&game.walkable, pos.as_ivec2(), chair)
+                        && let Some(path) = find_path(game, pos.as_ivec2(), chair)
                     {
                         debug!("{me:?} -> entering");
                         *self = CustomerState::Entering {
@@ -185,7 +185,7 @@ impl CustomerState {
                     *self = CustomerState::New;
                     BotInput::default()
                 } else if path.is_stuck() {
-                    if let Some(path) = find_path(&game.walkable, pos.as_ivec2(), *origin) {
+                    if let Some(path) = find_path(game, pos.as_ivec2(), *origin) {
                         *self = CustomerState::Exiting { path };
                     }
                     BotInput::default()
@@ -208,8 +208,7 @@ impl CustomerState {
                 *timeout -= dt;
                 *check += 1;
                 if *timeout <= 0. {
-                    let path = find_path(&game.walkable, pos.as_ivec2(), *origin)
-                        .expect("no path to exit");
+                    let path = find_path(game, pos.as_ivec2(), *origin).expect("no path to exit");
                     debug!("{me:?} -> exiting");
                     *self = CustomerState::Exiting { path };
                     return BotInput {
@@ -381,7 +380,7 @@ impl CustomerState {
                     .is_some_and(|pl| pl.items[0].is_none())
                 // TODO index out of bounds?
                 {
-                    if let Some(path) = find_path(&game.walkable, pos.as_ivec2(), *origin) {
+                    if let Some(path) = find_path(game, pos.as_ivec2(), *origin) {
                         *self = CustomerState::Exiting { path };
                     }
                     BotInput::default()
diff --git a/server/bot/src/algos/frank.rs b/server/bot/src/algos/frank.rs
index 3515f96d..489417a6 100644
--- a/server/bot/src/algos/frank.rs
+++ b/server/bot/src/algos/frank.rs
@@ -90,7 +90,7 @@ impl BotAlgo for Frank {
                         };
                     }
                 } else if let Some(path) =
-                    find_path_to_neighbour(&game.walkable, pos.as_ivec2(), tpos.as_ivec2())
+                    find_path_to_neighbour(game, pos.as_ivec2(), tpos.as_ivec2())
                 {
                     self.path = Some(path);
                 }
diff --git a/server/bot/src/algos/simple.rs b/server/bot/src/algos/simple.rs
index 0145cfcb..9c17cd82 100644
--- a/server/bot/src/algos/simple.rs
+++ b/server/bot/src/algos/simple.rs
@@ -243,7 +243,7 @@ impl<S: State> Context<'_, S> {
         }
     }
     pub fn interact_with(&mut self, tile: IVec2, duration: f32) -> LogicRes {
-        if let Some(path) = find_path_to_neighbour(&self.game.walkable, self.own_position, tile) {
+        if let Some(path) = find_path_to_neighbour(self.game, self.own_position, tile) {
             self.state.queue_segment(path, tile, duration);
             Err(())
         } else {
diff --git a/server/bot/src/algos/test.rs b/server/bot/src/algos/test.rs
index 20abbabd..387dd285 100644
--- a/server/bot/src/algos/test.rs
+++ b/server/bot/src/algos/test.rs
@@ -45,7 +45,7 @@ impl BotAlgo for Test {
             };
         } else if let Some((item, near)) = find_demand(game) {
             info!("demand {item:?} near {near}");
-            if let Some(path) = find_path_to_neighbour(&game.walkable, pos.as_ivec2(), near) {
+            if let Some(path) = find_path_to_neighbour(game, pos.as_ivec2(), near) {
                 self.path = Some(path);
             }
         }
diff --git a/server/bot/src/pathfinding.rs b/server/bot/src/pathfinding.rs
index a32442b1..e17ca80c 100644
--- a/server/bot/src/pathfinding.rs
+++ b/server/bot/src/pathfinding.rs
@@ -15,11 +15,12 @@
     along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
 */
+use hurrycurry_game_core::Game;
 use hurrycurry_protocol::glam::{IVec2, Vec2};
 use log::{debug, trace};
 use std::{
     cmp::Ordering,
-    collections::{BinaryHeap, HashMap, HashSet},
+    collections::{BinaryHeap, HashMap},
     time::Instant,
 };
 
@@ -54,19 +55,19 @@ impl Path {
     }
 }
 
-pub fn find_path_to_neighbour(walkable: &HashSet<IVec2>, from: IVec2, to: IVec2) -> Option<Path> {
+pub fn find_path_to_neighbour(game: &Game, from: IVec2, to: IVec2) -> Option<Path> {
     let mut paths = Vec::new();
     for xo in -1..=1 {
         for yo in -1..=1 {
             let to = to + IVec2::new(xo, yo);
-            if walkable.contains(&to) {
-                paths.extend(find_path(walkable, from, to))
+            if game.walkable.contains(&to) {
+                paths.extend(find_path(game, from, to))
             }
         }
     }
     paths.into_iter().min_by_key(|p| p.segments.len())
 }
-pub fn find_path(walkable: &HashSet<IVec2>, from: IVec2, to: IVec2) -> Option<Path> {
+pub fn find_path(game: &Game, from: IVec2, to: IVec2) -> Option<Path> {
     #[derive(Debug, PartialEq, Eq)]
     struct Open {
         heuristic: i32,
@@ -87,6 +88,7 @@ pub fn find_path(walkable: &HashSet<IVec2>, from: IVec2, to: IVec2) -> Option<Pa
 
     debug!("planning route from {from} to {to}");
     let start = Instant::now();
+    let chair = game.data.get_tile_by_name("chair");
     let mut visited = HashMap::new();
     let mut open = BinaryHeap::new();
     open.push(Open {
@@ -112,12 +114,20 @@ pub fn find_path(walkable: &HashSet<IVec2>, from: IVec2, to: IVec2) -> Option<Pa
         }
         for dir in [IVec2::NEG_X, IVec2::NEG_Y, IVec2::X, IVec2::Y] {
             let next = pos + dir;
-            if walkable.contains(&next) {
+            if game.walkable.contains(&next) {
+                let penalty = if let Some(chair) = chair
+                    && let Some(set) = game.tile_index.get(&chair)
+                    && set.contains(&next)
+                {
+                    8
+                } else {
+                    0
+                };
                 open.push(Open {
                     heuristic: -(distance + next.distance_squared(to).isqrt()),
                     pos: next,
                     prev_pos: pos,
-                    distance: distance + 1,
+                    distance: distance + penalty + 1,
                 });
             }
         }
-- 
cgit v1.3