1 files changed, 52 insertions, 0 deletions

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()
+}