Optimized finding valid snowball + bomb moves

10 files changed, 105 insertions, 303 deletions

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<i8>),
-    Dig(Point2d<i8>),
+    Move(Point2d),
+    Dig(Point2d),
     Shoot(Direction),
-    Bomb(Point2d<i8>),
-    Snowball(Point2d<i8>),
+    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<i8>, 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<i8>, i32); BOMB_DAMAGED_SPACES] = [
 
 pub const SNOWBALL_RANGE: i8 = 5;
 pub const SNOWBALL_FREEZES_SPACES: usize = 9;
-pub const SNOWBALL_FREEZES: [Vec2d<i8>; 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<i8>; 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<Command> {
         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<i8>; 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<i8>; 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<i8>; 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<i8>; 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<i8>) -> 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<i8>) -> Option<bool> {
+    pub fn at(&self, p: Point2d) -> Option<bool> {
         Map::internal_index(p).map(|(integer, bit)| {
             let mask = 1 << bit;
             self.cells[integer] & mask != 0
         })
     }
 
-    pub fn set(&mut self, p: Point2d<i8>) {
+    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<i8>) {
+    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<i8>,
+    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<i8>,
+    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<i8> {
+    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<T> {
-            $(pub $field: T),+
-        }
-
-        impl<T> $PointN<T> {
-            pub fn new($($field: T),+) -> $PointN<T> {
-                $PointN { $($field),+ }
-            }
-        }
-
-        impl<T: NumOps + Pow<u8, Output=T> + Copy> $PointN<T> {
-            pub fn distance_squared(self, other: $PointN<T>) -> T {
-                (self - other).magnitude_squared()
-            }
-        }
-
-
-        impl<T: Real + Pow<u8, Output=T>> $PointN<T> {
-            pub fn distance(self, other: $PointN<T>) -> T {
-                (self - other).magnitude()
-            }
-        }
-
-        impl<T: NumOps> Add<$VecN<T>> for $PointN<T> {
-            type Output = Self;
-
-            fn add(self, other: $VecN<T>) -> 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<T: NumAssignOps> AddAssign<$VecN<T>> for $PointN<T> {
-            fn add_assign(&mut self, other: $VecN<T>) {
-                $(self.$field += other.$field);+
-            }
-        }
+impl Point2d {
+    pub fn new(x: i8, y: i8) -> Point2d {
+        Point2d { x, y }
+    }
+}
 
-        impl<T: NumOps> Sub for $PointN<T> {
-            type Output = $VecN<T>;
+impl Add<Vec2d> for Point2d {
+    type Output = Self;
 
-            fn sub(self, other: Self) -> $VecN<T> {
-                $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<T> {
-            $(pub $field: T),+
-        }
-        
-        impl<T> $VecN<T> {
-            pub const fn new($($field: T),+) -> $VecN<T> {
-                $VecN { $($field),+ }
-            }
-        }
-
-        impl<T: NumOps + Ord + Signed + Copy> $VecN<T> {
-            pub fn walking_distance(&self) -> T {
-                fold_array!(max, { $(self.$field.abs()),+ })
-            }
-        }
-        
-        impl<T: NumOps + Pow<u8, Output=T> + Copy> $VecN<T> {
-            pub fn magnitude_squared(&self) -> T {
-                fold_array!(add, { $(self.$field.pow(2)),+ })
-            }
-        }
-
-        impl<T: Real + Pow<u8, Output=T>> $VecN<T> {
-            pub fn magnitude(&self) -> T {
-                self.magnitude_squared().sqrt()
-            }
-
-            pub fn unit(&self) -> $VecN<T> {
-                let mag = self.magnitude();
-                $VecN {
-                    $($field: self.$field / mag),+
-                }
-            }
-        }
-
-        impl<T: NumOps + Copy> $VecN<T> {
-            pub fn dot(&self, other: $VecN<T>) -> T {
-                fold_array!(add, { $(self.$field * other.$field),+ })
-            }
-        }
-
-        impl<T: NumOps> Add for $VecN<T> {
-            type Output = Self;
-
-            fn add(self, other: Self) -> Self {
-                $VecN {
-                    $($field: self.$field + other.$field),+
-                }
-            }
-        }
-
-        impl<T: NumAssignOps> AddAssign for $VecN<T> {
-            fn add_assign(&mut self, other: Self) {
-                $(self.$field += other.$field);+
-            }
-        }
-
-        impl<T: NumOps> Sub for $VecN<T> {
-            type Output = Self;
-
-            fn sub(self, other: Self) -> Self {
-                $VecN {
-                    $($field: self.$field - other.$field),+
-                }
-            }
-        }
-
-        impl<T: NumOps + Copy> Mul<T> for $VecN<T> {
-            type Output = Self;
-
-            fn mul(self, rhs: T) -> Self {
-                $VecN {
-                    $($field: self.$field * rhs),+
-                }
-            }
-        }
-
-        impl<T: Neg<Output=T>> Neg for $VecN<T> {
-            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<T: Real + Pow<u8, Output=T>> Vec2d<T> {
-    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<i8> 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,
+        }
     }
 }