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 -- a5...@mindlink.UUCP
-Scott
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%es...@dupont.com)
--
But now I have another question:
How do I check to see if a character has been entered on the keyboard,
and if so, how do I read just that character.
I need to know this since I'm working on a game.
thanks,
scott
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
>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. :-)