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