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
+}