Strategy that starts building exhaustive game state tree

This falls over (and takes the host machine with it) because its
memory usage grows catastrophically.

The main use of time, reported by perf, was cloning the map vector.

3 files changed, 84 insertions, 8 deletions

diff --git a/src/game.rs b/src/game.rs
index 434828a..8fd9153 100644
--- a/src/game.rs
+++ b/src/game.rs
@@ -4,20 +4,20 @@ use crate::json;
 
 use arrayvec::ArrayVec;
 
-#[derive(Debug, PartialEq, Eq)]
+#[derive(Debug, PartialEq, Eq, Clone)]
 pub struct GameBoard {
     pub players: [Player; 2],
     pub powerups: ArrayVec<[Powerup; 2]>,
     pub map: Map,
 }
 
-#[derive(Debug, PartialEq, Eq)]
+#[derive(Debug, PartialEq, Eq, Clone)]
 pub struct Player {
     pub active_worm: usize,
     pub worms: ArrayVec<[Worm; 3]>
 }
 
-#[derive(Debug, PartialEq, Eq)]
+#[derive(Debug, PartialEq, Eq, Clone)]
 pub struct Worm {
     pub id: i32,
     pub health: i32,
@@ -31,7 +31,7 @@ pub enum Powerup {
     Health(Point2d<i8>, i32)
 }
 
-#[derive(Debug, PartialEq, Eq)]
+#[derive(Debug, PartialEq, Eq, Clone)]
 pub struct Map {
     pub size: u8,
     /// This is 2d, each row is size long
@@ -223,7 +223,7 @@ impl Player {
             .find(|w| w.id == id)
     }
 
-    fn active_worm(&self) -> &Worm {
+    pub fn active_worm(&self) -> &Worm {
         &self.worms[self.active_worm]
     }
 
@@ -233,7 +233,7 @@ impl Player {
 }
 
 impl Map {
-    fn at(&self, p: Point2d<i8>) -> Option<CellType> {
+    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 {
             None
         } else {
diff --git a/src/geometry/direction.rs b/src/geometry/direction.rs
index 84fe785..119aeee 100644
--- a/src/geometry/direction.rs
+++ b/src/geometry/direction.rs
@@ -53,4 +53,18 @@ impl Direction {
             NorthWest => Vec2d::new(-1, -1),
         }
     }
+
+    pub fn all() -> [Direction; 8] {
+        use Direction::*;
+        [
+            North,
+            NorthEast,
+            East,
+            SouthEast,
+            South,
+            SouthWest,
+            West,
+            NorthWest,
+        ]
+    }
 }
diff --git a/src/strategy.rs b/src/strategy.rs
index 37d2265..afebd12 100644
--- a/src/strategy.rs
+++ b/src/strategy.rs
@@ -1,6 +1,68 @@
 use crate::command::Command;
-use crate::game::GameBoard;
+use crate::game::{GameBoard, CellType};
+use crate::geometry::*;
 
-pub fn choose_move(_state: &GameBoard) -> Command {
+struct GameTree {
+    state: GameBoard,
+    next_states: Vec<([Command; 2], GameTree)>
+}
+
+pub fn choose_move(state: &GameBoard) -> Command {
+    let mut root = GameTree {
+        state: state.clone(),
+        next_states: Vec::new()
+    };
+
+    let mut last_depth = vec!(&mut root);
+
+    for depth in 0.. {
+        println!("Trying depth {}", depth);
+        println!("{} wide", last_depth.len());
+        let mut next_depth = Vec::new();
+        for mut tree in last_depth {
+            populate_next_states(&mut tree);
+            for x in &mut tree.next_states {
+                next_depth.push(&mut x.1);
+            }
+        }
+        last_depth = next_depth;
+    }
+    
     Command::DoNothing
 }
+
+fn populate_next_states(tree: &mut GameTree) {
+    let valid_player_moves = valid_moves(&tree.state, 0);
+    let valid_opponent_moves = valid_moves(&tree.state, 1);
+    for player_move in valid_player_moves {
+        for opponent_move in &valid_opponent_moves {
+            let commands = [player_move, *opponent_move];
+            let mut new_state = tree.state.clone();
+            let _ = new_state.simulate(commands);
+            tree.next_states.push((commands, GameTree {
+                state: new_state,
+                next_states: Vec::new()
+            }));
+        }
+    }
+}
+
+fn valid_moves(state: &GameBoard, player_index: usize) -> Vec<Command> {
+    let worm = state.players[player_index].active_worm();
+    
+    let mut moves = Direction::all().iter()
+        .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)),
+            _ => None
+        })
+        .collect::<Vec<_>>();
+    let mut shoots = Direction::all().iter()
+        .map(|d| Command::Shoot(*d))
+        .collect::<Vec<_>>();
+    moves.append(&mut shoots);
+
+    moves
+}