How to ensure the Maze always has a valid path C++

Question

I am doing a practice problem from a book I am reading, the problem asks to generate a maze with a given height and width dynamically. This maze must always have a valid path as well. This is the part I am having problems with I can't figure out how I could ensure there will always be a valid path. This is my code, it generates a maze for example 10x10, 20x20, 30x30, etc. But sometimes there is no valid path. I tried to comment as much as I could to make it more readable since it is kinda messy. Thanks for any help you can provide.

#include<iostream>
#include<cstdlib>
#include<ctime>

int main()
{
int row, height; //declaring row and height int variables.
srand(time(NULL)); //seed for different random number;

std::cout<<"Enter row number: "; //prompts user for row number.
std::cin>>row;
std::cout<<"Enter height number: "; //prompts user for height number;
std::cin>>height;

char **maze; //declaring a pointer to a pointer named maze of type char.
maze=new char*[row]; //pointer points to a array of pointers.

for (int i=0;i<row;++i) //assigning an array to each pointer
{
    maze[i]=new char[row];
}

for (int i=1;i<row;++i) //creating random generation of maze * equal walls/borders.
{
    for (int j=1;j<height;++j)
    {
        int a=rand()%5+1; //if the random number divided by 2 does have a remainder than we place a blank space.
        if (a%2!=0)
        maze[i][j]=0;

        else    //otherwise we place a *, 42 is the ASCII code for *.
        maze[i][j]=42;
    }
}

//the code below creates the borders of the maze and guarantees that there is a exist and entrance to the maze.
//(Entrance is at the top, exit is at the bottom of the maze.
maze[0][0]=42;
maze[0][1]=0;

for (int i=2;i<=row;++i)
{
    maze[0][i]=42;
}

for (int i=1;i<height;++i)
{
    maze[i][0]=42;
}

for (int i=0;i<row;++i)
{
    maze[row-1][i]=42;
}

for (int i=0;i<height;++i)
{
    maze[i][height-1]=42;
}
maze[row-1][height-2]=0;

//This code prints the maze.
for (int i=0;i<row;++i)
{
    for (int j=0;j<height;++j)
    {
        std::cout<<maze[i][j];

    }
    std::cout<<"\n";
}

//deleting the maze freeing it from the heap.
for (int i=0;i<row;++i)
delete[] maze[i];

delete[] maze;


}

Answer 1

I know I am late on this post, but a better way would be to use recursion.

Have a function to find the starting and ending point of the maze to use for reference in the beginning and end.

Have another function that finds_next_move that is passed the array, x, and y, and possibly rows and cols. x and y are passed by reference.

Then another bool function to validate that the move is true. So it will try going straight, pass those parameters into the validate_move function and if it returns true then move that way, if false try the other directions.

Using if else here would work. Then in the if else statement increment your x or y variable accordingly. The validate_move function would only be called in the find_next_move function. Then loop through recursively through that until the solution is returned true.

But if you hit a dead end you will have to backtrack. so just add if statements for that too

You can also add a print function that is called when you move and in your previous spot it will print a trail for a solution, and if you have to backtrack then you can delete the trail.

Just some basic ideas I thought of :D

Answer 2

The best way to ensure that the path is there is put it there in the first place. Although previous solution: create the solution first and then use your algorithm will clearly work, it might create too easy maze.

Instead of this, take a look at already established algorithms to generate mazes.

Especially it makes sense to look at the application of Prim's and Kruskal's algorithm (at that wiki page) and think why exactly minimum spanning tree makes sense to generate mazes.

Answer 3

If you're looking for a coded solution then this answer is not for you. However, here are some ways you could accomplish the task.

---

Assumption:

This maze must always have a valid path as well.

This doesn't preclude the maze from having more than one solution.

---

Option A - Simple Brute Force

1. Generate a random maze
2. Test the maze for a solution
3. If there isn't a solution start again from #1

Option B - Create The Solution First

1. Create a start position
2. Create an end position
3. Create a random solution path from start to end
4. Randomly fill in the rest of the maze without modifying any locations already filled in
   • For example: Initialize the entire grid with a sentinel value (e.g., '#' which means it hasn't been filled in yet), these will be overwritten with a proper value when the solution is being created, lastly only these value may be overwritten when the maze is being randomly filled