hedgewars: comparison rust/landgen/src/maze.rs

equal deleted inserted replaced

-:1860852892c0
+:09beeec033ba
 pub width: usize,
 pub height: usize,
 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 {
 maze_template: MazeTemplate,
 }
 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_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 maze = Maze::new(
-let mut y_walls = vec![vec![true; seen_cells.width - 1]; seen_cells.height];
+&size,
-let mut x_edge_list = vec![vec![false; num_edges.width]; num_cells.height];
+self.maze_template.cell_size,
-let mut y_edge_list = vec![vec![false; num_cells.width]; num_edges.height];
+num_steps,
+self.maze_template.inverted,
-let mut maze = vec![vec![false; num_cells.width]; num_cells.height];
+self.maze_template.braidness,
+random_numbers,
-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;
-}
-}
-}
-};
 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 {
+let dir = Direction::new(random_numbers.next().unwrap_or_default() as usize);
-0 => Point::new(0, -1),
+step_done[current_step] = maze.see_cell(current_step, dir, random_numbers);
-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 {
+let (islands, fill_points) = maze.to_islands();
-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![Point::new(1, 1 + off_y)],
+fill_points,
 size: *size,
 play_box,
 intersections_box,
 }
 }
 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 do_invert = self.maze_template.inverted;
 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(), //??? Rect::at_origin(land_size).with_margin(land_size.to_square().width as i32 * -2),
 land.play_box(),
 random_numbers,
 );
 if !parameters.skip_distort {
 for p in &points.fill_points {
 land.fill(*p, zero, zero)
 }
-points.draw(&mut land, basic);
 land
 }
 }

branch	transitional_engine
changeset 16034	09beeec033ba
parent 16033	1860852892c0
child 16035	0caa3dfb3ba2