Source

ocaml-toys / maze / generator.ml

Full commit
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