From f4c27b7a834538bc75dd6f986c05635e6c58956c Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Wed, 14 Aug 2019 21:56:03 +0200 Subject: Optimized finding valid snowball + bomb moves --- src/bin/generate-lava-map.rs | 42 ---------- src/command.rs | 8 +- src/constants.rs | 6 +- src/game.rs | 63 ++++++--------- src/game/map.rs | 8 +- src/game/player.rs | 2 +- src/game/powerup.rs | 2 +- src/geometry/direction.rs | 2 +- src/geometry/point.rs | 93 ++++++---------------- src/geometry/vec.rs | 182 ++++++++++--------------------------------- 10 files changed, 105 insertions(+), 303 deletions(-) delete mode 100644 src/bin/generate-lava-map.rs diff --git a/src/bin/generate-lava-map.rs b/src/bin/generate-lava-map.rs deleted file mode 100644 index 1239480..0000000 --- a/src/bin/generate-lava-map.rs +++ /dev/null @@ -1,42 +0,0 @@ -use steam_powered_wyrm::constants::*; -use steam_powered_wyrm::game::map::Map; -use steam_powered_wyrm::geometry::*; - -fn main() { - let mut lava_map = [Map::default(); MAX_ROUNDS as usize + 1]; - let center = Point2d::new(MAP_SIZE as i8 / 2, MAP_SIZE as i8 / 2); - let center_f64 = Point2d::new(center.x as f64, center.y as f64); - - for (round, ref mut map) in lava_map.iter_mut().enumerate() { - let lava_progress = ((round as f64 - LAVA_ROUND_START as f64) - / (LAVA_ROUND_END - LAVA_ROUND_START) as f64) - .min(1.) - .max(0.); - let safe_radius = (MAP_SIZE / 2) as f64 * (1. - lava_progress) + 1.; - let safe_radius_squared = safe_radius * safe_radius; - - for (y, row) in MAP_ROW_SIZE.iter().enumerate() { - for x in row.x_offset..MAP_SIZE - row.x_offset { - let p_f64 = Point2d::new(x as f64, y as f64); - let p = Point2d::new(x as i8, y as i8); - - let is_lava = (p_f64 - center_f64).magnitude_squared() > safe_radius_squared; - if is_lava { - map.set(p); - } else { - map.clear(p); - } - } - } - } - - println!("pub const LAVA_MAP: [Map; MAX_ROUNDS as usize + 1] = ["); - for round in lava_map.iter() { - print!("Map {{ cells: ["); - for num in round.cells.iter() { - print!("{:#X}, ", num); - } - println!("] }},"); - } - println!("];"); -} diff --git a/src/command.rs b/src/command.rs index 4428b4d..c6d6695 100644 --- a/src/command.rs +++ b/src/command.rs @@ -32,11 +32,11 @@ impl Command { #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] pub enum Action { - Move(Point2d), - Dig(Point2d), + Move(Point2d), + Dig(Point2d), Shoot(Direction), - Bomb(Point2d), - Snowball(Point2d), + Bomb(Point2d), + Snowball(Point2d), DoNothing, } diff --git a/src/constants.rs b/src/constants.rs index e2db8fb..3f36db4 100644 --- a/src/constants.rs +++ b/src/constants.rs @@ -164,7 +164,8 @@ pub const SHOOT_DAMAGE: i32 = 8; pub const BOMB_RANGE: i8 = 5; pub const BOMB_DAMAGED_SPACES: usize = 13; -pub const BOMB_DAMAGES: [(Vec2d, i32); BOMB_DAMAGED_SPACES] = [ +pub const BOMB_DAMAGE_RANGE: i8 = 2; +pub const BOMB_DAMAGES: [(Vec2d, i32); BOMB_DAMAGED_SPACES] = [ (Vec2d::new(0, -2), 7), (Vec2d::new(2, 0), 7), (Vec2d::new(0, 2), 7), @@ -182,7 +183,8 @@ pub const BOMB_DAMAGES: [(Vec2d, i32); BOMB_DAMAGED_SPACES] = [ pub const SNOWBALL_RANGE: i8 = 5; pub const SNOWBALL_FREEZES_SPACES: usize = 9; -pub const SNOWBALL_FREEZES: [Vec2d; SNOWBALL_FREEZES_SPACES] = [ +pub const SNOWBALL_FREEZE_RANGE: i8 = 1; +pub const SNOWBALL_FREEZES: [Vec2d; SNOWBALL_FREEZES_SPACES] = [ Vec2d::new(-1, -1), Vec2d::new(0, -1), Vec2d::new(1, -1), diff --git a/src/game.rs b/src/game.rs index 32efef8..f2c0089 100644 --- a/src/game.rs +++ b/src/game.rs @@ -21,7 +21,7 @@ pub struct GameBoard { pub players: [Player; 2], pub powerups: ArrayVec<[Powerup; 2]>, pub map: Map, - pub occupied_cells: ArrayVec<[Point2d; 6]>, + pub occupied_cells: ArrayVec<[Point2d; 6]>, pub outcome: SimulationOutcome, } @@ -614,18 +614,17 @@ impl GameBoard { .collect() } - // TODO: These two dominate in terms of time taken. Optimize. 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] + 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 + let opponent_worm_positions: ArrayVec<[Point2d; 3]> = self.players [GameBoard::opponent(player_index)] .worms .iter() @@ -639,22 +638,16 @@ impl GameBoard { && (worm.position - target).magnitude_squared() < (BOMB_RANGE + 1).pow(2) { - let own_affected_worms = BOMB_DAMAGES - .iter() - .map(|(damage_offset, _)| target + *damage_offset) - .filter(|explosion_position| { - own_worm_positions.contains(explosion_position) - }) - .count(); - let opponent_affected_worms = BOMB_DAMAGES - .iter() - .map(|(damage_offset, _)| target + *damage_offset) - .filter(|explosion_position| { - opponent_worm_positions.contains(explosion_position) - }) - .count(); - - if own_affected_worms == 0 && opponent_affected_worms > 0 { + 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), @@ -674,12 +667,12 @@ impl GameBoard { .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] + 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 + let opponent_worm_positions: ArrayVec<[Point2d; 3]> = self.players [GameBoard::opponent(player_index)] .worms .iter() @@ -693,22 +686,16 @@ impl GameBoard { && (worm.position - target).magnitude_squared() < (SNOWBALL_RANGE + 1).pow(2) { - let own_affected_worms = SNOWBALL_FREEZES - .iter() - .map(|offset| target + *offset) - .filter(|explosion_position| { - own_worm_positions.contains(explosion_position) - }) - .count(); - let opponent_affected_worms = SNOWBALL_FREEZES - .iter() - .map(|offset| target + *offset) - .filter(|explosion_position| { - opponent_worm_positions.contains(explosion_position) - }) - .count(); - - if own_affected_worms == 0 && opponent_affected_worms > 0 { + 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), diff --git a/src/game/map.rs b/src/game/map.rs index 567e143..84ec99a 100644 --- a/src/game/map.rs +++ b/src/game/map.rs @@ -7,7 +7,7 @@ pub struct Map { } impl Map { - fn internal_index(p: Point2d) -> Option<(usize, usize)> { + fn internal_index(p: Point2d) -> Option<(usize, usize)> { if p.y < 0 || p.y as usize >= MAP_SIZE { None } else { @@ -23,14 +23,14 @@ impl Map { } } - pub fn at(&self, p: Point2d) -> Option { + pub fn at(&self, p: Point2d) -> Option { Map::internal_index(p).map(|(integer, bit)| { let mask = 1 << bit; self.cells[integer] & mask != 0 }) } - pub fn set(&mut self, p: Point2d) { + pub fn set(&mut self, p: Point2d) { if let Some((integer, bit)) = Map::internal_index(p) { let mask = 1 << bit; self.cells[integer] |= mask; @@ -38,7 +38,7 @@ impl Map { panic!("Tried to set an out of bounds bit, {:?}", p); } } - pub fn clear(&mut self, p: Point2d) { + pub fn clear(&mut self, p: Point2d) { if let Some((integer, bit)) = Map::internal_index(p) { let mask = !(1 << bit); self.cells[integer] &= mask; diff --git a/src/game/player.rs b/src/game/player.rs index 3d86c6d..0874c76 100644 --- a/src/game/player.rs +++ b/src/game/player.rs @@ -13,7 +13,7 @@ pub struct Player { pub struct Worm { pub id: i32, pub health: i32, - pub position: Point2d, + pub position: Point2d, pub bombs: u8, pub snowballs: u8, pub rounds_until_unfrozen: u8, diff --git a/src/game/powerup.rs b/src/game/powerup.rs index f8a8e2f..47e73a1 100644 --- a/src/game/powerup.rs +++ b/src/game/powerup.rs @@ -2,5 +2,5 @@ use crate::geometry::*; #[derive(Debug, PartialEq, Eq, Clone, Copy)] pub struct Powerup { - pub position: Point2d, + pub position: Point2d, } diff --git a/src/geometry/direction.rs b/src/geometry/direction.rs index d3f3b20..e37f750 100644 --- a/src/geometry/direction.rs +++ b/src/geometry/direction.rs @@ -40,7 +40,7 @@ impl Direction { } } - pub fn as_vec(&self) -> Vec2d { + pub fn as_vec(&self) -> Vec2d { use Direction::*; match self { North => Vec2d::new(0, -1), diff --git a/src/geometry/point.rs b/src/geometry/point.rs index c34d00f..1ab9b36 100644 --- a/src/geometry/point.rs +++ b/src/geometry/point.rs @@ -1,84 +1,37 @@ use crate::geometry::vec::*; use std::ops::*; -use num_traits::{NumOps, NumAssignOps}; -use num_traits::pow::Pow; -use num_traits::real::Real; -macro_rules! impl_point { - ($PointN:ident { $($field:ident),+ }, $VecN:ident) => { - #[derive(Debug, Default, Clone, Copy, Hash, PartialEq, Eq)] - pub struct $PointN { - $(pub $field: T),+ - } - - impl $PointN { - pub fn new($($field: T),+) -> $PointN { - $PointN { $($field),+ } - } - } - - impl + Copy> $PointN { - pub fn distance_squared(self, other: $PointN) -> T { - (self - other).magnitude_squared() - } - } - - - impl> $PointN { - pub fn distance(self, other: $PointN) -> T { - (self - other).magnitude() - } - } - - impl Add<$VecN> for $PointN { - type Output = Self; - - fn add(self, other: $VecN) -> Self { - $PointN { - $($field: self.$field + other.$field),+ - } - } - } +#[derive(Debug, Default, Clone, Copy, Hash, PartialEq, Eq)] +pub struct Point2d { + pub x: i8, + pub y: i8, +} - impl AddAssign<$VecN> for $PointN { - fn add_assign(&mut self, other: $VecN) { - $(self.$field += other.$field);+ - } - } +impl Point2d { + pub fn new(x: i8, y: i8) -> Point2d { + Point2d { x, y } + } +} - impl Sub for $PointN { - type Output = $VecN; +impl Add for Point2d { + type Output = Self; - fn sub(self, other: Self) -> $VecN { - $VecN { - $($field: self.$field - other.$field),+ - } - } + fn add(self, other: Vec2d) -> Self { + Point2d { + x: self.x.saturating_add(other.x), + y: self.y.saturating_add(other.y), } } } -impl_point!(Point2d { x, y }, Vec2d); -impl_point!(Point3d { x, y, z }, Vec3d); +impl Sub for Point2d { + type Output = Vec2d; -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn distance_in_x_dimension_example() { - let a = Point2d::new(1., 1.); - let b = Point2d::new(3., 1.); - assert_eq!(a.distance(b), 2.); - assert_eq!(a.distance_squared(b), 4.); - } - - #[test] - fn distance_in_y_dimension_example() { - let a = Point2d::new(1., 1.); - let b = Point2d::new(1., 3.); - assert_eq!(b.distance(a), 2.); - assert_eq!(b.distance_squared(a), 4.); + fn sub(self, other: Self) -> Vec2d { + Vec2d { + x: self.x.saturating_sub(other.x), + y: self.y.saturating_sub(other.y), + } } } diff --git a/src/geometry/vec.rs b/src/geometry/vec.rs index c99cf5e..375a0f9 100644 --- a/src/geometry/vec.rs +++ b/src/geometry/vec.rs @@ -1,160 +1,62 @@ use std::ops::*; -use num_traits::{NumOps, NumAssignOps, Signed}; -use num_traits::pow::Pow; -use num_traits::real::Real; -macro_rules! fold_array { - ($method:ident, { $x:expr }) => { $x }; - ($method:ident, { $x:expr, $y:expr }) => { $x.$method($y) }; - ($method:ident, { $x:expr, $y:expr, $z:expr }) => { $x.$method($y).$method($z) }; +#[derive(Debug, Default, Clone, Copy, Hash, PartialEq, Eq)] +pub struct Vec2d { + pub x: i8, + pub y: i8, } -macro_rules! impl_vector { - ($VecN:ident { $($field:ident),+ }) => { - #[derive(Debug, Default, Clone, Copy, Hash, PartialEq, Eq)] - pub struct $VecN { - $(pub $field: T),+ - } - - impl $VecN { - pub const fn new($($field: T),+) -> $VecN { - $VecN { $($field),+ } - } - } - - impl $VecN { - pub fn walking_distance(&self) -> T { - fold_array!(max, { $(self.$field.abs()),+ }) - } - } - - impl + Copy> $VecN { - pub fn magnitude_squared(&self) -> T { - fold_array!(add, { $(self.$field.pow(2)),+ }) - } - } - - impl> $VecN { - pub fn magnitude(&self) -> T { - self.magnitude_squared().sqrt() - } - - pub fn unit(&self) -> $VecN { - let mag = self.magnitude(); - $VecN { - $($field: self.$field / mag),+ - } - } - } - - impl $VecN { - pub fn dot(&self, other: $VecN) -> T { - fold_array!(add, { $(self.$field * other.$field),+ }) - } - } - - impl Add for $VecN { - type Output = Self; - - fn add(self, other: Self) -> Self { - $VecN { - $($field: self.$field + other.$field),+ - } - } - } - - impl AddAssign for $VecN { - fn add_assign(&mut self, other: Self) { - $(self.$field += other.$field);+ - } - } - - impl Sub for $VecN { - type Output = Self; - - fn sub(self, other: Self) -> Self { - $VecN { - $($field: self.$field - other.$field),+ - } - } - } - - impl Mul for $VecN { - type Output = Self; - - fn mul(self, rhs: T) -> Self { - $VecN { - $($field: self.$field * rhs),+ - } - } - } - - impl> Neg for $VecN { - type Output = Self; - - fn neg(self) -> Self { - $VecN { - $($field: -self.$field),+ - } - } - } - +impl Vec2d { + pub const fn new(x: i8, y: i8) -> Vec2d { + Vec2d { x, y } + } + pub fn magnitude_squared(&self) -> i8 { + self.x + .saturating_pow(2) + .saturating_add(self.y.saturating_pow(2)) } } -impl_vector!(Vec2d { x, y }); -impl_vector!(Vec3d { x, y, z }); +impl Add for Vec2d { + type Output = Self; -impl> Vec2d { - pub fn angle(&self) -> T { - self.y.atan2(self.x) + fn add(self, other: Self) -> Self { + Vec2d { + x: self.x.saturating_add(other.x), + y: self.y.saturating_add(other.y), + } } } +impl Sub for Vec2d { + type Output = Self; -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn right_angles_in_2d_vectors() { - use std::f32::consts::{FRAC_PI_2, PI}; - - assert_eq!(0., Vec2d::new(1., 0.).angle()); - assert_eq!(FRAC_PI_2, Vec2d::new(0., 1.).angle()); - assert_eq!(PI, Vec2d::new(-1., 0.).angle()); - assert_eq!(-FRAC_PI_2, Vec2d::new(0., -1.).angle()); + fn sub(self, other: Self) -> Self { + Vec2d { + x: self.x.saturating_sub(other.x), + y: self.y.saturating_sub(other.y), + } } +} - #[test] - fn unit_normalizes_2d_vector() { - let before = Vec2d::new(2., 10.); - let after = before.unit(); +impl Mul for Vec2d { + type Output = Self; - assert_eq!(1., after.magnitude()); - assert_eq!(before.angle(), after.angle()); + fn mul(self, other: i8) -> Self { + Vec2d { + x: self.x.saturating_mul(other), + y: self.y.saturating_mul(other), + } } +} - #[test] - fn unit_normalizes_3d_vector() { - let before = Vec3d::new(2., 10., -5.); - let after = before.unit(); - - assert_eq!(1., after.magnitude()); - // How to define 3d angle? 2 angles I suppose? - // assert_eq!(before.angle(), after.angle()); - } - - #[test] - fn dot_product_example_2d() { - let a = Vec2d::new(-6., 8.); - let b = Vec2d::new(5., 12.); - assert_eq!(66., a.dot(b)); - } +impl Neg for Vec2d { + type Output = Self; - #[test] - fn magnitude_squared_of_an_integer() { - let a = Vec2d::new(3, 4); - assert_eq!(25, a.magnitude_squared()); + fn neg(self) -> Self { + Vec2d { + x: -self.x, + y: -self.y, + } } } -- cgit v1.2.3