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 {

     7     width: usize,

     8     height: usize,

     9     cell_size: usize,

    10     inverted: bool,

    11     distortion_limiting_factor: u32,

    12     braidness: usize,

    13 }

    14 

    15 pub struct MazeLandGenerator {

    16     maze_template: MazeTemplate,

    17 }

    18 

    19 fn prev_odd(num: usize) -> usize {

    20     if num & 1 == 0 {

    21         num - 1

    22     } else {

    23         num

    24     }

    25 }

    26 

    27 impl MazeLandGenerator {

    28     pub fn new(maze_template: MazeTemplate) -> Self {

    29         Self { maze_template }

    30     }

    31 

    32     fn generate_outline<I: Iterator<Item = u32>>(

    33         &self,

    34         size: &Size,

    35         play_box: Rect,

    36         intersections_box: Rect,

    37         random_numbers: &mut I,

    38     ) -> OutlinePoints {

    39         let num_cells = Size::new(

    40             prev_odd(size.width / self.maze_template.cell_size),

    41             prev_odd(size.height / self.maze_template.cell_size),

    42         );

    43 

    44         let num_edges = Size::new(num_cells.width - 1, num_cells.height - 1);

    45         let seen_cells = Size::new(num_cells.width / 2, num_cells.height / 2);

    46 

    47         let num_steps = if self.maze_template.inverted { 3 } else { 1 };

    48         let mut step_done = vec![false; num_steps];

    49         let mut last_cell = vec![Point::diag(0); num_steps];

    50         let mut came_from_pos = vec![0; num_steps];

    51         let mut came_from = vec![vec![Point::diag(0); num_cells.area()]; num_steps];

    52 

    53         let mut done = false;

    54         let mut seen_list = vec![vec![None as Option<usize>; seen_cells.width]; seen_cells.height];

    55         let mut x_walls = vec![vec![true; seen_cells.width]; seen_cells.height - 1];

    56         let mut y_walls = vec![vec![true; seen_cells.width - 1]; seen_cells.height];

    57         let mut x_edge_list = vec![vec![false; num_edges.width]; num_cells.height];

    58         let mut y_edge_list = vec![vec![false; num_cells.width]; num_edges.height];

    59 

    60         let mut maze = vec![vec![false; num_cells.width]; num_cells.height];

    61 

    62         let off_y = 0;

    63 

    64         for current_step in 0..num_steps {

    65             let x = random_numbers.next().unwrap_or_default() as usize % (seen_cells.width - 1)

    66                 / num_steps;

    67             last_cell[current_step] = Point::new(

    68                 (x + current_step * seen_cells.width / num_steps) as i32,

    69                 random_numbers.next().unwrap_or_default() as i32 / num_steps as i32,

    70             );

    71         }

    72 

    73         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>>,

    74                         last_cell: &mut Vec<Point>, came_from: &mut Vec<Vec<Point>>, came_from_pos: &mut Vec<i32>| {

    75             loop {

    76                 let p = last_cell[current_step];

    77                 seen_list[p.y as usize][p.x as usize] = Some(current_step);

    78 

    79                 let mut dir = start_dir;

    80 

    81                 let next_dir_clockwise = true;//random_numbers.next().unwrap_or_default() % 2 == 0;

    82 

    83                 for _ in 0..5 {

    84                     let sp = p + dir;

    85                     let when_seen =

    86                         if sp.x < 0

    87                             || sp.x >= seen_cells.width as i32

    88                             || sp.y < 0

    89                             || sp.y >= seen_cells.height as i32

    90                         {

    91                             None

    92                         } else {

    93                             Some(seen_list[sp.y as usize][sp.x as usize])

    94                         }

    95                     ;

    96 

    97                     match when_seen {

    98                         None => {

    99                             // try another direction

   100                             if dir.x == -1 && p.x > 0 {

   101                                 y_walls[p.y as usize][p.x as usize - 1] = false;

   102                             }

   103                             if dir.x == 1 && p.x < seen_cells.width as i32 - 1 {

   104                                 y_walls[p.y as usize][p.x as usize] = false;

   105                             }

   106                             if dir.y == -1 && p.y > 0 {

   107                                 x_walls[p.y as usize][p.x as usize] = false;

   108                             }

   109                             if dir.y == 1 && p.y < seen_cells.height as i32 - 1 {

   110                                 x_walls[p.y as usize][p.x as usize] = false;

   111                             }

   112 

   113                             if next_dir_clockwise {

   114                                 dir = dir.rotate90();

   115                             } else {

   116                                 dir = dir.rotate270();

   117                             }

   118                         }

   119                         Some(None) => {

   120                             // cell was not seen yet, go there

   121                             if dir.y == -1 {

   122                                 x_walls[p.y as usize - 1][p.x as usize] = false;

   123                             }

   124                             if dir.y == 1 {

   125                                 x_walls[p.y as usize][p.x as usize] = false;

   126                             }

   127                             if dir.x == -1 {

   128                                 y_walls[p.y as usize][p.x as usize - 1] = false;

   129                             }

   130                             if dir.x == 1 {

   131                                 y_walls[p.y as usize][p.x as usize] = false;

   132                             }

   133                             last_cell[current_step] = p + dir;

   134                             came_from_pos[current_step] += 1;

   135                             came_from[came_from_pos[current_step] as usize][current_step] = p;

   136                         }

   137                         _ => {

   138                             return true;

   139                         }

   140                     }

   141                 }

   142 

   143                 last_cell[current_step] = came_from[came_from_pos[current_step] as usize][current_step];

   144                 came_from_pos[current_step] -= 1;

   145 

   146                 return came_from_pos[current_step] < 0;

   147             }

   148         };

   149 

   150         let mut islands: Vec<Polygon> = vec![];

   151         let mut polygon: Vec<Point> = vec![];

   152         let add_vertex = |p: Point, polygon: &mut Vec<Point>| {

   153             let cell_size = self.maze_template.cell_size as i32;

   154             let [x, y] = [p.x, p.y].map(|i| {

   155                 if self.maze_template.inverted || i & 1 == 0 {

   156                     cell_size

   157                 } else {

   158                     cell_size * 2 / 3

   159                 }

   160             });

   161             let new_point =

   162                 Point::new((p.x - 1) * cell_size + x, (p.y - 1) * cell_size + y + off_y);

   163 

   164             let nv = polygon.len();

   165             if nv > 2 {

   166                 if polygon[nv - 2].x == polygon[nv - 1].x && polygon[nv - 1].x == new_point.x

   167                     || polygon[nv - 2].y == polygon[nv - 1].y && polygon[nv - 1].y == new_point.y

   168                 {

   169                     polygon.pop();

   170                 }

   171             }

   172 

   173             polygon.push(new_point);

   174         };

   175 

   176         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>>| {

   177             let mut dir = dir.rotate270();

   178             let mut next_p = Some(p);

   179 

   180             while let Some(p) = next_p {

   181                 next_p = None;

   182 

   183                 for _ in 0..4 {

   184                     dir = dir.rotate90();

   185                     let cdir = Point::new(

   186                         if dir.x < 0 { 0 } else { dir.x },

   187                         if dir.y < 0 { 0 } else { dir.y },

   188                     );

   189 

   190                     let np = p + cdir;

   191                     let edge_list = if dir.x == 0 {

   192                         &mut *x_edge_list

   193                     } else {

   194                         &mut *y_edge_list

   195                     };

   196                     if np.x >= 0

   197                         && np.y > 0

   198                         && np.x < num_cells.width as i32

   199                         && np.y < num_cells.height as i32

   200                         && edge_list[np.y as usize][np.x as usize]

   201                     {

   202                         (*edge_list)[np.y as usize][np.x as usize] = false;

   203                         add_vertex(p + dir + Point::new(1, 1), polygon);

   204                         next_p = Some(p + dir);

   205                         break;

   206                     }

   207                 }

   208             }

   209         };

   210 

   211         while !done {

   212             done = true;

   213 

   214             for current_step in 0..num_steps {

   215                 if !step_done[current_step] {

   216                     let dir = match random_numbers.next().unwrap_or_default() % 4 {

   217                         0 => Point::new(0, -1),

   218                         1 => Point::new(1, 0),

   219                         2 => Point::new(0, 1),

   220                         3 => Point::new(-1, 0),

   221                         _ => panic!(),

   222                     };

   223                     step_done[current_step] =

   224                         see_cell(current_step, dir, &mut seen_list, &mut x_walls, &mut y_walls, &mut last_cell, &mut came_from, &mut came_from_pos);

   225                     done = false;

   226                 }

   227             }

   228         }

   229 

   230         for x in 0..seen_cells.width {

   231             for y in 0..seen_cells.height {

   232                 if seen_list[y][x].is_some() {

   233                     maze[y * 2 + 1][x * 2 + 1] = true;

   234                 }

   235             }

   236 

   237             for y in 0..seen_cells.height - 1 {

   238                 if !x_walls[y][x] {

   239                     maze[y * 2 + 2][x * 2 + 1] = true;

   240                 }

   241             }

   242         }

   243 

   244         for x in 0..seen_cells.width - 1 {

   245             for y in 0..seen_cells.height {

   246                 if !y_walls[y][x] {

   247                     maze[y * 2 + 1][x * 2 + 2] = true;

   248                 }

   249             }

   250         }

   251 

   252         for x in 0..num_edges.width {

   253             for y in 0..num_cells.height {

   254                 x_edge_list[y][x] = maze[y][x] != maze[y][x + 1];

   255             }

   256         }

   257 

   258         for x in 0..num_cells.width {

   259             for y in 0..num_edges.height {

   260                 y_edge_list[y][x] = maze[y][x] != maze[y + 1][x];

   261             }

   262         }

   263 

   264         for x in 0..num_edges.width {

   265             for y in 0..num_cells.height {

   266                 if x_edge_list[y][x] {

   267                     x_edge_list[y][x] = false;

   268                     add_vertex(Point::new(x as i32 + 1, y as i32 + 1), &mut polygon);

   269                     add_vertex(Point::new(x as i32 + 1, y as i32), &mut polygon);

   270                     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);

   271 

   272                     islands.push(Polygon::new(&polygon));

   273                     polygon.clear();

   274                 }

   275             }

   276         }

   277 

   278         OutlinePoints {

   279             islands,

   280             fill_points: vec![],

   281             size: *size,

   282             play_box,

   283             intersections_box,

   284         }

   285     }

   286 }

   287 

   288 impl LandGenerator for MazeLandGenerator {

   289     fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(

   290         &self,

   291         parameters: &LandGenerationParameters<T>,

   292         random_numbers: &mut I,

   293     ) -> Land2D<T> {

   294         let do_invert = false;

   295         let (basic, zero) = if do_invert {

   296             (parameters.zero, parameters.basic)

   297         } else {

   298             (parameters.basic, parameters.zero)

   299         };

   300 

   301         let land_size = Size::new(self.maze_template.width, self.maze_template.height);

   302         let mut land = Land2D::new(&land_size, basic);

   303 

   304         let mut points = self.generate_outline(

   305             &land.size().size(),

   306             Rect::at_origin(land_size).with_margin(land_size.to_square().width as i32 * -2),

   307             land.play_box(),

   308             random_numbers,

   309         );

   310 

   311         if !parameters.skip_distort {

   312             points.distort(parameters.distance_divisor, random_numbers);

   313         }

   314 

   315         if !parameters.skip_bezier {

   316             points.bezierize(5);

   317         }

   318 

   319         points.draw(&mut land, zero);

   320 

   321         for p in &points.fill_points {

   322             land.fill(*p, zero, zero)

   323         }

   324 

   325         points.draw(&mut land, basic);

   326 

   327         land

   328     }

   329 }