--- a/rust/landgen/src/maze.rs Tue Sep 10 18:21:31 2024 +0200
+++ b/rust/landgen/src/maze.rs Mon Sep 16 16:57:11 2024 +0200
@@ -9,7 +9,341 @@
pub cell_size: usize,
pub inverted: bool,
pub distortion_limiting_factor: u32,
- pub braidness: usize,
+ pub braidness: u32,
+}
+
+struct Maze {
+ inverted: bool,
+ braidness: u32,
+ off_y: i32,
+ num_cells: Size,
+ num_edges: Size,
+ seen_cells: Size,
+ cell_size: usize,
+ seen_list: Vec<Vec<Option<usize>>>,
+ walls: Vec<Vec<Vec<bool>>>,
+ edge_list: Vec<Vec<Vec<bool>>>,
+ last_cell: Vec<Point>,
+ came_from: Vec<Vec<Point>>,
+ came_from_pos: Vec<i32>,
+}
+
+fn in_line(p1: &Point, p2: &Point, p3: &Point) -> bool {
+ p1.x == p2.x && p2.x == p3.x || p1.y == p2.y && p2.y == p3.y
+}
+
+#[derive(Clone, Copy)]
+struct Direction(Point);
+
+impl Direction {
+ #[inline]
+ pub fn new(direction: usize) -> Self {
+ match direction % 4 {
+ 0 => Self(Point::new(0, -1)),
+ 1 => Self(Point::new(1, 0)),
+ 2 => Self(Point::new(0, 1)),
+ 3 => Self(Point::new(-1, 0)),
+ _ => panic!("Impossible"),
+ }
+ }
+
+ #[inline]
+ pub fn rotate_right(self) -> Self {
+ Self(self.0.rotate90())
+ }
+
+ #[inline]
+ pub fn rotate_left(self) -> Self {
+ Self(self.0.rotate270())
+ }
+
+ #[inline]
+ pub fn to_edge(self) -> Self {
+ Self(Point::new(
+ if self.0.x < 0 { 0 } else { self.0.x },
+ if self.0.y < 0 { 0 } else { self.0.y },
+ ))
+ }
+
+ #[inline]
+ pub fn orientation(&self) -> usize {
+ if self.0.x == 0 {
+ 0
+ } else {
+ 1
+ }
+ }
+}
+
+impl Maze {
+ pub fn new<I: Iterator<Item = u32>>(
+ size: &Size,
+ cell_size: usize,
+ num_steps: usize,
+ inverted: bool,
+ braidness: u32,
+ random_numbers: &mut I,
+ ) -> Self {
+ let num_cells = Size::new(
+ prev_odd(size.width / cell_size),
+ prev_odd(size.height / 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 mut last_cell = vec![Point::diag(0); num_steps];
+ let came_from_pos = vec![0; num_steps];
+ let came_from = vec![vec![Point::diag(0); num_steps]; num_cells.area()];
+
+ let seen_list = vec![vec![None as Option<usize>; seen_cells.width]; seen_cells.height];
+ let walls = vec![vec![vec![true; seen_cells.width]; seen_cells.height]; 2];
+ let edge_list = vec![vec![vec![false; num_cells.width]; num_cells.height]; 2];
+
+ 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 % seen_cells.height as i32,
+ );
+ }
+
+ Self {
+ inverted,
+ braidness,
+ off_y: ((size.height - num_cells.height * cell_size) / 2) as i32,
+ num_cells,
+ num_edges,
+ seen_cells,
+ cell_size,
+ seen_list,
+ walls,
+ edge_list,
+ last_cell,
+ came_from,
+ came_from_pos,
+ }
+ }
+
+ fn see_cell<I: Iterator<Item = u32>>(
+ &mut self,
+ current_step: usize,
+ start_dir: Direction,
+ random_numbers: &mut I,
+ ) -> bool {
+ let mut dir = start_dir;
+ loop {
+ let p = self.last_cell[current_step];
+ self.seen_list[p.y as usize][p.x as usize] = Some(current_step);
+
+ let next_dir_clockwise = random_numbers.next().unwrap_or_default() % 2 == 0;
+
+ for _ in 0..5 {
+ let sp = p + dir.0;
+ let when_seen = if sp.x < 0
+ || sp.x >= self.seen_cells.width as i32
+ || sp.y < 0
+ || sp.y >= self.seen_cells.height as i32
+ {
+ Some(current_step)
+ } else {
+ self.seen_list[sp.y as usize][sp.x as usize]
+ };
+
+ match when_seen {
+ Some(a) if a == current_step => {
+ // try another direction
+ if !self.inverted
+ && random_numbers.next().unwrap_or_default() % self.braidness == 0
+ {
+ if dir.0.x == -1 && p.x > 0 {
+ self.walls[dir.orientation()][p.y as usize][p.x as usize - 1] =
+ false;
+ }
+ if dir.0.x == 1 && p.x < self.seen_cells.width as i32 - 1 {
+ self.walls[dir.orientation()][p.y as usize][p.x as usize] = false;
+ }
+ if dir.0.y == -1 && p.y > 0 {
+ self.walls[dir.orientation()][p.y as usize - 1][p.x as usize] =
+ false;
+ }
+ if dir.0.y == 1 && p.y < self.seen_cells.height as i32 - 1 {
+ self.walls[dir.orientation()][p.y as usize][p.x as usize] = false;
+ }
+ }
+
+ if next_dir_clockwise {
+ dir = dir.rotate_right();
+ } else {
+ dir = dir.rotate_left();
+ }
+ }
+ None => {
+ // cell was not seen yet, go there
+ let o_dir = dir.rotate_right().rotate_right();
+ let op = p - o_dir.to_edge().0;
+ self.walls[o_dir.orientation()][op.y as usize][op.x as usize] = false;
+ self.last_cell[current_step] = sp;
+ self.came_from_pos[current_step] += 1;
+ self.came_from[self.came_from_pos[current_step] as usize][current_step] = p;
+ return false;
+ }
+ _ => {
+ return true;
+ }
+ }
+ }
+
+ self.last_cell[current_step] =
+ self.came_from[self.came_from_pos[current_step] as usize][current_step];
+ self.came_from_pos[current_step] -= 1;
+
+ if self.came_from_pos[current_step] < 0 {
+ return true;
+ }
+ }
+ }
+
+ fn add_vertex(&mut self, p: Point, polygon: &mut Vec<Point>) {
+ let [x, y] = [p.x, p.y].map(|i| {
+ if self.inverted || i & 1 == 0 {
+ self.cell_size
+ } else {
+ self.cell_size * 2 / 3
+ }
+ });
+ let new_point = Point::new(
+ (p.x - 1) * self.cell_size as i32 + x as i32,
+ (p.y - 1) * self.cell_size as i32 + y as i32 + self.off_y,
+ );
+
+ let nv = polygon.len();
+ if nv > 2 {
+ if in_line(&polygon[nv - 2], &polygon[nv - 1], &new_point) {
+ polygon.pop();
+ }
+ }
+
+ polygon.push(new_point);
+ }
+
+ fn add_edge(&mut self, p: Point, mut dir: Direction, polygon: &mut Vec<Point>) {
+ let mut next_p = Some(p);
+
+ while let Some(p) = next_p {
+ next_p = None;
+
+ for _ in 0..4 {
+ let cdir = dir.to_edge();
+
+ let np = p + cdir.0;
+
+ if np.x >= 0
+ && np.y >= 0
+ && np.x < self.num_cells.width as i32
+ && np.y < self.num_cells.height as i32
+ && self.edge_list[dir.orientation()][np.y as usize][np.x as usize]
+ {
+ self.edge_list[dir.orientation()][np.y as usize][np.x as usize] = false;
+ self.add_vertex(p + dir.0 + Point::new(1, 1), polygon);
+ next_p = Some(p + dir.0);
+ break;
+ }
+
+ dir = dir.rotate_right();
+ }
+ }
+ }
+
+ pub fn to_islands(mut self) -> (Vec<Polygon>, Vec<Point>) {
+ let mut islands: Vec<Polygon> = vec![];
+ let mut polygon: Vec<Point> = vec![];
+ let mut maze = vec![vec![false; self.num_cells.width]; self.num_cells.height];
+
+ for x in 0..self.seen_cells.width {
+ for y in 0..self.seen_cells.height {
+ if self.seen_list[y][x].is_some() {
+ maze[y * 2 + 1][x * 2 + 1] = true;
+ }
+ }
+
+ for y in 0..self.seen_cells.height - 1 {
+ if !self.walls[0][y][x] {
+ maze[y * 2 + 2][x * 2 + 1] = true;
+ }
+ }
+ }
+
+ for x in 0..self.seen_cells.width - 1 {
+ for y in 0..self.seen_cells.height {
+ if !self.walls[1][y][x] {
+ maze[y * 2 + 1][x * 2 + 2] = true;
+ }
+ }
+ }
+
+ for x in 0..self.num_edges.width {
+ for y in 0..self.num_cells.height {
+ self.edge_list[0][y][x] = maze[y][x] != maze[y][x + 1];
+ }
+ }
+
+ for x in 0..self.num_cells.width {
+ for y in 0..self.num_edges.height {
+ self.edge_list[1][y][x] = maze[y][x] != maze[y + 1][x];
+ }
+ }
+
+ let mut fill_points = vec![];
+
+ for y in 0..self.num_cells.height {
+ for x in 0..self.num_cells.width {
+ if maze[y][x] {
+ let half_cell = self.cell_size / 2;
+ let fill_point = Point::new(
+ (x * self.cell_size + half_cell) as i32,
+ (y * self.cell_size + half_cell) as i32 + self.off_y,
+ );
+ islands.push(Polygon::new(&[fill_point]));
+ fill_points.push(fill_point);
+ }
+ }
+ }
+
+ for x in 0..self.num_edges.width {
+ for y in 0..self.num_cells.height {
+ if self.edge_list[0][y][x] {
+ self.edge_list[0][y][x] = false;
+ self.add_vertex(Point::new(x as i32 + 1, y as i32 + 1), &mut polygon);
+ self.add_vertex(Point::new(x as i32 + 1, y as i32), &mut polygon);
+ self.add_edge(
+ Point::new(x as i32, y as i32 - 1),
+ Direction::new(0),
+ &mut polygon,
+ );
+
+ if polygon.len() > 4 {
+ if in_line(polygon.last().unwrap(), &polygon[0], &polygon[1]) {
+ polygon.pop();
+ }
+
+ /*
+ for p in &polygon {
+ println!("{} {}", p.x, p.y);
+ }
+ println!("\ne\n");
+ */
+
+ islands.push(Polygon::new(&polygon));
+ }
+ polygon.clear();
+ }
+ }
+ }
+
+ (islands, fill_points)
+ }
}
pub struct MazeLandGenerator {
@@ -36,248 +370,36 @@
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_steps]; num_cells.area()];
-
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 % seen_cells.height 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>| {
- let mut dir = start_dir;
- loop {
- let p = dbg!(last_cell[current_step]);
- seen_list[p.y as usize][p.x as usize] = Some(dbg!(current_step));
-
- let next_dir_clockwise = true;//random_numbers.next().unwrap_or_default() % 2 == 0;
-
- for _ in 0..5 {
- let sp = dbg!(p) + dbg!(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] = dbg!(sp);
- came_from_pos[current_step] += 1;
- came_from[came_from_pos[current_step] as usize][current_step] = p;
- return true;
- }
- _ => {
- 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;
- }
- }
- }
- };
+ let mut maze = Maze::new(
+ &size,
+ self.maze_template.cell_size,
+ num_steps,
+ self.maze_template.inverted,
+ self.maze_template.braidness,
+ random_numbers,
+ );
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);
+ let dir = Direction::new(random_numbers.next().unwrap_or_default() as usize);
+ step_done[current_step] = maze.see_cell(current_step, dir, random_numbers);
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();
- }
- }
- }
+ let (islands, fill_points) = maze.to_islands();
OutlinePoints {
islands,
- fill_points: vec![Point::new(1, 1 + off_y)],
+ fill_points,
size: *size,
play_box,
intersections_box,
@@ -291,7 +413,7 @@
parameters: &LandGenerationParameters<T>,
random_numbers: &mut I,
) -> Land2D<T> {
- let do_invert = false;
+ let do_invert = self.maze_template.inverted;
let (basic, zero) = if do_invert {
(parameters.zero, parameters.basic)
} else {
@@ -303,7 +425,7 @@
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(), //??? Rect::at_origin(land_size).with_margin(land_size.to_square().width as i32 * -2),
land.play_box(),
random_numbers,
);
@@ -322,8 +444,6 @@
land.fill(*p, zero, zero)
}
- points.draw(&mut land, basic);
-
land
}
}