From 63da94f7f1b25eddeb9ffd379f37c1a32e750fdb Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Tue, 21 May 2019 13:27:25 +0200 Subject: More robust game logic and reasoning --- src/command.rs | 9 ++-- src/game.rs | 132 +++++++++++++++++++++++++++++++---------------------- src/game/player.rs | 5 +- src/strategy.rs | 70 ++++++++-------------------- 4 files changed, 106 insertions(+), 110 deletions(-) (limited to 'src') diff --git a/src/command.rs b/src/command.rs index bca0f38..81e3d67 100644 --- a/src/command.rs +++ b/src/command.rs @@ -1,10 +1,11 @@ use std::fmt; use crate::geometry::Direction; +use crate::geometry::Point2d; #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] pub enum Command { - Move(i8, i8), - Dig(i8, i8), + Move(Point2d), + Dig(Point2d), Shoot(Direction), DoNothing, } @@ -13,8 +14,8 @@ impl fmt::Display for Command { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { use Command::*; match self { - Move(x, y) => write!(f, "move {} {}", x, y), - Dig(x, y) => write!(f, "dig {} {}", x, y), + Move(p) => write!(f, "move {} {}", p.x, p.y), + Dig(p) => write!(f, "dig {} {}", p.x, p.y), Shoot(dir) => write!(f, "shoot {}", dir), DoNothing => write!(f, "nothing"), } diff --git a/src/game.rs b/src/game.rs index 5ddbdfd..e3fb5c0 100644 --- a/src/game.rs +++ b/src/game.rs @@ -112,47 +112,65 @@ impl GameBoard { // Remove dead worms and update active worm for player in &mut self.players { player.clear_dead_worms(); - // Update the active worm - if player.worms.len() > 0 { - player.active_worm = (player.active_worm + 1).checked_rem(player.worms.len()).unwrap_or(0); - } + player.next_active_worm(); } } - pub fn simulate(&mut self, moves: [Command; 2]) -> SimulationOutcome { + pub fn simulate(&mut self, moves: [Command; 2]) { + self.simulate_moves(moves); + self.simulate_digs(moves); + self.simulate_shoots(moves); + + for player in &mut self.players { + player.clear_dead_worms(); + player.next_active_worm(); + } + + self.round += 1; + + self.outcome = match (self.players[0].worms.len(), self.players[1].worms.len(), self.round > self.max_rounds) { + (0, 0, _) => SimulationOutcome::Draw, + (_, 0, _) => SimulationOutcome::PlayerWon(0), + (0, _, _) => SimulationOutcome::PlayerWon(1), + (_, _, true) => SimulationOutcome::Draw, + _ => SimulationOutcome::Continue + }; + } + + fn simulate_moves(&mut self, moves: [Command; 2]) { match moves { - [Command::Move(x1, y1), Command::Move(x2, y2)] if x1 == x2 && y1 == y2 => { + [Command::Move(p1), Command::Move(p2)] if p1.x == p2.x && p1.y == p2.y => { // TODO: Get this from some sort of config rather let damage = 20; - debug_assert_eq!(Some(false), self.map.at(Point2d::new(x1, y1)), "Movement target wasn't empty, ({}, {})", x1, y1); + debug_assert_eq!(Some(false), self.map.at(Point2d::new(p1.x, p1.y)), "Movement target wasn't empty, ({}, {})", p1.x, p1.y); // Worms have a 50% chance of swapping places // here. I'm treating that as an edge case that I // don't need to handle for now. for player in &mut self.players { - player.active_worm_mut().health -= damage; + let worm = player.active_worm_mut(); + worm.health = worm.health.saturating_sub(damage); } }, _ => { for player_index in 0..moves.len() { - if let Command::Move(x, y) = moves[player_index] { - debug_assert_eq!(Some(false), self.map.at(Point2d::new(x, y)), "Movement target wasn't empty, ({}, {})", x, y); + if let Command::Move(p) = moves[player_index] { + debug_assert_eq!(Some(false), self.map.at(p), "Movement target wasn't empty, ({}, {})", p.x, p.y); let worm = self.players[player_index].active_worm_mut(); debug_assert!( - (worm.position.x - x).abs() <= 1 && - (worm.position.y - y).abs() <= 1, - "Tried to move too far away, ({}, {})", x, y + (worm.position.x - p.x).abs() <= 1 && + (worm.position.y - p.y).abs() <= 1, + "Tried to move too far away, ({}, {})", p.x, p.y ); - worm.position.x = x; - worm.position.y = y; - - self.powerups.retain(|p| { - if p.position == worm.position { - worm.health += p.value; + worm.position = p; + + self.powerups.retain(|power| { + if power.position == worm.position { + worm.health += power.value; false } else { true @@ -162,24 +180,28 @@ impl GameBoard { } } } - + } + + fn simulate_digs(&mut self, moves: [Command; 2]) { for player_index in 0..moves.len() { - if let Command::Dig(x, y) = moves[player_index] { + if let Command::Dig(p) = moves[player_index] { debug_assert!( - Some(true) == self.map.at(Point2d::new(x, y)) || - (player_index == 1 && moves[0] == Command::Dig(x, y)), - "Tried to dig through air, ({}, {})", x, y + Some(true) == self.map.at(p) || + (player_index == 1 && moves[0] == Command::Dig(p)), + "Tried to dig through air, ({}, {})", p.x, p.y ); debug_assert!{ - (self.players[player_index].active_worm().position.x - x).abs() <= 1 && - (self.players[player_index].active_worm().position.y - y).abs() <= 1, - "Tried to dig too far away, ({}, {})", x, y + (self.players[player_index].active_worm().position.x - p.x).abs() <= 1 && + (self.players[player_index].active_worm().position.y - p.y).abs() <= 1, + "Tried to dig too far away, ({}, {})", p.x, p.y }; - self.map.clear(Point2d::new(x, y)); + self.map.clear(p); } } - + } + + fn simulate_shoots(&mut self, moves: [Command; 2]) { for player_index in 0..moves.len() { if let Command::Shoot(dir) = moves[player_index] { let (center, weapon_range, weapon_damage) = { @@ -211,33 +233,38 @@ impl GameBoard { } } } + } - for player in &mut self.players { - player.clear_dead_worms(); - // Update the active worm - if player.worms.len() > 0 { - player.active_worm = (player.active_worm + 1).checked_rem(player.worms.len()).unwrap_or(0); - } - } + pub fn opponent(player_index: usize) -> usize { + (player_index + 1)%2 + } - self.round += 1; - self.outcome = match (self.players[0].worms.len(), self.players[1].worms.len(), self.round > self.max_rounds) { - (0, 0, _) => SimulationOutcome::Draw, - (_, 0, _) => SimulationOutcome::PlayerWon(0), - (0, _, _) => SimulationOutcome::PlayerWon(1), - (_, _, true) => SimulationOutcome::Draw, - _ => SimulationOutcome::Continue - }; + pub fn valid_move_commands(&self, player_index: usize) -> ArrayVec<[Command;8]> { + let worm = self.players[player_index].active_worm(); + let taken_positions = self.players.iter() + .flat_map(|p| p.worms.iter()) + .map(|w| w.position) + .collect::; 6]>>(); - self.outcome + Direction::all() + .iter() + .map(Direction::as_vec) + .map(|d| worm.position + d) + .filter(|p| !taken_positions.contains(p)) + .filter_map(|p| match self.map.at(p) { + Some(false) => Some(Command::Move(p)), + Some(true) => Some(Command::Dig(p)), + _ => None, + }) + .collect() } - - pub fn find_targets(&self, player_index: usize, center: Point2d, weapon_range: u8) -> Vec { + + pub fn valid_shoot_commands(&self, player_index: usize, center: Point2d, weapon_range: u8) -> ArrayVec<[Command;8]> { let range = weapon_range as i8; let dir_range = ((weapon_range as f32 + 1.) / 2f32.sqrt()).floor() as i8; - let mut directions: Vec = self.players[(player_index + 1)%2].worms + self.players[GameBoard::opponent(player_index)].worms .iter() .filter_map(|w| { let diff = w.position - center; @@ -265,17 +292,14 @@ impl GameBoard { } }) .filter(|(dir, range)| { + // TODO if this filtered all players, I don't need to dedup let diff = dir.as_vec(); !(1..*range).any(|distance| self.map.at(center + diff * distance) != Some(false) && !self.players[player_index].worms.iter().any(|w| w.position == center + diff * distance)) }) - .map(|(dir, _range)| dir) - .collect(); - - directions.sort(); - directions.dedup(); - directions + .map(|(dir, _range)| Command::Shoot(dir)) + .collect() } } diff --git a/src/game/player.rs b/src/game/player.rs index 3a9d36c..e083a7a 100644 --- a/src/game/player.rs +++ b/src/game/player.rs @@ -60,7 +60,10 @@ impl Player { } } } - // TODO: Cycle to next worm + + pub fn next_active_worm(&mut self) { + self.active_worm = (self.active_worm + 1).checked_rem(self.worms.len()).unwrap_or(0); + } } #[cfg(test)] diff --git a/src/strategy.rs b/src/strategy.rs index 16d639b..8d2eea5 100644 --- a/src/strategy.rs +++ b/src/strategy.rs @@ -9,6 +9,7 @@ use time::{Duration, PreciseTime}; use rand; use rand::prelude::*; +use arrayvec::ArrayVec; pub fn choose_move(state: &GameBoard, start_time: &PreciseTime, max_time: Duration) -> Command { let mut root_node = Node { @@ -110,6 +111,7 @@ fn mcts(node: &mut Node) -> Score { let mut new_state = node.state.clone(); new_state.simulate(commands); let score = rollout(&new_state); + // TODO: This could overshoot, trying to estimate from concluded game let unexplored = mcts_move_combo(&new_state); let new_node = Node { @@ -219,16 +221,11 @@ fn update(node: &mut Node, commands: [Command; 2], score: Score) { node.score_sum += score; } -// TODO: Remove all invalid moves onto other worms - fn heuristic_moves(state: &GameBoard, player_index: usize) -> Vec { let worm = state.players[player_index].active_worm(); - let mut shoots = state - .find_targets(player_index, worm.position, worm.weapon_range) - .iter() - .map(|d| Command::Shoot(*d)) - .collect::>(); + let shoots = state + .valid_shoot_commands(player_index, worm.position, worm.weapon_range); let closest_powerup = state.powerups .iter() @@ -245,30 +242,20 @@ fn heuristic_moves(state: &GameBoard, player_index: usize) -> Vec { .sum::() / state.players[player_index].worms.len() as i8 }; - let closest_opponent = state.players[(player_index + 1) % 2].worms + let closest_opponent = state.players[GameBoard::opponent(player_index)].worms .iter() .min_by_key(|w| (w.position - average_player_position).walking_distance()); let mut commands = if !shoots.is_empty() { // we're in combat now. Feel free to move anywhere. - let mut moves = Direction::all() - .iter() - .map(Direction::as_vec) - .map(|d| worm.position + d) - .filter_map(|p| match state.map.at(p) { - Some(false) => Some(Command::Move(p.x, p.y)), - Some(true) => Some(Command::Dig(p.x, p.y)), - _ => None, - }) - .collect::>(); - moves.append(&mut shoots); - moves + let moves = state.valid_move_commands(player_index); + moves.iter().chain(shoots.iter()).cloned().collect() } else if let Some(powerup) = closest_powerup { // there are powerups! Let's go grab the closest one. - moves_towards(state, worm.position, powerup.position) + moves_towards(state, player_index, powerup.position) } else if let Some(opponent) = closest_opponent { // we're not currently in combat. Let's go find the closest worm. - moves_towards(state, worm.position, opponent.position) + moves_towards(state, player_index, opponent.position) } else { // this shouldn't happen debug_assert!(false, "No valid heuristic moves"); @@ -278,46 +265,27 @@ fn heuristic_moves(state: &GameBoard, player_index: usize) -> Vec { commands } -fn moves_towards(state: &GameBoard, from: Point2d, to: Point2d) -> Vec { - let distance = (to - from).walking_distance(); - Direction::all() +fn moves_towards(state: &GameBoard, player_index: usize, to: Point2d) -> Vec { + let distance = (to - state.players[player_index].active_worm().position).walking_distance(); + state.valid_move_commands(player_index) .iter() - .map(Direction::as_vec) - .map(|d| from + d) - .filter(|p| (to - *p).walking_distance() < distance) - .filter_map(|p| match state.map.at(p) { - Some(false) => Some(Command::Move(p.x, p.y)), - Some(true) => Some(Command::Dig(p.x, p.y)), - _ => None, + .filter(|c| match c { + Command::Move(p) | Command::Dig(p) => (to - *p).walking_distance() < distance, + _ => false }) + .cloned() .collect() } -fn rollout_moves(state: &GameBoard, player_index: usize) -> Vec { +fn rollout_moves(state: &GameBoard, player_index: usize) -> ArrayVec<[Command; 8]> { let worm = state.players[player_index].active_worm(); - let shoots = state - .find_targets(player_index, worm.position, worm.weapon_range) - .iter() - .map(|d| Command::Shoot(*d)) - .collect::>(); + let shoots = state.valid_shoot_commands(player_index, worm.position, worm.weapon_range); if !shoots.is_empty() { return shoots; } // TODO: More directed destruction movements? - let mut moves = Direction::all() - .iter() - .map(Direction::as_vec) - .map(|d| worm.position + d) - .filter_map(|p| match state.map.at(p) { - Some(false) => Some(Command::Move(p.x, p.y)), - Some(true) => Some(Command::Dig(p.x, p.y)), - _ => None, - }) - .collect::>(); - - moves.push(Command::DoNothing); - moves + state.valid_move_commands(player_index) } -- cgit v1.2.3