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.

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