Commits

Anonymous committed 760ecc6

recdiv room generator that actually works

Comments (0)

Files changed (2)

maze/generator.ml

   if Maze.get maze (x, y) = needle then (x, y) 
   else select_point maze x1 y1 x2 y2 needle
 
-let gen_recdiv width height divisions =
+(*Start with an empty room.                                                  *)
+(*While the room is big enough, do a vertical or horizontal split, and repeat*)
+(*for each newly splitted room. Altern vertical and horizontal at each step. *)
+(*if the room is too small, do nothing.                                      *)
+(*ends by adding a door in the wall, taking care to open it in a usable path *)
+let gen_recdiv width height = 
+  let min_size = 5 in
   let maze = Array.make_matrix width height ' ' in
-  let minsize = 3 in
   let add_wall x1 y1 x2 y2 = 
     for x = x1 to x2 do
       for y = y1 to y2 do
       done
     done
   in
-  let pierce_holes x1 y1 x2 y2 = 
-    if x1 = x2 || y1 = y2 then ()
+  let rec open_vdoor xwall y h = 
+    let door = y + Random.int h in   
+    if xwall + 1 < height && Maze.get maze (xwall+1, door) = '#'
+      || xwall -1 > 0 && Maze.get maze (xwall-1, door) = '#'
+    then open_vdoor xwall y h
+    else Maze.set maze (xwall, door) ' '
+  in
+  let rec open_hdoor x ywall w = 
+    let door = x + Random.int w in
+    if ywall + 1 < width && Maze.get maze (door, ywall+1) = '#'
+      || ywall -1 > 0 && Maze.get maze (door, ywall-1) = '#'
+    then open_hdoor x ywall w
+    else Maze.set maze (door, ywall) ' '
+  in  
+  let rec vsplit x y w h = 
+    if w < min_size then ()
     else begin
-	    let xhole1 = x1 + Random.int (x2-x1) 
-		  and yhole1 = y1 + Random.int (y2-y1) in
-		  Maze.set maze (x1, yhole1) ' ';
-		  Maze.set maze (xhole1, y1) ' '
+      let xwall = (x+2) + Random.int (w - 4) in
+      add_wall xwall y xwall (y+h-1);
+      hsplit x y (xwall-x) h;
+      hsplit (xwall+1) y (w-(xwall-x)-1) h;     
+      open_vdoor xwall y h  
+    end
+  and hsplit x y w h =
+    if h < min_size then ()
+    else begin
+      let ywall = (y+2) + Random.int (h - 4) in
+      add_wall x ywall (x+w-1) ywall;
+      vsplit x y w (ywall-y);
+      vsplit x (ywall+1) w (h-(ywall-y)-1);
+      open_hdoor x ywall w
     end
   in
-  let rec divide x1 y1 x2 y2 divisions =
-    if divisions = 0 || (x2-x1) <= minsize || (y2-y1) <= minsize then
-      pierce_holes x1 y1 x2 y2
-    else begin
-      let xwall = 2 + x1 + Random.int (x2-x1-3) 
-      and ywall = 2 + y1 + Random.int (y2-y1-3) in
-      add_wall x1 ywall x2 ywall;
-      add_wall xwall y1 xwall y2;
-      let divisions = (pred divisions) in   
-      divide x1 y1 xwall ywall divisions;
-      divide xwall y1 x2 ywall divisions;
-      divide x1 ywall xwall y2 divisions;
-      divide xwall ywall x2 y2 divisions;
-    end
-  in 
-  divide 0 0 (width-1) (height-1) divisions;
+  if Random.bool() then vsplit 0 0 width height
+  else hsplit 0 0 width height;
+    
   let start = select_point maze 0 0 (width/2) (height/2) ' ' in
   let goal = select_point maze (width/2) (height/2) (width-1) (height-1) ' ' in
   Maze.set maze start '@';
   Maze.set maze goal 'X';
-  maze, start, goal    
+  maze, start, goal      
 
 (*Start at a particular cell and call it the "exit."                          *)
 (*Mark the current cell as visited, and get a list of its neighbors.          *)
 (*For each neighbor, starting with a randomly selected neighbor:              *)
 (* If that neighbor hasn't been visited, remove the wall between this cell    *)
 (* and that neighbor, and then recurse with that neighbor as the current cell.*)
-  
 let gen_backtracker width height =
   let maze = Array.make_matrix width height '#' in
   (* start with a random point, with even coords *)
     if Maze.get maze (x, y) = '#' then Maze.set maze (x, y) ' ';
     add_holes maze (pred n)
     
-
 let rec generate generator width height = match generator with
   | RANDOM -> 
     let generator = if Random.bool () then RECDIV else BACKTRACKER in
     generate generator width height
-  | RECDIV ->  
-    let divisions = (width*height)/50 in 
-    gen_recdiv width height divisions
+  | RECDIV -> gen_recdiv width height
   | BACKTRACKER -> 
     let maze, start, goal = gen_backtracker width height in
-    (add_holes maze (width+height)), start, goal
-  
+    (add_holes maze (width+height)), start, goal
   Sdlvideo.set_video_mode (width * Image.tilesize) (height * Image.tilesize) []
 
 let rec generate_maze generator width height =
-  let check_maze maze start goal =
+  let check_maze maze start goal = 
     let open Astar.Pathfinding in
     let min_steps = 5 in
     try