Maze Generator
The following 77line program randomly generates square 2D mazes using a depthfirst search, displaying them on screen using OpenGL:
(* The board size and line width used to render it. *)
let line_width = 8
(* Test if a position has not yet been visited. *)
let unvisited v (x, y) = try v.(y).(x) with _ > false
(* Mark a position as having been visited. *)
let visit v (x, y) = try v.(y).(x) < false with _ > ()
let choices visited (x, y) =
List.filter (unvisited visited) [x1, y; x+1, y; x, y1; x, y+1]
(* Randomly pick an unvisited neighbor. *)
let random_neighbor visited cell = match choices visited cell with
[] > None
 choices > Some (List.nth choices (Random.int (List.length choices)))
(* Draw to the given coordinate. *)
let vertex (x, y) =
GlDraw.vertex2 (float line_width *. (0.5 +. float x),
float line_width *. (0.5 +. float y))
(* Recurse over the maze. *)
let rec draw_maze_aux n visited cell k =
vertex cell;
GlDraw.ends ();
GlDraw.begins `points;
vertex cell;
GlDraw.ends ();
GlDraw.begins `line_strip;
vertex cell;
visit visited cell;
match random_neighbor visited cell with
Some neighbor >
draw_maze_aux n visited neighbor
(fun () > draw_maze_aux n visited cell k)
 _ >
GlDraw.ends ();
GlDraw.begins `line_strip;
k()
(* Render a maze. *)
let draw_maze n =
GlDraw.begins `line_strip;
vertex (0, 0);
draw_maze_aux n (Array.make_matrix n n true) (0, 0) (fun _ > ());
GlDraw.ends ();
flush stdout
let n = ref 1 and width = ref 1 and height = ref 1
(* Setup a 2D orthogonal projection. *)
let set_projection () =
GlMat.mode `projection;
GlMat.load_identity ();
GlMat.ortho ~x:(0., float !width) ~y:(0., float !height) ~z:(0., 1.);
GlMat.mode `modelview;
GlMat.load_identity ()
(* Resize the window, generating a new maze. *)
let reshape ~w ~h =
GlDraw.viewport 0 0 w h;
n := (min w h) / line_width;
width := w; height := h;
set_projection ();
Glut.postRedisplay ()
(* Memoize a function in a display list. *)
let memoize k =
let d = Hashtbl.create 1 in
fun x >
try GlList.call (Hashtbl.find d x) with Not_found >
let list = GlList.create `compile in
k x;
GlList.ends ();
GlList.call list;
Hashtbl.add d x list
(* Setup glut and enter the glut mainloop. *)
let () =
ignore (Glut.init Sys.argv);
ignore (Glut.createWindow "Maze");
GlDraw.line_width (float (line_width  2));
GlDraw.point_size (float (line_width  2));
Glut.reshapeFunc ~cb:reshape;
let draw = memoize draw_maze in
Glut.displayFunc (fun () > GlClear.clear [`color]; draw !n; Gl.flush ());
Glut.keyboardFunc ~cb:(fun ~key ~x ~y > if key=27 then exit 0);
Glut.mainLoop ()
This program can be compiled using:
ocamlopt I +lablgl lablgl.cmxa lablglut.cmxa unix.cmxa maze.ml o maze
The program can be executed to draw a maze on the screen:
$ ./maze
The following screenshot illustrates the capability of this program:
The task of converting this program into one which renders a 3D maze is left as an exercise for the reader.

Read OCaml for Scientists now!

