🚀 go-pugleaf

In article <1992Aug5.202648.12058@ccu1.aukuni.ac.nz>, rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:
|> 
|>     Hello.
|>     I'm looking for some code to generate consistent mazes.  This 
|> can be in any language but preferably either just a basic algorithm or 
|> C.  Can any one help me ??
|> 
|> Please mail to me direct I don't read this group much.

Ignoring the line above.  :-)

Ah, I have just the program, but its in turbo pascal.  I will
look around for it tonight, hopefully.

      SPHINX


====================================================
=== Kill others only if you wish to be killed.   ===
===                                       SPHINX ===   
====================================================

rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:

>    Hello.
>    I'm looking for some code to generate consistent mazes.  This 
>can be in any language but preferably either just a basic algorithm or 
>C.  Can any one help me ??

I'm not sure what a "consistant" maze is. I have some C code that generates
3d mazes, but it is a probabilistic thing: it just grows a random tree
of branching, turning corridors, and when one of them reaches the pre-chosen
exit point, it stops. Occasionally, all the branches on the tree dead end
before the pre-chosen exit point is reached, and the program simply
apologises and requests you start it again. That's fairly rare. The program
is neither bright nor brilliantly written, but it serves my purposes. It
more or less tries to fill a 3d cube, with a starting point on one face of
the cube and an ending point on the opposite face. Myriad improvements
are possible, but I haven't needed them. All the turns are right angles.

The output is to stdout and is an ascii description of the maze in
a language my 3d display code understands. If you want it badly enough,
I could mail the maze generator. It is *not* elegant code. But it is free.

Try sending mail to spider@decvax.dec.com. I seem to recall, some years
ago, that he wrote a good 2d maze generator. I vaguely recall that it
always succeeded, but he wrote it in SNOBOL and that the algorithm was
a bit bizarre. If you do, send along parts of this mail so he has some
idea what you are talking about.
--
He is a slave to a sign who uses or worships a significant thing without
knowing what it signifies.			-Augustine
smayo@wang.com

smayo@wang.com (Scott Mayo) writes:

>rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:

>>    Hello.
>>    I'm looking for some code to generate consistent mazes.  This 
>>can be in any language but preferably either just a basic algorithm or 
>>C.  Can any one help me ??

>I'm not sure what a "consistant" maze is. I have some C code that generates
		    ^^^^^^^^^^^^^^  I mean every room is connected to one 
or more others.  But it MUST be connected and I don't want to start
on one edge and move to another.  it just want's to be a full maze
of interconnected rooms 

HELP...

Ross

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