From f3a65c87313d2952f83d5f43327260b7a9ab81cc Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sat, 18 Apr 2020 22:17:47 +0200 Subject: Shortest path on replays --- src/command.rs | 2 +- src/global_json.rs | 162 +++++++++++++++++++ src/lib.rs | 1 + src/state.rs | 20 ++- tests/import-replay.sh | 3 +- vroomba-analysis/Cargo.lock | 366 +++++++++++++++++++++++++++++++++++++++++++ vroomba-analysis/Cargo.toml | 10 ++ vroomba-analysis/src/main.rs | 63 ++++++++ 8 files changed, 621 insertions(+), 6 deletions(-) create mode 100644 src/global_json.rs create mode 100644 vroomba-analysis/Cargo.lock create mode 100644 vroomba-analysis/Cargo.toml create mode 100644 vroomba-analysis/src/main.rs 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 { + 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 { + 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, +} + +#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)] +#[serde(rename_all = "camelCase")] +pub struct JsonPlayer { + // id: usize, + position: JsonPosition, + speed: usize, + // state: JsonPlayerState, + powerups: Vec, + // 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, } -#[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::>() + }, + |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::>() + ); + println!("{}", shortest_path.1); +} + +#[derive(Debug, Clone, Hash, PartialEq, Eq)] +struct Node { + state: GameState, + last_command: Command, +} -- cgit v1.2.3