Thread: Jumping into C++ Chapter 14, exercise 6.

Hi, in Jumping into C++, chapter 14, exercise 6 asks for building a maze, and then ensuring that it has a valid path.

Building a maze is simple, here's the code:

Code:

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


using namespace std;
char GetChar(char &MazeChar);




int h;
int w;


char MazeChar;
int main()
{


    srand(time(NULL));
    cout << "Type in height of the maze: \n";
    cin >> h;
    cout << "Type in width of the maze: \n";
    cin >> w;
    char **Maze = new char*[h];

// filling the two-dimensional array with values
    for (int i = 0; i < h; i++)
    {
        Maze[i] = new char[w];
    }


    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            GetChar(MazeChar);
            Maze[i][j] = MazeChar;
        }
    }
// printing the maze
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cout << Maze[i][j];
        }
        cout << "\n";
    }


}
// code to get either " " or "X" and doing it randomly
char GetChar(char &MazeChar)
{
    int CaseNr = 0;
    CaseNr = rand() % 2;
    switch (CaseNr)
    {
        case 0:
            MazeChar = ' ';
            break;
        case 1:
            MazeChar = 'X';
            break;
    }
}

It works, I can print a randomly generated maze

The maze: This program just prints some "spaces" and "X" characters in a two-dimensional array. X characters are the walls, and the maze is to go throught the spaces. Of course there's space between every line, but going horizontally through the space between the lines aren't allowed. Only going through ' ' characters is allowed.

But, how can I ensure that there's a valid path?

I tried putting this code after line 42 (before the printing loop), so that the program draws a valid path through the maze before printing the maze:

Code:

    int SP;
    SP = rand() % w;
    Maze[0][SP] = ' ';


    int CaseNr = 0;
    int ph = 0;
    int pw = SP;


    while(ph != h)
    {
    CaseNr = rand() % 4;
    switch(CaseNr)
    {
        case 0:
            if(ph == h){break;}
            ph = ph + 1;
            Maze[ph][pw] = ' ';
            break;
        case 1:
            if(ph == h){break;}
            ph = ph + 1;
            Maze[ph][pw] = ' ';
            break;
        case 2:
            if(pw == 0){break;}
            pw = pw - 1;
            Maze[ph][pw] = ' ';
            break;
        case 3:
            if(pw == w){break;}
            pw = pw + 1;
            Maze[ph][pw] = ' ';
            break;
        }
    }

Putting this code didn't work, the program just crashes, and I don't know why.

But, how can I ensure that there's a randomly generated but valid path?

I don't know how the author or some experienced programmer would solve this exercise.

What I tried to do is to:
1. put a random walls into a two-dimensional array.

2. make some changes so that the random-pattern has at least one valid path through it. I tried to make the program draw a randomly-generated valid path through the 2D-array, by moveing through the array and remove the walls (assign spaces) until reaching the last row of the array.

3. Printing the 2D array.

Here's the actual question, from "Jumping Into C++", Chap. 14, page 197:
6. Write a program that takes a width and a height and dynamically generates a maze with the given width and height. The maze must always have a valid path through it (how can you ensure this?). Print the maze to the screen once it’s been generated.

I think I see what you're up to. You want random walls so that it's maze-like to some degree. Then you want to drill a path through it to ensure that there's a path. I suppose that might kind of work.

In that case, look at your path-drilling code. Presumably you didn't mean for the first two cases to be identical. Fixing up that code a little:

Code:

int SP = rand() % w;  // starting position in top row
Maze[0][SP] = ' ';
 
int ph = 0;
int pw = SP;
 
while (ph < h - 1) {
    switch (rand() % 4) {
    case 0:
        if (ph > 0)
            ph--;
        break;
    case 1:
        if (ph < h - 1)
            ph++;
        break;
    case 2:
        if (pw > 0)
            pw--;
        break;
    case 3:
        if(pw < w - 1)
            pw++;
        break;
    }
    Maze[ph][pw] = ' ';
}

I don't see offhand why that would segfault (EDIT: spotted it!), although I don't think it's going to drill a very satisfying path since it's essentially undergoing Brownian motion.

Some maze generating algorithms are shown here: https://en.wikipedia.org/wiki/Maze_generation_algorithm. Unless the author of your book has covered something similar to those techniques, I'm not really sure what he expects you to do. Maybe your technique is appropriate.

EDIT: The upper bounds need to be compared to one-less-than the sizes.
EDIT2: I forgot to subtract 1 from the while loop condition, too.