From 8f88b294511b786e8ae518594eceafb8da9d3f34 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sun, 15 Jul 2018 22:55:55 +0200 Subject: Flipped bitfields on the opponent side to make implementation more concise --- src/engine/bitwise_engine.rs | 109 +++++++----------------------- src/engine/geometry.rs | 44 +++++++----- src/input/json.rs | 8 +-- tests/expressive_to_bitwise_comparison.rs | 8 ++- tests/monte_carlo_test.rs | 4 +- 5 files changed, 63 insertions(+), 110 deletions(-) diff --git a/src/engine/bitwise_engine.rs b/src/engine/bitwise_engine.rs index a70d5e2..4113e14 100644 --- a/src/engine/bitwise_engine.rs +++ b/src/engine/bitwise_engine.rs @@ -47,18 +47,19 @@ pub struct TeslaCooldown { impl GameState for BitwiseGameState { fn simulate(&mut self, settings: &GameSettings, player_command: Command, opponent_command: Command) -> GameStatus { - BitwiseGameState::perform_command(settings, &mut self.player, &mut self.player_buildings, player_command); BitwiseGameState::perform_command(settings, &mut self.opponent, &mut self.opponent_buildings, opponent_command); + BitwiseGameState::perform_command(settings, &mut self.player, &mut self.player_buildings, player_command); + BitwiseGameState::perform_command(settings, &mut self.opponent, &mut self.opponent_buildings, opponent_command); BitwiseGameState::update_construction(settings, &mut self.player_buildings); BitwiseGameState::update_construction(settings, &mut self.opponent_buildings); BitwiseGameState::fire_teslas(&mut self.player, &mut self.player_buildings, &mut self.opponent, &mut self.opponent_buildings); - BitwiseGameState::add_left_missiles(&mut self.player_buildings); - BitwiseGameState::add_right_missiles(&mut self.opponent_buildings); + BitwiseGameState::add_missiles(&mut self.player_buildings); + BitwiseGameState::add_missiles(&mut self.opponent_buildings); - BitwiseGameState::move_left_and_collide_missiles(&mut self.player, &mut self.player_buildings, &mut self.opponent_buildings.missiles); - BitwiseGameState::move_right_and_collide_missiles(&mut self.opponent, &mut self.opponent_buildings, &mut self.player_buildings.missiles); + BitwiseGameState::move_and_collide_missiles(&mut self.player, &mut self.player_buildings, &mut self.opponent_buildings.missiles); + BitwiseGameState::move_and_collide_missiles(&mut self.opponent, &mut self.opponent_buildings, &mut self.player_buildings.missiles); BitwiseGameState::add_energy(&mut self.player, &mut self.player_buildings); BitwiseGameState::add_energy(&mut self.opponent, &mut self.opponent_buildings); @@ -67,7 +68,6 @@ impl GameState for BitwiseGameState { self.status } - fn player(&self) -> &Player { &self.player } fn opponent(&self) -> &Player { &self.opponent } fn player_has_max_teslas(&self) -> bool { self.player_buildings.count_teslas() >= TESLA_MAX } @@ -83,7 +83,7 @@ impl GameState for BitwiseGameState { } fn location_of_unoccupied_opponent_cell(&self, i: usize) -> Point { let bit = find_bit_index_from_rank(self.opponent_buildings.occupied, i as u64); - let point = Point::new(bit%SINGLE_MAP_WIDTH+SINGLE_MAP_WIDTH, bit/SINGLE_MAP_WIDTH); + let point = Point::new(FULL_MAP_WIDTH - bit%SINGLE_MAP_WIDTH - 1, bit/SINGLE_MAP_WIDTH); debug_assert!(point.to_either_bitfield() & self.opponent_buildings.occupied == 0); point } @@ -283,9 +283,15 @@ impl BitwiseGameState { } fn fire_teslas(player: &mut Player, player_buildings: &mut PlayerBuildings, opponent: &mut Player, opponent_buildings: &mut PlayerBuildings) { - player_buildings.tesla_cooldowns.sort_by(|a, b| b.age.cmp(&a.age)); - opponent_buildings.tesla_cooldowns.sort_by(|a, b| b.age.cmp(&a.age)); + BitwiseGameState::fire_single_players_teslas_without_cleanup(player, player_buildings, opponent, opponent_buildings); + BitwiseGameState::fire_single_players_teslas_without_cleanup(opponent, opponent_buildings, player, player_buildings); + + BitwiseGameState::update_tesla_activity(player_buildings); + BitwiseGameState::update_tesla_activity(opponent_buildings); + } + fn fire_single_players_teslas_without_cleanup(player: &mut Player, player_buildings: &mut PlayerBuildings, opponent: &mut Player, opponent_buildings: &mut PlayerBuildings) { + player_buildings.tesla_cooldowns.sort_by(|a, b| b.age.cmp(&a.age)); for tesla in player_buildings.tesla_cooldowns.iter_mut().filter(|t| t.active) { tesla.age += 1; if tesla.cooldown > 0 { @@ -294,15 +300,17 @@ impl BitwiseGameState { player.energy -= TESLA_FIRING_ENERGY; tesla.cooldown = TESLA_COOLDOWN; - if tesla.pos.x + 1 >= SINGLE_MAP_WIDTH { + let flipped_pos = tesla.pos.flip_x(); + + if flipped_pos.x >= SINGLE_MAP_WIDTH - 1 { opponent.health = opponent.health.saturating_sub(TESLA_DAMAGE); } - let missed_cells = ((SINGLE_MAP_WIDTH - tesla.pos.x) as u32).saturating_sub(2); + let missed_cells = ((SINGLE_MAP_WIDTH - flipped_pos.x) as u32).saturating_sub(2); let top_row = if tesla.pos.y == 0 { 0 } else { tesla.pos.y - 1 }; let top_row_mask = 255u64 << (top_row * SINGLE_MAP_WIDTH); - let mut destroy_mask = top_row_mask.wrapping_shr(missed_cells) & top_row_mask; + let mut destroy_mask = top_row_mask.wrapping_shl(missed_cells) & top_row_mask; for _ in 0..(if tesla.pos.y == 0 || tesla.pos.y == MAP_HEIGHT-1 { 2 } else { 3 }) { let hits = destroy_mask & opponent_buildings.buildings[0]; @@ -313,39 +321,9 @@ impl BitwiseGameState { } } } - - for tesla in opponent_buildings.tesla_cooldowns.iter_mut().filter(|t| t.active) { - tesla.age += 1; - if tesla.cooldown > 0 { - tesla.cooldown -= 1; - } else if opponent.energy >= TESLA_FIRING_ENERGY { - opponent.energy -= TESLA_FIRING_ENERGY; - tesla.cooldown = TESLA_COOLDOWN; - - if tesla.pos.x <= SINGLE_MAP_WIDTH { - player.health = player.health.saturating_sub(TESLA_DAMAGE); - } - - let missed_cells = ((tesla.pos.x - SINGLE_MAP_WIDTH) as u32).saturating_sub(1); - - let top_row = if tesla.pos.y == 0 { 0 } else { tesla.pos.y - 1 }; - let top_row_mask = 255u64 << (top_row * SINGLE_MAP_WIDTH); - let mut destroy_mask = top_row_mask.wrapping_shl(missed_cells) & top_row_mask; - - for _ in 0..(if tesla.pos.y == 0 || tesla.pos.y == MAP_HEIGHT-1 { 2 } else { 3 }) { - let hits = destroy_mask & player_buildings.buildings[0]; - destroy_mask &= !hits; - BitwiseGameState::destroy_buildings(player_buildings, hits); - destroy_mask = destroy_mask << SINGLE_MAP_WIDTH; - } - } - } - - BitwiseGameState::update_tesla_activity(player_buildings); - BitwiseGameState::update_tesla_activity(opponent_buildings); } - fn add_left_missiles(player_buildings: &mut PlayerBuildings) { + fn add_missiles(player_buildings: &mut PlayerBuildings) { let mut missiles = player_buildings.missile_towers[0]; for mut tier in player_buildings.missiles.iter_mut() { let setting = !tier.0 & missiles; @@ -356,17 +334,6 @@ impl BitwiseGameState { BitwiseGameState::rotate_missile_towers(player_buildings); } - fn add_right_missiles(player_buildings: &mut PlayerBuildings) { - let mut missiles = player_buildings.missile_towers[0]; - for mut tier in player_buildings.missiles.iter_mut() { - let setting = !tier.1 & missiles; - tier.1 |= setting; - missiles &= !setting; - } - - BitwiseGameState::rotate_missile_towers(player_buildings); - } - //TODO: Add a pointer and stop rotating here fn rotate_missile_towers(player_buildings: &mut PlayerBuildings) { let zero = player_buildings.missile_towers[0]; @@ -378,46 +345,18 @@ impl BitwiseGameState { } - //TODO: Can I rearrange my bitfields to make these two functions one thing? - fn move_left_and_collide_missiles(opponent: &mut Player, opponent_buildings: &mut PlayerBuildings, player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) { + fn move_and_collide_missiles(opponent: &mut Player, opponent_buildings: &mut PlayerBuildings, player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) { for _ in 0..MISSILE_SPEED { for i in 0..MISSILE_MAX_SINGLE_CELL { - let about_to_hit_opponent = player_missiles[i].0 & LEFT_COL_MASK; + let about_to_hit_opponent = player_missiles[i].1 & LEFT_COL_MASK; let damage = about_to_hit_opponent.count_ones() as u8 * MISSILE_DAMAGE; opponent.health = opponent.health.saturating_sub(damage); - player_missiles[i].0 = (player_missiles[i].0 & !LEFT_COL_MASK) >> 1; - - let swapping_sides = player_missiles[i].1 & LEFT_COL_MASK; - player_missiles[i].0 |= swapping_sides << (SINGLE_MAP_WIDTH-1); player_missiles[i].1 = (player_missiles[i].1 & !LEFT_COL_MASK) >> 1; - - let mut hits = 0; - for health_tier in (0..DEFENCE_HEALTH).rev() { - hits = opponent_buildings.buildings[health_tier] & player_missiles[i].0; - player_missiles[i].0 &= !hits; - opponent_buildings.buildings[health_tier] &= !hits; - } - - BitwiseGameState::destroy_buildings(opponent_buildings, hits); - BitwiseGameState::update_tesla_activity(opponent_buildings); - } - } - } - - fn move_right_and_collide_missiles(opponent: &mut Player, opponent_buildings: &mut PlayerBuildings, player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) { - for _ in 0..MISSILE_SPEED { - for i in 0..MISSILE_MAX_SINGLE_CELL { - let about_to_hit_opponent = player_missiles[i].1 & RIGHT_COL_MASK; - let damage = about_to_hit_opponent.count_ones() as u8 * MISSILE_DAMAGE; - opponent.health = opponent.health.saturating_sub(damage); - player_missiles[i].1 = (player_missiles[i].1 & !RIGHT_COL_MASK) << 1; - let swapping_sides = player_missiles[i].0 & RIGHT_COL_MASK; - player_missiles[i].1 |= swapping_sides >> (SINGLE_MAP_WIDTH-1); + player_missiles[i].1 |= swapping_sides; player_missiles[i].0 = (player_missiles[i].0 & !RIGHT_COL_MASK) << 1; - let mut hits = 0; for health_tier in (0..DEFENCE_HEALTH).rev() { hits = opponent_buildings.buildings[health_tier] & player_missiles[i].1; diff --git a/src/engine/geometry.rs b/src/engine/geometry.rs index 293ffce..ee331b7 100644 --- a/src/engine/geometry.rs +++ b/src/engine/geometry.rs @@ -34,14 +34,30 @@ impl Point { self.x = self.x.wrapping_add(1); } - pub fn to_bitfield(&self) -> (u64, u64) { - if self.x >= SINGLE_MAP_WIDTH { - let index = self.y * SINGLE_MAP_WIDTH + self.x - SINGLE_MAP_WIDTH; - (0, 1 << index) + pub fn flip_x(&self) -> Point { + let flipped_x = if self.x >= SINGLE_MAP_WIDTH { + FULL_MAP_WIDTH - self.x - 1 } else { - let index = self.y * SINGLE_MAP_WIDTH + self.x; - (1 << index, 0) - } + self.x + }; + Point::new(flipped_x, self.y) + } +} + +impl Point { + /** + * # Bitfields + * + * 0,0 is the top left point. + * >> (towards 0) moves bits towards the player that owns that side + * << (towards max) moves bits towards the opponent + * This involves mirroring the x dimension for the opponent's side + */ + + + //TODO: Clean up the left vs right bitfield nonsense here, get rid of some branches + pub fn to_bitfield(&self) -> (u64, u64) { + (self.to_left_bitfield(), self.to_right_bitfield()) } pub fn to_left_bitfield(&self) -> u64 { @@ -57,19 +73,13 @@ impl Point { if self.x < SINGLE_MAP_WIDTH { 0 } else { - let index = self.y * SINGLE_MAP_WIDTH + self.x - SINGLE_MAP_WIDTH; + let index = self.y * SINGLE_MAP_WIDTH + FULL_MAP_WIDTH - self.x - 1; 1 << index } } pub fn to_either_bitfield(&self) -> u64 { - if self.x >= SINGLE_MAP_WIDTH { - let index = self.y * SINGLE_MAP_WIDTH + self.x - SINGLE_MAP_WIDTH; - 1 << index - } else { - let index = self.y * SINGLE_MAP_WIDTH + self.x; - 1 << index - } + self.to_left_bitfield() | self.to_right_bitfield() } } @@ -83,6 +93,8 @@ impl PartialOrd for Point { } impl Ord for Point { fn cmp(&self, other: &Point) -> Ordering { - self.y.cmp(&other.y).then(self.x.cmp(&other.x)) + let a = self.flip_x(); + let b = other.flip_x(); + a.y.cmp(&b.y).then(a.x.cmp(&b.x)) } } diff --git a/src/input/json.rs b/src/input/json.rs index c3d8474..000c355 100644 --- a/src/input/json.rs +++ b/src/input/json.rs @@ -202,12 +202,12 @@ impl State { } } for missile in &cell.missiles { - let mut bitwise_buildings = if missile.player_type == 'A' { - &mut player_buildings + let bitfields = point.to_bitfield(); + let (mut bitwise_buildings, mut left, mut right) = if missile.player_type == 'A' { + (&mut player_buildings, bitfields.0, bitfields.1) } else { - &mut opponent_buildings + (&mut opponent_buildings, bitfields.1, bitfields.0) }; - let (mut left, mut right) = point.to_bitfield(); for mut tier in bitwise_buildings.missiles.iter_mut() { let setting = (!tier.0 & left, !tier.1 & right); diff --git a/tests/expressive_to_bitwise_comparison.rs b/tests/expressive_to_bitwise_comparison.rs index 6a72748..e0c9a30 100644 --- a/tests/expressive_to_bitwise_comparison.rs +++ b/tests/expressive_to_bitwise_comparison.rs @@ -45,6 +45,8 @@ proptest! { let (settings, mut expressive_state) = input::json::read_expressive_state_from_file(STATE_PATH).expect("Failed to load expressive state"); let (_, mut bitwise_state) = input::json::read_bitwise_state_from_file(STATE_PATH).expect("Failed to load bitwise state"); + expressive_state.sort(); + let mut expected_status = GameStatus::Continue; while expected_status == GameStatus::Continue { let player_command = random_player_move(&settings, &expressive_state, &bitwise_state, &mut rng); @@ -176,11 +178,11 @@ fn build_bitwise_from_expressive(expressive: &expressive_engine::ExpressiveGameS let (mut left, mut right) = m.pos.to_bitfield(); let mut res = acc.clone(); for mut tier in res.iter_mut() { - let setting = (!tier.0 & left, !tier.1 & right); + let setting = (!tier.0 & right, !tier.1 & left); tier.0 |= setting.0; tier.1 |= setting.1; - left &= !setting.0; - right &= !setting.1; + right &= !setting.0; + left &= !setting.1; } res }); diff --git a/tests/monte_carlo_test.rs b/tests/monte_carlo_test.rs index 87feadb..832cdb3 100644 --- a/tests/monte_carlo_test.rs +++ b/tests/monte_carlo_test.rs @@ -10,12 +10,12 @@ const STATE_PATH: &str = "tests/state0.json"; #[test] fn it_does_a_normal_turn_successfully() { let start_time = PreciseTime::now(); - let (settings, state) = match input::json::read_expressive_state_from_file(STATE_PATH) { + let (settings, state) = match input::json::read_bitwise_state_from_file(STATE_PATH) { Ok(ok) => ok, Err(error) => panic!("Error while parsing JSON file: {}", error) }; let max_time = Duration::milliseconds(200); strategy::monte_carlo::choose_move(&settings, &state, &start_time, max_time); - assert!(start_time.to(PreciseTime::now()) < max_time + Duration::milliseconds(10)) + assert!(start_time.to(PreciseTime::now()) < max_time + Duration::milliseconds(50)) } -- cgit v1.2.3