# HG changeset patch
# User unC0Rr
# Date 1725969411 -7200
# Node ID 31cc1e45027344efc77346a2a7aee194ebbbb000
# Parent  1b1d5729ff3e211b6a6466b6fc3694091887737b
Add maze land generator ported from pascal engine

diff -r 1b1d5729ff3e -r 31cc1e450273 rust/integral-geometry/src/lib.rs
--- a/rust/integral-geometry/src/lib.rs	Wed Sep 04 14:54:34 2024 +0200
+++ b/rust/integral-geometry/src/lib.rs	Tue Sep 10 13:56:51 2024 +0200
@@ -61,6 +61,14 @@
     pub const fn rotate90(self) -> Self {
         Self::new(self.y, -self.x)
     }
+    #[inline]
+    pub const fn rotate180(self) -> Self {
+        Self::new(-self.x, -self.y)
+    }
+    #[inline]
+    pub const fn rotate270(self) -> Self {
+        Self::new(-self.y, self.x)
+    }
 
     #[inline]
     pub const fn cross(self, other: Point) -> i32 {
diff -r 1b1d5729ff3e -r 31cc1e450273 rust/landgen/src/lib.rs
--- a/rust/landgen/src/lib.rs	Wed Sep 04 14:54:34 2024 +0200
+++ b/rust/landgen/src/lib.rs	Tue Sep 10 13:56:51 2024 +0200
@@ -1,3 +1,4 @@
+pub mod maze;
 pub mod outline_template_based;
 pub mod wavefront_collapse;
 
diff -r 1b1d5729ff3e -r 31cc1e450273 rust/landgen/src/maze.rs
--- /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
+    }
+}
diff -r 1b1d5729ff3e -r 31cc1e450273 rust/landgen/src/outline_template_based/mod.rs
--- a/rust/landgen/src/outline_template_based/mod.rs	Wed Sep 04 14:54:34 2024 +0200
+++ b/rust/landgen/src/outline_template_based/mod.rs	Tue Sep 10 13:56:51 2024 +0200
@@ -1,3 +1,3 @@
-mod outline;
+pub mod outline;
 pub mod outline_template;
 pub mod template_based;
diff -r 1b1d5729ff3e -r 31cc1e450273 rust/landgen/src/outline_template_based/outline.rs
--- a/rust/landgen/src/outline_template_based/outline.rs	Wed Sep 04 14:54:34 2024 +0200
+++ b/rust/landgen/src/outline_template_based/outline.rs	Tue Sep 10 13:56:51 2024 +0200
@@ -11,7 +11,7 @@
     pub fill_points: Vec<Point>,
     pub size: Size,
     pub play_box: Rect,
-    intersections_box: Rect,
+    pub intersections_box: Rect,
 }
 
 impl OutlinePoints {
@@ -65,7 +65,7 @@
         &self,
         segment: Line,
         distance_divisor: u32,
-        distance_limiting_factor: u32,
+        distortion_limiting_factor: u32,
         random_numbers: &mut I,
     ) -> Option<Point> {
         #[inline]
@@ -226,7 +226,7 @@
             }
         }
 
-        let max_dist = normal_len * 128 / distance_limiting_factor;
+        let max_dist = normal_len * 128 / distortion_limiting_factor;
         dist_left = min(dist_left, max_dist);
         dist_right = min(dist_right, max_dist);
 
@@ -247,7 +247,7 @@
     fn divide_edges<I: Iterator<Item = u32>>(
         &mut self,
         distance_divisor: u32,
-        distance_limiting_factor: u32,
+        distortion_limiting_factor: u32,
         random_numbers: &mut I,
     ) {
         for is in 0..self.islands.len() {
@@ -257,7 +257,7 @@
                 if let Some(new_point) = self.divide_edge(
                     segment,
                     distance_divisor,
-                    distance_limiting_factor,
+                    distortion_limiting_factor,
                     random_numbers,
                 ) {
                     self.islands[is].split_edge(i, new_point);
@@ -280,11 +280,11 @@
         distance_divisor: u32,
         random_numbers: &mut I,
     ) {
-        let distance_limiting_factor = 100 + random_numbers.next().unwrap() as u32 % 8 * 10;
+        let distortion_limiting_factor = 100 + random_numbers.next().unwrap() as u32 % 8 * 10;
 
         loop {
             let old_len = self.total_len();
-            self.divide_edges(distance_divisor, distance_limiting_factor, random_numbers);
+            self.divide_edges(distance_divisor, distortion_limiting_factor, random_numbers);
 
             if self.total_len() == old_len {
                 break;
diff -r 1b1d5729ff3e -r 31cc1e450273 rust/mapgen/src/lib.rs
--- a/rust/mapgen/src/lib.rs	Wed Sep 04 14:54:34 2024 +0200
+++ b/rust/mapgen/src/lib.rs	Tue Sep 10 13:56:51 2024 +0200
@@ -14,6 +14,7 @@
     wavefront_collapse::generator::{
         TemplateDescription as WfcTemplate, WavefrontCollapseLandGenerator,
     },
+    maze::{MazeTemplate, MazeLandGenerator},
     LandGenerationParameters, LandGenerator,
 };
 use rand::{seq::SliceRandom, Rng};
@@ -176,6 +177,27 @@
     }
 }
 
+impl MapGenerator<MazeTemplate> {
+    pub fn import_yaml_templates(&mut self, text: &str) {
+        let mut desc: MazeTemplateCollectionDesc = serde_yaml::from_str(text).unwrap();
+        let templates = std::mem::take(&mut desc.templates);
+        self.templates = desc
+            .template_types
+            .into_iter()
+            .map(|(size, indices)| {
+                (
+                    TemplateType(size),
+                    indices.iter().map(|i| (&templates[*i]).into()).collect(),
+                )
+            })
+            .collect();
+    }
+
+    pub fn build_generator(&self, template: MazeTemplate) -> impl LandGenerator {
+        MazeLandGenerator::new(template)
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
 struct Color(u32);