jim@ism780c.UUCP (Jim Balter) (11/05/86)
#ifdef README This little program produces random rectangular mazes suitable for display on a ASCII character device. It should be easy to convert it for a bitmap or vector display if desired. Invoke as "mz nrows ncols". The output consists of nrows + 1 lines of 2 * ncols + 1 characters, so "mz 22 39" fits on a standard CRT screen. For more of a challenge, try "mz 65 65" on 11"x17" printer paper. There is always exactly one solution. #endif #include <stdio.h> #define oneof(n) (int)(((long)(n) * rand())/32768) #define BOT 0 #define LEFT 1 #define TOP 2 #define RIGHT 3 typedef struct {unsigned c_group:14, c_bot:1, c_left:1, c_next;} cell_t; #define group(cell) cells[cell].c_group #define setgroup(cell, g) (cells[cell].c_group = (g)) #define next(cell) cells[cell].c_next #define setnext(cell, g) (cells[cell].c_next = (g)) #define botwall(cell) !cells[cell].c_bot #define leftwall(cell) !cells[cell].c_left #define isborder(cell) (group(cell) == 0) cell_t *cells; #define neighbor(cell, side) ((cell) + nboff[side]) int nboff[4]; #define loc(r, c) ((r) * width + (c) + 1) int nrows, ncols, width, ncells; blast (cell, side) { switch( side ) { case BOT: cells[cell].c_bot = 1; break; case LEFT: cells[cell].c_left = 1; break; case TOP: cells[neighbor(cell, TOP )].c_bot = 1; break; case RIGHT: cells[neighbor(cell, RIGHT)].c_left = 1; break; } } init () { register r, c, cell; register long t; extern long time(); extern char *calloc(); t = time((long *)NULL); srand((unsigned)t + (unsigned)(t >> 16) + getpid()); ncells = nrows * ncols; width = ncols + 1; cells = (cell_t *)calloc((nrows+2) * width, sizeof(cell_t)); if( !cells ) { fprintf(stderr, "Not enough memory\n"); exit(-1); } cells += width; for( c = ncols; --c >= 0; ) { for( r = nrows; --r >= 0; ) { cell = loc(r, c); setgroup(cell, cell); } blast(loc(-1, c), LEFT); } blast(loc(-1, ncols), BOT); blast(loc(-1, ncols), LEFT); blast(loc(-1, -1), BOT); nboff[BOT] = width; nboff[LEFT] = -1; nboff[TOP] = -width; nboff[RIGHT] = 1; } #define isconnected(cell1, cell2) (group(cell1) == group(cell2)) join (cell, side) register cell; register side; { register ocell; register newgroup, oldgroup; blast(cell, side); oldgroup = group(cell); newgroup = group(neighbor(cell, side)); for( cell = oldgroup; cell; ocell = cell, cell = next(cell) ) setgroup(cell, newgroup); setnext(ocell, next(newgroup)); setnext(newgroup, oldgroup); } connect (cell) register cell; { register side, nb; side = oneof(2); if( isborder(nb = neighbor(cell, side)) || isconnected(cell, nb) ) { side = 1 - side; if( isborder(nb = neighbor(cell, side)) || isconnected(cell, nb) ) return 0; } join(cell, side); return 1; } print () { register r, c, cell, ch; for( r = -1; r < nrows; putchar('\n'), r++ ) for( c = 0; c <= ncols; c++ ) { cell = loc(r, c); if( leftwall(cell) ) ch = '|'; else { ch = '_'; if( leftwall(neighbor(cell, BOT)) ) { if( !botwall(cell) || !botwall(neighbor(cell, LEFT)) ) ch = '.'; } else if( !botwall(cell) && !botwall(neighbor(cell, LEFT)) ) ch = '.'; } putchar(ch); if( c == ncols ) break; putchar(botwall(cell)? '_' : ' '); } } main (argc, argv) char **argv; { register n, ncon; if( argc != 3 ) { fprintf(stderr, "usage: %s nrows ncols\n", argv[0]); exit(-1); } nrows = atoi(argv[1]); ncols = atoi(argv[2]); init(); for( ncon = ncells - 1; --ncon >= 0; ) for( n = oneof(ncells);; n = (n+1) % ncells ) if( connect(loc(n/ncols, n%ncols)) ) break; blast(loc(0, oneof(ncols)), TOP); blast(loc(nrows-1, oneof(ncols)), BOT); print(); } -- -- Jim Balter ({sdcrdcf!ism780c,ima}!jim)
chapman@cory.Berkeley.EDU (Brent Chapman) (11/06/86)
Thhis is a neat program, but it assumes that the range of values returned by rand() is 0 to ((2^15) - 1); this is not the case on BSD VAXen and Suns. On those machines (and presumeably others), the code compiles just fine, but sooner or later dies a horrid death when oneof() returns something wierd. The quick, machine independant fix is to mask off all but the low-order 15 bits of the result of rand(). This works, assuming that the low-order bits alone are reasonably random; this may or may not be a valid assumption, depending on your hardware and software. But it's good enough for the purposes of this program. Anyway, the definition of macro oneof() needs to be changed from: #define oneof(n) (int)(((long)(n) * rand())/32768) to: #define oneof(n) (int)(((long)(n) * (rand() & 0x7fff))/32768) This works, and is more portable than the original code (note that I do _not_ say that it is portable, or that doing it this way is a good idea; simply that it is _more_ portable than the original.). Brent -- Brent Chapman chapman@cory.berkeley.edu or ucbvax!cory!chapman
trent@cit-vax.Caltech.Edu (Ray Trent) (11/06/86)
In article <823@zen.BERKELEY.EDU> chapman@cory.Berkeley.EDU.UUCP (Brent Chapman) writes: >Anyway, the definition of macro oneof() needs to be changed from: > #define oneof(n) (int)(((long)(n) * rand())/32768) >to: > #define oneof(n) (int)(((long)(n) * (rand() & 0x7fff))/32768) I suppose this works...but isn't: #define oneof(n) (rand() % (n) + 1) more intuitive and efficient? -- DISCLAIMER, DAMMIT!!!! Any errors in this posting are computer errors generated by my spelling/syntax/usage/factual content checker. ../ray\.. (trent@csvax.caltech.edu, rat@caltech.bitnet, ...seismo!cit-vax!trent)
ajs@hpfcla.HP.COM (Alan Silverstein) (11/07/86)
> This is a neat program...
Yeah, and I'm curious what algorithm it uses. Unfortunately the code
contains ZERO comments, and I don't want to spend even fifteen minutes
groping through the code to figure it out (blech). End of sermon.
("Ah shut up, it's free software, you're not allowed to gripe." "Sure,
but the next program this author writes might be important, something
I have to live with. I *must* try to encourage better coding styles."
"You're tilting at windmills." "Sigh...")
tim@ism780c.UUCP (Tim Smith) (11/08/86)
Note: followups are being redirected to net.sources.d In article <1125@cit-vax.Caltech.Edu> trent@cit-vax.UUCP (Ray Trent) writes: > >I suppose this works...but isn't: > > #define oneof(n) (rand() % (n) + 1) > >more intuitive and efficient? Yes, but it also doesn't work! If n is not a divisor of 32768, the distribution will be off. For example, if n is 24000, then numbers from 1 to 8000 will be given twice as often as numbers from 9000 to 24000. -- emordnilapanalpanama Tim Smith USENET: sdcrdcf!ism780c!tim Compuserve: 72257,3706 Delphi or GEnie: mnementh
ma6nrr@bath63.UUCP (11/22/86)
I find the maze looks better if you alter the print () routine:
...
if( leftwall(cell) )
ch = '|';
else
{ ch='_';
if( !botwall(cell) && !botwall(neighbor(cell, LEFT)) )
ch='.';
}
putchar(ch);
(Actually my version uses neighbour instead of neighbor throughout)
This alteration only prints full stops not next to underlines.
(I hope this has SOME approval :-)