1 use common::{Point, Dimension};
3 use noise::{NoiseFn, OpenSimplex, Seedable};
5 use super::{Grid, Level, WallRegion};
6 use {point, time_scope};
8 ////////// LEVEL GENERATOR /////////////////////////////////////////////////////
10 #[derive(Debug, Default)]
11 pub struct LevelGenerator {
14 pub wall_smooth_radius: u8,
18 pub fn new(seed: u32) -> Self{
22 wall_smooth_radius: 2,
26 pub fn generate(&self) -> Level {
28 time_scope!("level generation");
31 let (width, height) = (2560 / cell_size, 1440 / cell_size);
34 cell_size: (cell_size, cell_size).into(),
35 size: (width, height).into(),
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);
57 Level::new(point!(0.0, 0.1), grid, walls)
61 fn simplex_noise(&self, grid: &mut Grid<bool>) {
62 let noise = OpenSimplex::new().set_seed(self.seed);
63 self.set_each(grid, |x, y| noise.get([x as f64 / 12.0, y as f64 / 12.0]) > 0.055, 1);
67 fn random_noise(&self, grid: &mut Grid<bool>) {
68 let mut rng: rand::prelude::StdRng = rand::SeedableRng::seed_from_u64(self.seed as u64);
69 let noise = OpenSimplex::new().set_seed(self.seed);
70 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
71 // let w = self.width as f64;
72 // self.set_each(|_x, _y| rng.gen_range(0, 100) > (45 + ((15 * _x) as f64 / w) as usize), 1); // opens up to the right
76 fn smooth(&self, grid: &mut Grid<bool>) {
78 for _i in 0..self.iterations {
79 let mut next = vec!(vec!(true; grid.size.height); grid.size.width);
80 for x in distance..(grid.size.width - distance) {
81 for y in distance..(grid.size.height - distance) {
82 match self.neighbours(&grid.cells, x, y, distance) {
83 n if n < 4 => next[x][y] = false,
84 n if n > 4 => next[x][y] = true,
85 _ => next[x][y] = grid.cells[x][y]
89 if grid.cells == next {
98 fn smooth_until_equilibrium(&self, grid: &mut Grid<bool>) {
103 let mut next = vec!(vec!(true; grid.size.height); grid.size.width);
104 for x in distance..(grid.size.width - distance) {
105 for y in distance..(grid.size.height - distance) {
106 match self.neighbours(&grid.cells, x, y, distance) {
107 n if n < 4 => next[x][y] = false,
108 n if n > 4 => next[x][y] = true,
109 _ => next[x][y] = grid.cells[x][y]
113 if grid.cells == next {
119 println!(" {} iterations needed", count);
122 fn neighbours(&self, grid: &Vec<Vec<bool>>, px: usize, py: usize, distance: usize) -> u8 {
124 for x in (px - distance)..=(px + distance) {
125 for y in (py - distance)..=(py + distance) {
126 if !(x == px && y == py) && grid[x][y] {
134 fn set_each<F: FnMut(usize, usize) -> bool>(&self, grid: &mut Grid<bool>, mut func: F, walls: usize) {
135 for x in walls..(grid.size.width - walls) {
136 for y in walls..(grid.size.height - walls) {
137 grid.cells[x][y] = func(x, y);
142 fn subdivide(&self, grid: &mut Grid<bool>) -> Grid<bool> {
143 let (width, height) = (grid.size.width * 2, grid.size.height * 2);
144 let mut cells = vec!(vec!(true; height); width);
145 for x in 1..(width - 1) {
146 for y in 1..(height - 1) {
147 cells[x][y] = grid.cells[x / 2][y / 2];
151 cell_size: (grid.cell_size.width / 2, grid.cell_size.height / 2).into(),
152 size: (width, height).into(),
157 fn find_regions(&self, grid: &Grid<bool>) -> Vec<Region> {
158 time_scope!(" finding all regions");
159 let mut regions = vec!();
160 let mut marked = vec!(vec!(false; grid.size.height); grid.size.width);
161 for x in 0..grid.size.width {
162 for y in 0..grid.size.height {
164 regions.push(self.get_region_at_point(grid, x, y, &mut marked));
171 fn get_region_at_point(&self, grid: &Grid<bool>, x: usize, y: usize, marked: &mut Vec<Vec<bool>>) -> Region {
172 let value = grid.cells[x][y];
173 let mut cells = vec!();
174 let mut queue = vec!((x, y));
177 while let Some(p) = queue.pop() {
179 for i in &[(-1, 0), (1, 0), (0, -1), (0, 1)] {
180 let ip = (p.0 as isize + i.0, p.1 as isize + i.1);
181 if ip.0 >= 0 && ip.0 < grid.size.width as isize && ip.1 >= 0 && ip.1 < grid.size.height as isize {
182 let up = (ip.0 as usize, ip.1 as usize);
183 if grid.cells[up.0][up.1] == value && !marked[up.0][up.1] {
184 marked[up.0][up.1] = true;
191 Region { value, cells }
194 fn delete_region(&self, grid: &mut Grid<bool>, region: &Region) {
195 for c in ®ion.cells {
196 grid.cells[c.0][c.1] = !region.value;
200 fn filter_regions(&self, grid: &mut Grid<bool>) {
201 let min_wall_size = 0.0015;
202 println!(" grid size: ({}, {}) = {} cells", grid.size.width, grid.size.height, grid.size.width * grid.size.height);
203 println!(" min wall size: {}", (grid.size.width * grid.size.height) as f64 * min_wall_size);
205 // delete all smaller wall regions
206 for r in self.find_regions(grid).iter().filter(|r| r.value) {
207 let percent = r.cells.len() as f64 / (grid.size.width * grid.size.height) as f64;
208 if percent < min_wall_size {
209 // println!(" delete wall region of size {}", r.cells.len());
210 self.delete_region(grid, r);
214 // delete all rooms but the largest
215 let regions = self.find_regions(grid); // check again, because if a removed room contains a removed wall, the removed wall will become a room
216 let mut rooms: Vec<&Region> = regions.iter().filter(|r| !r.value).collect();
217 rooms.sort_by_key(|r| r.cells.len());
219 while rooms.len() > 1 {
220 self.delete_region(grid, rooms.pop().unwrap());
224 fn find_walls(&self, grid: &Grid<bool>) -> Vec<Rc<WallRegion>> {
225 let mut walls = vec!();
226 for r in self.find_regions(&grid) {
228 let outline = r.outline(&grid.cell_size);
229 let mut floats = outline.iter().map(|p| point!(p.x as f64, p.y as f64)).collect();
230 self.smooth_wall(&mut floats, self.wall_smooth_radius as isize);
231 let wall = WallRegion::new(floats);
238 fn smooth_wall(&self, points: &mut Vec<Point<f64>>, radius: isize) {
239 let idx = |n| (n as isize + points.len() as isize) as usize % points.len();
240 let mut new_points = points.clone();
241 for i in 0..points.len() {
242 new_points[i] = ((i as isize + 1 - radius)..=(i as isize + radius)) // aggregates all points from -radius to +radius
243 .fold(points[idx(i as isize - radius)], |acc, o| acc + points[idx(o)]) // with addition
244 / (radius * 2 + 1) as f64;
246 *points = new_points;
250 ////////// REGION //////////////////////////////////////////////////////////////
254 cells: Vec<(usize, usize)>,
258 fn enclosing_rect(&self) -> (usize, usize, usize, usize) {
259 let mut min = (usize::MAX, usize::MAX);
260 let mut max = (0, 0);
261 for c in &self.cells {
262 if c.0 < min.0 { min.0 = c.0; }
263 else if c.0 > max.0 { max.0 = c.0; }
264 if c.1 < min.1 { min.1 = c.1; }
265 else if c.1 > max.1 { max.1 = c.1; }
267 (min.0, min.1, 1 + max.0 - min.0, 1 + max.1 - min.1)
270 pub fn outline(&self, scale: &Dimension<usize>) -> Vec<Point<isize>> {
271 let rect = self.enclosing_rect();
272 let (ox, oy, w, h) = rect;
273 let grid = self.grid(&rect);
274 let mut marked = vec!(vec!(false; h); w);
275 let mut outline = vec!();
276 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
277 let multiplier = (scale.width as isize, scale.height as isize);
278 let offset = (scale.width as isize / 2, scale.height as isize / 2);
280 let start = self.find_first_point_of_outline(&rect, &grid);
282 marked[p.x as usize][p.y as usize] = true;
284 outline.push((p + (ox as isize, oy as isize)) * multiplier + offset);
285 self.find_next_point_of_outline(&grid, &mut p, &mut directions);
289 marked[p.x as usize][p.y as usize] = true;
296 fn print_grid(&self, grid: &Vec<Vec<bool>>) {
298 let h = grid[0].len();
299 let mut g = vec!(vec!(false; w); h);
302 g[y][x] = grid[x][y];
305 println!("grid {} x {}", w, h);
308 print!("{}", n % 10);
311 for (n, row) in g.iter().enumerate() {
314 print!("{}", if *col { "#" } else { " " });
320 fn grid(&self, rect: &(usize, usize, usize, usize)) -> Vec<Vec<bool>> {
321 let (x, y, w, h) = rect;
322 let mut grid = vec!(vec!(false; *h); *w);
323 for c in &self.cells {
324 grid[c.0 - x][c.1 - y] = true;
329 fn find_first_point_of_outline(&self, rect: &(usize, usize, usize, usize), grid: &Vec<Vec<bool>>) -> Point<isize> {
330 let (ox, oy, w, h) = rect;
331 let is_outer_wall = (ox, oy) == (&0, &0); // we know this is always the outer wall of the level
334 if is_outer_wall && !grid[x][y] {
335 return point!(x as isize, y as isize - 1); // one step back because we're not on a wall tile
337 else if !is_outer_wall && grid[x][y] {
338 return point!(x as isize, y as isize);
342 panic!("no wall found!");
345 fn find_next_point_of_outline(&self, grid: &Vec<Vec<bool>>, p: &mut Point<isize>, directions: &mut Vec<(isize, isize)>) {
346 directions.rotate_left(2);
348 let d = directions[0];
349 if self.check(*p + d, grid) {
353 directions.rotate_right(1);
357 fn check(&self, p: Point<isize>, grid: &Vec<Vec<bool>>) -> bool {
358 if p.x < 0 || p.x >= grid.len() as isize || p.y < 0 || p.y >= grid[0].len() as isize {
361 grid[p.x as usize][p.y as usize]