How to create a maze: part 2 of 2

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:

II. Maze game:

This part of the tutorial will tell you how to use the code above to create a game. It will deal with graphics, user interfaces, keyboard and mouse input and implementing a game loop. This stuff is very basic and most intermediate programmers will probably skip this, but beginners will most likely skip the generating part and jump right down here (which is okay by me).

Almost everything here will be written in Allegro, so if you don’t have it you probably won’t be able to compile the code. You can, however continue reading and, if you know anything else, you may be able to rewrite to some other game library. As I said, this will be pretty simple.

For all you that skipped the first part of the tutorial, in this part I will be telling you about how to use the code above (which we will copy to a header) in any other project, without knowing how it works.

The first thing we will do is copy almost everything from the mazefull.cpp file to a header we will call maze.h. I have already done this for you so here is its content:

#include
#include
#include
#include
#define wall 1 //number value of wall on map
#define floor 0 //number value of floor on map

//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
{
if(x<0) x=0;
if(x>=n) x=0;
if(y<0) y=0;
if(y>=n) y=0;
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;
}
int number_range(int a, int b) //genearte a random number in the set of
{ return a+(rand() % (b-a+1)); }
int odd(int x)//tells if the given integer is odd
{ return (x % 2);}

The beginning is practically the same. We have all the includes, defines and our “coord” class, but after that something is different:

//MAZE CLASS:
class maze_t
{
public:
int counter;//needed to determine end of algorythm
char* maze;//maze array
int n; //size of maze
coord beg, end;//start and finish coordinates of the maze
maze_t(int size);//does all the helpful initialization of maze array
maze_t();//creates an empty zero-size array (not usefull to anyone)
~maze_t();//deletes the maze array

#ifdef ALLEGRO_H
void draw(BITMAP*,coord);//draws a maze as a picture
#endif
void generate();//generates maze as a number array
char & operator[](coord pos)//returns a reference of a cell in the maze array
{ return maze[(pos.m_pos(n))]; }
private:
coord find_next_random_move(coord);//finds next legal random move starting from a given position
void set_walls(coord,coord);//sets walls from the given position
coord find_backspace(coord,coord);//finds next legal backwards move from the given position
coord find_thin_wall(coord);//finds a wall (if there is one) he can brake to reveal empty space
};

Instead of public functions and variables and needing to initialize the maze array and other stuff we made a simple class that will hold and deal all that. Now al we have to do is:

maze_t myMaze(size); //to create a maze object
myMaze.generate(); //to generate a maze
myMaze(memory_buffer, player_position); //to draw the maze
if(myMaze[coord(0,1)]==0) //to check a coordinate in the maze
{
myMaze[coord(1,2)]=1; //to set a value on a given coordinate
}


Plus we get easy access to useful information like:

myMaze.n; //size of maze
myMaze.beg; myMaze.end; //start and finish of the maze (worth looking at only after the "myMaze.generate();")
myMaze.maze[1]; //direct access to maze array
myMaze.counter; //access to “free cells in the maze” counter (important for maze generation!)

Warning: If you decide to change the maze manually, before it has been generated, remember to decrease the counter for each empty cell you change!

At first I tried to leave al the function global, as they were, and create another one, which will initialize (create) the maze, but I had only problems with this. After some time I came to this idea and it worked. Now the user of the header doesn’t need to bother creating and erasing the maze array (or setting the default values, such as the “counter”) because constructors and destructor take care of this. This made the functions also slightly simpler so for all interested, take a look at the function definition. I will, however, go through the rest of the game tutorial:

NOTE: It’s been a month since I last looked into this tutorial and if I don’t get any response on it I don’t know why I should continue. The biggest problem I have is deciding how detailed it has to be. Do I have to write for complete beginners or should I just mention the more important stuff. Compared to the first part I think that writing a game like I did doesn’t require much creativity and ideas. Anyone can do it as long as they have a good game library and understand the documentation. So I quit from further explaining of how to write a maze game unless some asks me to…

III. Maze solver:

NOTE: Like above, I won’t go in much detail, so if anyone’s interested, write to my e-mail address (author section)…

The procedure:

• Move forward through the maze. Mark the places you’ve visited.
• If you run into a pace with several possible paths choose a random one.
• If you reach a dead-end move backwards along the visited path until you reach a crossing where there are paths you haven’t visited. Mark the places you’ve double-visited.
• Choose the path you haven’t visited.
• If you reach the end finish the algorithm.

A better algorithm would be to move along the path (blocks with two surrounding blocks), remember the crossings (blocks with three or four surrounding blocks) and if you reach a dead-end (blocks with one surrounding block) you could jump to the last visited crossing and move from there on. You could also solve the last procedure recursively.

For everybody who want to read more about this topic I also recommend a book called: “Algorithmics. The Spirit of Computing.” by David Harel.

Downloads

Download maze.h - 14.9 Kb
Download maze_h_test.cpp - 0.59 Kb
Download mazefull.cpp - 16.7 Kb
Download mazegame.cpp - 4.59 Kb
Download mazsolve.cpp - 4.98 Kb

Tags: Allegro, game, maze