let shuffle lst =
let swap array i j =
let temp = array.(i) in array.(i) <- array.(j); array.(j) <- temp
in
let shuffle_array array =
Array.iteri (fun i _ -> swap array i (Random.int (i+1))) array;
array
in
Array.to_list (shuffle_array (Array.of_list lst))
let rec select_point maze x1 y1 x2 y2 needle =
let x = x1 + Random.int (x2-x1)
and y = y1 + Random.int (y2-y1) in
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 =
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
(*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 *)
let start = select_point maze 0 0 (width-1) (height-1) '#' in
let start = if (fst start) mod 2 <> 0 then (fst start)-1, snd start else start in
let start = if (snd start) mod 2 <> 0 then fst start, (snd start)-1 else start in
let remove_wall (x1, y1) (x2, y2) =
if x1 <> x2 then Maze.set maze ((max x1 x2)-1, y1) ' '
else if y1 <> y2 then Maze.set maze (x1, (max y1 y2)-1) ' '
in
let even_neighbors maze (x, y) =
let nodes = [] in
let nodes = if x > 1 then (x-2, y) :: nodes else nodes in
let nodes = if x < width - 2 then (x+2, y) :: nodes else nodes in
let nodes = if y > 1 then (x, y-2) :: nodes else nodes in
let nodes = if y < height - 2 then (x, y+2) :: nodes else nodes in
nodes
in
let visited = ref [] in
let rec recurse previous current =
if not (List.mem current !visited) then begin
Maze.set maze current ' ';
remove_wall previous current;
visited := current :: !visited;
let neighbors = shuffle (even_neighbors maze current) in
List.iter (fun next -> recurse current next) neighbors
end
in
recurse start start;
let goal = select_point maze 0 0 (width-1) (height-1) ' ' in
Maze.set maze start '@';
Maze.set maze goal 'X';
maze, start, goal
let rec add_holes maze n = match+ n with
| 0 -> maze
| _ ->
let x = Random.int ((Maze.width maze) -1)
and y = Random.int ((Maze.height maze) -1) in
if Maze.get maze (x, y) = '#' then Maze.set maze (x, y) ' ';
add_holes maze (pred n)
let generate width height =
let maze, start, goal = gen_backtracker width height in
(add_holes maze (width+height)), start, goal