How to create a maze: part 1 of 2

Author: Danijel Korzinek

I. Random maze generator

First let me explain the procedure this program uses:

• first it initializes and reads the appropriate arguments (size of the maze)
• it creates some graphic stuff and the main maze array. It also creates two “coord” objects called beginning and end (they are not important for this first program, but are required for the game).
• then it starts the main algorithm
• after the algorithm finished it’s work it runs the draw_maze() procedure that translates the series of numbers into a picture of the maze.
• finally the maze is showed on screen and the program waits for ‘esc’ to be pressed.
• after the ‘esc’ being pressed the program de-initializes, meaning it clears all the graphic stuff and deletes the maze (frees the memory)

The drawing procedure works like this:

• it scans the maze array and puts a colored square for each number in that array (for example: yellow for zero[floor], gray for one[wall]). Eventually you can add more numbers and more colors (this will be useful for the maze solving algorithm later)
• optionally you can also add another smaller square that will be drawn on the position given as an argument of the function (this is useful for determining the position of the player in the maze game; I’ll explain it later)

Now for the algorithm:

• the main algorithm starts by cleaning the maze array (from all the trash it may contain). It also draws the outer walls.
• next it searches the random start and goal positions. They are leveled to have equal odds on their randomness, but can only be placed on coordinates that consist of odd numbers (I’ll explain this later).
• now the real algorithm starts. First it finds a random legal move and makes it (moves the position coordinate to that place, sets the cell to floor and sets the walls behind that cell)
• then it enters the loop which it repeats until the counter tells him he filled the whole map (the counter is always right)
• it finds the next legal random move and if such exists he repeats the whole procedure (move pos., set floor, set walls)
• if no legal move found it makes a back step and keeps tracing back until it finds an empty space two cells away from the one he is currently pointing to (in other words, an empty cell over the wall)
• if he finds such a cell he moves the position coord on the wall separating him from that cell and turns it to a floor. The normal loop is continued.

Explaining the code:

To explain the first part of the tutorial, we are going to use the file called mazefull.cpp (this was my final result of several attempts to create the program). First let’s explain the included files (using the #include directive):

• iostream.h - this is the C++ version of stdio.h. In my program, it is used to print error messages (for further details check some ‘iostream’ and file I/O tutorials). NOTE: if I were to run this program as it is (with only the basic arguments) these error messages would be printed out on screen. I use a simple stream re-direction by adding “>>log.txt” after the program name, making it print out its messages to a text file. I don’t know where does this method originate from, but I saw it work on Linux so I tried in DOS and it also worked…
• allegro.h - this is the header of the graphics library I intend to use during this tutorial. It will be used on two occasions in the first program: upon initialization of the graphics and in the drawing procedure called draw_maze()… If you re-implement these two parts of the code to another library, you may comment-out (or even delete) both this directive and parts of the code you’ve replaced.
• stdlib.h - needed for random number generator and integer to ASCII and vice versa conversions (srandom(), random(), itoa(), atoi()).
• time.h - also needed for random numbers.

Also on the beginning of the file we see the directives that define the maximum screen resolution (if you are using Win2k or WinNt and compile this in Allegro, change this to 320×200 so Allegro could chose standard VGA drivers, as Win2k and WinNt don’t support Vesa). We also see definitions of “floor” and “wall” which makes our program easier to read (the char array is filled only with numbers, 1 and 0). The first part of the file looks like this:

#include
#include
#include
#include

//resolution:
#define maxx 1024
#define maxy 768
#define wall 1 //int value of wall on map
#define floor 0 //int value of floor on map

The next part of the program is a definition of a class called “coord”. For those that don’t know, a class is a special structure that lets us define a variable that holds several other variables and functions that change these variables (so called “member” variables and functions). For detailed description of classes I recommend reading a tutorial, because classes are something every intermediate programmer should know inside out. To access these variables-inside-variables we will first have to create the so-called object (defined a simple variable, but using that class as the type; that’s why that type of programming is called Object Oriented programming) and access its members by writing them after a dot, which is after the name of the object. Like so:

coord CoordinateA; //defining an object
CoordinateA.x=0; //accesing the member variable "x"
CoordinateA.ret(0,-1);//accesing the member function "ret()"

The coordinate class is very useful, cause not only does it hold two different coordinates (which prevents us for defining ugly variables like: int pos_x, pos_y), but it also provides a couple of very useful functions for conversion and automation of the values of those variables. This makes our code more logical and much more readable. The full definition of the class is as follows:

//Coordinate class. Has x and y coordinates and some helper functions..
class coord
{
public:
int x,
y;

coord(): x(0), y(0) {} //empty constructor (used to show a NULL coordinate)
coord (int a, int b): x(a), y(b) {}//integer constructor
coord (const coord &c)//copy constructor
{
x=c.x;
y=c.y;
}

~coord(){} //empty destructor
void setW(char* maze, int n) //sets a coord in a given maze to wall
{ maze[x*n+y]=wall; }

void setF(char* maze, int n) //sets a coord in a given maze to floor
{ maze[x*n+y]=floor; }

coord ret(int x_of, int y_of) //returns a coordinate after vector change
{ return coord(x+x_of,y+y_of); }

int m_pos(int n) //returns te coord. as an index in the maze
{ return x*n+y; }

operator int ()//int converter (used to determine NULL coordinates)
{return int(x+y); }
};

// Some small helper functions:
int operator!=(coord a, coord b)//unequal operator for coordiates
{
return (a.x==b.x && a.y==b.y)?0:1;
}

int operator==(coord a, coord b)//equal operator for coordinates
{
return (a.x==b.x && a.y==b.y)?1:0;
}

I have added the first two helper functions on purpose, because they are operators that operate on the object of type “coord” (which is our class). Let me explain the class now. As we can see its contents are pretty straightforward. All the members are public, which means that they can be accessed from any part of the program with no limitations.

The members are: two integer variables (x and y coordinates) and a couple of functions that deal wit those variables. First three functions have no return type and carry the name of the class itself. They are so-called constructors. Each time an object (variable) of type “coord” is created a corresponding constructor is run. They are usually used to initialize values, but are also used for type-casting (if we want for example, to change a value of two integers to a “coord” we can just run coord(10,20) which will create a “coord” object without using a variable). I will mention the use of constructors when it appears in the program. Also, it is important to notice that there are three constructors. We can do that due to function overload (in other words, you can define any value of functions with the same name as long as they have different arguments).

The first constructor creates an empty coordinate, which is useful for us in two cases. First, when we declare an object and not bother initializing it with any values (like coord a,b,temp; and so on). The second time we use this constructor is when we want to inform our program that a certain coordinate is not valid. Because the cell at coordinate 0, 0 is always set to wall at the beginning of the program (before the start of the algorithm) and is never accessed after that, we are allowed to use that value as a type of NULL coordinate. Another thing we can do is adding the two values of a coordinate and if they equal zero then we are sure that we are dealing with our NULL coordinate (no other coordinate, when summed gives zero). As you may have noticed, the last member function of our class is an integer type converter (a special function that converts a coordinate to an int. To activate it all we have to do is write int(coord(20,30)) or (int)coord(20,30)). These two functions put together give us an easy way to deal with invalid values. For example, if we give our program to find the next random move and there is no such move, all that such a function has to do is return a coord() (empty coordinate) and all we have to do is check whether the (int)r (if r is the returned coord value of the function) is non-equal to zero. If it’s true, then we can use that coordinate. If not we have to find another way around. This is just a simple trick. Of course there are other ways to do that, but this seems good enough to me (both in code readability and program efficiency).

The second constructor takes two integers as arguments. It is used when we want to create an object and initialize it with some sensible values (like coord a(10,10), b(100,9); and so on). It can also be used to send values directly as objects of type coord without using variables (like a = coord(10,10); or some_function(coord(10,10));)

The last constructor is a special type of constructor and is used when we want to transfer a value of one object of type coord to another (like a = b; where both a and b are of type coord). It is also used in our last example where we sent a direct value to a variable: a = coord (10,10);. So first the int and then the copy constructor is used. Actually, this last constructor is used very often and until I have defined it my program behaved pretty weird, although it compiled and runned just as though nothing was wrong.

The function declared as a constructor, but with a tilde is called a destructor (you can only have one of those). As you probably figured out, it is activated upon deletion of an object. Mine is empty, as I have nothing to “destruct”, but if I had, for example created an array (using new or malloc) in any of my constructors I would have to delete it in my destructor (using delete or free).

The next two functions are here just for clearness. We could write maze[some_coordinates]=floor/wall; each time in our code, but this just looks simpler. We only have to write: coord_object.setW(maze, size);.

The ret function returns a coordinate object with the values of arguments given to that function added to the values of the coordinates in the active object. So if we want to check what is the coordinate of the cell to the left of the cell pointed currently by our a object, all we have to do is write a.ret(-1,0);. It may seem useless, but usually we don’t know the coordinates of a variable (because it is a variable, it varies) and want to check all the surrounding coordinates of that variable, we just can’t use any other method (actually we can, but that would be way to complicated). We are going to use this function allot, especially in the next_move, backspace_move, set_walls and other functions.

The m_pos function is used to return a value of the coordinates as a single integer, in a system that is used in a maze array. That just shortens our writing so instead writing maze[a.x*n+a.y] we write maze[a.ret(n)] and achieve the same effect.

The last function in the class definition block is the int operator. It is used to convert the value of coord to int. The purpose of this function has already been explained together with the empty constructor, so I’ll just skip it here.

There are still two more functions that need to be explained. They are equal and unequal operators. It is very important to define them (just like the copy constructor) because the program might behave strangely, even though it would run. The reason is, because the program would use, for example the int converter prior to comparing the two coordinates, which would result in comparing the sum of those coordinates instead of their real values.

Thus we have reached the end of our class definition and we are left with two more simple functions. The first just returns a random value between a and b (including both numbers) and the second informs us weather a certain given integer is odd (one for yes, zero for no). That one is used in the find_next_move(); function. I’ll explain it there. Here is the following part of the code:

int number_range(int a, int b) //genearte a random number in the set of
{ return a+(random() % (b-a+1)); }

int odd(int x)//tells if the given integer is odd
{ return (x % 2);}

In the next part of the code there are a couple of declarations of functions that are defined bellow the main():

// Globals
BITMAP *buffer;//graphic memory buffer
int counter(0);//needed to determine end of algorythm

//Function declarations
//Main functions:
void draw_maze(BITMAP* dest, char* maze, int n); //draws a maze as a picture
void generate_maze(char* maze, int n, coord &beg, coord &end); //generates maze as a number array
//Helper functions:
coord find_next_random_move(coord pos, char* maze, int n); //finds next legal random move starting from a given position
void set_walls(coord c_old, coord c_new, char* maze, int n); //sets walls from the given position
coord find_backspace(coord old, coord pos, char* maze, int n); //finds next legal backwards move from the given position
coord find_thin_wall(coord pos, char* maze, int n); //finds a wall (if there is one) he can brake to reveal empty space

First let’s mention the two very important globals. The first is the “bitmap”, or a graphic memory buffer. It is a part of Allegro library, so I won’t bother explaining the details. The second global variable is the counter. It is a very important variable because it tells our algorythm when to stop. It is global because it needs to be accessed from different parts of the program from different functions. We coud send it to every function as an argument, but that only complicates our work. It is very important, however to remember to use our counter, cause if we forget to set it up correcty or decrease it when it is needed, our program might never end. I haven’t had much problems with this, so I’ll just mention it when it appears in the program.

Now for the functions. The first one is a graphic function called draw_maze(). I mentioned it already, a couple of times so I won’t go int details again. It only changes the maze array, which is a set of numbers, to an mage and stores it in a graphical bitmap. If you decide to rewrite the code to work with some other graphics library, this would be the only function you’d have to change.

The second function is the function that holds our main algorithm. It is run from the program main() with an already initalized maze, its size and the two significant coordinates (used in the game example, so I’ll skip those now) as the arguments.

The rest of the functions are helper functions run only by the algorithm itslef (to shorten the code). They are the functions that find the next and backwards legal random move, sets the walls after a move has been done and find a wall that can be broken in case there is no other legal way of generating the maze.

The next part of the program is the main():

// main program:
int main(int argc, char** argv)
{
if(argc!=2)//Argument check...
{
cout<<"Argument error..."< <<"mazefull.exe [size] >>log.txt”< return -1;
}

int size=atoi(argv[1]);//reads the size variable from argument
if(size<5) size=5;//it is best if size of maze is bigger than five
if(!odd(size)) size++;//size should also be an odd number

cout <<"Starting program..." << endl;
counter = (size-2)*(size-2);//calculating counter from size

// Maze array:
char* maze;
maze = new char[size*size];

coord beg,end; //begining and end coord. (used to print to screen)
cout<< "GENERATE MAZE:"<< endl;

// My main algorythm:
generate_maze(maze,size,beg,end);
cout << " END GENERATE MAZE..." << endl;

This is the first half of the main. It initializes the values and generates the maze. The second part deals with the graphics. As you can see, this program takes arguments. It takes exactly one argument, which is the size of the maze. That size is odd and bigger than five. After the size variable set we can set the counter. The size of the counter is the amount of the empty cells inside the outer border (the outer border is the wall set on the first and last rows and columns of the maze), so its size is the amount of cells, minus first and the last, squared. Next the maze array is created. I used a char (on byte size), but if I wanted to save the maze to a file I’d put the value of each cell to a single bit (in the end each cell holds a value of one for a wall, or a zero for the floor). The beginning and end coordinates are also created, because we will later print their values to the log. After everything is prepared the main maze generating function is run.

cout << "Initializing Allegro..." << endl;
//Allegro init. routines...
allegro_init();
install_keyboard();

set_color_depth(32);
if(set_gfx_mode(GFX_AUTODETECT,maxx,maxy,0,0)<0)//setting graphics
{
cout << "Error setting graphics: " << allegro_error << endl;
return -2;
}

cout << "Alegro initialized..." << endl
<<" Prepearing scene..." << endl;

buffer = create_bitmap(maxx,maxy);//creating mem. buffer
clear(buffer);

draw_maze(buffer,maze,size); //Draws the array to the mem. buffer:

blit(buffer,screen,0,0,0,0,maxx,maxy); //Copies the buffer to screen...

cout << "Scene prepared..." << endl;
cout << "Begining coordinates: x=" << beg.x << " y=" << beg.y << endl;
cout << "End coordinates: x=" << end.x << " y=" << end.y << endl;

while(!key[1]);//Wait for ESC pressed…
cout << "Shutting down..." << endl;

//Freeing memory:
destroy_bitmap(buffer);
delete [] maze;

allegro_exit();//Usefull thing to do...
cout << "Finished succesfully..." << endl;
return 0;
}

This, second part of the main function is purely user-interface. We start with initializing Allegro, keyboard and graphics. After that we create the memory graphics buffer, use the draw_maze function upon it and blit the result to screen. Then the program waits for ESC key to be pressed (”esc” is 1 in scancode). We could alter this while loop to run anything else (and we will, in the game and solver program). After ESC being pressed the program frees up memory (very important!) and closes up…

I think this function is pretty simple to understand and there is nothing more I could add to it.

The next part of our code is the function definitions (from the declarations above). The first one is the draw_maze function:

//Some colors:
#define wall_c makecol32(125,125,125)
#define wall_c2 makecol32(0,0,0)
#define floor_c makecol32(255,255,150)
#define empty_c makecol32(255,255,255)

//Draw maze array to graphic memory buffer...
//(dest - mem.buffer, maze - maze array, n - size of maze array)
void draw_maze(BITMAP* dest, char* maze, int n)
{
int w = dest->w,//gets size of mem. bufer
h = dest->h;
coord b,l;//begining and length coords on mem. buffer
b.x=w/8;//this is where our maze will begin
b.y=h/8;
l.x=((3*w)/4)/n;//this is the length(size) of each cell
l.y=((3*h)/4)/n;

int i,j;//some temp variables
for(i=0; i for(j=0; j {
if(maze[i*n+j]==1)//if current cell is a wall
{
rectfill(dest,b.x+i*l.x,b.y+j*l.y,b.x+(i+1)*l.x,b.y+(j+1)*l.y,wall_c);
rect(dest,1+b.x+i*l.x,1+b.y+j*l.y,b.x+(i+1)*l.x-1,b.y+(j+1)*l.y-1,wall_c2);
}
else if(maze[i*n+j]==-1)//if it is empty (used for debug pourposes, but shouldn't usually occur)
rectfill(dest,b.x+i*l.x,b.y+j*l.y,b.x+(i+1)*l.x,b.y+(j+1)*l.y,empty_c);
else /*maze[i*n+j]==0*/ //if it is a floor
rectfill(dest,b.x+i*l.x,b.y+j*l.y,b.x+(i+1)*l.x,b.y+(j+1)*l.y,floor_c);
}
}

We start off by defining some often-used colors. The wall_c is used as the wall background, wall_c2 as the wall border, floor_c as floor color and empty_c as a debug color. The function takes three arguments, graphic memory buffer, maze array and maze size. Next it reads the size of the memory buffer (screen resolution, this method is specific to Allegro). After that it creates and initializes two coordinates. The first one holds the beginning of the maze on screen (it is independent of screen resolution) and the second holds the length and width of each cell (independent of resolution and maze size). Next it scans through the whole maze array and draws a rectangle filled with color corresponding to each number in the array. The coordinates of each rectangle is determined using the formula: begining_of_maze + index_of_cell * length_of_cell. And that’s about it.

The next function is the most important function in the whole program. In the first part of the function two things are initialized: the array is cleared and the beg/end positions are determined:

//The heart of the program:
//MAZE GENERATING ALGORYTHM
//(maze-maze array, n-size of maze array, beg/end-coordinates)
void generate_maze(char* maze, int n, coord &beg, coord &end)
{
int i,j;
cout << "clearing surface" << endl;
//Clearing surface
for(i=1; i<(n-1); i++)
for(j=1; j<(n-1); j++)
maze[i*n+j]=-1;//Sets interior to empty
//making outer walls
for(i=0; i<2; i++)
for(j=0; j maze[i*(n-1)*n+j]=wall;//Makes walls around everything
for(i=0; i for(j=0; j<2; j++)
maze[i*n+j*(n-1)]=wall;//Here same as above...

srandom(rawclock());
cout << "setting begining and end" << endl; //Looking for begining and end

beg.x=number_range(1,3);
switch(beg.x)
{
case 1:
beg.x=0;
beg.y=1+2*number_range(0,(n-3)/2);//only odd ones
break;
case 2:
beg.x=1+2*number_range(0,(n-3)/2);
beg.y= (n-1) * number_range(0,1);
break;
case 3:
beg.x=n-1;
beg.y=1+2*number_range(0,(n-3)/2);
}

end.x=beg.x;
while(end.x==beg.x || end.y==beg.y)
{
end.x=number_range(1,3);
switch(end.x)
{
case 1:
end.x=0;
end.y=1+2*number_range(0,(n-3)/2);
break;
case 2:
end.x=1+2*number_range(0,(n-3)/2);
end.y= (n-1) * number_range(0,1);
break;
case 3:
end.x=n-1;
end.y=1+2*number_range(0,(n-3)/2);
}
}

//Sets beg/end to floor:
maze[beg.x*n+beg.y]=floor;
maze[end.x*n+end.y]=floor;

In the beginning everything is set to -1 (empty). Then the outer-most cells are set to 1(wall) so we don’t walk outside the array. The second “for” loop sets the left and right-most columns and the third loop sets the upper and bottom rows. Next we seed the random number generator. The beg/end coordinates are found in such a way, so that there are equal odds on every position all over the maze (this can lead to strange results; even if both coordinates cannot be on the same wall-side, it happens they end up very close to each other making the solving trivial). First it looks for a random number between one and three. If it gets one he sets himself somewhere on the left wall, if he gets three he sets up on the right wall and if he gets two he sets somewhere on the upper or bottom walls. I think the same code is used in the maze screensaver i talked about :-). In the next part of the code begins the algorithm, the heart, brains and centre of the program (the rest of the code serves this part, the rest are just helpers, this is most important):

//HERE BEGINS THE FUN PART:
cout << "starting algorythm:" << endl;
coord pos, //current position
t,//temp var. one - used to retrieve next move
t2,//temp var. two - used to retrieve backspace move
t3;//temp var. three - used to hold old move (backspace procedure)

pos=end;//set postion to end //we move from end to begining making the maze harder
t=find_next_random_move(pos, maze, n);//speaks for itslef
pos=t;//it's okay to make first move
pos.setF(maze,n);//set that to floor
counter--;//decrement counter!
cout << "." << flush;

//MAIN LOOP:
do
{
t=find_next_random_move(pos, maze, n);//find next move
if(!(int)t)//if no such move is possible
{
t3=t2=pos;
while(!(int)t)//while no escape possible
{
t3=t2;
t2=find_backspace(pos,t2,maze,n);//find a way back
if(!(int)t2) t2=t3;//if stuck
if(t2.x<=0 || t2.x>=(n-1) || t2.y<=0 || t2.y>=(n-1)) t2=t3;//avoids leaving the maze
pos=t3;
cout<<"B"< t= find_thin_wall(pos,maze,n);//looks if there is a way out through a wall
if((int)t)//if so
{
pos=t;//set current position to that wall
pos.setF(maze,n);//brake it!
cout << "X" << flush;
}
}
}
else//if we have a free next move (normal procedure)
{
set_walls(pos,t,maze,n);//set walls around the old position
pos=t;
pos.setF(maze,n);//set floor to new pos.
counter--;//decrease counter!
cout << "." << flush;
}
}
while(counter);//does the loop while we still have something to build...

//Here ends all
cout << endl;
return;
}

It starts with defining four coordinate objects we are going to use to point towards different cells in the maze array. The pos coordinate will be our primary pointer. It will always point towards the cell we are currently standing on and we will use it to change those cells to wall or floor. The other three coordinates are temporary and will be used as helpers (the code gets a bit messed up with all these stupid names, but I’ll try to keep it as clear as possible). Now for the algorithm:

First we are on the end coordinate (this makes the maze harder to solve). Then we find the next legal random move and store its coordinate to “t”. The “t” pointer will be like a stick, with which we will check if we can make a move or not (the function may return NULL if no legal move exists). Since this is our first move we are sure we can make it so we set the “pos” to “t” (make a step forward), set the ground below us to floor (it was empty before), decrease the counter (very important!) and print a dot to the log. Congratulations, we just made our first step!

Next we enter the loop, which ends only when counter has reached zero. We poke for the next step (find next legal move and store it to “t”). If such move exists (function returned a non-zero coordinate) we move to the “else” statement. Inside we first build the walls from where we are standing (the method will be explained later), then make a step forward (move “pos” to “t”), set the floor, decrease the counter, print a dot. This procedure will be repeated until we find ourselves in the situation where no other legal move exists (we close ourselves up).

In case the function find_next_random_move(), fails to find us a legal move we enter the program block just after if(!(int)t). Here things get a bit more complicated as we have to introduce two more pointers. The “t2″ pointer will be used as a lead. That means it will always point to the next backspace move. To avoid going back-and-forth over and over again, such a variable is required, so we can send both “t2″ and “pos” to the function which will pick such a move that’s next to “t2″, but different from “pos” (I repeat, “t2″ is always in front of “pos”). The “t3″ variable is going to store the value of “t2″ in case the “backspace” function returns a zero-coordinate. In such case “t2″ is allowed to go back the same way it came. Afterwards “pos” receives the position of “t3″ (or old “t2″) and “B” (for backspace) is printed to log. There is also one more “if” statement which prevents our pointers from leaving the maze.

After the backspace has been made we use “t” (our poker) to check if the behind any of the walls there is some empty cells. If so, we walk inside such a wall (move “pos” to newly acquires “t”) and crush it :-). We print an “X” for each wall being smashed. From here we exit the “backspace loop” and resume finding next moves and setting floors and walls. If we, however don’t find a “thin wall” the “backspace” loop will repeat itself until such a wall is found…

This algorithm will first draw a random hall, then when it gets stuck it’ll go a couple of steps back, then find a thin wall, an continue making another hall. After most of the maze is filled, it will start tracing back looking for last few empty cells (resulting in lots of “B” in the log). Because this back step is fully random, we can’t really determine, when the algorithm ends (it may be one second, it may be ten years, no one knows), but usually it is a couple of seconds for n=100, which is already a very hard maze. Anyway, I like this code cause it always gives a different maze and this maze is always perfect (no empty cells, only one solution, no closed paths, no circular paths, no double walls etc.). Of course, there are a couple of other things we must take care of before we get such a maze and they are situated in the helper functions, so without further ado:

The first helper function is called find_next_random_move:

//Helper functions:
//Find next random move:
//(pos-current position, maze-maze array, n-size of maze)

coord find_next_random_move(coord pos, char* maze, int n)
{
coord m[3];//Possible moves…
int i(0);//Counter of legal moves
//Checks if given moves are legal
if(maze[(pos.ret(-1,0)).m_pos(n)]==-1 && pos.x>0
&& (odd(pos.y) || maze[(pos.ret(1,0)).m_pos(n)]==floor))//this is a rather complicated condition…
{
m[i]=pos.ret(-1,0);
i++;
}
if(maze[(pos.ret(1,0)).m_pos(n)]==-1 && pos.x<(n-1)
&& (odd(pos.y) || maze[(pos.ret(-1,0)).m_pos(n)]==floor))
{
m[i]=pos.ret(1,0);
i++;
}
if(maze[(pos.ret(0,-1)).m_pos(n)]==-1 && pos.y>0
&& (odd(pos.x) || maze[(pos.ret(0,1)).m_pos(n)]==floor))
{
m[i]=pos.ret(0,-1);
i++;
}

if(maze[(pos.ret(0,1)).m_pos(n)]==-1 && pos.y<(n-1)
&& (odd(pos.x) || maze[(pos.ret(0,-1)).m_pos(n)]==floor))
{
m[i]=pos.ret(0,1);
i++;
}

if(i==0) return coord();//If no legal move found return NULL coord
return m[number_range(0,i-1)];//Else return a random one from the legal ones
}

As arguments it takes our current position, the maze array and its size. What it actually does is look in all four possible directions and if the conditions are met it chooses a random one of them. Now, what are the conditions: first it has to be an empty cell (-1). To check this we use a structure like this: maze[(pos.ret(x_off, y_off)).m_pos(n)]==whatever;. This may look complicated, but it’s actually not. First we have pos coordinate on which we activate the ret() member function, which returns another coordinate (or “pos” after a vector change; check class definition for details), then we take that coordinate and return its value as an index of the maze (using m_pos()). All that is inside maze array’s brackets, so it just sets the pointer to a certain cell in the maze array.

Second thing we have to check is if we are inside the maze (who knows what is outside of the maze; without this our program could wander around our memory for ages, building mazes in forbidden space, until the computer crashed…). The last condition took me some time to write, but finally I managed. Its goal is to make a clean maze by making it impossible to change direction of the hall (for example if it was going up, to suddenly turn left) on even rows/columns. That means that he cannot make a turn on two cells (making a double wall), or make stairs (going constantly left and up, for example) which can make problems (closed, unreachable empty spaces, algorithm gets stuck, exits are not on clean, requires cleaning up after the main algorithm), but with this tiny correction our program will run smooth and clean. If you don’t believe me try deleting this condition, but make some kind of emergency exit out of the program, cause it may enter an infinite loop. This condition is made on the following way: it has equal rights as other conditions (the first two conditions and this, in the brackets, are separated with an AND operator, which means all those conditions have to be met). The condition in the brackets consists of two more conditions separated by OR operator, which means only one has to be met, but if neither are met the logical value is false. Those two conditions are: first we are in an odd row/column and second this move is not a change of direction. Read again if you are not sure of this, but then I wasn’t also for some time :-).

If a condition is met for a certain direction/move (there are four of them) then we add that move to a move array (that’s prepared on the beginning of the function) and a counter is increased. If the counter is still zero after all conditions checked, that means no move is possible (the function returns an empty coordinate). If the counter is positive, then we choose a random position of the move array and return that. It’s a neat trick and I’ll use it again in this program…

The next helper funtion is called set_walls(). It’s pretty longish, but don’t worry. I used copy paste to create it. It could look better, but I didn’t bother as it was fast enough:

//Sets walls....
//(c_old-walls are made around this point
// c_new-walls are made from this perspective maze-maze array, n-size of maze)
void set_walls(coord c_old, coord c_new, char* maze,int n)
{
int t;
if((c_new.x-c_old.x)==1)//Checks the position of two coords in relation to each other
{
t=(c_old.ret(0,-1)).m_pos(n);//Finds where to put first wall
if(maze[t]==-1)//If that place is empty….
{
maze[t]=wall;//Put a wall here
counter–;//Decrease counter! (very important)
}
t=(c_old.ret(0,1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(-1,0)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(-1,-1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(-1,1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
return;//Exit function here (no need to to other checks)
}
if((c_old.x-c_new.x)==1)
{
t=(c_old.ret(1,0)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(0,-1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(0,1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(1,1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(1,-1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
return;
}

if((c_new.y-c_old.y)==1)
{
t=(c_old.ret(0,-1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(-1,0)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(1,0)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(-1,-1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(1,-1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
return;
}

if((c_old.y-c_new.y)==1)
{
t=(c_old.ret(0,1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(-1,0)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(1,0)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(-1,1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
t=(c_old.ret(1,1)).m_pos(n);
if(maze[t]==-1)
{
maze[t]=wall;
counter–;
}
return;
}
}

As you have noticed, this function takes two pointers: one for where we currently stand and the other for where we want to go. What it does is it makes a “U” shaped wall “behind” the “new” pointer and “around” the “old” pointer. To me it looked as the simplest method to deal with the problem. There are four different directions for the “U” shape and five different walls to be set for each “U” shape (remember you can’t put a wall on a place where already something exists) hence the length of the code. But it’s nothing too serious.

I don’t think that there is anything more to be said for this fragment of the code except that it’s VERY important to decrease our counter for each wall set.

The next function is similar to “find_next_move” function. It is called find_backspace():

//Finds a good way back:
//(old - a place we came from [no reason to go back there]
// pos - a place we are know on
// maze-maze array, n-size of maze)
coord find_backspace(coord old, coord pos, char* maze, int n)
{
coord t,//used for clearness
m[4];//Possible moves

int i(0);//Counter of legal moves
t=pos.ret(0,-1);
if(maze[t.m_pos(n)]==floor && t!=old)
{
m[i] = t;
i++;
}
t=pos.ret(0,1);
if(maze[t.m_pos(n)]==floor && t!=old)
{
m[i] = t;
i++;
}
t = pos.ret(1,0);
if(maze[t.m_pos(n)]==floor && t!=old)
{
m[i] = t;
i++;
}
t = pos.ret(-1,0);
if(maze[t.m_pos(n)]==floor && t!=old)
{
m[i] = t;
i++;
}
if(i==0) return coord();
return m[number_range(0,i-1)];
}

The only difference is that it takes two pointers as arguments and has only two conditions. Number one, we are looking for a floor (not empty) and number two, the new move has to be different from the old (to avoid moving back and forth, check main algorithm for details).

The last function is also similar to “find_next_move” and is called find_thin_wall():

//Finds a wall one could brake to discover empty space from the other side...
coord find_thin_wall(coord pos, char* maze, int n)
{
coord m[4];//Possible walls
int i(0);//Counter of legal ones
if(maze[(pos.ret(-2,0)).m_pos(n)]==-1
&&pos.x>1)//so it wouldn’t break open the maze
{
m[i]=pos.ret(-1,0);
i++;
}
if(maze[(pos.ret(2,0)).m_pos(n)]==-1 && pos.x<(n-2))
{
m[i]=pos.ret(1,0);
i++;
}
if(maze[(pos.ret(0,-2)).m_pos(n)]==-1 && pos.y>1)
{
m[i]=pos.ret(0,-1);
i++;
}
if(maze[(pos.ret(0,2)).m_pos(n)]==-1 && pos.y<(n-2))
{
m[i]=pos.ret(0,1);
i++;
}
if(i==0) return coord();
return m[number_range(0,i-1)];
}

It’s even simpler than the others cause the only thing it has to check is if two cells away from the current spot there is some empty space. If so it sets a pointer to a wall separating out current position from empty space (there is always a wall separating a floor and empty space, if no legal move is possible) and then it returns that pointer.

This is it when for the first part of the tutorial titled “How to make a random maze generator”. You can run it and see if you like it. If you have any comments mail them to me, please. Now, stay tuned for the next part entitled:

Tags: Allegro, game, maze