Commits

Anonymous committed 9a79cf7

maze generator

Comments (0)

Files changed (2)

maze/generator.ml

+let rec select_point maze x1 y1 x2 y2 = 
+  let x = x1 + Random.int (x2-x1)
+  and y = y1 + Random.int (y2-y1) in
+  if Maze.get maze (x, y) = ' ' then (x, y) 
+  else select_point maze x1 y1 x2 y2
+
+let gen_recdiv height width divisions =
+  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
+        Maze.set maze (x, y) '#' 
+      done
+    done
+  in
+  let pierce_holes x1 y1 x2 y2 = 
+    if x1 = x2 || y1 = y2 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) ' '
+    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;
+  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    
+
+let generate height width = gen_recdiv height width 8
+  
-let pixel = 16
-
-let load_maze maze name = 
-  Graphics.set_window_title ("Maze solver - " ^ name);
-  let width = Maze.width maze and height = Maze.height maze in
-  Graphics.resize_window (width*pixel) (height*pixel);
-  let gray = Graphics.rgb 150 150 150 in
-  for x = 0 to width -1 do
-    for y = 0 to height - 1 do
-      let tile = Maze.get maze (x, y) in
-      let color = match tile with
-        | '@' -> Graphics.red
-        | 'X' -> Graphics.green
-        | '#' -> gray
-        | _ -> Graphics.white
-      in
-      Graphics.set_color color;
-      Graphics.fill_rect (x*pixel) ((height-1-y)*pixel) pixel pixel;
-      Graphics.set_color gray;
-      Graphics.draw_rect (x*pixel) ((height-1-y)*pixel) pixel pixel;
-    done
-  done 
-
-let draw_dot maze (x, y) = 
-  let shift = pixel / 2 in
-  let half = shift / 2 in
-  let height = Maze.height maze in
-  if Maze.get maze (x, y) <> '#' then Graphics.fill_rect 
-    (x*pixel + half) ((height-y-1)*pixel + half) shift shift
-
-let walk maze path =
-  Graphics.set_color Graphics.blue;
-  List.iter (draw_dot maze) path
-
-let solve maze goal start = 
-  let path = Astar.Pathfinding.find_path maze start goal in
-  walk maze path;
-  while Graphics.read_key() != ' ' do
-    ()
-  done
-
-let rec interact maze goal start current =
-  Graphics.set_color Graphics.black;
-  draw_dot maze current; 
-  
-  let key = Graphics.read_key() in
-  if key = ' ' then solve maze goal start
-  else begin
-    let next = match key with
-      | '6' -> (fst current) +1, snd current
-      | '4' -> (fst current) -1, snd current
-      | '8' -> fst current, (snd current) -1
-      | '2' -> fst current, (snd current) +1
-      | _ -> current
-    in
-    if not (Maze.check maze next) || Maze.get maze next = '#' then begin 
-      interact maze goal start current
-    end
-    else begin
-      Graphics.set_color 0xffc600;
-      draw_dot maze current;
-      if next = goal then solve maze goal start
-      else interact maze goal start next
-    end       
-  end
-         
-                   
-let _ =
-  let filename = "maze/maze.txt" in
-  let maze, goal, ants = Maze.Parser.from_file filename in
-  let start = List.hd ants in
-  Graphics.open_graph "";
-  load_maze maze filename;
+let pixel = 16
+
+let load_maze maze name = 
+  Graphics.set_window_title ("Maze solver - " ^ name);
+  let width = Maze.width maze and height = Maze.height maze in
+  Graphics.resize_window (width*pixel) (height*pixel);
+  let gray = Graphics.rgb 150 150 150 in
+  for x = 0 to width -1 do
+    for y = 0 to height - 1 do
+      let tile = Maze.get maze (x, y) in
+      let color = match tile with
+        | '@' -> Graphics.red
+        | 'X' -> Graphics.green
+        | '#' -> gray
+        | _ -> Graphics.white
+      in
+      Graphics.set_color color;
+      Graphics.fill_rect (x*pixel) ((height-1-y)*pixel) pixel pixel;
+      Graphics.set_color gray;
+      Graphics.draw_rect (x*pixel) ((height-1-y)*pixel) pixel pixel;
+    done
+  done 
+
+let draw_dot maze (x, y) = 
+  let shift = pixel / 2 in
+  let half = shift / 2 in
+  let height = Maze.height maze in
+  if Maze.get maze (x, y) <> '#' then Graphics.fill_rect 
+    (x*pixel + half) ((height-y-1)*pixel + half) shift shift
+
+let walk maze path =
+  Graphics.set_color Graphics.blue;
+  List.iter (draw_dot maze) path
+
+let solve maze goal start = 
+  let path = Astar.Pathfinding.find_path maze start goal in
+  walk maze path;
+  while Graphics.read_key() != ' ' do
+    ()
+  done
+
+let rec interact maze goal start current =
+  Graphics.set_color Graphics.black;
+  draw_dot maze current; 
+  
+  let key = Graphics.read_key() in
+  if key = ' ' then solve maze goal start
+  else begin
+    let next = match key with
+      | '6' -> (fst current) +1, snd current
+      | '4' -> (fst current) -1, snd current
+      | '8' -> fst current, (snd current) -1
+      | '2' -> fst current, (snd current) +1
+      | _ -> current
+    in
+    if not (Maze.check maze next) || Maze.get maze next = '#' then begin 
+      interact maze goal start current
+    end
+    else begin
+      Graphics.set_color 0xffc600;
+      draw_dot maze current;
+      if next = goal then solve maze goal start
+      else interact maze goal start next
+    end       
+  end
+         
+                   
+let _ =
+  Random.self_init ();
+  let maze, start, goal = Generator.generate 15 20 in
+  Graphics.open_graph "";
+  load_maze maze "auto";
   interact maze goal start start