diff options
Diffstat (limited to 'src/lib.rs')
-rw-r--r-- | src/lib.rs | 89 |
1 files changed, 67 insertions, 22 deletions
@@ -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(); |