Maze generation algorithm design (Recursive Division)

Question

I am trying to include a maze generation in my pathfinding visualization solution in order to generate mazes on what the current application can work on.

I found a very well structured website, there are bunch of maze generation algorithms, but I primarily focused on one: http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm

My programming language knowledge is mostly C++ and the application that I have is built with that + SDL2.0.

My "grid" (2D matrix) is made of "cells/nodes" represented by box textures rendered on the window surface. Where each "cell" can be in different states - obstacle == it's a wall - white state == it's passage.

What I face as an issue is that my "passage" is sometimes blocked by the next wall generated at random - which leads to unsolvable maze.

The question is how to avoid a wall that is generated to not block a previously opened passage?

CODE:

void RecursiveDivision::divide(NodesMap* map, int x, int y, int width, int 

height, Orientation orientation, SDL_Renderer* renderer)
{
    if (width < 2|| height < 2)
    {
        return;
    }

    bool wallIsHorizontal = orientation == Orientation::Horizontal ? true : false;

    //Where the wall is
    int wX = x  + (wallIsHorizontal ? 0 : rand() % (width-1));
    int wY = y + (wallIsHorizontal ? rand() % (height-1): 0);
    //Where the passage is
    int pX = wX + (wallIsHorizontal ? (rand() % width) : 0);
    int pY = wY + (wallIsHorizontal ? 0 : (rand() % height));
    //How long is the wall
    int wallLenght = (wallIsHorizontal ? width : height);
    //On whitch axis will the wall be drawn
    int dX = wallIsHorizontal ? 1 : 0;
    int dY = wallIsHorizontal ? 0 : 1;
    //Draw the wall
    for (int i = 0; i < wallLenght; ++i)
    {
        if (wX != pX || wY != pY)
        {
            map->getNode(wX, wY)->hardChangeState(NodeState::OBSTACLE);
        }
        
        wX += dX;
        wY += dY;
    }

    //Render the current state
    map->render(renderer, nullptr);
    SDL_RenderPresent(renderer);
    
    int nX = x; int nY = y;
    int w = wallIsHorizontal ? width : (wX - x);
    int h = wallIsHorizontal ? (wY - y ) : height;
    divide(map, nX, nY, w, h, chooseOrientation(w, h), renderer);

    nX = wallIsHorizontal ? x : (wX + 1);
    nY = wallIsHorizontal ? (wY + 1) : y;
    w = wallIsHorizontal ? width : (x + width - wX -1);
    h = wallIsHorizontal ? (y + height - wY-1 ) : height;
    divide(map, nX, nY, w, h, chooseOrientation(w, h),renderer);
}

Example:

2 step from the start of algorithm

Example - "finished maze" on 20x20 tile map:

Finished algorithm

Note

The screenshots you see are from separate run of the program, so they differ. I hope you can get the point.

what is the question? How to generate randomly the maze such that there is a possible solution? — 463035818_is_not_a_number
Yes, that is the question. How to avoid the blockage of the passages from the next wall that might be generated in such a way? — l000p
"What I face as an issue is that my "passage" is sometimes blocked by the next wall generated at random - which leads to unsolvable maze." Can you please show an example of such an invalid maze that was produced by your code? Actually, can you show an example of succession of mazes built by your algorithm by adding walls? — Stef
Edited. Screenshots from the problem in general and finished algorithm execution added. — l000p

Sho Sho · Accepted Answer · 2020-08-25T13:46:48

In contrast to the link you were inspired from, your walls take a space of one cell. The easiest way to avoid your problem would be that your walls can only be placed on one column/row out of two.

This is what would a maze with "thin walls" produce

And here's the equivalent with thick walls (what you're using)

As you can see, their grids don't have the same size, the first one is a 3x3, and the last is 5x5, without borders (edited since yours doesn't have borders).

You need to have a grid with odd sides. If it's based of a thin maze, make the sides 2 * n - 1 bigger, with n the length of the side of the thin maze*
Only place walls on odd numbered rows and colums (starting at index 0)
Place opening in walls on even numbered rows and colums

To resume, you can place walls

o o o o o
o o o o o <- here
o o o o o
o o o o o <- here
o o o o o
  ^   ^
here  here

(*) 2n - 1 is without borders, else use 2n + 1

How to implement this in your code:

    const int truewidth = (width-1)/2;
    const int trueheight = (height-1)/2;
    //Where the wall is
    int wX = x  + (wallIsHorizontal ? 0 : 2 * (rand() % (truewidth)) + 1);
    int wY = y + (wallIsHorizontal ? 2 * (rand() % (trueheight)) + 1: 0);
    //Where the passage is
    int pX = wX + (wallIsHorizontal ? 2 * (rand() % (truewidth)) : 0);
    int pY = wY + (wallIsHorizontal ? 0 : 2 * (rand() % (trueheight)));

/!\ untested yet

Maze generation algorithm design (Recursive Division)

1 Answers