Shortest path on replays

8 files changed, 621 insertions, 6 deletions

diff --git a/src/command.rs b/src/command.rs
index f95ef98..1858202 100644
--- a/src/command.rs
+++ b/src/command.rs
@@ -1,6 +1,6 @@
 use std::fmt;
 
-#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
 pub enum Command {
     Nothing,
     Accelerate,
diff --git a/src/global_json.rs b/src/global_json.rs
new file mode 100644
index 0000000..a27cd00
--- /dev/null
+++ b/src/global_json.rs
@@ -0,0 +1,162 @@
+use std::fs::File;
+use std::io::prelude::*;
+
+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())?;
+    Ok(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: usize,
+    // state: JsonPlayerState,
+    powerups: Vec<JsonPowerup>,
+    // boosting: bool,
+    boost_counter: usize,
+}
+
+#[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 {
+    block_number: usize,
+    lane: usize,
+}
+
+// #[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) -> GameState {
+        GameState {
+            status: GameStatus::Continue,
+            players: [self.players[0].to_player(), self.players[1].to_player()],
+            obstacles: self
+                .blocks
+                .iter()
+                .filter(|cell| {
+                    cell.surface_object == JsonSurfaceObject::Mud
+                        || cell.surface_object == JsonSurfaceObject::OilSpill
+                })
+                .map(|cell| cell.position.to_position())
+                .collect(),
+            powerup_oils: self
+                .blocks
+                .iter()
+                .filter(|cell| cell.surface_object == JsonSurfaceObject::OilItem)
+                .map(|cell| cell.position.to_position())
+                .collect(),
+            powerup_boosts: self
+                .blocks
+                .iter()
+                .filter(|cell| cell.surface_object == JsonSurfaceObject::Boost)
+                .map(|cell| cell.position.to_position())
+                .collect(),
+            finish_lines: self
+                .blocks
+                .iter()
+                .filter(|cell| cell.surface_object == JsonSurfaceObject::FinishLine)
+                .map(|cell| cell.position.to_position())
+                .collect(),
+        }
+    }
+}
+
+impl JsonPlayer {
+    fn to_player(&self) -> Player {
+        Player {
+            position: self.position.to_position(),
+            next_position: self.position.to_position(),
+            speed: self.speed,
+            boost_remaining: self.boost_counter,
+            oils: self
+                .powerups
+                .iter()
+                .filter(|powerup| **powerup == JsonPowerup::Oil)
+                .count(),
+            boosts: self
+                .powerups
+                .iter()
+                .filter(|powerup| **powerup == JsonPowerup::Boost)
+                .count(),
+            finished: false,
+        }
+    }
+}
+
+impl JsonPosition {
+    fn to_position(&self) -> Position {
+        Position {
+            x: self.block_number,
+            y: self.lane,
+        }
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 902cb73..ac73f72 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,5 +1,6 @@
 pub mod command;
 pub mod consts;
+pub mod global_json;
 pub mod json;
 pub mod state;
 
diff --git a/src/state.rs b/src/state.rs
index e05a884..177db45 100644
--- a/src/state.rs
+++ b/src/state.rs
@@ -1,7 +1,7 @@
 use crate::command::Command;
 use crate::consts::*;
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
 pub enum GameStatus {
     Continue,
     PlayerOneWon,
@@ -9,7 +9,7 @@ pub enum GameStatus {
     Draw, // Until I add score I guess
 }
 
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
 pub struct GameState {
     pub status: GameStatus,
     pub players: [Player; 2],
@@ -19,7 +19,7 @@ pub struct GameState {
     pub finish_lines: Vec<Position>,
 }
 
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
 pub struct Player {
     pub position: Position,
     pub next_position: Position,
@@ -30,7 +30,7 @@ pub struct Player {
     pub finished: bool,
 }
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
 pub struct Position {
     pub x: usize,
     pub y: usize,
@@ -64,6 +64,18 @@ impl GameState {
         };
     }
 
+    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;
+            player.finished = false;
+        }
+    }
+
     fn do_command(&mut self, player_index: usize, command: &Command) {
         use Command::*;
         self.players[player_index].tick_boost();
diff --git a/tests/import-replay.sh b/tests/import-replay.sh
index c2da003..d0130b1 100755
--- a/tests/import-replay.sh
+++ b/tests/import-replay.sh
@@ -14,7 +14,8 @@ for round_folder in $REPLAY_FOLDER/Round*; do
     player_folders=( "$round_folder"/* )
     player_folder=${player_folders[0]}
     opponent_folder=${player_folders[1]}
-    
+
+    cp "$round_foler/GlobalState.json" "$OUTPUT_FOLDER/$round_name/GlobalState.json"
     cp "$player_folder/JsonMap.json" "$OUTPUT_FOLDER/$round_name/JsonMap.json"
     head -n 1 "$player_folder/PlayerCommand.txt" > "$OUTPUT_FOLDER/$round_name/PlayerCommand.txt"
     head -n 1 "$opponent_folder/PlayerCommand.txt" > "$OUTPUT_FOLDER/$round_name/OpponentCommand.txt"
diff --git a/vroomba-analysis/Cargo.lock b/vroomba-analysis/Cargo.lock
new file mode 100644
index 0000000..48826bb
--- /dev/null
+++ b/vroomba-analysis/Cargo.lock
@@ -0,0 +1,366 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+[[package]]
+name = "ansi_term"
+version = "0.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b"
+dependencies = [
+ "winapi",
+]
+
+[[package]]
+name = "anyhow"
+version = "1.0.28"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d9a60d744a80c30fcb657dfe2c1b22bcb3e814c1a1e3674f32bf5820b570fbff"
+
+[[package]]
+name = "atty"
+version = "0.2.14"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8"
+dependencies = [
+ "hermit-abi",
+ "libc",
+ "winapi",
+]
+
+[[package]]
+name = "autocfg"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d"
+
+[[package]]
+name = "bitflags"
+version = "1.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
+
+[[package]]
+name = "clap"
+version = "2.33.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5067f5bb2d80ef5d68b4c87db81601f0b75bca627bc2ef76b141d7b846a3c6d9"
+dependencies = [
+ "ansi_term",
+ "atty",
+ "bitflags",
+ "strsim",
+ "textwrap",
+ "unicode-width",
+ "vec_map",
+]
+
+[[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 = "heck"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "20564e78d53d2bb135c343b3f47714a56af2061f1c928fdb541dc7b9fdd94205"
+dependencies = [
+ "unicode-segmentation",
+]
+
+[[package]]
+name = "hermit-abi"
+version = "0.1.11"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8a0d737e0f947a1864e93d33fdef4af8445a00d1ed8dc0c8ddb73139ea6abf15"
+dependencies = [
+ "libc",
+]
+
+[[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 = "lazy_static"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
+
+[[package]]
+name = "libc"
+version = "0.2.69"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "99e85c08494b21a9054e7fe1374a732aeadaff3980b6990b94bfd3a70f690005"
+
+[[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-macro-error"
+version = "1.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "98e9e4b82e0ef281812565ea4751049f1bdcdfccda7d3f459f2e138a40c08678"
+dependencies = [
+ "proc-macro-error-attr",
+ "proc-macro2",
+ "quote",
+ "syn",
+ "version_check",
+]
+
+[[package]]
+name = "proc-macro-error-attr"
+version = "1.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4f5444ead4e9935abd7f27dc51f7e852a0569ac888096d5ec2499470794e2e53"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+ "syn-mid",
+ "version_check",
+]
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "df246d292ff63439fea9bc8c0a270bed0e390d5ebd4db4ba15aba81111b5abe3"
+dependencies = [
+ "unicode-xid",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2bdc6c187c65bca4260c9011c9e3132efe4909da44726bad24cf7572ae338d7f"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "ryu"
+version = "1.0.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "535622e6be132bccd223f4bb2b8ac8d53cda3c7a6394944d3b2b33fb974f9d76"
+
+[[package]]
+name = "serde"
+version = "1.0.106"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "36df6ac6412072f67cf767ebbde4133a5b2e88e76dc6187fa7104cd16f783399"
+dependencies = [
+ "serde_derive",
+]
+
+[[package]]
+name = "serde_derive"
+version = "1.0.106"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9e549e3abf4fb8621bd1609f11dfc9f5e50320802273b12f3811a67e6716ea6c"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "serde_json"
+version = "1.0.51"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "da07b57ee2623368351e9a0488bb0b261322a15a6e0ae53e243cbdc0f4208da9"
+dependencies = [
+ "itoa",
+ "ryu",
+ "serde",
+]
+
+[[package]]
+name = "serde_repr"
+version = "0.1.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cd02c7587ec314570041b2754829f84d873ced14a96d1fd1823531e11db40573"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "strsim"
+version = "0.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a"
+
+[[package]]
+name = "structopt"
+version = "0.3.13"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ff6da2e8d107dfd7b74df5ef4d205c6aebee0706c647f6bc6a2d5789905c00fb"
+dependencies = [
+ "clap",
+ "lazy_static",
+ "structopt-derive",
+]
+
+[[package]]
+name = "structopt-derive"
+version = "0.4.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a489c87c08fbaf12e386665109dd13470dcc9c4583ea3e10dd2b4523e5ebd9ac"
+dependencies = [
+ "heck",
+ "proc-macro-error",
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "syn"
+version = "1.0.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0df0eb663f387145cab623dea85b09c2c5b4b0aef44e945d928e682fce71bb03"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-xid",
+]
+
+[[package]]
+name = "syn-mid"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7be3539f6c128a931cf19dcee741c1af532c7fd387baa739c03dd2e96479338a"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "textwrap"
+version = "0.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d326610f408c7a4eb6f51c37c330e496b08506c9457c9d34287ecc38809fb060"
+dependencies = [
+ "unicode-width",
+]
+
+[[package]]
+name = "unicode-segmentation"
+version = "1.6.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e83e153d1053cbb5a118eeff7fd5be06ed99153f00dbcd8ae310c5fb2b22edc0"
+
+[[package]]
+name = "unicode-width"
+version = "0.1.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "caaa9d531767d1ff2150b9332433f32a24622147e5ebb1f26409d5da67afd479"
+
+[[package]]
+name = "unicode-xid"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "826e7639553986605ec5979c7dd957c7895e93eabed50ab2ffa7f6128a75097c"
+
+[[package]]
+name = "vec_map"
+version = "0.8.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "05c78687fb1a80548ae3250346c3db86a80a7cdd77bda190189f2d0a0987c81a"
+
+[[package]]
+name = "version_check"
+version = "0.9.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "078775d0255232fb988e6fccf26ddc9d1ac274299aaedcedce21c6f72cc533ce"
+
+[[package]]
+name = "vroomba"
+version = "0.1.0"
+dependencies = [
+ "anyhow",
+ "serde",
+ "serde_json",
+ "serde_repr",
+]
+
+[[package]]
+name = "vroomba_analysis"
+version = "0.1.0"
+dependencies = [
+ "anyhow",
+ "pathfinding",
+ "structopt",
+ "vroomba",
+]
+
+[[package]]
+name = "winapi"
+version = "0.3.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8093091eeb260906a183e6ae1abdba2ef5ef2257a21801128899c3fc699229c6"
+dependencies = [
+ "winapi-i686-pc-windows-gnu",
+ "winapi-x86_64-pc-windows-gnu",
+]
+
+[[package]]
+name = "winapi-i686-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
+
+[[package]]
+name = "winapi-x86_64-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
diff --git a/vroomba-analysis/Cargo.toml b/vroomba-analysis/Cargo.toml
new file mode 100644
index 0000000..fa5d203
--- /dev/null
+++ b/vroomba-analysis/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "vroomba_analysis"
+version = "0.1.0"
+edition = "2018"
+
+[dependencies]
+anyhow = "1.0.27"
+vroomba = { path = "../" }
+pathfinding = "2.0.4"
+structopt = "0.3"
\ No newline at end of file
diff --git a/vroomba-analysis/src/main.rs b/vroomba-analysis/src/main.rs
new file mode 100644
index 0000000..e1d244b
--- /dev/null
+++ b/vroomba-analysis/src/main.rs
@@ -0,0 +1,63 @@
+use pathfinding::directed::astar;
+use std::path::PathBuf;
+use structopt::StructOpt;
+use vroomba::command::Command;
+use vroomba::consts::*;
+use vroomba::global_json;
+use vroomba::state::{GameState, GameStatus};
+
+#[derive(StructOpt, Debug)]
+#[structopt(name = "vroomba-analysis")]
+struct Opt {
+    /// Path to GlobalState.json
+    path: PathBuf,
+}
+
+fn main() {
+    let opt = Opt::from_args();
+    let initial_node = Node {
+        state: global_json::read_initial_state_from_global_json_file(opt.path.to_str().unwrap())
+            .unwrap(),
+        last_command: Command::Nothing,
+    };
+
+    let shortest_path = astar::astar(
+        &initial_node,
+        |node| {
+            let player_moves = node.state.valid_moves(0);
+            player_moves
+                .into_iter()
+                .map(|player_move| {
+                    let mut state = node.state.clone();
+                    state.update([player_move, Command::Accelerate]);
+                    (
+                        Node {
+                            state,
+                            last_command: player_move,
+                        },
+                        1,
+                    )
+                })
+                .collect::<Vec<_>>()
+        },
+        |node| (WIDTH - node.state.players[0].position.x) / SPEED_BOOST,
+        |node| node.state.status != GameStatus::Continue,
+    )
+    .unwrap();
+
+    println!(
+        "{:?}",
+        shortest_path
+            .0
+            .into_iter()
+            .map(|node| node.last_command)
+            .collect::<Vec<_>>()
+    );
+    println!("{}", shortest_path.1);
+}
+
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+struct Node {
+    state: GameState,
+    last_command: Command,
+}