From 3f5492b2bb67326be43cd7c5ba02ccf0ba1ae0e3 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 21:27:56 +0200 Subject: Refile for merging repos --- 2019-worms/src/game.rs | 779 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 779 insertions(+) create mode 100644 2019-worms/src/game.rs (limited to '2019-worms/src/game.rs') diff --git a/2019-worms/src/game.rs b/2019-worms/src/game.rs new file mode 100644 index 0000000..00289a0 --- /dev/null +++ b/2019-worms/src/game.rs @@ -0,0 +1,779 @@ +use crate::command::{Action, Command}; +use crate::constants::*; +use crate::geometry::*; +use crate::json; + +mod player; +use player::*; + +mod powerup; +use powerup::*; + +pub mod map; +use map::*; + +use arrayvec::ArrayVec; + +#[derive(Debug, PartialEq, Eq, Clone)] +pub struct GameBoard { + pub round: u16, + pub max_rounds: u16, + pub players: [Player; 2], + pub powerups: ArrayVec<[Powerup; 2]>, + pub map: Map, + pub occupied_cells: ArrayVec<[Point2d; 6]>, + pub outcome: SimulationOutcome, +} + +#[derive(Debug, PartialEq, Eq, Clone, Copy)] +pub enum SimulationOutcome { + PlayerWon(usize), + Draw, + Continue, +} + +impl GameBoard { + pub fn new(json: json::State) -> GameBoard { + let player = Player { + active_worm: json.active_worm_index().unwrap(), + moves_score: json.my_player.score - json.my_player.health_score(), + select_moves: json.my_player.remaining_worm_selections, + worms: json + .my_player + .worms + .iter() + .map(|w| Worm { + id: w.id, + health: w.health, + position: Point2d::new(w.position.x, w.position.y), + rounds_until_unfrozen: w.rounds_until_unfrozen, + bombs: w.banana_bombs.as_ref().map(|b| b.count).unwrap_or(0), + snowballs: w.snowballs.as_ref().map(|b| b.count).unwrap_or(0), + }) + .collect(), + }; + + let opponent = Player { + active_worm: 0, + moves_score: json.opponents[0].score - json.opponents[0].health_score(), + select_moves: json.opponents[0].remaining_worm_selections, + worms: json + .opponents + .iter() + .flat_map(|o| &o.worms) + .map(|w| Worm { + id: w.id, + health: w.health, + position: Point2d::new(w.position.x, w.position.y), + rounds_until_unfrozen: w.rounds_until_unfrozen, + bombs: if w.profession == json::WormType::Agent { + STARTING_BOMBS + } else { + 0 + }, + snowballs: if w.profession == json::WormType::Technologist { + STARTING_SNOWBALLS + } else { + 0 + }, + }) + .collect(), + }; + + let mut map = Map::default(); + for cell in json.map.iter().flatten() { + if cell.cell_type == json::CellType::Dirt { + map.set(Point2d::new(cell.x, cell.y)) + } + } + + let players = [player, opponent]; + let occupied_cells = players + .iter() + .flat_map(|p| p.worms.iter()) + .map(|w| w.position) + .collect(); + + GameBoard { + round: json.current_round, + max_rounds: json.max_rounds, + players, + powerups: json + .map + .iter() + .flatten() + .filter_map(|c| { + c.powerup.as_ref().map(|_p| Powerup { + position: Point2d::new(c.x, c.y), + }) + }) + .collect(), + map, + occupied_cells, + outcome: SimulationOutcome::Continue, + } + } + + pub fn update(&mut self, json: json::State) { + for w in &json.my_player.worms { + if let Some(worm) = self.players[0].find_worm_mut(w.id) { + worm.health = w.health; + worm.position = Point2d::new(w.position.x, w.position.y); + worm.bombs = w.banana_bombs.as_ref().map(|b| b.count).unwrap_or(0); + worm.snowballs = w.snowballs.as_ref().map(|b| b.count).unwrap_or(0); + } + } + for w in json.opponents.iter().flat_map(|o| &o.worms) { + if let Some(worm) = self.players[1].find_worm_mut(w.id) { + worm.health = w.health; + worm.position = Point2d::new(w.position.x, w.position.y); + } + } + + if !self.players[1].active_worm_is_frozen() { + if json + .opponents + .iter() + .any(|o| o.previous_command.starts_with("banana")) + { + for worm in &mut self.players[1].worms { + worm.bombs = worm.bombs.saturating_sub(1); + } + } + if json + .opponents + .iter() + .any(|o| o.previous_command.starts_with("snowball")) + { + for worm in &mut self.players[1].worms { + worm.snowballs = worm.snowballs.saturating_sub(1); + } + } + } + + self.players[0].moves_score = json.my_player.score - json.my_player.health_score(); + self.players[1].moves_score = json.opponents[0].score - json.opponents[0].health_score(); + + self.players[0].select_moves = json.my_player.remaining_worm_selections; + self.players[1].select_moves = json.opponents[0].remaining_worm_selections; + + self.powerups = json + .map + .iter() + .flatten() + .filter_map(|c| { + c.powerup.as_ref().map(|_p| Powerup { + position: Point2d::new(c.x, c.y), + }) + }) + .collect(); + + for cell in json.map.iter().flatten() { + let point = Point2d::new(cell.x, cell.y); + + if cfg!(debug_assertions) { + // This checks if my lava map is the same as the game + // engine's lava map. It's off by one because the game + // engine will update its one at the beginning of + // processing the round. + let lava = LAVA_MAP[self.round as usize]; + + let lava_at = lava.at(point); + // NB: Map hasn't been updated yet, so it can be used to tell previous state. + match (&cell.cell_type, self.map.at(point)) { + (json::CellType::Air, Some(false)) => assert!( + lava_at == Some(false), + "Lava at {:?} expected Some(false), but found {:?}", + point, + lava_at + ), + (json::CellType::Air, _) => assert!( + lava_at.is_some(), + "Lava at {:?} expected Some(_), but found {:?}", + point, + lava_at + ), + (json::CellType::Lava, _) => assert!( + lava_at == Some(true), + "Lava at {:?} expected Some(true), but found {:?}", + point, + lava_at + ), + (json::CellType::DeepSpace, _) => assert!( + lava_at == None, + "Lava at {:?} expected None, but found {:?}", + point, + lava_at + ), + (json::CellType::Dirt, _) => assert!( + lava_at.is_some(), + "Lava at {:?} expected Some(_), but found {:?}", + point, + lava_at + ), + }; + } + + if cell.cell_type == json::CellType::Air { + self.map.clear(point) + } + } + + self.clear_dead_worms(); + self.players[0].active_worm = json.active_worm_index().unwrap_or(0); + self.players[1].active_worm = json.opponent_active_worm_index().unwrap_or(0); + + self.round += 1; + debug_assert_eq!(json.current_round, self.round); + } + + pub fn simulate(&mut self, moves: [Command; 2]) { + self.simulate_worms_on_lava(); + self.simulate_tick_frozen_timers(); + + self.simulate_select(moves); + + let actions = self.identify_actions(moves); + + self.simulate_moves(actions); + self.simulate_digs(actions); + self.simulate_bombs(actions); + self.simulate_shoots(actions); + self.simulate_snowballs(actions); + + self.clear_dead_worms(); + + for player in &mut self.players { + 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_worms_on_lava(&mut self) { + let lava_map = LAVA_MAP[self.round as usize]; + self.players + .iter_mut() + .flat_map(|p| p.worms.iter_mut()) + .filter(|w| lava_map.at(w.position) == Some(true)) + .for_each(|ref mut w| w.health -= LAVA_DAMAGE); + } + + fn simulate_tick_frozen_timers(&mut self) { + self.players + .iter_mut() + .flat_map(|p| p.worms.iter_mut()) + .filter(|w| w.health > 0) + .for_each(|ref mut w| { + w.rounds_until_unfrozen = w.rounds_until_unfrozen.saturating_sub(1) + }); + } + + fn identify_actions(&self, moves: [Command; 2]) -> [Action; 2] { + let mut it = self.players.iter().zip(moves.iter()).map(|(p, m)| { + if p.active_worm_is_frozen() { + Action::DoNothing + } else { + m.action + } + }); + [it.next().unwrap(), it.next().unwrap()] + } + + fn simulate_select(&mut self, moves: [Command; 2]) { + moves + .iter() + .zip(self.players.iter_mut()) + .filter(|(_m, player)| !player.active_worm_is_frozen()) + .for_each(|(m, player)| { + if let Some(worm) = m.worm { + debug_assert!( + player.select_moves > 0, + "Could not make select move, out of select tokens" + ); + player.select_moves = player.select_moves.saturating_sub(1); + player.active_worm = player.find_worm_position(worm).unwrap_or(0); + } + }); + } + + fn simulate_moves(&mut self, actions: [Action; 2]) { + match actions { + [Action::Move(p1), Action::Move(p2)] if p1.x == p2.x && p1.y == p2.y => { + let damage = COLLISION_DAMAGE; + + 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 { + if let Some(worm) = player.active_worm_mut() { + worm.health -= damage; + } + // You might expect damage score too here, but nope + player.moves_score += MOVE_SCORE; + } + } + _ => { + for player_index in 0..actions.len() { + if let Action::Move(p) = actions[player_index] { + debug_assert_eq!( + Some(false), + self.map.at(p), + "Movement target wasn't empty, ({}, {})", + p.x, + p.y + ); + + self.players[player_index].moves_score += MOVE_SCORE; + + if let Some(worm) = self.players[player_index].active_worm_mut() { + debug_assert!( + (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 = p; + + self.powerups.retain(|power| { + if power.position == worm.position { + worm.health += HEALTH_PACK_VALUE; + false + } else { + true + } + }); + } + } + } + } + } + } + + fn simulate_digs(&mut self, actions: [Action; 2]) { + for player_index in 0..actions.len() { + if let Action::Dig(p) = actions[player_index] { + debug_assert!( + Some(true) == self.map.at(p) + || (player_index == 1 && actions[0] == Action::Dig(p)), + "Tried to dig through air, ({}, {})", + p.x, + p.y + ); + debug_assert! { + (self.players[player_index].active_worm().unwrap().position.x - p.x).abs() <= 1 && + (self.players[player_index].active_worm().unwrap().position.y - p.y).abs() <= 1, + "Tried to dig too far away, ({}, {})", p.x, p.y + }; + + self.players[player_index].moves_score += DIG_SCORE; + + self.map.clear(p); + } + } + } + + fn simulate_bombs(&mut self, actions: [Action; 2]) { + // NB: Damage radius has the cell distance rounded UP, throwing range has the cell distance rounded DOWN + + let map_clone: Map = self.map; + + for player_index in 0..actions.len() { + if let Action::Bomb(p) = actions[player_index] { + if self.map.at(p).is_some() { + if let Some(worm) = self.players[player_index].active_worm_mut() { + debug_assert!(worm.bombs > 0, "Worm is throwing a bomb it doesn't have"); + debug_assert!((worm.position - p).magnitude_squared() < 6 * 6); // max range is 5, but it's 5 after rounding down + + worm.bombs = worm.bombs.saturating_sub(1); + + for &(damage_offset, weapon_damage) in BOMB_DAMAGES.iter() { + let target = p + damage_offset; + + if map_clone.at(target) == Some(true) { + self.map.clear(target); + self.players[player_index].moves_score += DIG_SCORE; + } + self.powerups.retain(|powerup| powerup.position != target); + + let target_own_worm: Option<&mut Worm> = self.players[player_index] + .worms + .iter_mut() + .find(|w| w.position == target); + + if let Some(target_worm) = target_own_worm { + target_worm.health -= weapon_damage; + self.players[player_index].moves_score -= + weapon_damage * ATTACK_SCORE_MULTIPLIER; + if target_worm.health <= 0 { + self.players[player_index].moves_score -= KILL_SCORE; + } + } + + let target_opponent_worm: Option<&mut Worm> = self.players + [GameBoard::opponent(player_index)] + .worms + .iter_mut() + .find(|w| w.position == target); + if let Some(target_worm) = target_opponent_worm { + target_worm.health -= weapon_damage; + self.players[player_index].moves_score += + weapon_damage * ATTACK_SCORE_MULTIPLIER; + if target_worm.health <= 0 { + self.players[player_index].moves_score += KILL_SCORE; + } + } + } + } + } + } + } + } + + pub fn simulate_snowballs(&mut self, actions: [Action; 2]) { + for player_index in 0..actions.len() { + if let Action::Snowball(p) = actions[player_index] { + if self.map.at(p).is_some() { + if let Some(worm) = self.players[player_index].active_worm_mut() { + debug_assert!( + worm.snowballs > 0, + "Worm is throwing a snowball it doesn't have" + ); + debug_assert!((worm.position - p).magnitude_squared() < 6 * 6); // max range is 5, but it's 5 after rounding down + + worm.snowballs = worm.snowballs.saturating_sub(1); + + for &freeze_offset in SNOWBALL_FREEZES.iter() { + let target = p + freeze_offset; + + let target_own_worm: Option<&mut Worm> = self.players[player_index] + .worms + .iter_mut() + .find(|w| w.position == target); + + if let Some(target_worm) = target_own_worm { + target_worm.rounds_until_unfrozen = FREEZE_DURATION; + self.players[player_index].moves_score -= FREEZE_SCORE; + } + + let target_opponent_worm: Option<&mut Worm> = self.players + [GameBoard::opponent(player_index)] + .worms + .iter_mut() + .find(|w| w.position == target); + if let Some(target_worm) = target_opponent_worm { + target_worm.rounds_until_unfrozen = FREEZE_DURATION; + self.players[player_index].moves_score += FREEZE_SCORE; + } + } + } + } + } + } + } + + fn simulate_shoots(&mut self, actions: [Action; 2]) { + 'players_loop: for player_index in 0..actions.len() { + if let Action::Shoot(dir) = actions[player_index] { + if let Some(worm) = self.players[player_index].active_worm() { + let center = worm.position; + let diff = dir.as_vec(); + + let range = if dir.is_diagonal() { + SHOOT_RANGE_DIAGONAL + } else { + SHOOT_RANGE + }; + + for distance in 1..=range { + let target = center + diff * distance; + match self.map.at(target) { + Some(false) => { + let target_own_worm: Option<&mut Worm> = self.players[player_index] + .worms + .iter_mut() + .find(|w| w.position == target); + + if let Some(target_worm) = target_own_worm { + target_worm.health -= SHOOT_DAMAGE; + self.players[player_index].moves_score -= + SHOOT_DAMAGE * ATTACK_SCORE_MULTIPLIER; + if target_worm.health <= 0 { + self.players[player_index].moves_score -= KILL_SCORE; + } + continue 'players_loop; + } + + let target_opponent_worm: Option<&mut Worm> = self.players + [GameBoard::opponent(player_index)] + .worms + .iter_mut() + .find(|w| w.position == target); + + if let Some(target_worm) = target_opponent_worm { + target_worm.health -= SHOOT_DAMAGE; + self.players[player_index].moves_score += + SHOOT_DAMAGE * ATTACK_SCORE_MULTIPLIER; + if target_worm.health <= 0 { + self.players[player_index].moves_score += KILL_SCORE; + } + + continue 'players_loop; + } + } + _ => break, + } + } + + // You get here if the shot missed. Hits are an early return. + self.players[player_index].moves_score += MISSED_ATTACK_SCORE; + } + } + } + } + + fn clear_dead_worms(&mut self) { + for player in &mut self.players { + player.clear_dead_worms(); + } + + self.occupied_cells = self + .players + .iter() + .flat_map(|p| p.worms.iter()) + .map(|w| w.position) + .collect(); + } + + pub fn opponent(player_index: usize) -> usize { + (player_index + 1) % 2 + } + + fn selects_iter(&self, player_index: usize) -> impl Iterator, &Worm)> { + let no_select = self.players[player_index] + .active_worm() + .into_iter() + .map(|w| (None, w)); + + let has_select_moves = self.players[player_index].select_moves > 0; + let active_worm_index = self.players[player_index].active_worm; + let selects = self.players[player_index] + .worms + .iter() + .enumerate() + .filter(move |(p, _w)| has_select_moves && active_worm_index != *p) + .map(|(_p, w)| (Some(w.id), w)); + + no_select.chain(selects) + } + + fn pruned_valid_move_commands(&self, player_index: usize) -> ArrayVec<[Command; 8]> { + self.players[player_index] + .active_worm() + .into_iter() + .flat_map(|worm| { + // TODO: If you aren't on lava, don't step onto the lava + Direction::ALL + .iter() + .map(Direction::as_vec) + .map(move |d| worm.position + d) + .filter(|p| !self.occupied_cells.contains(p)) + .filter_map(|p| match self.map.at(p) { + Some(false) => Some(Action::Move(p)), + Some(true) => Some(Action::Dig(p)), + _ => None, + }) + .map(Command::new) + }) + .collect() + } + + fn pruned_valid_bomb_commands(&self, player_index: usize) -> Vec { + self.selects_iter(player_index) + .filter(|(_, worm)| worm.bombs > 0) + .flat_map(|(select, worm)| { + let mut result = Vec::with_capacity((BOMB_RANGE * 2 + 1).pow(2) as usize - 12); + let own_worm_positions: ArrayVec<[Point2d; 3]> = self.players[player_index] + .worms + .iter() + .map(|w| w.position) + .collect(); + let opponent_worm_positions: ArrayVec<[Point2d; 3]> = self.players + [GameBoard::opponent(player_index)] + .worms + .iter() + .map(|w| w.position) + .collect(); + + for y in worm.position.y - BOMB_RANGE..=worm.position.y + BOMB_RANGE { + for x in worm.position.x - BOMB_RANGE..=worm.position.x + BOMB_RANGE { + let target = Point2d::new(x, y); + if self.map.at(target).is_some() + && (worm.position - target).magnitude_squared() + < (BOMB_RANGE + 1).pow(2) + { + let own_affected_worms = own_worm_positions.iter().any(|p| { + (target - *p).magnitude_squared() + <= BOMB_DAMAGE_RANGE * BOMB_DAMAGE_RANGE + }); + let opponent_affected_worms = opponent_worm_positions.iter().any(|p| { + (target - *p).magnitude_squared() + <= BOMB_DAMAGE_RANGE * BOMB_DAMAGE_RANGE + }); + + if !own_affected_worms && opponent_affected_worms { + result.push(Command { + worm: select, + action: Action::Bomb(target), + }); + } + } + } + } + + result + }) + .collect() + } + + fn pruned_valid_snowball_commands(&self, player_index: usize) -> Vec { + self.selects_iter(player_index) + .filter(|(_, worm)| worm.snowballs > 0) + .flat_map(|(select, worm)| { + let mut result = Vec::with_capacity((SNOWBALL_RANGE * 2 + 1).pow(2) as usize - 12); + let own_worm_positions: ArrayVec<[Point2d; 3]> = self.players[player_index] + .worms + .iter() + .map(|w| w.position) + .collect(); + let opponent_worm_positions: ArrayVec<[Point2d; 3]> = self.players + [GameBoard::opponent(player_index)] + .worms + .iter() + .map(|w| w.position) + .collect(); + + for y in worm.position.y - SNOWBALL_RANGE..=worm.position.y + SNOWBALL_RANGE { + for x in worm.position.x - SNOWBALL_RANGE..=worm.position.x + SNOWBALL_RANGE { + let target = Point2d::new(x, y); + if self.map.at(target).is_some() + && (worm.position - target).magnitude_squared() + < (SNOWBALL_RANGE + 1).pow(2) + { + let own_affected_worms = own_worm_positions.iter().any(|p| { + (target - *p).magnitude_squared() + <= SNOWBALL_FREEZE_RANGE * SNOWBALL_FREEZE_RANGE + }); + let opponent_affected_worms = opponent_worm_positions.iter().any(|p| { + (target - *p).magnitude_squared() + <= SNOWBALL_FREEZE_RANGE * SNOWBALL_FREEZE_RANGE + }); + + if !own_affected_worms && opponent_affected_worms { + result.push(Command { + worm: select, + action: Action::Snowball(target), + }); + } + } + } + } + + result + }) + .collect() + } + + fn pruned_valid_shoot_commands(&self, player_index: usize) -> Vec { + self.selects_iter(player_index) + .flat_map(|(select, worm)| { + self.players[GameBoard::opponent(player_index)] + .worms + .iter() + .filter_map(move |w| { + let diff = w.position - worm.position; + if diff.x == 0 && diff.y.abs() <= SHOOT_RANGE { + if diff.y > 0 { + Some((Direction::South, diff.y)) + } else { + Some((Direction::North, -diff.y)) + } + } else if diff.y == 0 && diff.x.abs() <= SHOOT_RANGE { + if diff.x > 0 { + Some((Direction::East, diff.x)) + } else { + Some((Direction::West, -diff.x)) + } + } else if diff.x.abs() == diff.y.abs() + && diff.x.abs() <= SHOOT_RANGE_DIAGONAL + { + match (diff.x > 0, diff.y > 0) { + (true, true) => Some((Direction::SouthEast, diff.x)), + (false, true) => Some((Direction::SouthWest, -diff.x)), + (true, false) => Some((Direction::NorthEast, diff.x)), + (false, false) => Some((Direction::NorthWest, -diff.x)), + } + } else { + None + } + }) + .filter(move |(dir, range)| { + let diff = dir.as_vec(); + // NB: This is up to range EXCLUSIVE, so if there's + // anything in the way, even another good shot, skip. + !(1..*range).any(|distance| { + self.map.at(worm.position + diff * distance) != Some(false) + && !self + .players + .iter() + .flat_map(|p| p.worms.iter()) + .any(|w| w.position == worm.position + diff * distance) + }) + }) + .map(move |(dir, _range)| Command { + worm: select, + action: Action::Shoot(dir), + }) + }) + .collect() + } + + pub fn pruned_valid_moves(&self, player_index: usize) -> Vec { + if self.players[player_index].active_worm_is_frozen_after_tick() { + vec![Command::new(Action::DoNothing)] + } else { + self.pruned_valid_shoot_commands(player_index) + .iter() + .chain(self.pruned_valid_move_commands(player_index).iter()) + .chain(self.pruned_valid_bomb_commands(player_index).iter()) + .chain(self.pruned_valid_snowball_commands(player_index).iter()) + .chain([Command::new(Action::DoNothing)].iter()) + .cloned() + .collect() + } + } +} + +#[cfg(test)] +mod test {} -- cgit v1.2.3