prim's algorithm generated maze missing walls

Question

So I'm implementing a maze generator using prim's algorithm. the maze itself generates pretty much fine, however two (touching) walls would always be missing.

the mazes I'm generating (the right and bottom walls are missing):

Maze 1

here the left and top walls are missing:

Maze 2

The code I use to generate the maze:

int _height = 50;
int _width = 50;
private bool[,] maze = new bool[_height, _width];


private void generateMaze()
{
    //_height = 50
    //_width = 50
    List<MazeCell> walls = new List<MazeCell>();
    int randX = genRand(1, _height-1);
    int randY = genRand(1, _width-1);
    maze[randX, randY] = true;
    MazeCell start = new MazeCell(randX, randY, null);

    for (int i = -1; i <= 1; i++)
    {
        for(int j = -1; j <= 1; j++)
        {
            if ((i == 0 && j == 0) || (i != 0 && j != 0))
                continue;
            try
            {
                if (maze[randX + i, randY + j])
                    continue;
            }
            catch(Exception e)
            {
                continue;
            }
            walls.Add(new MazeCell(randX + i, randY + j, start));
        }
    }

    while (walls.Count > 0)
    {
        int index = genRand(0, walls.Count - 1);
        MazeCell cur = walls[index];
        MazeCell op = cur.opposite();
        walls.RemoveAt(index);
        try
        {
            if(!maze[cur.x, cur.y])
            {
                if(!maze[op.x, op.y])
                {
                    maze[cur.x, cur.y] = true;
                    maze[op.x, op.y] = true;

                    for (int i = -1; i <= 1; i++)
                    {
                        for (int j = -1; j <= 1; j++)
                        {
                            if (i == 0 && j == 0 || i != 0 && j != 0)
                                continue;
                            try
                            {
                                if (maze[op.x + i, op.y + j])
                                    continue;
                            }
                            catch (Exception e)
                            {
                                continue;
                            }
                            walls.Add(new MazeCell(op.x + i, op.y + j, op));
                        }
                    }
                }
            }
        }
        catch (Exception e) { }
    }
}

private int genRand(int min, int max)
{
    Random rnd = new Random();
    return rnd.Next(min, max);
}

And the mazeCell class:

public class MazeCell
{
    public int x;
    public int y;
    public bool passage = false;
    MazeCell parent;

    public MazeCell(int x, int y, MazeCell parent)
    {
        this.x = x;
        this.y = y;
        this.parent = parent;
    }

    public MazeCell opposite()
    {
        if (x.CompareTo(parent.x) != 0)
            return new MazeCell(x + x.CompareTo(parent.x), y, this);
        if (y.CompareTo(parent.y) != 0)
            return new MazeCell(x, y + y.CompareTo(parent.y), this);
        return null;
    }
}

the code is an adaptation of java code I found here: http://jonathanzong.com/blog/2012/11/06/maze-generation-with-prims-algorithm

I can't find where it suddenly decides to remove walls. Any help is greatly appreciated!

When you have height and width of 50 does that include the right and bottom walls? If you index starts at zero then genRand(1, _height-1) and genRand(1, _width-1); are random. So you would need the height and width to be 50 + 1 and then put a solid wall at index 50 (both row and column). Or changes height-1 to height -2 as well as width- 1 to width - 2. then add solid wall to index 50 (row and column). — jdweng
@jdweng the 50 does include the walls, however the disappearing walls can also be the left and top walls, it seems completely random which of the two happens. I've updated the question with an example of both. — Alexander de Haan
BTW you shouldn't keep creating new instances of the Random class. Do it once and then use that instance over and over. That way you can also create it with a seed value when you want to test in a repeatable manner. — Ian Mercer
Instead of using an Exception to detect the case where op.x+i and op.y+j is outside the maze you should use an explicit comparison with the minimum and maximum bounds you want to use. This may be where your algorithm is leaking off into the border you want to maintain. It's also a really bad practice to catch all Exceptions like this, if it's an index exception you are looking for, use that instead. — Ian Mercer
@IanMercer after making the random a global variable and replacing all the try catch statements with comparisons, it still messes up the border. — Alexander de Haan

Ian Mercer Ian Mercer · Accepted Answer · 2020-05-10T21:23:58

I tried your code and if you move the new Random outside the method to a member variable (so it's created just once), then it seems to work just fine.

There is no code to ensure that there is a boundary around the edge of the whole maze: the maze will happily wander right up to any edge. What you are seeing is an artifact of non-randomness caused by resetting Random every time.

If set Random to the same seed over and over in that method I see long runs down two sides also.

Here's sample output for 15x15 with proper random values:

XXXXXXXXX X X X
X         X X X
X X XXXXXXXXXXX
X X X     X   X
XXXXXXXXX X X X
X X         X X
X XXX XXXXXXX X
  X   X   X   X
XXXXX X X XXX X
X     X X      
XXXXXXX X XXXXX
X X   X X X   X
X XXX XXXXXXX X
  X X X X      
XXX X X XXXXXXX

prim's algorithm generated maze missing walls

Maze 1

Maze 2

2 Answers