author | unC0Rr |
Mon, 16 Sep 2024 16:57:11 +0200 | |
branch | transitional_engine |
changeset 16034 | 09beeec033ba |
parent 16033 | 1860852892c0 |
child 16035 | 0caa3dfb3ba2 |
permissions | -rw-r--r-- |
16032 | 1 |
use crate::outline_template_based::outline::OutlinePoints; |
2 |
use crate::{LandGenerationParameters, LandGenerator}; |
|
3 |
use integral_geometry::{Point, Polygon, Rect, Size}; |
|
4 |
use land2d::Land2D; |
|
5 |
||
6 |
pub struct MazeTemplate { |
|
16033
1860852892c0
Use rust implementation of maze generator in engine
unC0Rr
parents:
16032
diff
changeset
|
7 |
pub width: usize, |
1860852892c0
Use rust implementation of maze generator in engine
unC0Rr
parents:
16032
diff
changeset
|
8 |
pub height: usize, |
1860852892c0
Use rust implementation of maze generator in engine
unC0Rr
parents:
16032
diff
changeset
|
9 |
pub cell_size: usize, |
1860852892c0
Use rust implementation of maze generator in engine
unC0Rr
parents:
16032
diff
changeset
|
10 |
pub inverted: bool, |
1860852892c0
Use rust implementation of maze generator in engine
unC0Rr
parents:
16032
diff
changeset
|
11 |
pub distortion_limiting_factor: u32, |
16034 | 12 |
pub braidness: u32, |
13 |
} |
|
14 |
||
15 |
struct Maze { |
|
16 |
inverted: bool, |
|
17 |
braidness: u32, |
|
18 |
off_y: i32, |
|
19 |
num_cells: Size, |
|
20 |
num_edges: Size, |
|
21 |
seen_cells: Size, |
|
22 |
cell_size: usize, |
|
23 |
seen_list: Vec<Vec<Option<usize>>>, |
|
24 |
walls: Vec<Vec<Vec<bool>>>, |
|
25 |
edge_list: Vec<Vec<Vec<bool>>>, |
|
26 |
last_cell: Vec<Point>, |
|
27 |
came_from: Vec<Vec<Point>>, |
|
28 |
came_from_pos: Vec<i32>, |
|
29 |
} |
|
30 |
||
31 |
fn in_line(p1: &Point, p2: &Point, p3: &Point) -> bool { |
|
32 |
p1.x == p2.x && p2.x == p3.x || p1.y == p2.y && p2.y == p3.y |
|
33 |
} |
|
34 |
||
35 |
#[derive(Clone, Copy)] |
|
36 |
struct Direction(Point); |
|
37 |
||
38 |
impl Direction { |
|
39 |
#[inline] |
|
40 |
pub fn new(direction: usize) -> Self { |
|
41 |
match direction % 4 { |
|
42 |
0 => Self(Point::new(0, -1)), |
|
43 |
1 => Self(Point::new(1, 0)), |
|
44 |
2 => Self(Point::new(0, 1)), |
|
45 |
3 => Self(Point::new(-1, 0)), |
|
46 |
_ => panic!("Impossible"), |
|
47 |
} |
|
48 |
} |
|
49 |
||
50 |
#[inline] |
|
51 |
pub fn rotate_right(self) -> Self { |
|
52 |
Self(self.0.rotate90()) |
|
53 |
} |
|
54 |
||
55 |
#[inline] |
|
56 |
pub fn rotate_left(self) -> Self { |
|
57 |
Self(self.0.rotate270()) |
|
58 |
} |
|
59 |
||
60 |
#[inline] |
|
61 |
pub fn to_edge(self) -> Self { |
|
62 |
Self(Point::new( |
|
63 |
if self.0.x < 0 { 0 } else { self.0.x }, |
|
64 |
if self.0.y < 0 { 0 } else { self.0.y }, |
|
65 |
)) |
|
66 |
} |
|
67 |
||
68 |
#[inline] |
|
69 |
pub fn orientation(&self) -> usize { |
|
70 |
if self.0.x == 0 { |
|
71 |
0 |
|
72 |
} else { |
|
73 |
1 |
|
74 |
} |
|
75 |
} |
|
76 |
} |
|
77 |
||
78 |
impl Maze { |
|
79 |
pub fn new<I: Iterator<Item = u32>>( |
|
80 |
size: &Size, |
|
81 |
cell_size: usize, |
|
82 |
num_steps: usize, |
|
83 |
inverted: bool, |
|
84 |
braidness: u32, |
|
85 |
random_numbers: &mut I, |
|
86 |
) -> Self { |
|
87 |
let num_cells = Size::new( |
|
88 |
prev_odd(size.width / cell_size), |
|
89 |
prev_odd(size.height / cell_size), |
|
90 |
); |
|
91 |
||
92 |
let num_edges = Size::new(num_cells.width - 1, num_cells.height - 1); |
|
93 |
let seen_cells = Size::new(num_cells.width / 2, num_cells.height / 2); |
|
94 |
||
95 |
let mut last_cell = vec![Point::diag(0); num_steps]; |
|
96 |
let came_from_pos = vec![0; num_steps]; |
|
97 |
let came_from = vec![vec![Point::diag(0); num_steps]; num_cells.area()]; |
|
98 |
||
99 |
let seen_list = vec![vec![None as Option<usize>; seen_cells.width]; seen_cells.height]; |
|
100 |
let walls = vec![vec![vec![true; seen_cells.width]; seen_cells.height]; 2]; |
|
101 |
let edge_list = vec![vec![vec![false; num_cells.width]; num_cells.height]; 2]; |
|
102 |
||
103 |
for current_step in 0..num_steps { |
|
104 |
let x = random_numbers.next().unwrap_or_default() as usize % (seen_cells.width - 1) |
|
105 |
/ num_steps; |
|
106 |
last_cell[current_step] = Point::new( |
|
107 |
(x + current_step * seen_cells.width / num_steps) as i32, |
|
108 |
random_numbers.next().unwrap_or_default() as i32 % seen_cells.height as i32, |
|
109 |
); |
|
110 |
} |
|
111 |
||
112 |
Self { |
|
113 |
inverted, |
|
114 |
braidness, |
|
115 |
off_y: ((size.height - num_cells.height * cell_size) / 2) as i32, |
|
116 |
num_cells, |
|
117 |
num_edges, |
|
118 |
seen_cells, |
|
119 |
cell_size, |
|
120 |
seen_list, |
|
121 |
walls, |
|
122 |
edge_list, |
|
123 |
last_cell, |
|
124 |
came_from, |
|
125 |
came_from_pos, |
|
126 |
} |
|
127 |
} |
|
128 |
||
129 |
fn see_cell<I: Iterator<Item = u32>>( |
|
130 |
&mut self, |
|
131 |
current_step: usize, |
|
132 |
start_dir: Direction, |
|
133 |
random_numbers: &mut I, |
|
134 |
) -> bool { |
|
135 |
let mut dir = start_dir; |
|
136 |
loop { |
|
137 |
let p = self.last_cell[current_step]; |
|
138 |
self.seen_list[p.y as usize][p.x as usize] = Some(current_step); |
|
139 |
||
140 |
let next_dir_clockwise = random_numbers.next().unwrap_or_default() % 2 == 0; |
|
141 |
||
142 |
for _ in 0..5 { |
|
143 |
let sp = p + dir.0; |
|
144 |
let when_seen = if sp.x < 0 |
|
145 |
|| sp.x >= self.seen_cells.width as i32 |
|
146 |
|| sp.y < 0 |
|
147 |
|| sp.y >= self.seen_cells.height as i32 |
|
148 |
{ |
|
149 |
Some(current_step) |
|
150 |
} else { |
|
151 |
self.seen_list[sp.y as usize][sp.x as usize] |
|
152 |
}; |
|
153 |
||
154 |
match when_seen { |
|
155 |
Some(a) if a == current_step => { |
|
156 |
// try another direction |
|
157 |
if !self.inverted |
|
158 |
&& random_numbers.next().unwrap_or_default() % self.braidness == 0 |
|
159 |
{ |
|
160 |
if dir.0.x == -1 && p.x > 0 { |
|
161 |
self.walls[dir.orientation()][p.y as usize][p.x as usize - 1] = |
|
162 |
false; |
|
163 |
} |
|
164 |
if dir.0.x == 1 && p.x < self.seen_cells.width as i32 - 1 { |
|
165 |
self.walls[dir.orientation()][p.y as usize][p.x as usize] = false; |
|
166 |
} |
|
167 |
if dir.0.y == -1 && p.y > 0 { |
|
168 |
self.walls[dir.orientation()][p.y as usize - 1][p.x as usize] = |
|
169 |
false; |
|
170 |
} |
|
171 |
if dir.0.y == 1 && p.y < self.seen_cells.height as i32 - 1 { |
|
172 |
self.walls[dir.orientation()][p.y as usize][p.x as usize] = false; |
|
173 |
} |
|
174 |
} |
|
175 |
||
176 |
if next_dir_clockwise { |
|
177 |
dir = dir.rotate_right(); |
|
178 |
} else { |
|
179 |
dir = dir.rotate_left(); |
|
180 |
} |
|
181 |
} |
|
182 |
None => { |
|
183 |
// cell was not seen yet, go there |
|
184 |
let o_dir = dir.rotate_right().rotate_right(); |
|
185 |
let op = p - o_dir.to_edge().0; |
|
186 |
self.walls[o_dir.orientation()][op.y as usize][op.x as usize] = false; |
|
187 |
self.last_cell[current_step] = sp; |
|
188 |
self.came_from_pos[current_step] += 1; |
|
189 |
self.came_from[self.came_from_pos[current_step] as usize][current_step] = p; |
|
190 |
return false; |
|
191 |
} |
|
192 |
_ => { |
|
193 |
return true; |
|
194 |
} |
|
195 |
} |
|
196 |
} |
|
197 |
||
198 |
self.last_cell[current_step] = |
|
199 |
self.came_from[self.came_from_pos[current_step] as usize][current_step]; |
|
200 |
self.came_from_pos[current_step] -= 1; |
|
201 |
||
202 |
if self.came_from_pos[current_step] < 0 { |
|
203 |
return true; |
|
204 |
} |
|
205 |
} |
|
206 |
} |
|
207 |
||
208 |
fn add_vertex(&mut self, p: Point, polygon: &mut Vec<Point>) { |
|
209 |
let [x, y] = [p.x, p.y].map(|i| { |
|
210 |
if self.inverted || i & 1 == 0 { |
|
211 |
self.cell_size |
|
212 |
} else { |
|
213 |
self.cell_size * 2 / 3 |
|
214 |
} |
|
215 |
}); |
|
216 |
let new_point = Point::new( |
|
217 |
(p.x - 1) * self.cell_size as i32 + x as i32, |
|
218 |
(p.y - 1) * self.cell_size as i32 + y as i32 + self.off_y, |
|
219 |
); |
|
220 |
||
221 |
let nv = polygon.len(); |
|
222 |
if nv > 2 { |
|
223 |
if in_line(&polygon[nv - 2], &polygon[nv - 1], &new_point) { |
|
224 |
polygon.pop(); |
|
225 |
} |
|
226 |
} |
|
227 |
||
228 |
polygon.push(new_point); |
|
229 |
} |
|
230 |
||
231 |
fn add_edge(&mut self, p: Point, mut dir: Direction, polygon: &mut Vec<Point>) { |
|
232 |
let mut next_p = Some(p); |
|
233 |
||
234 |
while let Some(p) = next_p { |
|
235 |
next_p = None; |
|
236 |
||
237 |
for _ in 0..4 { |
|
238 |
let cdir = dir.to_edge(); |
|
239 |
||
240 |
let np = p + cdir.0; |
|
241 |
||
242 |
if np.x >= 0 |
|
243 |
&& np.y >= 0 |
|
244 |
&& np.x < self.num_cells.width as i32 |
|
245 |
&& np.y < self.num_cells.height as i32 |
|
246 |
&& self.edge_list[dir.orientation()][np.y as usize][np.x as usize] |
|
247 |
{ |
|
248 |
self.edge_list[dir.orientation()][np.y as usize][np.x as usize] = false; |
|
249 |
self.add_vertex(p + dir.0 + Point::new(1, 1), polygon); |
|
250 |
next_p = Some(p + dir.0); |
|
251 |
break; |
|
252 |
} |
|
253 |
||
254 |
dir = dir.rotate_right(); |
|
255 |
} |
|
256 |
} |
|
257 |
} |
|
258 |
||
259 |
pub fn to_islands(mut self) -> (Vec<Polygon>, Vec<Point>) { |
|
260 |
let mut islands: Vec<Polygon> = vec![]; |
|
261 |
let mut polygon: Vec<Point> = vec![]; |
|
262 |
let mut maze = vec![vec![false; self.num_cells.width]; self.num_cells.height]; |
|
263 |
||
264 |
for x in 0..self.seen_cells.width { |
|
265 |
for y in 0..self.seen_cells.height { |
|
266 |
if self.seen_list[y][x].is_some() { |
|
267 |
maze[y * 2 + 1][x * 2 + 1] = true; |
|
268 |
} |
|
269 |
} |
|
270 |
||
271 |
for y in 0..self.seen_cells.height - 1 { |
|
272 |
if !self.walls[0][y][x] { |
|
273 |
maze[y * 2 + 2][x * 2 + 1] = true; |
|
274 |
} |
|
275 |
} |
|
276 |
} |
|
277 |
||
278 |
for x in 0..self.seen_cells.width - 1 { |
|
279 |
for y in 0..self.seen_cells.height { |
|
280 |
if !self.walls[1][y][x] { |
|
281 |
maze[y * 2 + 1][x * 2 + 2] = true; |
|
282 |
} |
|
283 |
} |
|
284 |
} |
|
285 |
||
286 |
for x in 0..self.num_edges.width { |
|
287 |
for y in 0..self.num_cells.height { |
|
288 |
self.edge_list[0][y][x] = maze[y][x] != maze[y][x + 1]; |
|
289 |
} |
|
290 |
} |
|
291 |
||
292 |
for x in 0..self.num_cells.width { |
|
293 |
for y in 0..self.num_edges.height { |
|
294 |
self.edge_list[1][y][x] = maze[y][x] != maze[y + 1][x]; |
|
295 |
} |
|
296 |
} |
|
297 |
||
298 |
let mut fill_points = vec![]; |
|
299 |
||
300 |
for y in 0..self.num_cells.height { |
|
301 |
for x in 0..self.num_cells.width { |
|
302 |
if maze[y][x] { |
|
303 |
let half_cell = self.cell_size / 2; |
|
304 |
let fill_point = Point::new( |
|
305 |
(x * self.cell_size + half_cell) as i32, |
|
306 |
(y * self.cell_size + half_cell) as i32 + self.off_y, |
|
307 |
); |
|
308 |
islands.push(Polygon::new(&[fill_point])); |
|
309 |
fill_points.push(fill_point); |
|
310 |
} |
|
311 |
} |
|
312 |
} |
|
313 |
||
314 |
for x in 0..self.num_edges.width { |
|
315 |
for y in 0..self.num_cells.height { |
|
316 |
if self.edge_list[0][y][x] { |
|
317 |
self.edge_list[0][y][x] = false; |
|
318 |
self.add_vertex(Point::new(x as i32 + 1, y as i32 + 1), &mut polygon); |
|
319 |
self.add_vertex(Point::new(x as i32 + 1, y as i32), &mut polygon); |
|
320 |
self.add_edge( |
|
321 |
Point::new(x as i32, y as i32 - 1), |
|
322 |
Direction::new(0), |
|
323 |
&mut polygon, |
|
324 |
); |
|
325 |
||
326 |
if polygon.len() > 4 { |
|
327 |
if in_line(polygon.last().unwrap(), &polygon[0], &polygon[1]) { |
|
328 |
polygon.pop(); |
|
329 |
} |
|
330 |
||
331 |
/* |
|
332 |
for p in &polygon { |
|
333 |
println!("{} {}", p.x, p.y); |
|
334 |
} |
|
335 |
println!("\ne\n"); |
|
336 |
*/ |
|
337 |
||
338 |
islands.push(Polygon::new(&polygon)); |
|
339 |
} |
|
340 |
polygon.clear(); |
|
341 |
} |
|
342 |
} |
|
343 |
} |
|
344 |
||
345 |
(islands, fill_points) |
|
346 |
} |
|
16032 | 347 |
} |
348 |
||
349 |
pub struct MazeLandGenerator { |
|
350 |
maze_template: MazeTemplate, |
|
351 |
} |
|
352 |
||
353 |
fn prev_odd(num: usize) -> usize { |
|
354 |
if num & 1 == 0 { |
|
355 |
num - 1 |
|
356 |
} else { |
|
357 |
num |
|
358 |
} |
|
359 |
} |
|
360 |
||
361 |
impl MazeLandGenerator { |
|
362 |
pub fn new(maze_template: MazeTemplate) -> Self { |
|
363 |
Self { maze_template } |
|
364 |
} |
|
365 |
||
366 |
fn generate_outline<I: Iterator<Item = u32>>( |
|
367 |
&self, |
|
368 |
size: &Size, |
|
369 |
play_box: Rect, |
|
370 |
intersections_box: Rect, |
|
371 |
random_numbers: &mut I, |
|
372 |
) -> OutlinePoints { |
|
373 |
let num_steps = if self.maze_template.inverted { 3 } else { 1 }; |
|
374 |
let mut step_done = vec![false; num_steps]; |
|
375 |
let mut done = false; |
|
376 |
||
16034 | 377 |
let mut maze = Maze::new( |
378 |
&size, |
|
379 |
self.maze_template.cell_size, |
|
380 |
num_steps, |
|
381 |
self.maze_template.inverted, |
|
382 |
self.maze_template.braidness, |
|
383 |
random_numbers, |
|
384 |
); |
|
16032 | 385 |
|
386 |
while !done { |
|
387 |
done = true; |
|
388 |
||
389 |
for current_step in 0..num_steps { |
|
390 |
if !step_done[current_step] { |
|
16034 | 391 |
let dir = Direction::new(random_numbers.next().unwrap_or_default() as usize); |
392 |
step_done[current_step] = maze.see_cell(current_step, dir, random_numbers); |
|
16032 | 393 |
done = false; |
394 |
} |
|
395 |
} |
|
396 |
} |
|
397 |
||
16034 | 398 |
let (islands, fill_points) = maze.to_islands(); |
16032 | 399 |
|
400 |
OutlinePoints { |
|
401 |
islands, |
|
16034 | 402 |
fill_points, |
16032 | 403 |
size: *size, |
404 |
play_box, |
|
405 |
intersections_box, |
|
406 |
} |
|
407 |
} |
|
408 |
} |
|
409 |
||
410 |
impl LandGenerator for MazeLandGenerator { |
|
411 |
fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>( |
|
412 |
&self, |
|
413 |
parameters: &LandGenerationParameters<T>, |
|
414 |
random_numbers: &mut I, |
|
415 |
) -> Land2D<T> { |
|
16034 | 416 |
let do_invert = self.maze_template.inverted; |
16032 | 417 |
let (basic, zero) = if do_invert { |
418 |
(parameters.zero, parameters.basic) |
|
419 |
} else { |
|
420 |
(parameters.basic, parameters.zero) |
|
421 |
}; |
|
422 |
||
423 |
let land_size = Size::new(self.maze_template.width, self.maze_template.height); |
|
424 |
let mut land = Land2D::new(&land_size, basic); |
|
425 |
||
426 |
let mut points = self.generate_outline( |
|
427 |
&land.size().size(), |
|
16034 | 428 |
land.play_box(), //??? Rect::at_origin(land_size).with_margin(land_size.to_square().width as i32 * -2), |
16032 | 429 |
land.play_box(), |
430 |
random_numbers, |
|
431 |
); |
|
432 |
||
433 |
if !parameters.skip_distort { |
|
434 |
points.distort(parameters.distance_divisor, random_numbers); |
|
435 |
} |
|
436 |
||
437 |
if !parameters.skip_bezier { |
|
438 |
points.bezierize(5); |
|
439 |
} |
|
440 |
||
441 |
points.draw(&mut land, zero); |
|
442 |
||
443 |
for p in &points.fill_points { |
|
444 |
land.fill(*p, zero, zero) |
|
445 |
} |
|
446 |
||
447 |
land |
|
448 |
} |
|
449 |
} |