From ebe7d5cd5cc42d8f3f02ca926f4b920ada03765f Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Fri, 26 Apr 2019 19:43:59 +0200 Subject: Refactored game map to use less memory --- src/constants.rs | 49 ++++++++++++++++++++++++++ src/game.rs | 104 +++++++++++++++++++++++++++++++++++-------------------- src/lib.rs | 1 + src/strategy.rs | 6 ++-- 4 files changed, 119 insertions(+), 41 deletions(-) create mode 100644 src/constants.rs (limited to 'src') 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, 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) -> Option { - 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) -> Option { + 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) -> 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) { + 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) { + 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 { .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::>(); -- cgit v1.2.3