(* Maze generator in O'Caml by Joe Wingbermuehle * 20070605 *) type maze_element = Space | Wall | Border ;; type maze = Maze of (int * int * maze_element array array) ;; (* Display a maze. *) let show_maze m = let show_element e = match e with Space -> " " | _ -> "[]" in let Maze (width, height, a) = m in for y = 0 to height - 1 do for x = 0 to width - 1 do print_string (show_element a.(x).(y)) done; print_newline (); done ;; (* Initialize a maze to be carved. *) let initialize_maze width height = let a = Array.make_matrix width height Wall in for y = 0 to height - 1 do a.(0).(y) <- Border; a.(width - 1).(y) <- Border done; for x = 0 to width - 1 do a.(x).(0) <- Border; a.(x).(height - 1) <- Border done; a.(1).(1) <- Space; Maze (width, height, a) ;; (* Carve starting at x, y. *) let rec do_carve_maze m x y = let Maze (width, height, a) = m in let move_x x1 y1 x2 y2 = if a.(x1).(y1) == Wall && a.(x2).(y2) == Wall then begin a.(x1).(y1) <- Space; a.(x2).(y2) <- Space; do_carve_maze m x2 y2; true end else false in let move dir x y = match dir with 0 -> move_x x (y - 1) x (y - 2) | 1 -> move_x x (y + 1) x (y + 2) | 2 -> move_x (x - 1) y (x - 2) y | _ -> move_x (x + 1) y (x + 2) y in let rec try_move dir count x y = if count < 4 then let status = move dir x y in if not status then let next_dir = (dir + 1) mod 4 in try_move next_dir (count + 1) x y else () else () in if a.(x).(y) == Space then begin a.(x).(y) <- Space; let dir = Random.int 4 in try_move dir 0 x y end else () ;; (* Carve an initialized maze. *) let carve_maze m = let Maze (width, height, a) = m in for y = 0 to (height - 2) / 2 do for x = 0 to (width - 2) / 2 do do_carve_maze m (x * 2 + 1) (y * 2 + 1) done done; a.(0).(1) <- Space; a.(width - 1).(height - 2) <- Space ;; (* Entry point for the maze generator. *) let main () = Random.self_init (); let m = initialize_maze 39 23 in carve_maze m; show_maze m ;; main () ;;