src/core/level/lvlgen.rs

   1 use geometry::{Point, Dimension};
   2 use noise::{NoiseFn, OpenSimplex, Seedable};
   3 use rand::Rng;
   4 use super::{Grid, Level, WallRegion};
   5 use {point, dimen, time_scope};
   6
   7 ////////// LEVEL GENERATOR /////////////////////////////////////////////////////
   8
   9 #[derive(Debug, Default)]
  10 pub struct LevelGenerator {
  11     pub seed: u32,
  12     pub iterations: u8,
  13     pub wall_smooth_radius: u8,
  14 }
  15
  16 impl LevelGenerator {
  17     pub fn new(seed: u32) -> Self{
  18         LevelGenerator {
  19             seed,
  20             iterations: 5,
  21             wall_smooth_radius: 2,
  22         }
  23     }
  24
  25     pub fn generate(&self) -> Level {
  26         dbg!(self);
  27         time_scope!("level generation");
  28
  29         let scale = 20.0;
  30         let size = dimen!((2560.0 / scale) as usize, (1440.0 / scale) as usize);
  31
  32         let mut grid = Grid {
  33             scale: (scale, scale).into(),
  34             cells: vec!(vec!(true; size.height); size.width),
  35             size,
  36         };
  37
  38         // start with some noise
  39 //      self.simplex_noise(&mut grid);
  40         self.random_noise(&mut grid);
  41
  42         // smooth with cellular automata
  43         self.smooth(&mut grid);
  44 //      grid.smooth_until_equilibrium(&mut grid);
  45
  46         // increase resolution
  47         for _i in 0..1 {
  48             grid = self.subdivide(&mut grid);
  49             self.smooth(&mut grid);
  50 //          self.smooth_until_equilibrium(&mut grid);
  51         }
  52
  53         self.filter_regions(&mut grid);
  54
  55         let walls = self.find_walls(&grid);
  56         Level::new(point!(0.0, 0.1), grid, walls)
  57     }
  58
  59     #[allow(dead_code)]
  60     fn simplex_noise(&self, grid: &mut Grid<bool>) {
  61         let noise = OpenSimplex::new().set_seed(self.seed);
  62         self.set_each(grid, |x, y| noise.get([x as f64 / 12.0, y as f64 / 12.0]) > 0.055, 1);
  63     }
  64
  65     #[allow(dead_code)]
  66     fn random_noise(&self, grid: &mut Grid<bool>) {
  67         let mut rng: rand::prelude::StdRng = rand::SeedableRng::seed_from_u64(self.seed as u64);
  68         let noise = OpenSimplex::new().set_seed(self.seed);
  69         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
  70         // let w = self.width as f64;
  71         // self.set_each(|_x, _y| rng.gen_range(0, 100) > (45 + ((15 * _x) as f64 / w) as usize), 1); // opens up to the right
  72     }
  73
  74     #[allow(dead_code)]
  75     fn smooth(&self, grid: &mut Grid<bool>) {
  76         let distance = 1;
  77         for _i in 0..self.iterations {
  78             let mut next = vec!(vec!(true; grid.size.height); grid.size.width);
  79             for x in distance..(grid.size.width - distance) {
  80                 for y in distance..(grid.size.height - distance) {
  81                     match self.neighbours(&grid.cells, x, y, distance) {
  82                         n if n < 4 => next[x][y] = false,
  83                         n if n > 4 => next[x][y] = true,
  84                         _ => next[x][y] = grid.cells[x][y]
  85                     }
  86                 }
  87             }
  88             if grid.cells == next {
  89                 break; // exit early
  90             } else {
  91                 grid.cells = next;
  92             }
  93         }
  94     }
  95
  96     #[allow(dead_code)]
  97     fn smooth_until_equilibrium(&self, grid: &mut Grid<bool>) {
  98         let distance = 1;
  99         let mut count = 0;
 100         loop {
 101             count += 1;
 102             let mut next = vec!(vec!(true; grid.size.height); grid.size.width);
 103             for x in distance..(grid.size.width - distance) {
 104                 for y in distance..(grid.size.height - distance) {
 105                     match self.neighbours(&grid.cells, x, y, distance) {
 106                         n if n < 4 => next[x][y] = false,
 107                         n if n > 4 => next[x][y] = true,
 108                         _ => next[x][y] = grid.cells[x][y]
 109                     };
 110                 }
 111             }
 112             if grid.cells == next {
 113                 break;
 114             } else {
 115                 grid.cells = next;
 116             }
 117         }
 118         println!("  {} iterations needed", count);
 119     }
 120
 121     fn neighbours(&self, grid: &[Vec<bool>], px: usize, py: usize, distance: usize) -> u8 {
 122         let mut count = 0;
 123         for x in (px - distance)..=(px + distance) {
 124             for y in (py - distance)..=(py + distance) {
 125                 if !(x == px && y == py) && grid[x][y] {
 126                     count += 1;
 127                 }
 128             }
 129         }
 130         count
 131     }
 132
 133     fn set_each<F: FnMut(usize, usize) -> bool>(&self, grid: &mut Grid<bool>, mut func: F, walls: usize) {
 134         for x in walls..(grid.size.width - walls) {
 135             for y in walls..(grid.size.height - walls) {
 136                 grid.cells[x][y] = func(x, y);
 137             }
 138         }
 139     }
 140
 141     fn subdivide(&self, grid: &mut Grid<bool>) -> Grid<bool> {
 142         let (width, height) = (grid.size.width * 2, grid.size.height * 2);
 143         let mut cells = vec!(vec!(true; height); width);
 144         for x in 1..(width - 1) {
 145             for y in 1..(height - 1) {
 146                 cells[x][y] = grid.cells[x / 2][y / 2];
 147             }
 148         }
 149         Grid {
 150             scale: (grid.scale.width / 2.0, grid.scale.height / 2.0).into(),
 151             size: (width, height).into(),
 152             cells
 153         }
 154     }
 155
 156     fn find_regions(&self, grid: &Grid<bool>) -> Vec<Region> {
 157         time_scope!("  finding all regions");
 158         let mut regions = vec!();
 159         let mut marked = vec!(vec!(false; grid.size.height); grid.size.width);
 160         for x in 0..grid.size.width {
 161             for y in 0..grid.size.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<bool>, 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.size.width as isize && ip.1 >= 0 && ip.1 < grid.size.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<bool>, 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<bool>) {
 200         let min_wall_size = 0.0015;
 201         println!("  grid size: ({}, {}) = {} cells", grid.size.width, grid.size.height, grid.size.width * grid.size.height);
 202         println!("  min wall size: {}", (grid.size.width * grid.size.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.size.width * grid.size.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<bool>) -> Vec<WallRegion> {
 224         let mut walls = vec!();
 225         for r in self.find_regions(&grid) {
 226             if r.value {
 227                 let outline = r.outline(&grid.scale);
 228                 let mut floats = outline.iter().map(|p| point!(p.x as f64, p.y as f64)).collect();
 229                 self.smooth_wall(&mut floats, self.wall_smooth_radius as isize);
 230                 let wall = WallRegion::new(floats);
 231                 walls.push(wall);
 232             }
 233         }
 234         walls
 235     }
 236
 237     fn smooth_wall(&self, points: &mut Vec<Point<f64>>, radius: isize) {
 238         let idx = |n| (n as isize + points.len() as isize) as usize % points.len();
 239         let mut new_points = points.clone();
 240         for i in 0..points.len() {
 241             new_points[i] = ((i as isize + 1 - radius)..=(i as isize + radius))                  // aggregates all points from -radius to +radius
 242                 .fold(points[idx(i as isize - radius)], |acc, o| acc + points[idx(o)]) // with addition
 243                 / (radius * 2 + 1) as f64;
 244         }
 245         *points = new_points;
 246     }
 247 }
 248
 249 ////////// REGION //////////////////////////////////////////////////////////////
 250
 251 struct Region {
 252     value: bool,
 253     cells: Vec<(usize, usize)>,
 254 }
 255
 256 impl Region {
 257     fn enclosing_rect(&self) -> (usize, usize, usize, usize) {
 258         let mut min = (usize::MAX, usize::MAX);
 259         let mut max = (0, 0);
 260         for c in &self.cells {
 261             if      c.0 < min.0 { min.0 = c.0; }
 262             else if c.0 > max.0 { max.0 = c.0; }
 263             if      c.1 < min.1 { min.1 = c.1; }
 264             else if c.1 > max.1 { max.1 = c.1; }
 265         }
 266         (min.0, min.1, 1 + max.0 - min.0, 1 + max.1 - min.1)
 267     }
 268
 269     pub fn outline(&self, scale: &Dimension<f64>) -> Vec<Point<isize>> {
 270         let rect = self.enclosing_rect();
 271         let (ox, oy, w, h) = rect;
 272         let grid = self.grid(&rect);
 273         let mut marked = vec!(vec!(false; h); w);
 274         let mut outline = vec!();
 275         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
 276         let multiplier = (scale.width as isize, scale.height as isize);
 277         let offset = (scale.width as isize / 2, scale.height as isize / 2);
 278
 279         let start = self.find_first_point_of_outline(&rect, &grid);
 280         let mut p = start;
 281         marked[p.x as usize][p.y as usize] = true;
 282         loop {
 283             outline.push((p + (ox as isize, oy as isize)) * multiplier + offset);
 284             self.find_next_point_of_outline(&grid, &mut p, &mut directions);
 285             if p == start {
 286                 break;
 287             }
 288             marked[p.x as usize][p.y as usize] = true;
 289         }
 290
 291         outline
 292     }
 293
 294     #[allow(dead_code)]
 295     fn print_grid(&self, grid: &[Vec<bool>]) {
 296         let w = grid.len();
 297         let h = grid[0].len();
 298         let mut g = vec!(vec!(false; w); h);
 299         for x in 0..w {
 300             for y in 0..h {
 301                 g[y][x] = grid[x][y];
 302             }
 303         }
 304         println!("grid {} x {}", w, h);
 305         print!("    ");
 306         for n in 0..w {
 307             print!("{}", n % 10);
 308         }
 309         println!();
 310         for (n, row) in g.iter().enumerate() {
 311             print!("{:>3}|", n);
 312             for col in row {
 313                 print!("{}", if *col { "#" } else { " " });
 314             }
 315             println!("|");
 316         }
 317     }
 318
 319     fn grid(&self, rect: &(usize, usize, usize, usize)) -> Vec<Vec<bool>> {
 320         let (x, y, w, h) = rect;
 321         let mut grid = vec!(vec!(false; *h); *w);
 322         for c in &self.cells {
 323             grid[c.0 - x][c.1 - y] = true;
 324         }
 325         grid
 326     }
 327
 328     fn find_first_point_of_outline(&self, rect: &(usize, usize, usize, usize), grid: &[Vec<bool>]) -> Point<isize> {
 329         let (ox, oy, w, h) = rect;
 330         let is_outer_wall = (ox, oy) == (&0, &0); // we know this is always the outer wall of the level
 331         for x in 0..*w {
 332             for y in 0..*h {
 333                 if is_outer_wall && !grid[x][y] {
 334                     return point!(x as isize, y as isize - 1); // one step back because we're not on a wall tile
 335                 }
 336                 else if !is_outer_wall && grid[x][y] {
 337                     return point!(x as isize, y as isize);
 338                 }
 339             }
 340         }
 341         panic!("no wall found!");
 342     }
 343
 344     fn find_next_point_of_outline(&self, grid: &[Vec<bool>], p: &mut Point<isize>, directions: &mut Vec<(isize, isize)>) {
 345         directions.rotate_left(2);
 346         loop {
 347             let d = directions[0];
 348             if self.check(*p + d, grid) {
 349                 *p += d;
 350                 break;
 351             }
 352             directions.rotate_right(1);
 353         }
 354     }
 355
 356     fn check(&self, p: Point<isize>, grid: &[Vec<bool>]) -> bool {
 357         if p.x < 0 || p.x >= grid.len() as isize || p.y < 0 || p.y >= grid[0].len() as isize {
 358             false
 359         } else {
 360             grid[p.x as usize][p.y as usize]
 361         }
 362     }
 363 }