OT: Maze Generator Update

Since my QC (venus) website is no longer active, I thought I'd put the files for a maze generator some place where they can be accessed, especially since I have received emails about it... Here is the original information that was on venus before it disappeared:

Maze Generator Using Disjoint Sets

I recently went through several files of mine that had been stored away from my undergrad days. So I thought I might share them. Someone might like them. I have not changed any of the code since it was first written. I have only changed the formatting of a couple of files to make them easier to read and modified the comment header slightly (also for readability). Everything is well commented, which was my style at the time :-) Hopefully I have not erased anything important as I was doing these modifications, but I have no patience to test it at the moment. Oh, and I added a GPL for my code only, just in case (though no one will really want this... :-P )

This particular project is from Prof Stewart Weiss' CS 335 class, and consisted of writing a program that would generate mazes. It was compiled under Visual Studio 6.0 C++. We had studied Disjoint Sets in our class and were allowed to use code from Mark Allen Weiss' book from which we were studying. In addition to printing out to a text file, for extra credit we could output a graphical representation of the maze. For this I used code from Owen L. Astrachan's book which I think is from CMU Graphics. Two example outputs can be seen below:

Other outputs include (for the two unknowns,
sorry I forgot what I punched in and have no patience to create more
mazes or count cells):
• 5X5.txt
• 25X40.txt
• 40X30.txt
• unknown dimensions 1
• unknown dimensions 2

The idea is fairly simple. The maze is broken up into cells. We will use the idea of disjoint sets: in the beginning each cell is in its own set. Cells are randomly chosen to remove a wall (and one of the four walls is also randomly chosen) and as the wall is removed, the cell and its new neighbor are then placed in the same set. You keep doing this until all cells are within the first (entry) cell's set. At this point you have a maze.

You should make sure that once a cell is in the main (entry cell's) set, it should
never be picked again to remove wall. You also have to be careful not
to remove the outer border walls, thus creating alternate exits :-)

The disjoint sets class was modified from the original given in the book. There was a problem with the find() function so it was changed. Also, I added extra functions to make it fit with the maze class. I also created a vector of cells for the maze (see Cell class and Maze class below). I would have done things differently if I were doing writing this now, but this was in the beginning of my programming experience.

Here are the disjoint sets files
• DisjSets.h
• DisjSets.cpp

I created a Cell class to represent each cell of the maze. This way I could control the walls of the cells and keep track of which walls were still up or down when I printed out the maze.

Here are the Cell class files
• Cell.h
• cell.cpp

Next I wrote a Maze class to keep track of all of the cells. At first I thought to implement this using a 2-dimensional array, but ultimately decided to use a linear vector (defined in DisjSets) folded onto itself. There is also a list used to contain all cells of the maze. This is not the maze itself, but rather the cells that have not yet been placed into the main set in order to create a maze. I did this to cut down on run time because you do not want to remove walls from cells that have already become part of the main set and randomly picking cells most likely leads to picking cells that have already been chosen (especially towards the end). So keeping a pool of possible choices was the only logical thing to do to cut down on run time.

Here are the Maze class files
• maze.h
• maze.cpp

Now for the main part of the program. At the time I was obsessed
with making the main() function as small as possible:

int main(){
    string resp;

    while(true){

        getMazeInfo();

        cout<<"To quit press 'q', otherwise press a key"<<endl;
        cin>>resp;

        if(resp=="q")
            break;

    }//end while

    return 0;

Granted it could have been smaller... :-) It basically loops forever creating mazes of whatever size (I think 50x60 is the max) is requested and stops when the user wants to leave. The code is NOT perfect. Just glancing over ASSN3Main.cpp, I see a buffer overflow error could occur in the getMazeInfo() function. Plus there were better ways now of dealing with the graphics. (Yes I COULD fix it, but then I would find other things and before you know it this would explode into a full time project...Ok. Maybe I'm exaggerating). Perhaps some day when I have more time I will rewrite this little application. It's kinda fun to create mazes...

The main code:
• ASSN3Main.cpp

I am releasing all of the code in gzip files as well as a precompiled executable. You can use 7zip to open the files. If you use the executable, you will see a message box saying something about how this was compiled with the student version and can't be used as commercial software or some such. Just push Ok and you're set. After you input the dimensions and the name of the output file to which you would like the maze saved, a graphical window will pop up. Click it with the mouse and the maze should display. You have to push ESC to get out of the graphical maze window.

• maze-allcode.tgz
• maze-exe.tgz

Hopefully I have managed to include all of the code that is needed. Let me know if something is missing.