1 files changed, 64 insertions, 2 deletions
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
+}