1
\$\begingroup\$

I have made a random maze generator that allows for custom sizes via command arguments. It uses depth-first search and is written is C++. Could you look over my code and suggest any improvements possible?

/*
 * Maze Generator:
 *   Made by Jaden Peterson in 2016
 */

/*
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 * This program uses the Direct-First Search algorithm
 *   You can learn more about it at:
 *     https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search
 */

#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

#define UP    0
#define DOWN  1
#define LEFT  2
#define RIGHT 3

int maze_size[2];

int start_axis;
int start_side;

std::vector< std::vector< int > > dfs_path;

/*
 * Structure of the maze vector:
 *                     |--> Filled in?
 *   Row --> Collumn --|
 *                     |--> Has been visited?
 */
std::vector< std::vector< std::vector< bool > > > maze;

// Select a random direction based on our options, append it to the current path, and move there
bool randomMove(bool first_move){
    int random_neighbor;
    std::vector< std::vector< int > > unvisited_neighbors;

    for(int direction = 0; direction < 4; direction++){
        int possible_pmd[2] = {0, 0};

        if(direction == UP){
            possible_pmd[1] = -1;
        } else if(direction == DOWN){
            possible_pmd[1] = 1;
        } else if(direction == LEFT){
            possible_pmd[0] = -1;
        } else {
            possible_pmd[0] = 1;
        }

        if(dfs_path.back()[0] + possible_pmd[0] * 2 > 0 &&
           dfs_path.back()[0] + possible_pmd[0] * 2 < maze_size[0] - 1 &&
           dfs_path.back()[1] + possible_pmd[1] * 2 > 0 &&
           dfs_path.back()[1] + possible_pmd[1] * 2 < maze_size[1] - 1){
            if(!maze[dfs_path.back()[1] + possible_pmd[1] * 2]
                    [dfs_path.back()[0] + possible_pmd[0] * 2][1]){
                std::vector< int > possible_move_delta = {possible_pmd[0], possible_pmd[1]};

                unvisited_neighbors.push_back(possible_move_delta);
            }
        }
    }

    if(unvisited_neighbors.size() > 0){
        random_neighbor = rand() % unvisited_neighbors.size();

        for(int a = 0; a < !first_move + 1; a++){
            std::vector< int > new_location;

            new_location.push_back(dfs_path.back()[0] + unvisited_neighbors[random_neighbor][0]);
            new_location.push_back(dfs_path.back()[1] + unvisited_neighbors[random_neighbor][1]);

            dfs_path.push_back(new_location);

            maze[dfs_path.back()[1]][dfs_path.back()[0]][0] = false;
            maze[dfs_path.back()[1]][dfs_path.back()[0]][1] = true;
        }

        return true;
    } else {
        return false;
    }
}

bool validInteger(char* cstr){
    std::string str(cstr);

    for(char& c : str){
        if(!isdigit(c)){
            return false;
        }
    }

    return true;
}
// The fun part ;)
void generateMaze(){
    bool first_move = true;
    bool success = true;

    while((int) dfs_path.size() > 1 - first_move){
        if(!success){
            dfs_path.pop_back();

            if(!first_move && dfs_path.size() > 2){
                dfs_path.pop_back();
            } else {
                break;
            }

            success = true;
        }

        while(success){
            success = randomMove(first_move);

            if(first_move){
                first_move = false;
            }
        }
    }
}

// Initialize the maze vector with a completely-filled grid with the size the user specified
void initializeMaze(){
    for(int a = 0; a < maze_size[1]; a++){
        for(int b = 0; b < maze_size[0]; b++){
            bool is_border;

            if(a == 0 || a == maze_size[1] - 1 ||
               b == 0 || b == maze_size[0] - 1){
                is_border = true;
            } else {
                is_border = false;
            }

            std::vector< bool > new_cell = {true, is_border};

            if((unsigned int) a + 1 > maze.size()){
                std::vector< std::vector< bool > > new_row = {new_cell};

                maze.push_back(new_row);
            } else {
                maze[a].push_back(new_cell);
            }
        }
    }
}

void parseArgs(int argc, char* argv[]){
    bool width_found = false;
    bool height_found = false;
    int processing_number = -1;

    for(int arg = 1; arg < argc; arg++){
        if(processing_number > -1){
            if(validInteger(argv[arg])){
                maze_size[processing_number] = atoi(argv[arg]);

                processing_number = -1;
            } else {
                std::cerr << "'" << argv[arg] << "'" << " is not a valid integer." << std::endl;
                exit(1);
            }
        } else {
            if(!strcmp(argv[arg], "-w")){
                processing_number = 0;
                width_found = true;
            } else if(!strcmp(argv[arg], "-h")){
                processing_number = 1;
                height_found = true;
            } else {
                std::cerr << "'" << argv[arg] << "'" << " is not a valid argument." << std::endl;
                exit(1);
            }
        }
    }

    if(!width_found || !height_found){
        std::cerr << "You must specify the width and height with '-w' and '-h'" << std::endl;
        exit(1);
    }
}

void printMaze(){
    for(unsigned int a = 0; a < maze.size(); a++){
        for(unsigned int b = 0; b < maze[a].size(); b++){
            if(maze[a][b][0]){
                std::cout << "██";
            } else {
                std::cout << "  ";
            }
        }

        std::cout << std::endl;
    }
}

// Set a random point (start or end)
void randomPoint(bool part){
    int axis;
    int side;

    if(!part){
        axis = rand() % 2;
        side = rand() % 2;

        start_axis = axis;
        start_side = side;
    } else {
        bool done = false;

        while(!done){
            axis = rand() % 2;
            side = rand() % 2;

            if(axis != start_axis ||
               side != start_side){
                done = true;
            }
        }
    }

    std::vector< int > location = {0, 0};

    if(!side){
        location[!axis] = 0;
    } else {
        location[!axis] = maze_size[!axis] - 1;
    }

    location[axis] = 2 * (rand() % ((maze_size[axis] + 1) / 2 - 2)) + 1;

    if(!part){
        dfs_path.push_back(location);
    }

    maze[location[1]][location[0]][0] = false;
    maze[location[1]][location[0]][1] = true;
}

int main(int argc, char* argv[]){
    srand(time(NULL));

    parseArgs(argc, argv);

    // The width and height must be greater than or equal to 5 or it won't work
    // The width and height must be odd or else we will have extra walls
    for(int a = 0; a < 2; a++){
        if(maze_size[a] < 5){
            maze_size[a] = 5;
        } else if(maze_size[a] % 2 == 0){
            maze_size[a]--;
        }
    }

    initializeMaze();
    randomPoint(false);
    randomPoint(true);
    generateMaze();

    printMaze();

    return 0;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Don;t think it is ever necessary to mention "Cross-Platform" when talking about C++. Unless you are into very obscure optimizations or OS specific libraries its going to be cross platform and all the reviews are going to encourage you to use standard C++ features over platform specific hacks. \$\endgroup\$ – Martin York Jul 20 '16 at 23:51
6
\$\begingroup\$

OOPs

int maze_size[2];

int start_axis;
int start_side;

std::vector< std::vector< int > > dfs_path;

Global variables should be avoided, as they can easily conflict with variables added in other places and don't allow easy duplication. And they're easy to avoid in an object-oriented C++ program (OOP).

class Maze_Path {

    int maze_size[2];

    int start_axis;
    int start_side;

    std::vector< std::vector< int > > dfs_path;

So on and so forth. Then

int main(int argc, char* argv[]){
    srand(time(NULL));

    parseArgs(argc, argv);

    // The width and height must be greater than or equal to 5 or it won't work
    // The width and height must be odd or else we will have extra walls
    for(int a = 0; a < 2; a++){
        if(maze_size[a] < 5){
            maze_size[a] = 5;
        } else if(maze_size[a] % 2 == 0){
            maze_size[a]--;
        }
    }

    initializeMaze();
    randomPoint(false);
    randomPoint(true);
    generateMaze();

    printMaze();

    return 0;
}

becomes something like

int main(int argc, char* argv[]) {
    srand(time(NULL));

    Maze maze;

    maze.parseArgs(argc, argv);
    maze.normalizeSize();
    maze.initialize();

    maze.setStart(maze.selectRandomPoint());
    do {
        maze.setEnd(maze.selectRandomPoint());
    } while (maze.getStart() == maze.getEnd());

    Maze_Path path(maze);
    path.find();

    maze.print();
    path.print();
}

Note that I removed the argument from the function to select a random point. Now it just returns a point without any knowledge of how the point will be used. The setters handle assigning the point.

Although you might want to change some of that. For example, why is normalSize() done outside of parseArgs? Why have a separate initialize() step? Why have separate steps selecting the start and end?

Consider

int main(int argc, char* argv[]) {
    srand(time(NULL));

    Maze maze = Maze::parseArgs(argc, argv);
    maze.print();

    Maze_Path path(maze);
    path.find();
    path.print();
}

The Maze class knows how to parse arguments and create a maze. The path finding class knows how to do a depth first search (although it doesn't tell the caller that's what it is doing--we could switch to another search type with no one the wiser). Both know how to display themselves.

Now main isn't cluttered with all sorts of implementation details that callers shouldn't need to know. E.g. that heights and widths need to be odd numbers. Or that you need to parse, normalize, initialize the maze, and then choose endpoints--in that order. Why should a caller need to know that the random selection can choose the end to be the same place as the start?

And of course we got rid of the global variables. A side effect of this is that we could create and search more than one maze now. The original program only allowed for one.

A more advanced version might make the srand happen automatically in Maze and/or Maze_Path. Then the caller wouldn't even have to know that srand needed to be called. Making it only happen once is tricky though, so I won't try to get into that here. I just wanted to mention it, as the previous principles would suggest that we don't want to call srand from main.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.