My favourite maze-generating algorithm: consider the graph with one node per cell and edges for all the places where there can be, or not be, walls. Now constru

My favourite maze-generating algorithm: consider the graph with one node per cell and edges for all the places where there can be, or not be, walls. Now construct a random spanning tree for the graph, and remove the walls corresponding to edges of the spanning tree. Finally, choose two leaves of the tree (for bonus points, two leaves that are maximally far apart; for even more bonus points, interpret "far apart" in a way that tries to maximize the difficulty of finding the path between them) and label them "start" and "end". How do you construct a random spanning tree? One way is to use Kruskal's algorithm with random weights on the edges. See http://www.mccaughan.org.uk/software/make-maze-1.02.tar.gz http://www.mccaughan.org.uk/software/make-maze-1.02.tar.gz for an implementation and http://www.mccaughan.org.uk/software/mazes/90x100.ps http://www.mccaughan.org.uk/software/mazes/90x100.ps for a typical maze it generates. (I first saw this algorithm on a web page of Olin Shivers, who had a nice Scheme implementation. Nice, but slow and memory-hungry. Mine does roughly the same as his, but in reasonably tightly-written C and with some neat tricks to make the output compact.)