Search code examples
c++algorithmrecursionmatrixmaze

Maze generation algorithm design (Recursive Division)

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.

Solution

  • 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

    3x3 thin maze

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

    5x5 thick maze

    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