Naive shortest-path based bot

4 files changed, 130 insertions, 0 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c2b7199..967ef8f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -7,12 +7,69 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "013a6e0a2cbe3d20f9c60b65458f7a7f7a5e636c5d0f45a5a6aee5d4b1f01785"
 
 [[package]]
+name = "autocfg"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d"
+
+[[package]]
+name = "either"
+version = "1.5.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bb1f6b1ce1c140482ea30ddd3335fc0024ac7ee112895426e0a629a6c20adfe3"
+
+[[package]]
+name = "fixedbitset"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "37ab347416e802de484e4d03c7316c48f1ecb56574dfd4a46a80f173ce1de04d"
+
+[[package]]
+name = "indexmap"
+version = "1.3.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "076f042c5b7b98f31d205f1249267e12a6518c1481e9dae9764af19b707d2292"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "itertools"
+version = "0.8.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f56a2d0bc861f9165be4eb3442afd3c236d8a98afd426f65d92324ae1091a484"
+dependencies = [
+ "either",
+]
+
+[[package]]
 name = "itoa"
 version = "0.4.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b8b7a7c0c47db5545ed3fef7468ee7bb5b74691498139e4b3f6a20685dc6dd8e"
 
 [[package]]
+name = "num-traits"
+version = "0.2.11"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c62be47e61d1842b9170f0fdeec8eba98e60e90e5446449a0545e5152acd7096"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "pathfinding"
+version = "2.0.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "86f4d8cc85ca67860ef4324faf86973a39e4e1c78338987eda29a8e6b6ec0c0e"
+dependencies = [
+ "fixedbitset",
+ "indexmap",
+ "itertools",
+ "num-traits",
+]
+
+[[package]]
 name = "proc-macro2"
 version = "1.0.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -100,6 +157,7 @@ name = "vroomba"
 version = "0.1.0"
 dependencies = [
  "anyhow",
+ "pathfinding",
  "serde",
  "serde_json",
  "serde_repr",
diff --git a/Cargo.toml b/Cargo.toml
index 6158188..818e132 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,6 +8,7 @@ anyhow = "1.0.27"
 serde = { version = "1.0", features = ["derive"] }
 serde_repr = "0.1"
 serde_json = "1.0"
+pathfinding = "2.0.4"
 
 [profile.release]
 lto = true
diff --git a/src/lib.rs b/src/lib.rs
index 446a494..04629c3 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -5,10 +5,17 @@ pub mod json;
 pub mod state;
 
 use command::*;
+use consts::*;
+use pathfinding::prelude::*;
 use state::*;
 use std::cmp::Ordering;
 
 pub fn choose_command(state: &GameState) -> Command {
+    // choose_command_with_looking_forward_heuristic(state)
+    choose_command_with_astar(state)
+}
+
+fn choose_command_with_looking_forward_heuristic(state: &GameState) -> Command {
     let player_moves = state.valid_moves(0);
     let naive_result = player_moves
         .into_iter()
@@ -48,3 +55,48 @@ fn compare_states(a: &GameState, b: &GameState) -> Ordering {
             .then(a.players[0].boosts.cmp(&b.players[0].boosts))
     }
 }
+
+fn choose_command_with_astar(state: &GameState) -> Command {
+    shortest_path_first_command(state).unwrap_or(Command::Accelerate)
+}
+
+fn shortest_path_first_command(initial_state: &GameState) -> Option<Command> {
+    let shortest_path_states = astar(
+        initial_state,
+        |state| {
+            state
+                .good_moves(0)
+                .into_iter()
+                .filter(|player_move| *player_move != Command::UseOil)
+                .map(|player_move| {
+                    let mut state = state.clone();
+                    state.update([player_move, Command::Decelerate]);
+                    (state, 1)
+                })
+                .collect::<Vec<_>>()
+        },
+        |state| (WIDTH - state.players[0].position.x) / SPEED_BOOST,
+        |state| state.status != GameStatus::Continue,
+    )
+    .unwrap();
+
+    shortest_path_states
+        .0
+        .iter()
+        .zip(shortest_path_states.0.iter().skip(1))
+        .map(|(state, next)| {
+            let player_move = state
+                .valid_moves(0)
+                .into_iter()
+                .filter(|player_move| *player_move != Command::UseOil)
+                .find(|player_move| {
+                    let mut state = state.clone();
+                    state.update([*player_move, Command::Decelerate]);
+                    state == *next
+                })
+                .unwrap();
+
+            player_move
+        })
+        .next()
+}
diff --git a/src/state.rs b/src/state.rs
index 0a5fd71..7cc1ab4 100644
--- a/src/state.rs
+++ b/src/state.rs
@@ -208,6 +208,25 @@ impl GameState {
         }
         result
     }
+
+    pub fn good_moves(&self, player_index: usize) -> Vec<Command> {
+        let player = &self.players[player_index];
+        let mut result = Vec::with_capacity(7);
+        result.push(Command::Accelerate);
+        if player.position.y > MIN_Y {
+            result.push(Command::TurnLeft);
+        }
+        if player.position.y < MAX_Y - 1 {
+            result.push(Command::TurnRight);
+        }
+        if player.boosts > 0 {
+            result.push(Command::UseBoost);
+        }
+        if player.oils > 0 {
+            result.push(Command::UseOil);
+        }
+        result
+    }
 }
 
 impl Player {