A bit faster through caching set of occupied spots

3 files changed, 31 insertions, 10 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 19a813f..18f72c4 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -25,6 +25,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "fnv"
+version = "1.0.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "fuchsia-cprng"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -212,6 +217,7 @@ name = "steam-powered-wyrm"
 version = "0.1.0"
 dependencies = [
  "arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)",
+ "fnv 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 1.0.90 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -268,6 +274,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum autocfg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "a6d640bee2da49f60a4068a7fae53acde8982514ab7bae8b8cea9e88cbcfd799"
 "checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12"
 "checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
+"checksum fnv 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "2fad85553e09a6f881f739c29f0b00b0f01357c743266d478b68951ce23285f3"
 "checksum fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba"
 "checksum itoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1306f3464951f30e30d12373d31c79fbd52d236e5e896fd92f96ec7babbbe60b"
 "checksum libc 0.2.51 (registry+https://github.com/rust-lang/crates.io-index)" = "bedcc7a809076656486ffe045abeeac163da1b558e963a31e29fbfbeba916917"
diff --git a/Cargo.toml b/Cargo.toml
index 58d1b0c..860129e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -10,8 +10,9 @@ rand = "0.6.5"
 time = "0.1.42"
 num-traits = "0.2.6"
 arrayvec = "0.4.10"
+fnv = "1.0.6"
 
 [profile.release]
 debug = true
-debug-assertions = true
-overflow-checks = true
\ No newline at end of file
+# debug-assertions = true
+# overflow-checks = true
\ No newline at end of file
diff --git a/src/game.rs b/src/game.rs
index 982c276..18731a2 100644
--- a/src/game.rs
+++ b/src/game.rs
@@ -12,6 +12,7 @@ mod map;
 use map::*;
 
 use arrayvec::ArrayVec;
+use fnv::FnvHashSet;
 
 #[derive(Debug, PartialEq, Eq, Clone)]
 pub struct GameBoard {
@@ -20,6 +21,7 @@ pub struct GameBoard {
     pub players: [Player; 2],
     pub powerups: ArrayVec<[Powerup; 2]>,
     pub map: Map,
+    pub occupied_cells: FnvHashSet<Point2d<i8>>,
     pub outcome: SimulationOutcome
 }
 
@@ -65,11 +67,17 @@ impl GameBoard {
                 map.set(Point2d::new(cell.x, cell.y))
             }
         }
+
+        let players = [player, opponent];
+        let occupied_cells = players.iter()
+                .flat_map(|p| p.worms.iter())
+                .map(|w| w.position)
+                .collect();
             
         GameBoard {
             round: json.current_round,
             max_rounds: json.max_rounds,
-            players: [player, opponent],
+            players,
             powerups: json.map.iter().flatten().filter_map(|c| {
                 c.powerup.as_ref().map(|p| Powerup {
                     position: Point2d::new(c.x, c.y),
@@ -77,6 +85,7 @@ impl GameBoard {
                 })
             }).collect(),
             map,
+            occupied_cells,
             outcome: SimulationOutcome::Continue
         }
     }
@@ -119,6 +128,11 @@ impl GameBoard {
 
         self.round += 1;
         debug_assert_eq!(json.current_round, self.round);
+
+        self.occupied_cells = self.players.iter()
+            .flat_map(|p| p.worms.iter())
+            .map(|w| w.position)
+            .collect();
     }
 
     pub fn simulate(&mut self, moves: [Command; 2]) {
@@ -173,6 +187,9 @@ impl GameBoard {
                                 "Tried to move too far away, ({}, {})", p.x, p.y
                             );
 
+                            self.occupied_cells.remove(&worm.position);
+                            self.occupied_cells.insert(p);
+
                             worm.position = p;
                             
                             self.powerups.retain(|power| {
@@ -239,6 +256,7 @@ impl GameBoard {
                                     if target_worm.health <= 0 {
                                         // TODO: This will probably be changed soon https://github.com/EntelectChallenge/2019-Worms/issues/42
                                         self.players[player_index].moves_score += 40;
+                                        self.occupied_cells.remove(&target_worm.position);
                                     } else {
                                         self.players[player_index].moves_score -= 20;
                                     }
@@ -252,6 +270,7 @@ impl GameBoard {
                                     target_worm.health -= weapon_damage;
                                     if target_worm.health <= 0 {
                                         self.players[player_index].moves_score += 40;
+                                        self.occupied_cells.remove(&target_worm.position);
                                     } else {
                                         self.players[player_index].moves_score += 20;
                                     }
@@ -274,19 +293,13 @@ impl GameBoard {
         (player_index + 1)%2
     }
 
-
     pub fn valid_move_commands(&self, player_index: usize) -> ArrayVec<[Command;8]> {
         if let Some(worm) = self.players[player_index].active_worm() {
-            let taken_positions = self.players.iter()
-                .flat_map(|p| p.worms.iter())
-                .map(|w| w.position)
-                .collect::<ArrayVec<[Point2d<i8>; 6]>>();
-            
             Direction::all()
                 .iter()
                 .map(Direction::as_vec)
                 .map(|d| worm.position + d)
-                .filter(|p| !taken_positions.contains(p))
+                .filter(|p| !self.occupied_cells.contains(p))
                 .filter_map(|p| match self.map.at(p) {
                     Some(false) => Some(Command::Move(p)),
                     Some(true) => Some(Command::Dig(p)),