[net.sources] mz.c

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 :-)