a563@mindlink.UUCP (Dave Kirsch) (09/06/89)
> smarison writes: > Does anyone have any good random maze generators written in C? I'm > writing a program and need to generate a random maze but I have no > idea how to do it. Here is a little maze program I hacked out a while ago: #include <stdio.h> #include <stdlib.h> int maze[10][10]; #define NORTH 0x01 #define SOUTH 0x02 #define WEST 0x04 #define EAST 0x08 int dirs[4] = {0x01, 0x02, 0x04, 0x08}; int cdirs[4]; void generate(void) { int x, y; int n; int i, j, k, l; x = random(10); y = random(10); n = 99; for (i = 0; i < 10; i++) for (j = 0; j < 10; j++) maze[i][j] = 0; while (n > 0) { printf("%d ", n); for (i = 0; i < 4; i++) cdirs[i] = dirs[i]; for (i = 0; i < 10; i++) { do { j = random(4); k = random(4); } while (j == k); l = cdirs[j]; cdirs[j] = cdirs[k]; cdirs[k] = l; } for (i = 0; i < 4; i++) switch (cdirs[i]) { case NORTH : if (y == 0 || maze[x][y - 1] != 0) break; maze[x][y--] |= NORTH; maze[x][y] |= SOUTH; goto next; case SOUTH : if (y == 9 || maze[x][y + 1] != 0) break; maze[x][y++] |= SOUTH; maze[x][y] |= NORTH; goto next; case WEST : if (x == 0 || maze[x - 1][y] != 0) break; maze[x--][y] |= WEST; maze[x][y] |= EAST; goto next; case EAST : if (x == 9 || maze[x + 1][y] != 0) break; maze[x++][y] |= EAST; maze[x][y] |= WEST; goto next; } /* if here... no place to go */ if (x == 9) { x = 0; if (y == 9) y = 0; else y++; } else x++; while (maze[x][y] == 0) { if (x == 9) { x = 0; if (y == 9) y = 0; else y++; } else x++; } continue; next : n--; } printf("\n\n"); } void printmaze(void) { int i, j; printf("+"); for (i = 0; i < 10; i++) printf("-+"); printf("\n"); for (i = 0; i < 10; i++) { printf("|"); for (j = 0; j < 10; j++) if (maze[j][i] & EAST) printf(" "); else printf(" |"); printf("\n+"); for (j = 0; j < 10; j++) if (maze[j][i] & SOUTH) printf(" +"); else printf("-+"); printf("\n"); } } void main(void) { generate(); printmaze(); } It generates a 10x10 maze with bits set on each int in the maze array indicating openings in that direction (the #defines list what bits coorespond to what direction). This is a interesting little algorithm in that it only generates one solution to a maze, though it may not be the most effeicent. Yes, I know there is a goto in the code, but, like I said, I just played one day on how to generate a maze and came up with this, it was just a quick hack :) It's written in portable ANSI C, except for the random() function I think. I'm using Turbo C under MSDOS and it has a random function. random() is a macro defined as: #define random(n) (rand() % (n)) So all it does is take the value from the rand() function (which returns 0 to 32767) and mods it to the range n. So random(10) will return a random number from 0 to 9. Have fun. Dave Kirsch -- a563@mindlink.UUCP
smarison@hawk.ulowell.edu (Dr. oTTo) (09/07/89)
Does anyone have any good random maze generators written in C? I'm writing a program and need to generate a random maze but I have no idea how to do it. -Scott
leipold@eplrx7.UUCP (leipold) (09/08/89)
smarison writes: > Does anyone have any good random maze generators written in C? I'm > writing a program and need to generate a random maze but I have no > idea how to do it. The following code generates a spanning tree maze, which by definition has only one solution. It cops out and uses a simple 'printer-plot' output format -- the original I wrote for the Macintosh included Mac graphics and a little 'snake' which crawled through the maze to solve it... --Walt L. --------------- #include <math.h> #include <stdio.h> #include <strings.h> #define MAXROW 12 #define MAXCOL 18 #define WALLUP 1 #define WALLDOWN 0 #define min(a,b) (a)<=(b) ? (a) : (b) #define max(a,b) (a)>=(b) ? (a) : (b) int right[MAXCOL][MAXROW], down [MAXCOL][MAXROW]; main () /* generate spanning tree maze */ { int row,col; NewMaze(&col,&row); MakeMaze(1,1,col,row); BreakDown(0,1,1,1); BreakDown(col,row,col+1,row); ShowMaze(1,1,col,row); } NewMaze(xmax,ymax) int *xmax,*ymax; { int i,j; *xmax = MAXCOL-1; *ymax = MAXROW-1; for (i=0; i<=*xmax; i+=1) for (j=0; j<=*ymax; j+=1) { right[i][j]=WALLUP; down [i][j]=WALLUP; } for (i=0; i<=*xmax; i+=1) right[i][0]=WALLDOWN; for (j=0; j<=*ymax; j+=1) down[0][j]=WALLDOWN; } MakeMaze(xa,ya,xb,yb) int xa,ya,xb,yb; { int x0,x1,x2,x3,y0,y1,y2,y3; int RandBetween(); x1=min(xa,xb); y1=min(ya,yb); x2=max(xa,xb); y2=max(ya,yb); if (x1==x2 && y1==y2) return; else if ((x2-x1)+(y2-y1) == 1) BreakDown(x1,y1,x2,y2); else if (x2-x1 > y2-y1) { x3 = RandBetween(x1,x2-1); MakeMaze(x1,y1,x3,y2); MakeMaze(x3+1,y1,x2,y2); y0 = RandBetween(y1,y2); BreakDown(x3,y0,x3+1,y0); } else { y3 = RandBetween(y1,y2-1); MakeMaze(x1,y1,x2,y3); MakeMaze(x1,y3+1,x2,y2); x0 = RandBetween(x1,x2); BreakDown(x0,y3,x0,y3+1); } } ShowMaze(x1,y1,x2,y2) int x1,y1,x2,y2; { int i,j; char rt[256],dn[256]; for (j=y1-1; j<=y2; j+=1) { strcpy(rt,"\0"); strcpy(dn,"\0"); for (i=x1-1; i<=x2; i+=1) { strcat(rt,(right[i][j] == WALLUP) ? " 00" : " "); strcat(dn,(down [i][j] == WALLUP) ? "0000" : " 00"); } printf("%s\n",rt); printf("%s\n",dn); } } BreakDown(x1,y1,x2,y2) int x1,y1,x2,y2; { if (x1 == x2) down[x1][y1] = WALLDOWN; else if (y1 == y2) right[x1][y1] = WALLDOWN; } int RandBetween(n1,n2) int n1,n2; { return n1 + (abs(random()) % (n2-n1+1)); /* assumes 'random' returns 15-bit random number */ } -- "As long as you've lit one candle, Walt Leipold you're allowed to curse the darkness." (leipolw%esvax@dupont.com) --
userAKDU@ualtamts.BITNET (Al Dunbar) (09/14/89)
In article <757@eplrx7.UUCP>, leipold@eplrx7.UUCP (leipold) writes: >smarison writes: >> Does anyone have any good random maze generators written in C? I'm >> writing a program and need to generate a random maze but I have no >> idea how to do it. > >The following code generates a spanning tree maze, which by definition >has only one solution. ... > >--Walt L. > >--------------- A theoretical question: is this algorithm complete, or is there at least one maze that it is unable to generate, regardless of the contrariness of the random number function? The algorithm says: "To make a maze out of an array of closed cells: 1) divide it into two adjacent sub- arrays separated by a common wall chosen at random; 2) make each sub- array into a maze; 3) connect the two mazes by removing one of the segments of the wall separating them." Any maze produced this way will be spanned in one direction by one straight wall containing only a single break. Using trial and error, I have as yet been unable to devise a maze that did not have this property, but somehow it doesn't seem likely to be impossible. Can anyone prove this either way? /Al Dunbar
fisher@sc2a.unige.ch (Markus Fischer) (09/19/89)
In article <14777@swan.ulowell.edu>, smarison@hawk.ulowell.edu (Dr. oTTo) writes: > Does anyone have any good random maze generators written in C? You want a maze ? Here is one: char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C); -- E; J[ E] =T [E ]= E) printf("._"); for(;(A-=Z=!Z) || (printf("\n|" ) , A = 39 ,C -- ) ; Z || printf (M ))M[Z]=Z[A-(E =A[J-Z])&&!C & A == T[ A] |6<<27<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];} It works, too ! The program first pauses to have you enter the number of lines of maze you want, then goes about to write it (on 79 char). Ah, before i forget: the left shift of the rand() function is implementation specific. Correct it if needed... (where? on the bottom left corner :-) NOTE: This aMAZEing program isn't mine, it's just the source on which I learned C for the first time (indentation and comments came later :-). As a rough guess, this *must* be the winner of an `obfuscated c code contest' some years ago, but i got this without reference... If the author is listening, congratulations and apologies ! Markus
perry@ccssrv.UUCP (Perry Hutchison) (09/21/89)
In article <127@sc2a.unige.ch> fisher@sc2a.unige.ch (Markus Fischer) writes: >You want a maze ? Here is one: <7 lines of utterly incomprehensible code mercifully omitted> YIKES!!! >It works, too ! Accidents happen. > this *must* be the winner of an `obfuscated c code contest' Yes, I suppose so (GROAN) If you ever get tired of comp.sources.misc and want the moderator to resign, I suppose you could try submitting this. :-)