A few years ago one of my winning entries in the International
Obfuscated C Code Contest generated and let the user solve a 3D maze.
The program below is not obfuscated, and it only generates a 2D maze,
but it illustrates the principle.
The idea is to start with a solid area of wall and then tunnel out the
passageways. From a given point, it tries in a random order to tunnel
in each of the four directions. If it succeeds, it digs a tunnel to
that neighboring location and stores the direction it used to get to
that location, and then continues to tunnel from that new location.
When it gets to a point where it can't tunnel in any direction, it
uses the direction to back out to its previous location. It is not
recursive, like many maze generating programs. It stores it's stack
inside of the maze. The resulting maze could be used to generate a
bitmap image. In this case I just output a text representation.
Don
===========================================================
#include <stdio.h>
#include <time.h>
unsigned int rnd()
{
static unsigned int x = time(0);
x = 63663*(x&65535) + (x>>16);
return x&65535;
}
int main()
{
// Size should be odd
const int size = 199;
char m[size][size];
int i,j,d,x,y,tmp,order[4] = {0,1,2,3};
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
enum markers { passage=4, start=5, wall=6 };
// Fill area solid
for(i = 0; i < size; ++i)
for(j = 0; j < size; ++j)
m[i][j] = wall;
for(i = 0; i < size; ++i)
m[i][0] = m[0][i] = m[i][size-1] = m[size-1][i] = passage;
// Select starting location
i = j = (size/2) & 0xfffe;
m[i][j] = start;
// Dig tunnels
while(1)
{
// Permute directions
for(x = 1; x < 4; ++x)
{
y = rnd() % (x+1);
tmp = order[x];
order[x] = order[y];
order[y] = tmp;
}
// Try directions in selected order
for(d = 0; d < 4; ++d)
{
x = dir[order[d]][0];
y = dir[order[d]][1];
if (m[i+2*x][j+2*y] == wall)
{
m[i+x][j+y] = passage;
i += 2*x;
j += 2*y;
m[i][j] = order[d];
break;
}
}
// Nowhere to go. Back out.
if (d == passage)
{
x = m[i][j];
m[i][j] = passage;
if (x == start) break; // Done
i -= 2*dir[x][0];
j -= 2*dir[x][1];
}
}
// Start and end
m[2][1] = m[size-3][size-2] = passage;
// Print result
for(i = 0; i < size; ++i)
{
for(j = 0; j < size; ++j)
printf("%c", (m[i][j] == wall) ? '#' : ' ');
printf("\n");
}
return 0;
}
On Jan 29, 6:51 pm, Dave <[email protected]> wrote:
> Does anyone have any ideas about how to generate mazes? I'd like an
> algorithm that can make many different mazes, maybe using a random number
> generator. Each maze should be guaranteed to have one and only one solution.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
