--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/landgen/src/maze.rs Tue Sep 10 13:56:51 2024 +0200
@@ -0,0 +1,329 @@
+use crate::outline_template_based::outline::OutlinePoints;
+use crate::{LandGenerationParameters, LandGenerator};
+use integral_geometry::{Point, Polygon, Rect, Size};
+use land2d::Land2D;
+
+pub struct MazeTemplate {
+ width: usize,
+ height: usize,
+ cell_size: usize,
+ inverted: bool,
+ distortion_limiting_factor: u32,
+ braidness: usize,
+}
+
+pub struct MazeLandGenerator {
+ maze_template: MazeTemplate,
+}
+
+fn prev_odd(num: usize) -> usize {
+ if num & 1 == 0 {
+ num - 1
+ } else {
+ num
+ }
+}
+
+impl MazeLandGenerator {
+ pub fn new(maze_template: MazeTemplate) -> Self {
+ Self { maze_template }
+ }
+
+ fn generate_outline<I: Iterator<Item = u32>>(
+ &self,
+ size: &Size,
+ play_box: Rect,
+ intersections_box: Rect,
+ random_numbers: &mut I,
+ ) -> OutlinePoints {
+ let num_cells = Size::new(
+ prev_odd(size.width / self.maze_template.cell_size),
+ prev_odd(size.height / self.maze_template.cell_size),
+ );
+
+ let num_edges = Size::new(num_cells.width - 1, num_cells.height - 1);
+ let seen_cells = Size::new(num_cells.width / 2, num_cells.height / 2);
+
+ let num_steps = if self.maze_template.inverted { 3 } else { 1 };
+ let mut step_done = vec![false; num_steps];
+ let mut last_cell = vec![Point::diag(0); num_steps];
+ let mut came_from_pos = vec![0; num_steps];
+ let mut came_from = vec![vec![Point::diag(0); num_cells.area()]; num_steps];
+
+ let mut done = false;
+ let mut seen_list = vec![vec![None as Option<usize>; seen_cells.width]; seen_cells.height];
+ let mut x_walls = vec![vec![true; seen_cells.width]; seen_cells.height - 1];
+ let mut y_walls = vec![vec![true; seen_cells.width - 1]; seen_cells.height];
+ let mut x_edge_list = vec![vec![false; num_edges.width]; num_cells.height];
+ let mut y_edge_list = vec![vec![false; num_cells.width]; num_edges.height];
+
+ let mut maze = vec![vec![false; num_cells.width]; num_cells.height];
+
+ let off_y = 0;
+
+ for current_step in 0..num_steps {
+ let x = random_numbers.next().unwrap_or_default() as usize % (seen_cells.width - 1)
+ / num_steps;
+ last_cell[current_step] = Point::new(
+ (x + current_step * seen_cells.width / num_steps) as i32,
+ random_numbers.next().unwrap_or_default() as i32 / num_steps as i32,
+ );
+ }
+
+ let see_cell = |current_step: usize, start_dir: Point, seen_list: &mut Vec<Vec<Option<usize>>>, x_walls: &mut Vec<Vec<bool>>, y_walls: &mut Vec<Vec<bool>>,
+ last_cell: &mut Vec<Point>, came_from: &mut Vec<Vec<Point>>, came_from_pos: &mut Vec<i32>| {
+ loop {
+ let p = last_cell[current_step];
+ seen_list[p.y as usize][p.x as usize] = Some(current_step);
+
+ let mut dir = start_dir;
+
+ let next_dir_clockwise = true;//random_numbers.next().unwrap_or_default() % 2 == 0;
+
+ for _ in 0..5 {
+ let sp = p + dir;
+ let when_seen =
+ if sp.x < 0
+ || sp.x >= seen_cells.width as i32
+ || sp.y < 0
+ || sp.y >= seen_cells.height as i32
+ {
+ None
+ } else {
+ Some(seen_list[sp.y as usize][sp.x as usize])
+ }
+ ;
+
+ match when_seen {
+ None => {
+ // try another direction
+ if dir.x == -1 && p.x > 0 {
+ y_walls[p.y as usize][p.x as usize - 1] = false;
+ }
+ if dir.x == 1 && p.x < seen_cells.width as i32 - 1 {
+ y_walls[p.y as usize][p.x as usize] = false;
+ }
+ if dir.y == -1 && p.y > 0 {
+ x_walls[p.y as usize][p.x as usize] = false;
+ }
+ if dir.y == 1 && p.y < seen_cells.height as i32 - 1 {
+ x_walls[p.y as usize][p.x as usize] = false;
+ }
+
+ if next_dir_clockwise {
+ dir = dir.rotate90();
+ } else {
+ dir = dir.rotate270();
+ }
+ }
+ Some(None) => {
+ // cell was not seen yet, go there
+ if dir.y == -1 {
+ x_walls[p.y as usize - 1][p.x as usize] = false;
+ }
+ if dir.y == 1 {
+ x_walls[p.y as usize][p.x as usize] = false;
+ }
+ if dir.x == -1 {
+ y_walls[p.y as usize][p.x as usize - 1] = false;
+ }
+ if dir.x == 1 {
+ y_walls[p.y as usize][p.x as usize] = false;
+ }
+ last_cell[current_step] = p + dir;
+ came_from_pos[current_step] += 1;
+ came_from[came_from_pos[current_step] as usize][current_step] = p;
+ }
+ _ => {
+ return true;
+ }
+ }
+ }
+
+ last_cell[current_step] = came_from[came_from_pos[current_step] as usize][current_step];
+ came_from_pos[current_step] -= 1;
+
+ return came_from_pos[current_step] < 0;
+ }
+ };
+
+ let mut islands: Vec<Polygon> = vec![];
+ let mut polygon: Vec<Point> = vec![];
+ let add_vertex = |p: Point, polygon: &mut Vec<Point>| {
+ let cell_size = self.maze_template.cell_size as i32;
+ let [x, y] = [p.x, p.y].map(|i| {
+ if self.maze_template.inverted || i & 1 == 0 {
+ cell_size
+ } else {
+ cell_size * 2 / 3
+ }
+ });
+ let new_point =
+ Point::new((p.x - 1) * cell_size + x, (p.y - 1) * cell_size + y + off_y);
+
+ let nv = polygon.len();
+ if nv > 2 {
+ if polygon[nv - 2].x == polygon[nv - 1].x && polygon[nv - 1].x == new_point.x
+ || polygon[nv - 2].y == polygon[nv - 1].y && polygon[nv - 1].y == new_point.y
+ {
+ polygon.pop();
+ }
+ }
+
+ polygon.push(new_point);
+ };
+
+ let add_edge = |p: Point, dir: Point, polygon: &mut Vec<Point>, x_edge_list: &mut Vec<Vec<bool>>, y_edge_list: &mut Vec<Vec<bool>>| {
+ let mut dir = dir.rotate270();
+ let mut next_p = Some(p);
+
+ while let Some(p) = next_p {
+ next_p = None;
+
+ for _ in 0..4 {
+ dir = dir.rotate90();
+ let cdir = Point::new(
+ if dir.x < 0 { 0 } else { dir.x },
+ if dir.y < 0 { 0 } else { dir.y },
+ );
+
+ let np = p + cdir;
+ let edge_list = if dir.x == 0 {
+ &mut *x_edge_list
+ } else {
+ &mut *y_edge_list
+ };
+ if np.x >= 0
+ && np.y > 0
+ && np.x < num_cells.width as i32
+ && np.y < num_cells.height as i32
+ && edge_list[np.y as usize][np.x as usize]
+ {
+ (*edge_list)[np.y as usize][np.x as usize] = false;
+ add_vertex(p + dir + Point::new(1, 1), polygon);
+ next_p = Some(p + dir);
+ break;
+ }
+ }
+ }
+ };
+
+ while !done {
+ done = true;
+
+ for current_step in 0..num_steps {
+ if !step_done[current_step] {
+ let dir = match random_numbers.next().unwrap_or_default() % 4 {
+ 0 => Point::new(0, -1),
+ 1 => Point::new(1, 0),
+ 2 => Point::new(0, 1),
+ 3 => Point::new(-1, 0),
+ _ => panic!(),
+ };
+ step_done[current_step] =
+ see_cell(current_step, dir, &mut seen_list, &mut x_walls, &mut y_walls, &mut last_cell, &mut came_from, &mut came_from_pos);
+ done = false;
+ }
+ }
+ }
+
+ for x in 0..seen_cells.width {
+ for y in 0..seen_cells.height {
+ if seen_list[y][x].is_some() {
+ maze[y * 2 + 1][x * 2 + 1] = true;
+ }
+ }
+
+ for y in 0..seen_cells.height - 1 {
+ if !x_walls[y][x] {
+ maze[y * 2 + 2][x * 2 + 1] = true;
+ }
+ }
+ }
+
+ for x in 0..seen_cells.width - 1 {
+ for y in 0..seen_cells.height {
+ if !y_walls[y][x] {
+ maze[y * 2 + 1][x * 2 + 2] = true;
+ }
+ }
+ }
+
+ for x in 0..num_edges.width {
+ for y in 0..num_cells.height {
+ x_edge_list[y][x] = maze[y][x] != maze[y][x + 1];
+ }
+ }
+
+ for x in 0..num_cells.width {
+ for y in 0..num_edges.height {
+ y_edge_list[y][x] = maze[y][x] != maze[y + 1][x];
+ }
+ }
+
+ for x in 0..num_edges.width {
+ for y in 0..num_cells.height {
+ if x_edge_list[y][x] {
+ x_edge_list[y][x] = false;
+ add_vertex(Point::new(x as i32 + 1, y as i32 + 1), &mut polygon);
+ add_vertex(Point::new(x as i32 + 1, y as i32), &mut polygon);
+ add_edge(Point::new(x as i32, y as i32 - 1), Point::new(0, -1), &mut polygon, &mut x_edge_list, &mut y_edge_list);
+
+ islands.push(Polygon::new(&polygon));
+ polygon.clear();
+ }
+ }
+ }
+
+ OutlinePoints {
+ islands,
+ fill_points: vec![],
+ size: *size,
+ play_box,
+ intersections_box,
+ }
+ }
+}
+
+impl LandGenerator for MazeLandGenerator {
+ fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
+ &self,
+ parameters: &LandGenerationParameters<T>,
+ random_numbers: &mut I,
+ ) -> Land2D<T> {
+ let do_invert = false;
+ let (basic, zero) = if do_invert {
+ (parameters.zero, parameters.basic)
+ } else {
+ (parameters.basic, parameters.zero)
+ };
+
+ let land_size = Size::new(self.maze_template.width, self.maze_template.height);
+ let mut land = Land2D::new(&land_size, basic);
+
+ let mut points = self.generate_outline(
+ &land.size().size(),
+ Rect::at_origin(land_size).with_margin(land_size.to_square().width as i32 * -2),
+ land.play_box(),
+ random_numbers,
+ );
+
+ if !parameters.skip_distort {
+ points.distort(parameters.distance_divisor, random_numbers);
+ }
+
+ if !parameters.skip_bezier {
+ points.bezierize(5);
+ }
+
+ points.draw(&mut land, zero);
+
+ for p in &points.fill_points {
+ land.fill(*p, zero, zero)
+ }
+
+ points.draw(&mut land, basic);
+
+ land
+ }
+}