src/core/level/lvlgen.rs

   1 use {point, time_scope};
   2 use common::Point2D;
   3 use super::{Grid, Level};
   4 use noise::{NoiseFn, OpenSimplex, Seedable};
   5 use rand::Rng;
   6
   7 ////////// LEVEL GENERATOR /////////////////////////////////////////////////////
   8
   9 #[derive(Default)]
  10 pub struct LevelGenerator {
  11     pub seed: u32,
  12     pub iterations: u8,
  13 }
  14
  15 impl LevelGenerator {
  16     pub fn new(seed: u32, iterations: u8) -> Self{
  17         LevelGenerator { seed, iterations }
  18     }
  19
  20     pub fn generate(&self) -> Level {
  21         time_scope!("grid generation");
  22
  23         let cell_size = 20;
  24         let (width, height) = (2560 / cell_size, 1440 / cell_size);
  25
  26         let mut grid = Grid {
  27             cell_size,
  28             width,
  29             height,
  30             cells: vec!(vec!(true; height); width),
  31         };
  32
  33         // start with some noise
  34 //      self.simplex_noise(&mut grid);
  35         self.random_noise(&mut grid);
  36
  37         // smooth with cellular automata
  38         self.smooth(&mut grid);
  39 //      grid.smooth_until_equilibrium(&mut grid);
  40
  41         // increase resolution
  42         for _i in 0..1 {
  43             grid = self.subdivide(&mut grid);
  44             self.smooth(&mut grid);
  45 //          self.smooth_until_equilibrium(&mut grid);
  46         }
  47
  48         self.filter_regions(&mut grid);
  49
  50         let walls = self.find_walls(&grid);
  51         Level {
  52             gravity: point!(0.0, 0.1),
  53             grid,
  54             walls,
  55         }
  56     }
  57
  58     #[allow(dead_code)]
  59     fn simplex_noise(&self, grid: &mut Grid) {
  60         let noise = OpenSimplex::new().set_seed(self.seed);
  61         self.set_each(grid, |x, y| noise.get([x as f64 / 12.0, y as f64 / 12.0]) > 0.055, 1);
  62     }
  63
  64     #[allow(dead_code)]
  65     fn random_noise(&self, grid: &mut Grid) {
  66         let mut rng: rand::prelude::StdRng = rand::SeedableRng::seed_from_u64(self.seed as u64);
  67         let noise = OpenSimplex::new().set_seed(self.seed);
  68         self.set_each(grid, |_x, _y| rng.gen_range(0, 100) > (45 + (150.0 * noise.get([_x as f64 / 40.0, _y as f64 / 10.0])) as usize), 1); // more horizontal platforms
  69         // let w = self.width as f64;
  70         // self.set_each(|_x, _y| rng.gen_range(0, 100) > (45 + ((15 * _x) as f64 / w) as usize), 1); // opens up to the right
  71     }
  72
  73     #[allow(dead_code)]
  74     fn smooth(&self, grid: &mut Grid) {
  75         let distance = 1;
  76         for _i in 0..self.iterations {
  77             let mut next = vec!(vec!(true; grid.height); grid.width);
  78             for x in distance..(grid.width - distance) {
  79                 for y in distance..(grid.height - distance) {
  80                     match self.neighbours(&grid.cells, x, y, distance) {
  81                         n if n < 4 => next[x][y] = false,
  82                         n if n > 4 => next[x][y] = true,
  83                         _ => next[x][y] = grid.cells[x][y]
  84                     }
  85                 }
  86             }
  87             if grid.cells == next {
  88                 break; // exit early
  89             } else {
  90                 grid.cells = next;
  91             }
  92         }
  93     }
  94
  95     #[allow(dead_code)]
  96     fn smooth_until_equilibrium(&self, grid: &mut Grid) {
  97         let distance = 1;
  98         let mut count = 0;
  99         loop {
 100             count += 1;
 101             let mut next = vec!(vec!(true; grid.height); grid.width);
 102             for x in distance..(grid.width - distance) {
 103                 for y in distance..(grid.height - distance) {
 104                     match self.neighbours(&grid.cells, x, y, distance) {
 105                         n if n < 4 => next[x][y] = false,
 106                         n if n > 4 => next[x][y] = true,
 107                         _ => next[x][y] = grid.cells[x][y]
 108                     };
 109                 }
 110             }
 111             if grid.cells == next {
 112                 break;
 113             } else {
 114                 grid.cells = next;
 115             }
 116         }
 117         println!("{} iterations needed", count);
 118     }
 119
 120     fn neighbours(&self, grid: &Vec<Vec<bool>>, px: usize, py: usize, distance: usize) -> u8 {
 121         let mut count = 0;
 122         for x in (px - distance)..=(px + distance) {
 123             for y in (py - distance)..=(py + distance) {
 124                 if !(x == px && y == py) && grid[x][y] {
 125                     count += 1;
 126                 }
 127             }
 128         }
 129         count
 130     }
 131
 132     fn set_each<F: FnMut(usize, usize) -> bool>(&self, grid: &mut Grid, mut func: F, walls: usize) {
 133         for x in walls..(grid.width - walls) {
 134             for y in walls..(grid.height - walls) {
 135                 grid.cells[x][y] = func(x, y);
 136             }
 137         }
 138     }
 139
 140     fn subdivide(&self, grid: &mut Grid) -> Grid {
 141         let (width, height) = (grid.width * 2, grid.height * 2);
 142         let mut cells = vec!(vec!(true; height); width);
 143         for x in 1..(width - 1) {
 144             for y in 1..(height - 1) {
 145                 cells[x][y] = grid.cells[x / 2][y / 2];
 146             }
 147         }
 148         Grid {
 149             cell_size: grid.cell_size / 2,
 150             width,
 151             height,
 152             cells
 153         }
 154     }
 155
 156     fn find_regions(&self, grid: &Grid) -> Vec<Region> {
 157         time_scope!("finding all regions");
 158         let mut regions = vec!();
 159         let mut marked = vec!(vec!(false; grid.height); grid.width);
 160         for x in 0..grid.width {
 161             for y in 0..grid.height {
 162                 if !marked[x][y] {
 163                     regions.push(self.get_region_at_point(grid, x, y, &mut marked));
 164                 }
 165             }
 166         }
 167         regions
 168     }
 169
 170     fn get_region_at_point(&self, grid: &Grid, x: usize, y: usize, marked: &mut Vec<Vec<bool>>) -> Region {
 171         let value = grid.cells[x][y];
 172         let mut cells = vec!();
 173         let mut queue = vec!((x, y));
 174         marked[x][y] = true;
 175
 176         while let Some(p) = queue.pop() {
 177             cells.push(p);
 178             for i in &[(-1, 0), (1, 0), (0, -1), (0, 1)] {
 179                 let ip = (p.0 as isize + i.0, p.1 as isize + i.1);
 180                 if ip.0 >= 0 && ip.0 < grid.width as isize && ip.1 >= 0 && ip.1 < grid.height as isize {
 181                     let up = (ip.0 as usize, ip.1 as usize);
 182                     if grid.cells[up.0][up.1] == value && !marked[up.0][up.1] {
 183                         marked[up.0][up.1] = true;
 184                         queue.push(up);
 185                     }
 186                 }
 187             }
 188         }
 189
 190         Region { value, cells }
 191     }
 192
 193     fn delete_region(&self, grid: &mut Grid, region: &Region) {
 194         for c in &region.cells {
 195             grid.cells[c.0][c.1] = !region.value;
 196         }
 197     }
 198
 199     fn filter_regions(&self, grid: &mut Grid) {
 200         let min_wall_size = 0.0015;
 201         println!("grid size: ({}, {}) = {} cells", grid.width, grid.height, grid.width * grid.height);
 202         println!("min wall size: {}", (grid.width * grid.height) as f64 * min_wall_size);
 203
 204         // delete all smaller wall regions
 205         for r in self.find_regions(grid).iter().filter(|r| r.value) {
 206             let percent = r.cells.len() as f64 / (grid.width * grid.height) as f64;
 207             if percent < min_wall_size {
 208                 // println!("delete wall region of size {}", r.cells.len());
 209                 self.delete_region(grid, r);
 210             }
 211         }
 212
 213         // delete all rooms but the largest
 214         let regions = self.find_regions(grid); // check again, because if a removed room contains a removed wall, the removed wall will become a room
 215         let mut rooms: Vec<&Region> = regions.iter().filter(|r| !r.value).collect();
 216         rooms.sort_by_key(|r| r.cells.len());
 217         rooms.reverse();
 218         while rooms.len() > 1 {
 219             self.delete_region(grid, rooms.pop().unwrap());
 220         }
 221     }
 222
 223     fn find_walls(&self, grid: &Grid) -> Vec<Vec<Point2D<isize>>> {
 224         let mut walls = vec!();
 225         for r in self.find_regions(&grid) {
 226             if r.value {
 227                 let mut outline = r.outline(grid.cell_size);
 228                 for i in 2..(outline.len() - 2) {
 229 //                  outline[i] = (outline[i - 1] + outline[i] + outline[i + 1]) / 3;
 230                     outline[i] = (outline[i - 2] + outline[i - 1] + outline[i] + outline[i + 1] + outline[i + 2]) / 5;
 231                 }
 232                 walls.push(outline);
 233             }
 234         }
 235         walls
 236     }
 237 }
 238
 239 ////////// REGION //////////////////////////////////////////////////////////////
 240
 241 struct Region {
 242     value: bool,
 243     cells: Vec<(usize, usize)>,
 244 }
 245
 246 impl Region {
 247     fn enclosing_rect(&self) -> (usize, usize, usize, usize) {
 248         let mut min = (usize::MAX, usize::MAX);
 249         let mut max = (0, 0);
 250         for c in &self.cells {
 251             if      c.0 < min.0 { min.0 = c.0; }
 252             else if c.0 > max.0 { max.0 = c.0; }
 253             if      c.1 < min.1 { min.1 = c.1; }
 254             else if c.1 > max.1 { max.1 = c.1; }
 255         }
 256         (min.0, min.1, 1 + max.0 - min.0, 1 + max.1 - min.1)
 257     }
 258
 259     pub fn outline(&self, scale: usize) -> Vec<Point2D<isize>> {
 260         let rect = self.enclosing_rect();
 261         let (ox, oy, w, h) = rect;
 262         let grid = self.grid(&rect);
 263         let mut marked = vec!(vec!(false; h); w);
 264         let mut outline = vec!();
 265         let mut directions = vec!((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)); // 8 directions rotating right from starting direction right
 266
 267         let mut p = self.find_first_point_of_outline(&rect, &grid);
 268         marked[p.x as usize][p.y as usize] = true;
 269         loop {
 270             outline.push((p + (ox as isize, oy as isize)) * scale as isize);
 271             self.find_next_point_of_outline(&grid, &mut p, &mut directions);
 272             if marked[p.x as usize][p.y as usize] {
 273                 // we're back at the beginning
 274                 break;
 275             }
 276             marked[p.x as usize][p.y as usize] = true;
 277         }
 278
 279         outline
 280     }
 281
 282     #[allow(dead_code)]
 283     fn print_grid(&self, grid: &Vec<Vec<bool>>) {
 284         let w = grid.len();
 285         let h = grid[0].len();
 286         let mut g = vec!(vec!(false; w); h);
 287         for x in 0..w {
 288             for y in 0..h {
 289                 g[y][x] = grid[x][y];
 290             }
 291         }
 292         println!("grid {} x {}", w, h);
 293         print!("    ");
 294         for n in 0..w {
 295             print!("{}", n % 10);
 296         }
 297         println!();
 298         for (n, row) in g.iter().enumerate() {
 299             print!("{:>3}|", n);
 300             for col in row {
 301                 print!("{}", if *col { "#" } else { " " });
 302             }
 303             println!("|");
 304         }
 305     }
 306
 307     fn grid(&self, rect: &(usize, usize, usize, usize)) -> Vec<Vec<bool>> {
 308         let (x, y, w, h) = rect;
 309         let mut grid = vec!(vec!(false; *h); *w);
 310         for c in &self.cells {
 311             grid[c.0 - x][c.1 - y] = true;
 312         }
 313         grid
 314     }
 315
 316     fn find_first_point_of_outline(&self, rect: &(usize, usize, usize, usize), grid: &Vec<Vec<bool>>) -> Point2D<isize> {
 317         let (ox, oy, w, h) = rect;
 318         let is_outer_wall = (ox, oy) == (&0, &0); // we know this is always the outer wall of the level
 319         for x in 0..*w {
 320             for y in 0..*h {
 321                 if is_outer_wall && !grid[x][y] {
 322                     return point!(x as isize, y as isize - 1); // one step back because we're not on a wall tile
 323                 }
 324                 else if !is_outer_wall && grid[x][y] {
 325                     return point!(x as isize, y as isize);
 326                 }
 327             }
 328         }
 329         panic!("no wall found!");
 330     }
 331
 332     fn find_next_point_of_outline(&self, grid: &Vec<Vec<bool>>, p: &mut Point2D<isize>, directions: &mut Vec<(isize, isize)>) {
 333         directions.rotate_left(2);
 334         loop {
 335             let d = directions[0];
 336             if self.check(*p + d, grid) {
 337                 *p += d;
 338                 break;
 339             }
 340             directions.rotate_right(1);
 341         }
 342     }
 343
 344     fn check(&self, p: Point2D<isize>, grid: &Vec<Vec<bool>>) -> bool {
 345         if p.x < 0 || p.x >= grid.len() as isize || p.y < 0 || p.y >= grid[0].len() as isize {
 346             false
 347         } else {
 348             grid[p.x as usize][p.y as usize]
 349         }
 350     }
 351 }