1 use {point, time_scope};
3 use super::{Grid, Level};
4 use noise::{NoiseFn, OpenSimplex, Seedable};
7 ////////// LEVEL GENERATOR /////////////////////////////////////////////////////
9 #[derive(Debug, Default)]
10 pub struct LevelGenerator {
13 pub wall_smooth_radius: u8,
17 pub fn new(seed: u32) -> Self{
21 wall_smooth_radius: 2,
25 pub fn generate(&self) -> Level {
26 println!("new level from {:?}", self);
27 time_scope!("level generation");
30 let (width, height) = (2560 / cell_size, 1440 / cell_size);
36 cells: vec!(vec!(true; height); width),
39 // start with some noise
40 // self.simplex_noise(&mut grid);
41 self.random_noise(&mut grid);
43 // smooth with cellular automata
44 self.smooth(&mut grid);
45 // grid.smooth_until_equilibrium(&mut grid);
47 // increase resolution
49 grid = self.subdivide(&mut grid);
50 self.smooth(&mut grid);
51 // self.smooth_until_equilibrium(&mut grid);
54 self.filter_regions(&mut grid);
56 let walls = self.find_walls(&grid);
58 gravity: point!(0.0, 0.1),
65 fn simplex_noise(&self, grid: &mut Grid<bool>) {
66 let noise = OpenSimplex::new().set_seed(self.seed);
67 self.set_each(grid, |x, y| noise.get([x as f64 / 12.0, y as f64 / 12.0]) > 0.055, 1);
71 fn random_noise(&self, grid: &mut Grid<bool>) {
72 let mut rng: rand::prelude::StdRng = rand::SeedableRng::seed_from_u64(self.seed as u64);
73 let noise = OpenSimplex::new().set_seed(self.seed);
74 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
75 // let w = self.width as f64;
76 // self.set_each(|_x, _y| rng.gen_range(0, 100) > (45 + ((15 * _x) as f64 / w) as usize), 1); // opens up to the right
80 fn smooth(&self, grid: &mut Grid<bool>) {
82 for _i in 0..self.iterations {
83 let mut next = vec!(vec!(true; grid.height); grid.width);
84 for x in distance..(grid.width - distance) {
85 for y in distance..(grid.height - distance) {
86 match self.neighbours(&grid.cells, x, y, distance) {
87 n if n < 4 => next[x][y] = false,
88 n if n > 4 => next[x][y] = true,
89 _ => next[x][y] = grid.cells[x][y]
93 if grid.cells == next {
102 fn smooth_until_equilibrium(&self, grid: &mut Grid<bool>) {
107 let mut next = vec!(vec!(true; grid.height); grid.width);
108 for x in distance..(grid.width - distance) {
109 for y in distance..(grid.height - distance) {
110 match self.neighbours(&grid.cells, x, y, distance) {
111 n if n < 4 => next[x][y] = false,
112 n if n > 4 => next[x][y] = true,
113 _ => next[x][y] = grid.cells[x][y]
117 if grid.cells == next {
123 println!(" {} iterations needed", count);
126 fn neighbours(&self, grid: &Vec<Vec<bool>>, px: usize, py: usize, distance: usize) -> u8 {
128 for x in (px - distance)..=(px + distance) {
129 for y in (py - distance)..=(py + distance) {
130 if !(x == px && y == py) && grid[x][y] {
138 fn set_each<F: FnMut(usize, usize) -> bool>(&self, grid: &mut Grid<bool>, mut func: F, walls: usize) {
139 for x in walls..(grid.width - walls) {
140 for y in walls..(grid.height - walls) {
141 grid.cells[x][y] = func(x, y);
146 fn subdivide(&self, grid: &mut Grid<bool>) -> Grid<bool> {
147 let (width, height) = (grid.width * 2, grid.height * 2);
148 let mut cells = vec!(vec!(true; height); width);
149 for x in 1..(width - 1) {
150 for y in 1..(height - 1) {
151 cells[x][y] = grid.cells[x / 2][y / 2];
155 cell_size: grid.cell_size / 2,
162 fn find_regions(&self, grid: &Grid<bool>) -> Vec<Region> {
163 time_scope!(" finding all regions");
164 let mut regions = vec!();
165 let mut marked = vec!(vec!(false; grid.height); grid.width);
166 for x in 0..grid.width {
167 for y in 0..grid.height {
169 regions.push(self.get_region_at_point(grid, x, y, &mut marked));
176 fn get_region_at_point(&self, grid: &Grid<bool>, x: usize, y: usize, marked: &mut Vec<Vec<bool>>) -> Region {
177 let value = grid.cells[x][y];
178 let mut cells = vec!();
179 let mut queue = vec!((x, y));
182 while let Some(p) = queue.pop() {
184 for i in &[(-1, 0), (1, 0), (0, -1), (0, 1)] {
185 let ip = (p.0 as isize + i.0, p.1 as isize + i.1);
186 if ip.0 >= 0 && ip.0 < grid.width as isize && ip.1 >= 0 && ip.1 < grid.height as isize {
187 let up = (ip.0 as usize, ip.1 as usize);
188 if grid.cells[up.0][up.1] == value && !marked[up.0][up.1] {
189 marked[up.0][up.1] = true;
196 Region { value, cells }
199 fn delete_region(&self, grid: &mut Grid<bool>, region: &Region) {
200 for c in ®ion.cells {
201 grid.cells[c.0][c.1] = !region.value;
205 fn filter_regions(&self, grid: &mut Grid<bool>) {
206 let min_wall_size = 0.0015;
207 println!(" grid size: ({}, {}) = {} cells", grid.width, grid.height, grid.width * grid.height);
208 println!(" min wall size: {}", (grid.width * grid.height) as f64 * min_wall_size);
210 // delete all smaller wall regions
211 for r in self.find_regions(grid).iter().filter(|r| r.value) {
212 let percent = r.cells.len() as f64 / (grid.width * grid.height) as f64;
213 if percent < min_wall_size {
214 // println!(" delete wall region of size {}", r.cells.len());
215 self.delete_region(grid, r);
219 // delete all rooms but the largest
220 let regions = self.find_regions(grid); // check again, because if a removed room contains a removed wall, the removed wall will become a room
221 let mut rooms: Vec<&Region> = regions.iter().filter(|r| !r.value).collect();
222 rooms.sort_by_key(|r| r.cells.len());
224 while rooms.len() > 1 {
225 self.delete_region(grid, rooms.pop().unwrap());
229 fn find_walls(&self, grid: &Grid<bool>) -> Vec<Vec<Point<isize>>> {
230 let mut walls = vec!();
231 for r in self.find_regions(&grid) {
233 let mut outline = r.outline(grid.cell_size);
234 for i in 2..(outline.len() - 2) {
235 // outline[i] = (outline[i - 1] + outline[i] + outline[i + 1]) / 3;
236 outline[i] = (outline[i - 2] + outline[i - 1] + outline[i] + outline[i + 1] + outline[i + 2]) / 5;
245 ////////// REGION //////////////////////////////////////////////////////////////
249 cells: Vec<(usize, usize)>,
253 fn enclosing_rect(&self) -> (usize, usize, usize, usize) {
254 let mut min = (usize::MAX, usize::MAX);
255 let mut max = (0, 0);
256 for c in &self.cells {
257 if c.0 < min.0 { min.0 = c.0; }
258 else if c.0 > max.0 { max.0 = c.0; }
259 if c.1 < min.1 { min.1 = c.1; }
260 else if c.1 > max.1 { max.1 = c.1; }
262 (min.0, min.1, 1 + max.0 - min.0, 1 + max.1 - min.1)
265 pub fn outline(&self, scale: usize) -> Vec<Point<isize>> {
266 let rect = self.enclosing_rect();
267 let (ox, oy, w, h) = rect;
268 let grid = self.grid(&rect);
269 let mut marked = vec!(vec!(false; h); w);
270 let mut outline = vec!();
271 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
273 let start = self.find_first_point_of_outline(&rect, &grid);
275 marked[p.x as usize][p.y as usize] = true;
277 outline.push((p + (ox as isize, oy as isize)) * scale as isize);
278 self.find_next_point_of_outline(&grid, &mut p, &mut directions);
282 marked[p.x as usize][p.y as usize] = true;
289 fn print_grid(&self, grid: &Vec<Vec<bool>>) {
291 let h = grid[0].len();
292 let mut g = vec!(vec!(false; w); h);
295 g[y][x] = grid[x][y];
298 println!("grid {} x {}", w, h);
301 print!("{}", n % 10);
304 for (n, row) in g.iter().enumerate() {
307 print!("{}", if *col { "#" } else { " " });
313 fn grid(&self, rect: &(usize, usize, usize, usize)) -> Vec<Vec<bool>> {
314 let (x, y, w, h) = rect;
315 let mut grid = vec!(vec!(false; *h); *w);
316 for c in &self.cells {
317 grid[c.0 - x][c.1 - y] = true;
322 fn find_first_point_of_outline(&self, rect: &(usize, usize, usize, usize), grid: &Vec<Vec<bool>>) -> Point<isize> {
323 let (ox, oy, w, h) = rect;
324 let is_outer_wall = (ox, oy) == (&0, &0); // we know this is always the outer wall of the level
327 if is_outer_wall && !grid[x][y] {
328 return point!(x as isize, y as isize - 1); // one step back because we're not on a wall tile
330 else if !is_outer_wall && grid[x][y] {
331 return point!(x as isize, y as isize);
335 panic!("no wall found!");
338 fn find_next_point_of_outline(&self, grid: &Vec<Vec<bool>>, p: &mut Point<isize>, directions: &mut Vec<(isize, isize)>) {
339 directions.rotate_left(2);
341 let d = directions[0];
342 if self.check(*p + d, grid) {
346 directions.rotate_right(1);
350 fn check(&self, p: Point<isize>, grid: &Vec<Vec<bool>>) -> bool {
351 if p.x < 0 || p.x >= grid.len() as isize || p.y < 0 || p.y >= grid[0].len() as isize {
354 grid[p.x as usize][p.y as usize]