7 files changed, 917 insertions, 0 deletions
diff --git a/2020-overdrive/src/command.rs b/2020-overdrive/src/command.rs
new file mode 100644
index 0000000..1858202
--- /dev/null
+++ b/2020-overdrive/src/command.rs
@@ -0,0 +1,27 @@
+use std::fmt;
+
+#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
+pub enum Command {
+    Nothing,
+    Accelerate,
+    Decelerate,
+    TurnLeft,
+    TurnRight,
+    UseBoost,
+    UseOil,
+}
+
+impl fmt::Display for Command {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use Command::*;
+        match self {
+            Nothing => write!(f, "NOTHING"),
+            Accelerate => write!(f, "ACCELERATE"),
+            Decelerate => write!(f, "DECELERATE"),
+            TurnLeft => write!(f, "TURN_LEFT"),
+            TurnRight => write!(f, "TURN_RIGHT"),
+            UseBoost => write!(f, "USE_BOOST"),
+            UseOil => write!(f, "USE_OIL"),
+        }
+    }
+}
diff --git a/2020-overdrive/src/consts.rs b/2020-overdrive/src/consts.rs
new file mode 100644
index 0000000..8010eba
--- /dev/null
+++ b/2020-overdrive/src/consts.rs
@@ -0,0 +1,14 @@
+pub const SPEED_0: u16 = 0;
+pub const SPEED_1: u16 = 3;
+pub const SPEED_2: u16 = 6;
+pub const SPEED_3: u16 = 8;
+pub const SPEED_4: u16 = 9;
+pub const SPEED_BOOST: u16 = 15;
+
+pub const BOOST_DURATION: u8 = 5;
+
+pub const MIN_Y: u8 = 1;
+pub const HEIGHT: u8 = 4;
+pub const MAX_Y: u8 = MIN_Y + HEIGHT;
+
+pub const WIDTH: u16 = 1500;
diff --git a/2020-overdrive/src/global_json.rs b/2020-overdrive/src/global_json.rs
new file mode 100644
index 0000000..7ac109a
--- /dev/null
+++ b/2020-overdrive/src/global_json.rs
@@ -0,0 +1,165 @@
+use std::convert::TryInto;
+use std::fs::File;
+use std::io::prelude::*;
+use std::rc::Rc;
+
+use anyhow::Result;
+use serde::{Deserialize, Serialize};
+use serde_json;
+use serde_repr::{Deserialize_repr, Serialize_repr};
+
+use crate::state::*;
+
+pub fn read_initial_state_from_global_json_file(filename: &str) -> Result<GameState> {
+    let mut state = read_state_from_global_json_file(filename)?;
+    state.reset_players_to_start();
+    Ok(state)
+}
+
+pub fn read_state_from_global_json_file(filename: &str) -> Result<GameState> {
+    let mut file = File::open(filename)?;
+    let mut content = String::new();
+    file.read_to_string(&mut content)?;
+    let json_state: JsonState = serde_json::from_str(content.as_ref())?;
+    json_state.to_game_state()
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonState {
+    // pub current_round: usize,
+    // pub max_rounds: usize,
+    pub players: [JsonPlayer; 2],
+    pub blocks: Vec<JsonBlock>,
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonPlayer {
+    // id: usize,
+    position: JsonPosition,
+    speed: u16,
+    // state: JsonPlayerState,
+    powerups: Vec<JsonPowerup>,
+    // boosting: bool,
+    boost_counter: u8,
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonBlock {
+    position: JsonPosition,
+    surface_object: JsonSurfaceObject,
+    // occupied_by_player_id: usize,
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonPosition {
+    lane: u8,
+    block_number: u16,
+}
+
+// #[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+// #[serde(rename_all = "SCREAMING_SNAKE_CASE")]
+// pub enum JsonPlayerState {
+//     Ready,
+//     Nothing,
+//     TurningLeft,
+//     TurningRight,
+//     Accelerating,
+//     Decelarating,
+//     PickedUpPowerup,
+//     UsedBoost,
+//     UsedOil,
+//     HitMud,
+//     HitOil,
+//     Finishing,
+// }
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "SCREAMING_SNAKE_CASE")]
+pub enum JsonPowerup {
+    Boost,
+    Oil,
+}
+
+#[derive(Serialize_repr, Deserialize_repr, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+#[repr(u8)]
+pub enum JsonSurfaceObject {
+    Empty = 0,
+    Mud = 1,
+    OilSpill = 2,
+    OilItem = 3,
+    FinishLine = 4,
+    Boost = 5,
+}
+
+impl JsonState {
+    fn to_game_state(&self) -> Result<GameState> {
+        Ok(GameState {
+            status: GameStatus::Continue,
+            players: [self.players[0].to_player()?, self.players[1].to_player()?],
+            muds: Rc::new(
+                self.blocks
+                    .iter()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::Mud)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+            oil_spills: Rc::new(
+                self.blocks
+                    .iter()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::OilSpill)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+            powerup_oils: Rc::new(
+                self.blocks
+                    .iter()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::OilItem)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+            powerup_boosts: Rc::new(
+                self.blocks
+                    .iter()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::Boost)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+        })
+    }
+}
+
+impl JsonPlayer {
+    fn to_player(&self) -> Result<Player> {
+        Ok(Player {
+            position: self.position.to_position(),
+            speed: self.speed,
+            boost_remaining: self.boost_counter,
+            oils: self
+                .powerups
+                .iter()
+                .filter(|powerup| **powerup == JsonPowerup::Oil)
+                .count()
+                .try_into()?,
+            boosts: self
+                .powerups
+                .iter()
+                .filter(|powerup| **powerup == JsonPowerup::Boost)
+                .count()
+                .try_into()?,
+        })
+    }
+}
+
+impl JsonPosition {
+    fn to_position(&self) -> Position {
+        Position {
+            x: self.block_number,
+            y: self.lane,
+        }
+    }
+}
diff --git a/2020-overdrive/src/json.rs b/2020-overdrive/src/json.rs
new file mode 100644
index 0000000..82fc9fc
--- /dev/null
+++ b/2020-overdrive/src/json.rs
@@ -0,0 +1,185 @@
+use std::convert::TryInto;
+use std::fs::File;
+use std::io::prelude::*;
+use std::rc::Rc;
+
+use anyhow::Result;
+use serde::{Deserialize, Serialize};
+use serde_json;
+use serde_repr::{Deserialize_repr, Serialize_repr};
+
+use crate::state::*;
+
+pub fn read_state_from_json_file(filename: &str) -> Result<GameState> {
+    let mut file = File::open(filename)?;
+    let mut content = String::new();
+    file.read_to_string(&mut content)?;
+    let json_state: JsonState = serde_json::from_str(content.as_ref())?;
+    json_state.to_game_state()
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonState {
+    // pub current_round: usize,
+    // pub max_rounds: usize,
+    pub player: JsonPlayer,
+    pub opponent: JsonOpponent,
+    pub world_map: Vec<Vec<JsonWorldMapCell>>,
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonPlayer {
+    // id: usize,
+    position: JsonPosition,
+    speed: u16,
+    // state: JsonPlayerState,
+    powerups: Vec<JsonPowerup>,
+    // boosting: bool,
+    boost_counter: u8,
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonOpponent {
+    // id: usize,
+    position: JsonPosition,
+    speed: u16,
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonWorldMapCell {
+    position: JsonPosition,
+    surface_object: JsonSurfaceObject,
+    // occupied_by_player_id: usize,
+}
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+pub struct JsonPosition {
+    y: u8,
+    x: u16,
+}
+
+// #[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+// #[serde(rename_all = "SCREAMING_SNAKE_CASE")]
+// pub enum JsonPlayerState {
+//     Ready,
+//     Nothing,
+//     TurningLeft,
+//     TurningRight,
+//     Accelerating,
+//     Decelarating,
+//     PickedUpPowerup,
+//     UsedBoost,
+//     UsedOil,
+//     HitMud,
+//     HitOil,
+//     Finishing,
+// }
+
+#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "SCREAMING_SNAKE_CASE")]
+pub enum JsonPowerup {
+    Boost,
+    Oil,
+}
+
+#[derive(Serialize_repr, Deserialize_repr, Clone, Debug, PartialEq, Eq)]
+#[serde(rename_all = "camelCase")]
+#[repr(u8)]
+pub enum JsonSurfaceObject {
+    Empty = 0,
+    Mud = 1,
+    OilSpill = 2,
+    OilItem = 3,
+    FinishLine = 4,
+    Boost = 5,
+}
+
+impl JsonState {
+    fn to_game_state(&self) -> Result<GameState> {
+        Ok(GameState {
+            status: GameStatus::Continue,
+            players: [self.player.to_player()?, self.opponent.to_player()],
+            muds: Rc::new(
+                self.world_map
+                    .iter()
+                    .flatten()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::Mud)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+            oil_spills: Rc::new(
+                self.world_map
+                    .iter()
+                    .flatten()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::OilSpill)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+            powerup_oils: Rc::new(
+                self.world_map
+                    .iter()
+                    .flatten()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::OilItem)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+            powerup_boosts: Rc::new(
+                self.world_map
+                    .iter()
+                    .flatten()
+                    .filter(|cell| cell.surface_object == JsonSurfaceObject::Boost)
+                    .map(|cell| cell.position.to_position())
+                    .collect(),
+            ),
+        })
+    }
+}
+
+impl JsonPlayer {
+    fn to_player(&self) -> Result<Player> {
+        Ok(Player {
+            position: self.position.to_position(),
+            speed: self.speed,
+            boost_remaining: self.boost_counter,
+            oils: self
+                .powerups
+                .iter()
+                .filter(|powerup| **powerup == JsonPowerup::Oil)
+                .count()
+                .try_into()?,
+            boosts: self
+                .powerups
+                .iter()
+                .filter(|powerup| **powerup == JsonPowerup::Boost)
+                .count()
+                .try_into()?,
+        })
+    }
+}
+
+impl JsonOpponent {
+    // TODO: Track opponent powerups from round to round?
+    fn to_player(&self) -> Player {
+        Player {
+            position: self.position.to_position(),
+            speed: self.speed,
+            boost_remaining: 0,
+            oils: 0,
+            boosts: 0,
+        }
+    }
+}
+
+impl JsonPosition {
+    fn to_position(&self) -> Position {
+        Position {
+            x: self.x,
+            y: self.y,
+        }
+    }
+}
diff --git a/2020-overdrive/src/lib.rs b/2020-overdrive/src/lib.rs
new file mode 100644
index 0000000..c36a817
--- /dev/null
+++ b/2020-overdrive/src/lib.rs
@@ -0,0 +1,147 @@
+pub mod command;
+pub mod consts;
+pub mod global_json;
+pub mod json;
+pub mod state;
+
+use command::*;
+use consts::*;
+use pathfinding::prelude::*;
+use state::*;
+use std::cmp::Ordering;
+
+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 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
+                    })
+            })
+            .collect();
+    }
+
+    states
+        .into_iter()
+        .max_by(|a, b| compare_events(&a.events, &b.events))
+        .unwrap()
+        .moves
+        .into_iter()
+        .next()
+        .unwrap()
+}
+
+fn compare_states(a: &GameState, b: &GameState) -> Ordering {
+    if a.status == GameStatus::PlayerOneWon && b.status == GameStatus::PlayerOneWon {
+        a.players[0].speed.cmp(&b.players[0].speed)
+    } else if a.status == GameStatus::PlayerOneWon {
+        Ordering::Greater
+    } else if b.status == GameStatus::PlayerOneWon {
+        Ordering::Less
+    } else {
+        let weighted_position_a = a.players[0].position.x + a.players[0].boosts * 2;
+        let weighted_position_b = b.players[0].position.x + b.players[0].boosts * 2;
+
+        weighted_position_a
+            .cmp(&weighted_position_b)
+            .then(a.players[0].speed.cmp(&b.players[0].speed))
+            .then(a.players[0].position.x.cmp(&b.players[0].position.x))
+            .then(a.players[0].boosts.cmp(&b.players[0].boosts))
+    }
+}
+
+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)
+}
+
+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],
+                        &mut GameStateUpdateEvents::default(),
+                    );
+                    (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
+                .good_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],
+                        &mut GameStateUpdateEvents::default(),
+                    );
+                    state == *next
+                })
+                .unwrap();
+
+            player_move
+        })
+        .next()
+}
diff --git a/2020-overdrive/src/main.rs b/2020-overdrive/src/main.rs
new file mode 100644
index 0000000..c5f7857
--- /dev/null
+++ b/2020-overdrive/src/main.rs
@@ -0,0 +1,24 @@
+use std::io::prelude::*;
+use std::io::stdin;
+
+use vroomba::command::Command;
+use vroomba::*;
+
+fn main() {
+    for line in stdin().lock().lines() {
+        let round_number = line
+            .expect("Failed to read line from stdin: {}")
+            .parse::<usize>()
+            .expect("Round number was not an unsigned integer: {}");
+        let command =
+            match json::read_state_from_json_file(&format!("./rounds/{}/state.json", round_number))
+            {
+                Ok(state) => choose_command(round_number, &state),
+                Err(e) => {
+                    eprintln!("WARN: State file could not be parsed: {}", e);
+                    Command::Nothing
+                }
+            };
+        println!("C;{};{}", round_number, command);
+    }
+}
diff --git a/2020-overdrive/src/state.rs b/2020-overdrive/src/state.rs
new file mode 100644
index 0000000..acbce80
--- /dev/null
+++ b/2020-overdrive/src/state.rs
@@ -0,0 +1,355 @@
+use crate::command::Command;
+use crate::consts::*;
+use std::collections::BTreeSet;
+use std::ops::Bound::{Excluded, Included};
+use std::rc::Rc;
+
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
+pub enum GameStatus {
+    Continue,
+    PlayerOneWon,
+    PlayerTwoWon,
+    Draw, // Until I add score I guess
+}
+
+// TODO: Maintain sorted vecs for these BTrees? Do the range counts
+// with binary searches to find indices only.
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+pub struct GameState {
+    pub status: GameStatus,
+    pub players: [Player; 2],
+    pub muds: Rc<BTreeSet<Position>>,
+    pub oil_spills: Rc<BTreeSet<Position>>,
+    pub powerup_oils: Rc<BTreeSet<Position>>,
+    pub powerup_boosts: Rc<BTreeSet<Position>>,
+}
+
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+pub struct Player {
+    pub position: Position,
+    pub speed: u16,
+    pub boost_remaining: u8,
+    pub oils: u16,
+    pub boosts: u16,
+}
+
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
+pub struct Position {
+    pub y: u8,
+    pub x: u16,
+}
+
+#[derive(Debug, Clone, Default)]
+pub struct GameStateUpdateEvents {
+    pub players: [GameStatePlayerUpdateEvents; 2],
+}
+#[derive(Debug, Clone, Default)]
+pub struct GameStatePlayerUpdateEvents {
+    pub boosts_used: u16,
+    pub boosts_collected: u16,
+    pub boosts_maintained: u8,
+    pub mud_hit: u16,
+    pub oil_collected: u16,
+    pub distance_travelled: u16,
+}
+
+impl GameState {
+    pub fn update(&mut self, commands: [Command; 2], events: &mut GameStateUpdateEvents) {
+        if self.status != GameStatus::Continue {
+            return;
+        }
+
+        let next_positions = [
+            self.do_command(0, &commands[0], &mut events.players[0]),
+            self.do_command(1, &commands[1], &mut events.players[1]),
+        ];
+        let next_positions = self.update_player_collisions(next_positions, events);
+        self.update_player_travel(next_positions, events);
+
+        self.status = if self.players[0].finished() && self.players[1].finished() {
+            if self.players[0].speed > self.players[1].speed {
+                GameStatus::PlayerOneWon
+            } else if self.players[0].speed < self.players[1].speed {
+                GameStatus::PlayerTwoWon
+            } else {
+                GameStatus::Draw
+            }
+        } else if self.players[0].finished() {
+            GameStatus::PlayerOneWon
+        } else if self.players[1].finished() {
+            GameStatus::PlayerTwoWon
+        } else {
+            GameStatus::Continue
+        };
+    }
+
+    pub fn reset_players_to_start(&mut self) {
+        self.players[0].position = Position { x: 1, y: 1 };
+        self.players[1].position = Position { x: 1, y: 4 };
+        for player in &mut self.players {
+            player.speed = 5;
+            player.boost_remaining = 0;
+            player.oils = 0;
+            player.boosts = 0;
+        }
+    }
+
+    fn do_command(
+        &mut self,
+        player_index: usize,
+        command: &Command,
+        events: &mut GameStatePlayerUpdateEvents,
+    ) -> Position {
+        use Command::*;
+        self.players[player_index].tick_boost();
+        let mut next_y = self.players[player_index].position.y;
+
+        match command {
+            Nothing => {}
+            Accelerate => self.players[player_index].accelerate(),
+            Decelerate => self.players[player_index].decelerate(),
+            TurnLeft => next_y = next_y.saturating_sub(1).max(MIN_Y),
+            TurnRight => next_y = next_y.saturating_add(1).min(MAX_Y),
+            UseBoost => {
+                events.boosts_used += 1;
+                self.players[player_index].boost();
+            }
+            UseOil => {
+                debug_assert!(self.players[player_index].oils > 0);
+                self.players[player_index].oils = self.players[player_index].oils.saturating_sub(1);
+                let player_position = self.players[player_index].position;
+                let mut oil_spills = (*self.oil_spills).clone();
+                oil_spills.insert(Position {
+                    x: player_position.x.saturating_sub(1),
+                    y: player_position.y,
+                });
+                self.oil_spills = Rc::new(oil_spills);
+            }
+        }
+
+        let turning = match command {
+            TurnLeft | TurnRight => true,
+            _ => false,
+        };
+
+        let next_x = self.players[player_index].next_position_x(turning);
+        Position {
+            x: next_x,
+            y: next_y,
+        }
+    }
+
+    fn update_player_collisions(
+        &mut self,
+        next_positions: [Position; 2],
+        _events: &mut GameStateUpdateEvents,
+    ) -> [Position; 2] {
+        let same_lanes_before = self.players[0].position.y == self.players[1].position.y;
+        let same_lanes_after = next_positions[0].y == next_positions[1].y;
+        let first_passing_second = self.players[0].position.x < self.players[1].position.x
+            && next_positions[0].x >= next_positions[1].x;
+        let second_passing_first = self.players[1].position.x < self.players[0].position.x
+            && next_positions[1].x >= next_positions[0].x;
+        let same_x_after = next_positions[0].x == next_positions[1].x;
+
+        if same_lanes_before && same_lanes_after && first_passing_second {
+            [
+                Position {
+                    y: next_positions[0].y,
+                    x: next_positions[1].x.saturating_sub(1),
+                },
+                next_positions[1],
+            ]
+        } else if same_lanes_before && same_lanes_after && second_passing_first {
+            [
+                next_positions[0],
+                Position {
+                    y: next_positions[1].y,
+                    x: next_positions[0].x.saturating_sub(1),
+                },
+            ]
+        } else if same_lanes_after && same_x_after {
+            [
+                Position {
+                    y: self.players[0].position.y,
+                    x: self.players[0].next_position_x(true),
+                },
+                Position {
+                    y: self.players[1].position.y,
+                    x: self.players[1].next_position_x(true),
+                },
+            ]
+        } else {
+            next_positions
+        }
+    }
+
+    fn update_player_travel(
+        &mut self,
+        next_positions: [Position; 2],
+        events: &mut GameStateUpdateEvents,
+    ) {
+        for (i, (player, next_position)) in self
+            .players
+            .iter_mut()
+            .zip(next_positions.iter())
+            .enumerate()
+        {
+            player.move_along(
+                *next_position,
+                &self.muds,
+                &self.oil_spills,
+                &self.powerup_oils,
+                &self.powerup_boosts,
+                &mut events.players[i],
+            );
+        }
+    }
+
+    pub fn valid_moves(&self, player_index: usize) -> Vec<Command> {
+        let player = &self.players[player_index];
+        let mut result = Vec::with_capacity(7);
+        result.push(Command::Nothing);
+        result.push(Command::Accelerate);
+        if player.speed > SPEED_0 {
+            result.push(Command::Decelerate);
+        }
+        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
+    }
+
+    pub fn good_moves(&self, player_index: usize) -> Vec<Command> {
+        let player = &self.players[player_index];
+        let mut result = Vec::with_capacity(5);
+        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 {
+    fn accelerate(&mut self) {
+        self.speed = match self.speed {
+            i if i < SPEED_1 => SPEED_1,
+            i if i < SPEED_2 => SPEED_2,
+            i if i < SPEED_3 => SPEED_3,
+            SPEED_BOOST => SPEED_BOOST,
+            _ => SPEED_4,
+        };
+    }
+
+    fn decelerate(&mut self) {
+        self.speed = match self.speed {
+            i if i <= SPEED_1 => SPEED_0,
+            i if i <= SPEED_2 => SPEED_1,
+            i if i <= SPEED_3 => SPEED_2,
+            i if i <= SPEED_4 => SPEED_3,
+            _ => SPEED_4,
+        };
+        self.boost_remaining = 0;
+    }
+
+    fn decelerate_from_obstacle(&mut self) {
+        self.speed = match self.speed {
+            i if i <= SPEED_2 => SPEED_1,
+            i if i <= SPEED_3 => SPEED_2,
+            i if i <= SPEED_4 => SPEED_3,
+            _ => SPEED_4,
+        };
+        self.boost_remaining = 0;
+    }
+
+    fn boost(&mut self) {
+        debug_assert!(self.boosts > 0);
+        self.speed = SPEED_BOOST;
+        self.boost_remaining = BOOST_DURATION;
+        self.boosts = self.boosts.saturating_sub(1);
+    }
+
+    fn tick_boost(&mut self) {
+        self.boost_remaining = self.boost_remaining.saturating_sub(1);
+        if self.boost_remaining == 0 && self.speed == SPEED_BOOST {
+            self.speed = SPEED_4;
+        }
+    }
+
+    fn next_position_x(&mut self, turning: bool) -> u16 {
+        if turning {
+            self.position.x.saturating_add(self.speed.saturating_sub(1))
+        } else {
+            self.position.x.saturating_add(self.speed)
+        }
+    }
+
+    fn move_along(
+        &mut self,
+        next_position: Position,
+        muds: &BTreeSet<Position>,
+        oil_spills: &BTreeSet<Position>,
+        powerup_oils: &BTreeSet<Position>,
+        powerup_boosts: &BTreeSet<Position>,
+        events: &mut GameStatePlayerUpdateEvents,
+    ) {
+        let range = (
+            Included(Position {
+                y: next_position.y,
+                x: self.position.x.saturating_add(1),
+            }),
+            Excluded(Position {
+                y: next_position.y,
+                x: next_position.x.saturating_add(1),
+            }),
+        );
+
+        let mud_hit = muds
+            .range(range)
+            .count()
+            .saturating_add(oil_spills.range(range).count());
+        for _ in 0..mud_hit {
+            self.decelerate_from_obstacle();
+        }
+
+        let oil_collected = powerup_oils.range(range).count() as u16;
+        self.oils = self.oils.saturating_add(oil_collected);
+        let boosts_collected = powerup_boosts.range(range).count() as u16;
+        self.boosts = self.boosts.saturating_add(boosts_collected);
+
+        events.mud_hit = events.mud_hit.saturating_add(mud_hit as u16);
+        events.boosts_collected = events.boosts_collected.saturating_add(boosts_collected);
+        events.oil_collected = events.oil_collected.saturating_add(oil_collected);
+        events.distance_travelled = events
+            .distance_travelled
+            .saturating_add(next_position.x.saturating_sub(self.position.x));
+        if self.speed == SPEED_BOOST {
+            events.boosts_maintained = events.boosts_maintained.saturating_add(1);
+        }
+
+        self.position = next_position;
+    }
+
+    fn finished(&self) -> bool {
+        self.position.x >= WIDTH
+    }
+}