Version française
Home     About     Download     Resources     Contact us    
Browse thread
Maze generator
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jon Harrop <jon@f...>
Subject: Maze generator

Whilst revamping our website, I took the time to improve the maze generator:

  http://www.ffconsultancy.com/ocaml/maze/

it is now 30% shorter and much faster, using an array instead of a functional 
map. It also uses continuation passing style instead of an explicit stack. 
But it no longer produces PostScript output.

The program uses a simple depth first search. An interesting alternative 
algorithm involves keeping track of sets of connection cells and breaking 
walls to unify the sets until you have a spanning tree. That should be easy 
to code in OCaml but I think it will generate mazes that are much harder to 
solve.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists