🚀 go-pugleaf

rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:
(wants a maze generator)

OK, here's mine.

---cut here---

#include <stdio.h>

/*
 * maze - a simple maze generator
 *   useage: maze [h] [v] [rooms] [style] [seed1] [seed2]
 *
 * h is horizontal, v is vertical dimensions
 *
 * rooms is number of 2x2 rooms to try to place before generating maze
 * (not all rooms may be placed)
 *
 * style is one of:
 *  -1: change style throughout maze
 *   0: normal maze
 *   1: staircase/zigzag
 *   2: twisty maze
 *   3: long zigzags/corridors
 *   4: spiral maze
 *
 * seed1 & seed2 are random number seeds to use
 *
 */

/* note: longs should be 32 bits */
/* random number seeds */
unsigned long tseed, cseed;

unsigned long turn, curve, random;

int h, v, size;			/* h&v dimensions, and total size */
int style, rooms;		/* maze style, #rooms */
char *maze;
extern char *malloc();		/* maze array; can just use maze[10000] */

/* each cell has bits for the right & bottom wall */
#define NOWALL	0x00
#define RWALL	0x01
#define	BWALL	0x02
#define	RBWALL	0x03

/* part of a room, and which cell of room prints out room number */
#define	ROOM	0x04
#define	ROOMNO	(0x08|ROOM)
#define	RDOOR	0x10
#define	BDOOR	0x20

/* empty cells at start */
#define	EMPTY	0x40

/*
 * This is a good random number generator
 * someone posted to comp.lang.c
 */
unsigned long
rnd()
{
    cseed *= 69069;
    tseed ^= ((tseed >> 15) & 0x0001FFFF);
    tseed ^= (tseed << 17);

    return(tseed ^ cseed);
}

main(argc, argv)
int argc;
char *argv[];
{
    /* grab args, or plug in default values */
    if (argc >= 4)
	rooms = atoi(argv[3]);
    else
	rooms = -1;
    if (argc >= 3)
	v = atoi(argv[2]);
    else
	v = 20;
    if (argc >= 2)
	h = atoi(argv[1]);
    else
	h = 38;
    if (argc >= 5)
	style = atoi(argv[4]);
    else
	style = -1;
    if (argc >= 6)
	cseed = atoi(argv[5]);
    else
	cseed = h-v+style+rooms;
    if (argc >= 7)
	tseed = atoi(argv[6]);
    else
	tseed = h^(v<<4)^(style<<8);

    /* Let's get small... NOT! */
    if (h < 7 && v < 7)
	h = 7;
    if (h < 3)
	h = 3;
    if (v < 3)
	v = 3;

    /* We pad the maze 1 cell all around so we don't have to check edges */
    h += 2;
    v += 2;
    size = h*v;
    maze = malloc(size);

    if (maze) {
	genmaze();
	printmaze();
    }
}

genmaze()
{
    int i,j,k,ok,n,on,row,count;
    int oi, oj;
    int a[2];

    /* eat up first couple of rnds() */
    rnd();
    rnd();

    /* zero out maze */
    for (i = size-1; i; i--)
	maze[i] = EMPTY;
    
    /* set up borders */
    for (i = h-1; i; i--)
	maze[i] = BWALL;
    for (i = size-1; i >= size-h; i--)
	maze[i] = NOWALL;

    for (i = size - 2*h; i >= h; i -= h)
	maze[i] = RWALL;
    for (i = size-1; i >= 0; i -= h)
	maze[i] = NOWALL;

    /* turn is likelyhood of turning; curve is direction to turn */
    turn  = 0xFFFFFFFF;
    curve = 0xFFFFFFFF;
    random = 0;
    switch (style) {
    default:
    case -1:
	random = (rnd()+rnd())>>5; /* how often we change styles in maze */
	turn = rnd();			/* totally random attributes */
	curve = rnd();
	break;
    case 0:
	turn  >>= 1;	/* 50% chance to turn */
	curve >>= 1;	/* 50% chance to turn same way */
	break;
    case 1:
	turn  >>= 3;	/* 87% chance to turn */
	curve >>= 3;	/* 87% chance to turn same way */
	break;		/* gives us zigzag maze */
    case 2:
	turn  >>= 3;	/* 87% chance to turn */
	curve >>= 1;	/* 50% chance to turn same way */
	break;		/* gives us twisty maze */
    case 3:
	turn  >>= 4;
	turn = ~turn;	/* 6% chance to turn */
	curve >>= 1;	/* 50% chance to turn same way */
	break;		/* gives us long corridors */
    case 4:
	turn  >>= 4;
	turn = ~turn;	/* 6% chance to turn */
	curve >>= 4;	/* 87% chance to turn same way */
	break;		/* gives us spirals */
    }

    /* count of how many cells we dig until done */
    count = (h-2)*(v-2);

    /* put rooms in first */
    if (rooms == -1)
	rooms = (rnd() & 15) + 1;

    /* occupy top left corner so I can start there */
    maze[1+h] = RBWALL;
    for (; rooms--;) {
	/* pick a rnd location: this needs 32-bit math to work */
	i = ((rnd() & 0xFFFF) * (h-3))>>16;
	j = ((rnd() & 0xFFFF) * (v-3))>>16;
	i++, j++;
	row = j*h;
	/* if I can, put a room there */
	if (count > 4 &&
	  maze[i+row] == EMPTY &&
	  maze[i+row+1] == EMPTY &&
	  maze[i+row+h] == EMPTY &&
	  maze[i+row+h+1] == EMPTY) {
	    maze[i+row] = ROOMNO;
	    maze[i+row+1] = RWALL|ROOM;
	    maze[i+row+h] = BWALL|ROOM;
	    maze[i+row+h+1] = RBWALL|ROOM;
	    count -= 4;
	}
    }
    /* unfill starting cell */
    maze[1+h] = EMPTY;
    i = j = 1;
    row = j*h;

    /* ok & on are turn & curve state variables */
    ok = rnd() & 1;
    on = (rnd() & 2) - 1;

    /* don't branch out from a room unless I have no other choice */
    rooms = ROOM;
    for (; count--;) {
	oi = i; oj = j;
scan:
	a[0] = 3*(maze[i+row-1]!=EMPTY) + (maze[i+row+1]!=EMPTY);
	a[1] = 3*(maze[i+row-h]!=EMPTY) + (maze[i+row+h]!=EMPTY);
	/* This is an easy way to find an open direction */
	if (a[0]+a[1] == 8) {
	    /* blocked; find a new place to dig from */
	    do {
		i++;
		if (i >= h-1) {
		    i = 1;
		    j++;
		    row += h;
		    if (j >= v-1) {
			j = 1;
			row = h;
		    }
		}
		/* if we've scanned whole maze, there are undug places */
		/* that can only be gotten to by digging out rooms; do so */
		if (i== oi && j == oj)
		    rooms = 0;
	    } while (maze[i+row] == EMPTY || (maze[i+row] & rooms));
	    goto scan;
	}

	/* do I try to turn? */
	if (rnd() > turn)
	    ok = 1-ok;
	k = ok;

	/* if a 4, I can't go that way; turn */
	if (a[k] == 4) {
	    k = 1-k;
	    if (style != 3)	/* this lets style 3 produce long zigzags */
		ok = k;
	}

	/* do I change direction of turn? */
	if (rnd() > curve)
	    on = -on;
	n = on;
	/* if sum is 2, I can't go that way; go other way */
	if (a[k]+n == 2)
	    n = -n;

	/* If I am going right or down, remove a wall from this cell */
	if (n == 1) {
	    if (k == 0)
		maze[i+row] &= ~RWALL;
	    else
		maze[i+row] &= ~BWALL;
	}

	/* change to new cell */
	if (k == 0)
	    i += n;
	else {
	    j += n;
	    row = j*h;
	}

	/* new cell has walls */
	maze[i+row] = RBWALL;
	/* If I am going left or up, remove a wall from this cell */
	if (n == -1) {
	    if (k == 0)
		maze[i+row] &= ~RWALL;
	    else
		maze[i+row] &= ~BWALL;
	}

	/* If maze style is random, change styles occasionally */
	if (rnd() < random) {
	    turn = rnd();
	    curve = rnd();
	}
    }

    /* Now scan through and make doors out from rooms */
    row = 0;
    for (j = 1; j < v-1; j++) {
	row += h;
	for (i = 1; i < h-1; i++) {
	    if (maze[i+row] != ROOMNO)
		continue;
	    count = 0;
	    do {
		if (rnd() & 1) {
		    k = ((rnd() & 1) ? i+1 : i-1);
		    n = row + (rnd() & 1) * h;
		    if (k > 0 && k < h-2) {
			maze[k+n] &= ~RWALL;
			maze[k+n] |= RDOOR;
			count = 1;
		    }
		}
		else {
		    n = ((rnd() & 1) ? row+h : row-h);
		    k = i + (rnd() & 1);
		    if (n > 0 && n < (v-2)*h) {
			maze[k+n] &= ~BWALL;
			maze[k+n] |= BDOOR;
			count = 1;
		    }
		}
	    } while (!count || !(rnd() & 3));
	}
    }
}

printmaze()
{
    int i,j,row,room;

    room = 0;
    for (j = 0; j < v-1; j++) {
	row = h*j;
	for (i = 0; i < h; i++) {
	    if (maze[i+row] == EMPTY) {
		putchar('?');
		putchar('?');
		continue;
	    }
	    if (maze[i+row] == ROOMNO) {
		putchar((room/10)+'A');
		putchar((room%10)+'0');
		room++;
		continue;
	    }
	    if (maze[i+row] & BWALL)
		putchar('_');
	    else {
		if (maze[i+row] & BDOOR)
		    putchar('.');
		else
		    putchar(' ');
	    }
	    if (maze[i+row] & RWALL)
		putchar('|');
	    else {
		if (maze[i+row] & RDOOR)
		    putchar(':');
		else {
		    if ((maze[i+row] & (BWALL|BDOOR)) &&
		      (maze[i+row+1] & (BWALL|BDOOR)))
			putchar('_');
		    else
			putchar(' ');
		}
	    }
	}
	putchar('\n');
    }
}

---
Merlyn LeRoy