mz.c

[Jim Balter]

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