Refactored game map to use less memory

4 files changed, 119 insertions, 41 deletions

diff --git a/src/constants.rs b/src/constants.rs
new file mode 100644
index 0000000..dcda1d5
--- /dev/null
+++ b/src/constants.rs
@@ -0,0 +1,49 @@
+pub const MAP_SIZE: usize = 33;
+pub const MAP_ROW_SIZE: [MapRow; MAP_SIZE] = [
+    MapRow { start_bit: 0, x_offset: 11 },
+    MapRow { start_bit: 11, x_offset: 8 },
+    MapRow { start_bit: 28, x_offset: 7 },
+    MapRow { start_bit: 47, x_offset: 6 },
+    MapRow { start_bit: 68, x_offset: 4 },
+    MapRow { start_bit: 93, x_offset: 4 },
+    MapRow { start_bit: 118, x_offset: 3 },
+    MapRow { start_bit: 145, x_offset: 2 },
+    MapRow { start_bit: 174, x_offset: 1 },
+    MapRow { start_bit: 205, x_offset: 1 },
+    MapRow { start_bit: 236, x_offset: 1 },
+    MapRow { start_bit: 267, x_offset: 0 },
+    MapRow { start_bit: 300, x_offset: 0 },
+    MapRow { start_bit: 333, x_offset: 0 },
+    MapRow { start_bit: 366, x_offset: 0 },
+    MapRow { start_bit: 399, x_offset: 0 },
+    MapRow { start_bit: 432, x_offset: 0 },
+    MapRow { start_bit: 465, x_offset: 0 },
+    MapRow { start_bit: 498, x_offset: 0 },
+    MapRow { start_bit: 531, x_offset: 0 },
+    MapRow { start_bit: 564, x_offset: 0 },
+    MapRow { start_bit: 597, x_offset: 0 },
+    MapRow { start_bit: 630, x_offset: 1 },
+    MapRow { start_bit: 661, x_offset: 1 },
+    MapRow { start_bit: 692, x_offset: 1 },
+    MapRow { start_bit: 723, x_offset: 2 },
+    MapRow { start_bit: 752, x_offset: 3 },
+    MapRow { start_bit: 779, x_offset: 4 },
+    MapRow { start_bit: 804, x_offset: 4 },
+    MapRow { start_bit: 829, x_offset: 6 },
+    MapRow { start_bit: 850, x_offset: 7 },
+    MapRow { start_bit: 869, x_offset: 8 },
+    MapRow { start_bit: 886, x_offset: 11 },
+];
+pub const MAP_BITSIZE: usize = 897;
+pub const MAP_U64S: usize = 15;
+
+pub struct MapRow {
+    pub start_bit: usize,
+    pub x_offset: usize
+}
+
+impl MapRow {
+    pub fn len(&self) -> usize {
+        MAP_SIZE - 2 * self.x_offset
+    }
+}
diff --git a/src/game.rs b/src/game.rs
index 8fd9153..be2dcce 100644
--- a/src/game.rs
+++ b/src/game.rs
@@ -1,10 +1,11 @@
 use crate::geometry::*;
 use crate::command::Command;
 use crate::json;
+use crate::constants::*;
 
 use arrayvec::ArrayVec;
 
-#[derive(Debug, PartialEq, Eq, Clone)]
+#[derive(Clone)]
 pub struct GameBoard {
     pub players: [Player; 2],
     pub powerups: ArrayVec<[Powerup; 2]>,
@@ -31,18 +32,9 @@ pub enum Powerup {
     Health(Point2d<i8>, i32)
 }
 
-#[derive(Debug, PartialEq, Eq, Clone)]
+#[derive(Clone)]
 pub struct Map {
-    pub size: u8,
-    /// This is 2d, each row is size long
-    pub cells: ArrayVec<[CellType; 2048]>
-}
-
-#[derive(Debug, PartialEq, Eq, Clone, Copy)]
-pub enum CellType {
-    Air,
-    Dirt,
-    DeepSpace,
+    pub cells: [u64; MAP_U64S]
 }
 
 #[derive(Debug, PartialEq, Eq, Clone, Copy)]
@@ -78,20 +70,22 @@ impl GameBoard {
                 weapon_range: commando_range
             }).collect()
         };
+
+        let mut map = Map {
+            cells: [0; MAP_U64S]
+        };
+        for cell in json.map.iter().flatten() {
+            if cell.cell_type == json::CellType::Dirt {
+                map.set(Point2d::new(cell.x, cell.y))
+            }
+        }
             
         GameBoard {
             players: [player, opponent],
             powerups: json.map.iter().flatten().filter_map(|c| {
                 c.powerup.clone().map(|p| Powerup::Health(Point2d::new(c.x, c.y), p.value))
             }).collect(),
-            map: Map {
-                size: json.map_size,
-                cells: json.map.iter().flatten().map(|c| match c.cell_type {
-                    json::CellType::Air => CellType::Air,
-                    json::CellType::Dirt => CellType::Dirt,
-                    json::CellType::DeepSpace => CellType::DeepSpace,
-                }).collect()
-            }
+            map
         }
     }
 
@@ -112,7 +106,7 @@ impl GameBoard {
                 let damage = 20;
 
 
-                debug_assert_eq!(Some(CellType::Air), self.map.at(Point2d::new(x1, y1)));
+                debug_assert_eq!(Some(false), self.map.at(Point2d::new(x1, y1)), "Movement target wasn't empty, ({}, {})", x1, y1);
                 // 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.
@@ -123,13 +117,14 @@ impl GameBoard {
             _ => {
                 for player_index in 0..moves.len() {
                     if let Command::Move(x, y) = moves[player_index] {
-                        debug_assert_eq!(Some(CellType::Air), self.map.at(Point2d::new(x, y)));
+                        debug_assert_eq!(Some(false), self.map.at(Point2d::new(x, y)), "Movement target wasn't empty, ({}, {})", x, y);
 
                         let worm = self.players[player_index].active_worm_mut();
 
                         debug_assert!(
                             (worm.position.x - x).abs() <= 1 &&
-                                (worm.position.y - y).abs() <= 1
+                                (worm.position.y - y).abs() <= 1,
+                            "Tried to move too far away, ({}, {})", x, y
                         );
 
                         worm.position.x = x;
@@ -141,19 +136,18 @@ impl GameBoard {
 
         for player_index in 0..moves.len() {
             if let Command::Dig(x, y) = moves[player_index] {
-                println!("Player {} is digging {}, {}", player_index, x, y);
                 debug_assert!(
-                    Some(CellType::Dirt) == self.map.at(Point2d::new(x, y)) ||
-                        Some(CellType::Air) == self.map.at(Point2d::new(x, y))
+                    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
                 );
                 debug_assert!{
                     (self.players[player_index].active_worm().position.x - x).abs() <= 1 &&
-                        (self.players[player_index].active_worm().position.y - y).abs() <= 1
+                        (self.players[player_index].active_worm().position.y - y).abs() <= 1,
+                    "Tried to dig too far away, ({}, {})", x, y
                 };
 
-                if let Some(c) = self.map.at_mut(Point2d::new(x, y)) {
-                    *c = CellType::Air;
-                }
+                self.map.clear(Point2d::new(x, y));
             }
         }
 
@@ -174,7 +168,7 @@ impl GameBoard {
                 for distance in 1..=range {
                     let target = center + diff * distance;
                     match self.map.at(target) {
-                        Some(CellType::Air) => {
+                        Some(false) => {
                             let target_worm: Option<&mut Worm> = self.players.iter_mut()
                                 .flat_map(|p| p.worms.iter_mut())
                                 .find(|w| w.position == target);
@@ -233,19 +227,53 @@ impl Player {
 }
 
 impl Map {
-    pub fn at(&self, p: Point2d<i8>) -> Option<CellType> {
-        if p.y < 0 || p.x < 0 || p.y as u8 >= self.size || p.x as u8 >= self.size {
+    pub fn at(&self, p: Point2d<i8>) -> Option<bool> {
+        if p.y < 0 || p.y as usize >= MAP_SIZE {
             None
         } else {
-            Some(self.cells[p.y as usize * self.size as usize + p.x as usize])
+            let row_data = &MAP_ROW_SIZE[p.y as usize];
+            if p.x < row_data.x_offset as i8 || p.x as usize >= row_data.x_offset + row_data.len() {
+                None
+            } else {
+                let global_bit = row_data.start_bit + p.x as usize - row_data.x_offset;
+                let integer = global_bit / 64;
+                let bit = global_bit % 64;
+                let mask = 1 << bit;
+                Some(self.cells[integer] & mask != 0)
+            }
         }
     }
 
-    fn at_mut(&mut self, p: Point2d<i8>) -> Option<&mut CellType> {
-        if p.y < 0 || p.x < 0 || p.y as u8 >= self.size || p.x as u8 >= self.size {
-            None
+    fn set(&mut self, p: Point2d<i8>) {
+        if p.y < 0 || p.y as usize >= MAP_SIZE {
+            debug_assert!(false, "Tried to set an out of bounds bit, {:?}", p);
         } else {
-            Some(&mut self.cells[p.y as usize * self.size as usize + p.x as usize])
+            let row_data = &MAP_ROW_SIZE[p.y as usize];
+            if p.x < row_data.x_offset as i8 || p.x as usize >= row_data.x_offset + row_data.len() {
+                debug_assert!(false, "Tried to set an out of bounds bit, {:?}", p);
+            } else {
+                let global_bit = row_data.start_bit + p.x as usize - row_data.x_offset;
+                let integer = global_bit / 64;
+                let bit = global_bit % 64;
+                let mask = 1 << bit;
+                self.cells[integer] |= mask;
+            }
+        }
+    }
+    fn clear(&mut self, p: Point2d<i8>) {
+        if p.y < 0 || p.y as usize >= MAP_SIZE {
+            debug_assert!(false, "Tried to set an out of bounds bit, {:?}", p);
+        } else {
+            let row_data = &MAP_ROW_SIZE[p.y as usize];
+            if p.x < row_data.x_offset as i8 || p.x as usize >= row_data.x_offset + row_data.len() {
+                debug_assert!(false, "Tried to set an out of bounds bit, {:?}", p);
+            } else {
+                let global_bit = row_data.start_bit + p.x as usize - row_data.x_offset;
+                let integer = global_bit / 64;
+                let bit = global_bit % 64;
+                let mask = !(1 << bit);
+                self.cells[integer] &= mask;
+            }
         }
     }
 }
diff --git a/src/lib.rs b/src/lib.rs
index c0a6cd6..e981d70 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -3,3 +3,4 @@ pub mod json;
 pub mod geometry;
 pub mod game;
 pub mod strategy;
+pub mod constants;
diff --git a/src/strategy.rs b/src/strategy.rs
index afebd12..dd15854 100644
--- a/src/strategy.rs
+++ b/src/strategy.rs
@@ -1,5 +1,5 @@
 use crate::command::Command;
-use crate::game::{GameBoard, CellType};
+use crate::game::GameBoard;
 use crate::geometry::*;
 
 struct GameTree {
@@ -54,8 +54,8 @@ fn valid_moves(state: &GameBoard, player_index: usize) -> Vec<Command> {
         .map(Direction::as_vec)
         .map(|d| worm.position + d)
         .filter_map(|p| match state.map.at(p) {
-            Some(CellType::Air) => Some(Command::Move(p.x, p.y)),
-            Some(CellType::Dirt) => Some(Command::Dig(p.x, p.y)),
+            Some(false) => Some(Command::Move(p.x, p.y)),
+            Some(true) => Some(Command::Dig(p.x, p.y)),
             _ => None
         })
         .collect::<Vec<_>>();