Xref: utzoo comp.sources.wanted:14478 alt.sources.d:1162 rec.games.misc:12809 rec.games.programmer:2685 Path: utzoo!utgpu!cs.utexas.edu!sdd.hp.com!news.cs.indiana.edu!msi.umn.edu!noc.MR.NET!gacvx2.gac.edu!gacvx2.gac.edu!scott From: scott@mcs-server.gac.edu (Scott Hess) Newsgroups: aus.games,comp.sources.wanted,alt.sources.d,rec.games.misc,rec.games.programmer Subject: Re: Maze generation Message-ID: Date: 13 Dec 90 06:33:56 GMT References: <1215@syacus.acus.oz> Organization: Gustavus Adolphus College Lines: 46 Nntp-Posting-Host: mcs-server.gac.edu In-reply-to: martins@syacus.acus.oz's message of 13 Dec 90 01:19:40 GMTLines: 46 In article <1215@syacus.acus.oz> martins@syacus.acus.oz (Martin Schwenke) writes: I am interested in software or algorithms for generating mazes with unique solutions. I am also, but less, interested in maze solving algorithms, and programs. A nice solution I found to this is the following algorithm (adapted from a particularily ugly BASIC program . . .): Your maze is made up of a bunch of cells in a 2d array. Each looks something like: O? ?X Where O is open, ? are uncertain, and X is a wall. So, you need two bits per cell to represent this. To start out, set all the cells to be closed (both ? are X). Pick a random cell (this can be anywhere, just choose somewhere). loop From the current cell, do a random walk. This means, pick a random direction. Look in that direction to see if you can move there. If so, open a path to there (either in your cell [right/down], or the appropriate neighbor [up/left]). Assume an implicit wall on the right hand side. until you run into a wall. Now, you need to find a new place to start. So, what you do is begin scanning the array in some fashion (say, left to right, top to bottom - reading fashion) for closed cells. Once you find one, open a path to a neighbor, and then random walk . . . Do this over and over until all cells are accounted for (as found by running over the starting scan block again). While this isn't the most complex solution, it generated very acceptable mazes for my purposes (I was to write a maze-solver. What good's a solver without a generator :-]. To add to the fun, it was in text mode on a PC, so I wrote a virtual window for it . . . :-) -- scott hess scott@gac.edu Independent NeXT Developer GAC Undergrad "Tried anarchy, once. Found it had too many constraints . . ." "Buy `Sweat 'n wit '2 Live Crew'`, a new weight loss program by Richard Simmons . . ."