User:Dllu/Maze
| This is a Wikipedia user page. This is not an encyclopedia article or the talk page for an encyclopedia article. If you find this page on any site other than Wikipedia, you are viewing a mirror site. Be aware that the page may be outdated and that the user in whose space this page is located may have no personal affiliation with any site other than Wikipedia. The original page is located at http://en.wikipedia.org/wiki/User:Dllu/Maze. |
Here is some C code for generating mazes! This code is capable of both using Prim's algorithm and depth-first search. The maze generator "grows" the maze until the counter for the number of "in" cells reaches the maximum possible. Note that my implementation of random cell selection in Prim's algorithm is extremely slow since it calls rand() something on the order of O(n3) times. I was too lazy to do that using more efficient means since this started out as a program that only uses backtracking. Backtracking is very fast, however.
This maze generator is somewhat unique in that it has a one layer "padding" of cells that are already marked as being in the maze even though they're not part of the maze. The reason for this is that when growing the maze, I don't have to separately check if we have reached the boundary.
If you have any comments or suggestions for improvement, please post it in the Discussion page!
//Purpy Pupple's amazing maze generator.
//Released under the CC-BY-SA 3.0 License and the GFDL
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define UP 0 //-y
#define DOWN 1 //+y
#define LEFT 2 //-x
#define RIGHT 3 //+x
#define OUTFILE "MAZE"
#define WHITE fprintf(outfile, "%c%c%c", 255,255,255)
#define BLACK fprintf(outfile, "%c%c%c", 0,0,0)
#define RED fprintf(outfile, "%c%c%c", 0,0,255)
#define nodeadend//generate a maze without any dead ends! (consequently, many solutions to maze)
//#define prim //enable this to generate mazes using prim's algorithm.
#define backtrack//enable this to generate mazes using depth-first search. Don't enable both.
//#define movie //this option spams bitmaps to illustrate each step of generation.
long numin=1; //Number of cells in the maze.
const int xsize=152;
const int ysize=122;
void initialize();
void generate();
void savebmp(int xspecial, int yspecial);
struct cell{
bool in; //Is this cell in the maze?
bool up; //Does the wall above this cell exist?
bool left;//Does the wall to the left of this cell exist?
int prevx, prevy; //The coordinates of the previous cell, used for backtracking.
};
cell MAZE[xsize][ysize];
int main(){
srand((unsigned int)time(NULL)); //seed random number generator with system time
initialize(); //initialize the maze
generate(); //generate the maze
#ifdef movie
for(int i=1;i<10;i++){
numin++;
savebmp(0,0); //output the bitmap
}
#else movie
savebmp(0,0);
#endif
return 0;
}
void initialize(){
//Initialize the maze!
for(int x=0;x<xsize;x++){
for(int y=0;y<ysize;y++){
//The maze cells on the edges of the maze are "in" to provide padding. Otherwise, all maze cells are not in.
MAZE[x][y].in = (x==0||x==xsize-1||y==0||y==ysize-1)?1:0;
//All maze cells have all walls existing by default, except the perimeter cells.
MAZE[x][y].up = (x==0||x==xsize-1||y==0)?0:1;
MAZE[x][y].left = (x==0||y==0||y==ysize-1)?0:1;
}
}
return;
}
void generate(){
int xcur=1, ycur=1;//start growing from the corner. It could theoretically start growing from anywhere, doesn't matter.
MAZE[xcur][ycur].in = 1;
int whichway;
bool success;
do{
#ifdef movie
savebmp(xcur,ycur);
#endif
#ifdef nodeadend
if( MAZE[xcur][ycur-1].in&&MAZE[xcur][ycur+1].in&&
MAZE[xcur-1][ycur].in&&MAZE[xcur+1][ycur].in ){
//If at a dead end, randomly destroy a wall to make it not a dead end!
do{
success=0;
whichway=rand()%4;
switch(whichway){
case UP:
if(MAZE[xcur][ycur].up&&ycur!=1){
success=1;
MAZE[xcur][ycur].up=0;
}
break;
case DOWN:
if(MAZE[xcur][ycur+1].up&&ycur!=ysize-2){
success=1;
MAZE[xcur][ycur+1].up=0;
}
break;
case LEFT:
if(MAZE[xcur][ycur].left&&xcur!=1){
success=1;
MAZE[xcur][ycur].left=0;
}
break;
case RIGHT:
if(MAZE[xcur+1][ycur].left&&xcur!=xsize-2){
success=1;
MAZE[xcur+1][ycur].left=0;
}
break;
}
}while(!success);
}
#endif
#ifdef backtrack
while( MAZE[xcur][ycur-1].in&&MAZE[xcur][ycur+1].in&&
MAZE[xcur-1][ycur].in&&MAZE[xcur+1][ycur].in ){
//If all the neighbourhood cells are in, backtrack.
int xcur2=MAZE[xcur][ycur].prevx;
ycur=MAZE[xcur][ycur].prevy;
xcur=xcur2;
}
#endif
#ifdef prim
do{
//randomly find a cell that's in the maze
xcur=rand()%(xsize-2)+1;
ycur=rand()%(ysize-2)+1;
}while(!MAZE[xcur][ycur].in ||
MAZE[xcur][ycur-1].in&&MAZE[xcur][ycur+1].in&&
MAZE[xcur-1][ycur].in&&MAZE[xcur+1][ycur].in);
#endif
do{
//Randomly grow the maze if possible.
success=0;
whichway=rand()%4;
switch(whichway){
case UP:
if(!MAZE[xcur][ycur-1].in){
success=1;
MAZE[xcur][ycur].up=0;
MAZE[xcur][ycur-1].prevx=xcur;
MAZE[xcur][ycur-1].prevy=ycur;
ycur--;
}
break;
case DOWN:
if(!MAZE[xcur][ycur+1].in){
success=1;
MAZE[xcur][ycur+1].up=0;
MAZE[xcur][ycur+1].prevx=xcur;
MAZE[xcur][ycur+1].prevy=ycur;
ycur++;
}
break;
case LEFT:
if(!MAZE[xcur-1][ycur].in){
success=1;
MAZE[xcur][ycur].left=0;
MAZE[xcur-1][ycur].prevx=xcur;
MAZE[xcur-1][ycur].prevy=ycur;
xcur--;
}
break;
case RIGHT:
if(!MAZE[xcur+1][ycur].in){
success=1;
MAZE[xcur+1][ycur].left=0;
MAZE[xcur+1][ycur].prevx=xcur;
MAZE[xcur+1][ycur].prevy=ycur;
xcur++;
}
break;
}
}while(!success);
MAZE[xcur][ycur].in=1;
numin++; //Every iteration of this loop, one maze cell is added to the maze.
}while(numin<(xsize-2)*(ysize-2));
#ifdef movie
savebmp(xcur,ycur);
#endif
return;
}
void savebmp(int xspecial, int yspecial){
//save a bitmap file! the xspecial, yspecial pixel is coloured red.
FILE * outfile;
int extrabytes, paddedsize;
int x, y, n;
int width=(xsize-1)*2-1;
int height=(ysize-1)*2-1;
extrabytes = (4 - ((width * 3) % 4))%4;
char filename[200];
sprintf(filename, "%s_%dx%d_n%d.bmp", OUTFILE, xsize, ysize, numin);
paddedsize = ((width * 3) + extrabytes) * height;
unsigned int headers[13] = {paddedsize + 54, 0, 54, 40, width, height, 0, 0, paddedsize, 0, 0, 0, 0};
outfile = fopen(filename, "wb");
fprintf(outfile, "BM");
for (n = 0; n <= 5; n++){
fprintf(outfile, "%c", headers[n] & 0x000000FF);
fprintf(outfile, "%c", (headers[n] & 0x0000FF00) >> 8);
fprintf(outfile, "%c", (headers[n] & 0x00FF0000) >> 16);
fprintf(outfile, "%c", (headers[n] & (unsigned int) 0xFF000000) >> 24);
}
fprintf(outfile, "%c", 1);fprintf(outfile, "%c", 0);
fprintf(outfile, "%c", 24);fprintf(outfile, "%c", 0);
for (n = 7; n <= 12; n++){
fprintf(outfile, "%c", headers[n] & 0x000000FF);
fprintf(outfile, "%c", (headers[n] & 0x0000FF00) >> 8);
fprintf(outfile, "%c", (headers[n] & 0x00FF0000) >> 16);
fprintf(outfile, "%c", (headers[n] & (unsigned int) 0xFF000000) >> 24);
}
//Actual writing of data begins here:
for(y = 0; y <= height - 1; y++){
for(x = 0; x <= width - 1; x++){
if(x%2 == 1 && y%2 == 1){
if(x/2+1 == xspecial && y/2+1 == yspecial) RED;
else{
if(MAZE[x/2+1][y/2+1].in) WHITE; else BLACK;
}
}else if(x%2 == 0 && y%2 == 0){
BLACK;
}else if(x%2 == 0 && y%2 == 1){
if(MAZE[x/2+1][y/2+1].left) BLACK; else WHITE;
}else if(x%2 == 1 && y%2 == 0){
if(MAZE[x/2+1][y/2+1].up) BLACK; else WHITE;
}
}
if (extrabytes){ // See above - BMP lines must be of lengths divisible by 4.
for (n = 1; n <= extrabytes; n++){
fprintf(outfile, "%c", 0);
}
}
}
printf("file printed: %s\n", filename);
fclose(outfile);
return;
}
Demonstration of capability
[edit]I also generated this extreme 2000x2000 maze which is so large (and has to be viewed at full size) that it makes no sense to view it as a thumbnail. The solution for that is here.
Other mazes
[edit]These mazes below were not generated by the above algorithm. Instead, they were made by a variant of Prim's algorithm with many starting points simultaneously. The multiple regions thus created are then linked together at different places. I made that older algorithm when I was 16 for my friend's computer science project. Unfortunately that friend didn't follow my instructions on submitting the project and got marks taken off for not compiling. Also, the code for that project is excessively verbose because the project requirements included a minimum number of lines of code. It is also very, very slow because of the same reason as I mentioned earlier about choosing cells in Prim's algorithm. So I'm too embarrassed to upload the source code for those.
 |
 |