Maze Generator

    #include <cstdlib>
    #include <iostream>
    #include <time.h>

    using namespace std;

    struct tile{

        bool exit;
        tile* west;
        tile* north;
        tile* east;
        tile* south;

        tile(){
            exit = false;
            west = NULL;
            north = NULL;
            south = NULL;
            east = NULL;
        };
    };

    class maze{

    private:


        static const int max_height = 10;
        static const int max_width = 10;

        tile new_maze[max_width][max_height];

    public:

        maze(){
            init_class_vars();
        };


        static void init_class_vars(){

            static bool first_run = false;

            if(!first_run){
                first_run = true;
                srand(time(NULL));
            };

        };

        //generate maze
        void generate_maze(){
            int x;
            int y;

            for (x = 0; x < max_width; ++x){
                for (y = 0; y < max_height; ++y){
                    make_exit(x, y);
                };
            };

            do {
                reset_exit();           //assume you can't reach any tile
                run_maze(0, 0);         //run the maze starting at 0, 0

            } while (!check_maze());    //check to make sure you can reach all tiles
                                        //if not, this function will make a needed exit
                                        //and try again.
        };

        //output maze to console
        void output_maze(){
            int x;
            int y;

            string row1;
            string row2;
            string row3;

            for (y = 0; y < max_height; ++y){
                for (x = 0; x < max_width; ++x){
                    row1 = row1 + static_cast<char>(219);
                    row3 = row3 + static_cast<char>(219);
                    if(!new_maze[x][y].north){
                        if(x == 0 && y == 0){
                            row1 = row1 + ' ';
                        } else {
                            row1 = row1 + static_cast<char>(219);
                        }
                    } else {
                        row1 = row1 + ' ';
                    };

                    if(!new_maze[x][y].south){
                        if(x == (max_width - 1) && y == (max_width - 1)){
                            row3 = row3 + ' ';
                        } else {
                            row3 = row3 + static_cast<char>(219);
                        };
                    } else {
                        row3 = row3 + ' ';
                    };

                    if(!new_maze[x][y].west){
                        row2 = row2 + static_cast<char>(219);
                        row2 = row2 + ' ';
                    } else {
                        row2 = row2 + "  ";
                    };

                    if(!new_maze[x][y].east){
                        row2 = row2 + static_cast<char>(219);
                    } else {
                        row2 = row2 + ' ';
                    };

                    row1 = row1 + static_cast<char>(219);
                    row3 = row3 + static_cast<char>(219);
                };
                row1 = row1 + '\n';
                row2 = row2 + '\n';
                row3 = row3 + '\n';

                cout<<row1<<row2<<row3;
                row1.clear();
                row2.clear();
                row3.clear();
            };
        };

    private:

        //make an exit on a floor tile if one does not already exist.
        bool make_exit(int x, int y){

            if(!new_maze[x][y].exit){
                new_maze[x][y].exit = true;
                switch (select_direction(x, y)){
                    case 0:  //north
                        new_maze[x][y].north = &new_maze[x][y - 1];
                        new_maze[x][y - 1].south = &new_maze[x][y];
                        make_exit(x, (y - 1));
                        break;
                    case 1:  //south
                        new_maze[x][y].south = &new_maze[x][y + 1];
                        new_maze[x][y + 1].north = &new_maze[x][y];
                        make_exit(x, y + 1);

                        break;
                    case 2: //east
                        new_maze[x][y].east = &new_maze[x + 1][y];
                        new_maze[x + 1][y].west = &new_maze[x][y];
                        make_exit((x + 1), y);

                        break;
                    case 3: //west
                        new_maze[x][y].west = &new_maze[x - 1][y];
                        new_maze[x - 1][y].east = &new_maze[x][y];
                        make_exit((x - 1), y);
                        break;
                    default:
                        cout<<"Error! direction not recognized!\n";
                        break;
                };

            };



        };

        //reset all the exits to false
        void reset_exit(){
            int x;
            int y;

            for (x = 0; x < max_width; ++x)
                for (y = 0; y < max_height; ++y)
                    new_maze[x][y].exit = false;
        };

        //run the maze.  Leave a marker in every tile you visit
        void run_maze(int start_x, int start_y){
            run_maze(new_maze[start_x][start_y]);
        };

        //run the maze, set every tile you visit to true.
        void run_maze(tile &current_tile){

            if(!current_tile.exit){

                current_tile.exit = true;

                if(current_tile.north){
                    run_maze(*current_tile.north);
                };

                if(current_tile.east){
                    run_maze(*current_tile.east);
                };

                if(current_tile.south){
                    run_maze(*current_tile.south);
                };

                if(current_tile.west){
                    run_maze(*current_tile.west);
                };

            };
        };

        //Check to make sure every tile has an exit.
        //if we find tiles that cannot be reached, force an exit in the area
        //and return false

        //if all tiles have an exit, return true.
        bool check_maze(){
            int x;
            int y;

            for (x = 0; x < max_width; ++x){
                for (y = 0; y < max_height; ++y){
                    if(!new_maze[x][y].exit){
                        while(!force_exit(x, y, select_direction(x, y)));
                        return false;
                    };
                };
            };

            return true;
        };

        //force an exit in an area that we can't reach after the maze is initally
        //generated.
        bool force_exit(int x, int y, int direction){
            switch(direction){
                case 0: //north
                    while(!new_maze[x][y].exit && y != 0){
                        --y;
                    };

                    if(new_maze[x][y].exit){
                        new_maze[x][y].south = &new_maze[x][y + 1];
                        new_maze[x][y + 1].north = &new_maze[x][y];
                        return true;
                    } else {
                        return false;
                    };
                    break;
                case 1: //south

                    while(!new_maze[x][y].exit && y != (max_height - 1)){
                        ++y;
                    };

                    if(new_maze[x][y].exit){
                        new_maze[x][y].north = &new_maze[x][y - 1];
                        new_maze[x][y - 1].south = &new_maze[x][y];
                        return true;
                    } else {
                        return false;
                    };
                    break;

                case 2: //east

                    while(!new_maze[x][y].exit && x != (max_width - 1)){
                        ++x;
                    };

                    if(new_maze[x][y].exit){
                        new_maze[x][y].west = &new_maze[x - 1][y];
                        new_maze[x - 1][y].east = &new_maze[x][y];
                        return true;
                    } else {
                        return false;
                    };
                    break;
                case 3: //west

                    while(!new_maze[x][y].exit && x != 0){
                        --x;
                    };

                    if(new_maze[x][y].exit){
                        new_maze[x][y].east = &new_maze[x + 1][y];
                        new_maze[x + 1][y].west = &new_maze[x][y];
                        return true;
                    } else {
                        return false;
                    };
                    break;
                default:
                    cout<<"Error in force_direction! direction "<<direction<<" unknown!\n";
                    return false;
            };
        };

        //select a direction.  If you cannot travel in that direction, pick a new
        //direction.
        int select_direction(int x, int y){

            int direction;

            //0 = north
            //1 = south
            //2 = east
            //3 = west

            while (true){
                direction = rand() % 4;

                switch(direction){
                    case 0: //north
                        if(y != 0)
                            return direction;
                        break;
                    case 1: //south
                        if(y != (max_height - 1))
                            return direction;
                        break;
                    case 2: //east
                        if(x != (max_width - 1))
                            return direction;
                        break;
                    case 3: //west
                        if(x != 0)
                            return direction;
                        break;
                    default:
                        cout<<"Error in select_direction! Direction "<<direction<<" unknown!\n";
                };
            };
        };



    };

    int main(int argc, char *argv[])
    {
        maze my_maze;
        my_maze.generate_maze();
        my_maze.output_maze();

        system("PAUSE");
        return EXIT_SUCCESS;
    }