Cellular-automata based cave level generator

6 files changed, 162 insertions, 3 deletions

diff --git a/src/cli.yml b/src/cli.yml
index 7c374e102048..937b44c9c6f9 100644
--- a/src/cli.yml
+++ b/src/cli.yml
@@ -12,3 +12,11 @@ args:
 subcommands:
   - debug:
       about: Writes debug information to the terminal and exits
+  - generate-level:
+      about: Generate a level and print it to the screen
+      args:
+      - generator:
+          long: generator
+          value_name: GEN
+          help: Select which generator to use
+          takes_value: true
diff --git a/src/level_gen/cave_automata.rs b/src/level_gen/cave_automata.rs
new file mode 100644
index 000000000000..e46d542e6955
--- /dev/null
+++ b/src/level_gen/cave_automata.rs
@@ -0,0 +1,85 @@
+use crate::level_gen::util::rand_initialize;
+use crate::types::Dimensions;
+use rand::Rng;
+
+pub struct Params {
+    chance_to_start_alive: f64,
+    dimensions: Dimensions,
+    birth_limit: i32,
+    death_limit: i32,
+    steps: usize,
+}
+
+impl Default for Params {
+    fn default() -> Self {
+        Params {
+            chance_to_start_alive: 0.45,
+            dimensions: Dimensions { w: 80, h: 20 },
+            birth_limit: 4,
+            death_limit: 3,
+            steps: 2,
+        }
+    }
+}
+
+pub fn generate<R: Rng + ?Sized>(
+    params: &Params,
+    rand: &mut R,
+) -> Vec<Vec<bool>> {
+    let mut cells =
+        rand_initialize(&params.dimensions, rand, params.chance_to_start_alive);
+    for _ in 0..params.steps {
+        step_automata(&mut cells, params);
+    }
+    cells
+}
+
+fn step_automata(cells: &mut Vec<Vec<bool>>, params: &Params) {
+    let orig_cells = (*cells).clone();
+    for x in 0..(params.dimensions.h as usize) {
+        for y in 0..(params.dimensions.w as usize) {
+            let nbs = num_alive_neighbors(&orig_cells, x as i32, y as i32);
+            if orig_cells[x][y] {
+                if nbs < params.death_limit {
+                    cells[x][y] = false;
+                } else {
+                    cells[x][y] = true;
+                }
+            } else {
+                if nbs > params.birth_limit {
+                    cells[x][y] = true;
+                } else {
+                    cells[x][y] = false;
+                }
+            }
+        }
+    }
+}
+
+const COUNT_EDGES_AS_NEIGHBORS: bool = true;
+
+fn num_alive_neighbors(cells: &Vec<Vec<bool>>, x: i32, y: i32) -> i32 {
+    let mut count = 0;
+    for i in -1..2 {
+        for j in -1..2 {
+            if i == 0 && j == 0 {
+                continue;
+            }
+
+            let neighbor_x = x + i;
+            let neighbor_y = y + j;
+
+            if COUNT_EDGES_AS_NEIGHBORS
+                && (neighbor_x < 0
+                    || neighbor_y < 0
+                    || neighbor_x >= (cells.len() as i32)
+                    || neighbor_y >= (cells[0].len()) as i32)
+            {
+                count += 1;
+            } else if cells[neighbor_x as usize][neighbor_y as usize] {
+                count += 1;
+            }
+        }
+    }
+    count
+}
diff --git a/src/level_gen/display.rs b/src/level_gen/display.rs
new file mode 100644
index 000000000000..4472bf4fe392
--- /dev/null
+++ b/src/level_gen/display.rs
@@ -0,0 +1,17 @@
+use std::io::{self, Write};
+
+pub fn print_generated_level<W>(
+    level: &Vec<Vec<bool>>,
+    out: &mut W,
+) -> io::Result<()>
+where
+    W: Write,
+{
+    for row in level {
+        for cell in row {
+            write!(out, "{}", if *cell { "X" } else { " " })?;
+        }
+        write!(out, "\n")?;
+    }
+    Ok(())
+}
diff --git a/src/level_gen/mod.rs b/src/level_gen/mod.rs
new file mode 100644
index 000000000000..4df57a408fa8
--- /dev/null
+++ b/src/level_gen/mod.rs
@@ -0,0 +1,3 @@
+pub mod cave_automata;
+pub mod display;
+pub mod util;
diff --git a/src/level_gen/util.rs b/src/level_gen/util.rs
new file mode 100644
index 000000000000..89a4a6a882da
--- /dev/null
+++ b/src/level_gen/util.rs
@@ -0,0 +1,31 @@
+use crate::types::Dimensions;
+use rand::{distributions, Rng};
+
+pub fn falses(dims: &Dimensions) -> Vec<Vec<bool>> {
+    let mut ret = Vec::with_capacity(dims.h as usize);
+    for _ in 0..dims.h {
+        let mut row = Vec::with_capacity(dims.w as usize);
+        for _ in 0..dims.w {
+            row.push(false);
+        }
+        ret.push(row);
+    }
+    ret
+}
+
+pub fn rand_initialize<R: Rng + ?Sized>(
+    dims: &Dimensions,
+    rng: &mut R,
+    alive_chance: f64,
+) -> Vec<Vec<bool>> {
+    let distrib = distributions::Bernoulli::new(alive_chance).unwrap();
+    let mut ret = Vec::with_capacity(dims.h as usize);
+    for _ in 0..dims.h {
+        let mut row = Vec::with_capacity(dims.w as usize);
+        for _ in 0..dims.w {
+            row.push(rng.sample(distrib));
+        }
+        ret.push(row);
+    }
+    ret
+}
diff --git a/src/main.rs b/src/main.rs
index 69b7304e49d2..8479b5fa437c 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -35,12 +35,15 @@ mod types;
 mod entities;
 mod display;
 mod game;
+mod level_gen;
 mod messages;
 mod settings;
 
 use clap::App;
 use game::Game;
 use prettytable::format::consts::FORMAT_BOX_CHARS;
+use rand::rngs::SmallRng;
+use rand::SeedableRng;
 use settings::Settings;
 
 use backtrace::Backtrace;
@@ -73,14 +76,12 @@ fn main() {
     let settings = Settings::load().unwrap();
     settings.logging.init_log();
     let stdout = io::stdout();
-    let stdout = stdout.lock();
+    let mut stdout = stdout.lock();
 
     let stdin = io::stdin();
     let stdin = stdin.lock();
 
     let termsize = termion::terminal_size().ok();
-    // let termwidth = termsize.map(|(w, _)| w - 2).unwrap_or(70);
-    // let termheight = termsize.map(|(_, h)| h - 2).unwrap_or(40);
     let (termwidth, termheight) = termsize.unwrap_or((70, 40));
 
     match matches.subcommand() {
@@ -94,6 +95,20 @@ fn main() {
             table.set_format(*FORMAT_BOX_CHARS);
             table.printstd();
         }
+        ("generate-level", params) => {
+            let params = params.unwrap();
+            let mut rand = SmallRng::from_entropy();
+            let level = match params.value_of("generator") {
+                None => panic!("Must supply a generator with --generator"),
+                Some("cave_automata") => level_gen::cave_automata::generate(
+                    &Default::default(),
+                    &mut rand,
+                ),
+                Some(gen) => panic!("Unrecognized generator: {}", gen),
+            };
+            level_gen::display::print_generated_level(&level, &mut stdout)
+                .unwrap();
+        }
         _ => {
             let stdout = stdout.into_raw_mode().unwrap();
             init(settings, stdout, stdin, termwidth, termheight);