Event-based heuristic at the beginning, astar at the end

1 files changed, 67 insertions, 22 deletions

diff --git a/src/lib.rs b/src/lib.rs
index 04629c3..519b804 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -10,31 +10,57 @@ 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)
+pub fn choose_command(round: usize, state: &GameState) -> Command {
+    if round <= 100 {
+        choose_command_with_looking_forward_heuristic(state)
+    } else {
+        choose_command_with_astar(state)
+    }
+}
+
+#[derive(Debug, Clone)]
+struct HeuristicLookaheadState {
+    moves: Vec<Command>,
+    events: GameStateUpdateEvents,
+    current_state: GameState,
 }
 
 fn choose_command_with_looking_forward_heuristic(state: &GameState) -> Command {
-    let player_moves = state.valid_moves(0);
-    let naive_result = player_moves
-        .into_iter()
-        .map(|player_move| {
-            let mut state = state.clone();
-            state.update([player_move, Command::Accelerate]);
-            (player_move, state)
-        })
-        .flat_map(|(player_move, state)| {
-            state.valid_moves(0).into_iter().map(move |second_move| {
-                let mut second_move_state = state.clone();
-                second_move_state.update([second_move, Command::Accelerate]);
-                (player_move, second_move_state)
+    let depth = 3;
+    let mut states = vec![HeuristicLookaheadState {
+        moves: Vec::new(),
+        events: GameStateUpdateEvents::default(),
+        current_state: state.clone(),
+    }];
+
+    for _ in 0..depth {
+        states = states
+            .into_iter()
+            .flat_map(move |state| {
+                state
+                    .current_state
+                    .good_moves(0)
+                    .into_iter()
+                    .map(move |player_move| {
+                        let mut state = state.clone();
+                        state.moves.push(player_move);
+                        state
+                            .current_state
+                            .update([player_move, Command::Accelerate], &mut state.events);
+                        state
+                    })
             })
-        })
-        .max_by(|(_, a), (_, b)| compare_states(a, b))
+            .collect();
+    }
+
+    states
+        .into_iter()
+        .max_by(|a, b| compare_events(&a.events, &b.events))
+        .unwrap()
+        .moves
+        .into_iter()
+        .next()
         .unwrap()
-        .0;
-    naive_result
 }
 
 fn compare_states(a: &GameState, b: &GameState) -> Ordering {
@@ -56,7 +82,20 @@ fn compare_states(a: &GameState, b: &GameState) -> Ordering {
     }
 }
 
+fn compare_events(a: &GameStateUpdateEvents, b: &GameStateUpdateEvents) -> Ordering {
+    let a = &a.players[0];
+    let b = &b.players[0];
+    a.boosts_collected
+        .cmp(&b.boosts_collected)
+        .then(a.boosts_maintained.cmp(&b.boosts_maintained))
+        .then(a.distance_travelled.cmp(&b.distance_travelled))
+        .then(a.mud_hit.cmp(&b.mud_hit).reverse())
+        .then(a.boosts_used.cmp(&b.boosts_used).reverse())
+}
+
 fn choose_command_with_astar(state: &GameState) -> Command {
+    // TODO: Find all shortest paths, choose the one that has the
+    // highest end speed, or otherwise wins
     shortest_path_first_command(state).unwrap_or(Command::Accelerate)
 }
 
@@ -70,7 +109,10 @@ fn shortest_path_first_command(initial_state: &GameState) -> Option<Command> {
                 .filter(|player_move| *player_move != Command::UseOil)
                 .map(|player_move| {
                     let mut state = state.clone();
-                    state.update([player_move, Command::Decelerate]);
+                    state.update(
+                        [player_move, Command::Decelerate],
+                        &mut GameStateUpdateEvents::default(),
+                    );
                     (state, 1)
                 })
                 .collect::<Vec<_>>()
@@ -91,7 +133,10 @@ fn shortest_path_first_command(initial_state: &GameState) -> Option<Command> {
                 .filter(|player_move| *player_move != Command::UseOil)
                 .find(|player_move| {
                     let mut state = state.clone();
-                    state.update([*player_move, Command::Decelerate]);
+                    state.update(
+                        [*player_move, Command::Decelerate],
+                        &mut GameStateUpdateEvents::default(),
+                    );
                     state == *next
                 })
                 .unwrap();