1

I was trying to implement a C# version of the Java code given in this answer to generate a random maze, but my code doesn't quite generate the mazes correctly - it creates "isolated" wall sections, in other words:

#####
#   #
# # #
#   #
#####

... where one wall section is surrounded by 7 passage sections. The entire maze with this algorithm looks something like:

###########
#         #
# # # ### #
#       # #
### # ### #
# #   #   #
# ### # # #
#         #
### ### # #
#         #
###########

I'm not sure how the algorithm I linked avoids doing this, and what I'm doing differently that causes it. The maze should be nothing but corridors, with no isolated wall sections, for example:

Sample maze

Could anyone help with what my algorithm is doing wrong? Here is my algorithm:

namespace MazeGenerator {
    public class MazeGenerator {
        private readonly Random _rnd = new Random(1212);
        // NOTE: cells grid dimensions must be odd, odd (will give size 1 border around maze)
        private readonly bool[,] _cells = new bool[11,11]; // All maze cells default to wall (false), not path (true)

        private struct CellPosition {
            public int X;
            public int Y;

            public override string ToString() {
                return $"{X}, {Y}";
            }
        }

        public bool[,] GenerateMaze() {
            Console.Clear();

            // Random starting position must be odd, odd (will give size 1 border around maze)

            //var posRnd = new CellPosition {
            //    X = _rnd.Next(0, _cells.GetLength(0)),
            //    Y = _rnd.Next(0, _cells.GetLength(1))
            //};
            var posRnd = new CellPosition {
                X = 1,
                Y = 1
            };
            setCell(posRnd, true); // Set initial random cell to path

            var candidateCells = new List<CellPosition>();
            candidateCells.AddRange(getCandidateCellsFor(posRnd, false)); // Get cell's wall candidates
            while (candidateCells.Count > 0) {
                // Pick random cell from candidate collection
                int thisCellIndex;
                var thisCell = candidateCells[thisCellIndex = _rnd.Next(0, candidateCells.Count)];

                // Get cell's path candidates
                var pathCandidates = getCandidateCellsFor(thisCell, true);

                if (pathCandidates.Count > 0) {
                    // Connect random path candidate with cell
                    connectCell(pathCandidates[_rnd.Next(0, pathCandidates.Count)], thisCell);
                }

                // Add this candidate cell's wall candidates to collection to process
                candidateCells.AddRange(getCandidateCellsFor(thisCell, false));

                // Remove this candidate call from collection
                candidateCells.RemoveAt(thisCellIndex);

                renderMaze(_cells);
                //Thread.Sleep(1000);
            }

            return _cells;
        }

        /// <summary>
        /// Sets the cell in the given position to the given state.
        /// </summary>
        /// <param name="posRnd">The position of the cell to set.</param>
        /// <param name="isPath">The state to set the cell to.  If true, sets to path; otherwise, sets to wall.</param>
        private void setCell(CellPosition posRnd, bool isPath) {
            _cells[posRnd.X, posRnd.Y] = isPath;
        }

        /// <summary>
        /// Connects two cells that are a distance of 2 apart with path, where cell A is already a path cell.
        /// </summary>
        /// <param name="cellA">Path cell to connect cell B to.</param>
        /// <param name="cellB">Wall cell to connect to cell A.</param>
        private void connectCell(CellPosition cellA, CellPosition cellB) {
            var x = (cellA.X + cellB.X) / 2;
            var y = (cellA.Y + cellB.Y) / 2;
            _cells[cellB.X, cellB.Y] = true;
            _cells[x, y] = true;
        }

        private bool cellHasValidPosition(CellPosition position) {
            return
                position.X >= 0 &&
                position.Y >= 0 &&
                position.X < _cells.GetLength(0) &&
                position.Y < _cells.GetLength(1);
        }

        /// <summary>
        /// Gets candidate cells for a given cell given its position.
        /// </summary>
        /// <param name="position">The cell's position.</param>
        /// <param name="getPathCells">If true, gets path candidate cells; otherwise, gets wall candidate cells.</param>
        /// <returns>The candidate cells for the given cell.</returns>
        private IList<CellPosition> getCandidateCellsFor(CellPosition position, bool getPathCells) {
            var candidatePathCells = new List<CellPosition>();
            var candidateWallCells = new List<CellPosition>();

            var northCandidate = new CellPosition { X = position.X, Y = position.Y - 2 };
            var eastCandidate = new CellPosition { X = position.X + 2, Y = position.Y };
            var southCandidate = new CellPosition { X = position.X, Y = position.Y + 2 };
            var westCandidate = new CellPosition { X = position.X - 2, Y = position.Y };

            if (cellHasValidPosition(northCandidate)) {
                if (_cells[northCandidate.X, northCandidate.Y]) { candidatePathCells.Add(northCandidate); }
                else { candidateWallCells.Add(northCandidate); }
            }
            if (cellHasValidPosition(eastCandidate)) {
                if (_cells[eastCandidate.X, eastCandidate.Y]) { candidatePathCells.Add(eastCandidate); }
                else { candidateWallCells.Add(eastCandidate); }
            }
            if (cellHasValidPosition(southCandidate)) {
                if (_cells[southCandidate.X, southCandidate.Y]) { candidatePathCells.Add(southCandidate); }
                else { candidateWallCells.Add(southCandidate); }
            }
            if (cellHasValidPosition(westCandidate)) {
                if (_cells[westCandidate.X, westCandidate.Y]) { candidatePathCells.Add(westCandidate); }
                else { candidateWallCells.Add(westCandidate); }
            }

            if (getPathCells) { return candidatePathCells; }
            else { return candidateWallCells; }
        }

        private static void renderMaze(bool[,] maze) {
            Console.Clear();
            for (var x = 0; x < maze.GetLength(0); x++) {
                for (var y = 0; y < maze.GetLength(1); y++) {
                    Console.Write($"{(maze[x,y] ? " " : "#")}");
                }
                Console.WriteLine();
            }
        }
    }
}
Jez
  • 27,951
  • 32
  • 136
  • 233
  • 1
    When you use a debugger, what is the *first* line that does something unexpected? – Scott Hunter Jun 15 '22 at 15:04
  • It's picking a candidate cell from the candidate cells collection that's already been set to a path cell. Thus, it connects path to path, knocking out the wall between them, when presumably, it should only ever connect wall to path, knocking out a candidate wall and the connecting wall. I can see why it's doing it; what I can't see is why the Java code I referenced *isn't* doing that. – Jez Jun 15 '22 at 15:09
  • How should it tell that the candidate cell has already been set to a path cell? – Scott Hunter Jun 15 '22 at 15:12
  • Yes, I can put in an if statement to check (and short-circuit the rest of the while loop) and that does seem to solve it. So I would appear to have fixed the bug. But there is no such if statement in the Java code, so I'm curious as to what equivalent mechanism it is using that I've missed. – Jez Jun 15 '22 at 15:15
  • Your `getCandidatCellsFor` looks very different than `cellsAround`; doesn't necessarily mean its wrong. That Java function checks for something being a wall, which (best i can tell) your doesn't. – Scott Hunter Jun 15 '22 at 15:26
  • In you images and text examples, which is passage and which is wall? – RBarryYoung Jun 15 '22 at 16:13

1 Answers1

3

OK, the problem seems to be that the original Java code was using a HashSet whereas I was using a List to store candidate cells. The HashSet intrinsically prevents duplicate candidate cells from being stored by only adding cells that are unique (don't match existing entries in the HashSet). I reworked the C# code to use a HashSet and now it seems to work as intended:

namespace MazeGenerator {
    public class MazeGenerator {
        private readonly Random _rnd = new();
        // NOTE: cells grid dimensions must be odd, odd (will give size 1 border around maze)
        private readonly bool[,] _cells = new bool[11,11]; // All maze cells default to wall (false), not path (true)

        private struct CellPosition {
            public int X;
            public int Y;

            public override string ToString() {
                return $"{X}, {Y}";
            }
        }

        public bool[,] GenerateMaze() {
            Console.Clear();

            // Random starting position must be odd, odd (will give size 1 border around maze)

            //var posRnd = new CellPosition {
            //    X = _rnd.Next(0, _cells.GetLength(0)),
            //    Y = _rnd.Next(0, _cells.GetLength(1))
            //};
            var posRnd = new CellPosition {
                X = 1,
                Y = 1
            };
            setCell(posRnd, true); // Set initial random cell to path

            var candidateCells = new HashSet<CellPosition>();
            candidateCells.UnionWith(getCandidateCellsFor(posRnd, false)); // Get cell's wall candidates
            while (candidateCells.Count > 0) {
                // Pick random cell from candidate collection
                var thisCell = candidateCells.ElementAt(_rnd.Next(0, candidateCells.Count));

                // Get cell's path candidates
                var pathCandidates = getCandidateCellsFor(thisCell, true);

                if (pathCandidates.Count > 0) {
                    // Connect random path candidate with cell
                    connectCell(pathCandidates[_rnd.Next(0, pathCandidates.Count)], thisCell);
                }

                // Add this candidate cell's wall candidates to collection to process
                candidateCells.UnionWith(getCandidateCellsFor(thisCell, false));

                // Remove this candidate call from hashset collection
                candidateCells.Remove(thisCell);

                renderMaze(_cells);
                Thread.Sleep(50);
            }

            return _cells;
        }

        /// <summary>
        /// Sets the cell in the given position to the given state.
        /// </summary>
        /// <param name="posRnd">The position of the cell to set.</param>
        /// <param name="isPath">The state to set the cell to.  If true, sets to path; otherwise, sets to wall.</param>
        private void setCell(CellPosition posRnd, bool isPath) {
            _cells[posRnd.X, posRnd.Y] = isPath;
        }

        /// <summary>
        /// Connects two cells that are a distance of 2 apart with path, where cell A is already a path cell.
        /// </summary>
        /// <param name="cellA">Path cell to connect cell B to.</param>
        /// <param name="cellB">Wall cell to connect to cell A.</param>
        private void connectCell(CellPosition cellA, CellPosition cellB) {
            var x = (cellA.X + cellB.X) / 2;
            var y = (cellA.Y + cellB.Y) / 2;
            _cells[cellB.X, cellB.Y] = true;
            _cells[x, y] = true;
        }

        private bool cellHasValidPosition(CellPosition position) {
            return
                position.X >= 0 &&
                position.Y >= 0 &&
                position.X < _cells.GetLength(0) &&
                position.Y < _cells.GetLength(1);
        }

        /// <summary>
        /// Gets candidate cells for a given cell given its position.
        /// </summary>
        /// <param name="position">The cell's position.</param>
        /// <param name="getPathCells">If true, gets path candidate cells; otherwise, gets wall candidate cells.</param>
        /// <returns>The candidate cells for the given cell.</returns>
        private IList<CellPosition> getCandidateCellsFor(CellPosition position, bool getPathCells) {
            var candidatePathCells = new List<CellPosition>();
            var candidateWallCells = new List<CellPosition>();

            var northCandidate = new CellPosition { X = position.X, Y = position.Y - 2 };
            var eastCandidate = new CellPosition { X = position.X + 2, Y = position.Y };
            var southCandidate = new CellPosition { X = position.X, Y = position.Y + 2 };
            var westCandidate = new CellPosition { X = position.X - 2, Y = position.Y };

            if (cellHasValidPosition(northCandidate)) {
                if (_cells[northCandidate.X, northCandidate.Y]) { candidatePathCells.Add(northCandidate); }
                else { candidateWallCells.Add(northCandidate); }
            }
            if (cellHasValidPosition(eastCandidate)) {
                if (_cells[eastCandidate.X, eastCandidate.Y]) { candidatePathCells.Add(eastCandidate); }
                else { candidateWallCells.Add(eastCandidate); }
            }
            if (cellHasValidPosition(southCandidate)) {
                if (_cells[southCandidate.X, southCandidate.Y]) { candidatePathCells.Add(southCandidate); }
                else { candidateWallCells.Add(southCandidate); }
            }
            if (cellHasValidPosition(westCandidate)) {
                if (_cells[westCandidate.X, westCandidate.Y]) { candidatePathCells.Add(westCandidate); }
                else { candidateWallCells.Add(westCandidate); }
            }

            if (getPathCells) { return candidatePathCells; }
            else { return candidateWallCells; }
        }

        private static void renderMaze(bool[,] maze, string title = "Generating maze...") {
            Console.Clear();
            Console.WriteLine(title);
            Console.WriteLine();
            for (var x = 0; x < maze.GetLength(0); x++) {
                for (var y = 0; y < maze.GetLength(1); y++) {
                    Console.Write($"{(maze[x,y] ? " " : "#")}");
                }
                Console.WriteLine();
            }
        }
    }
}
Jez
  • 27,951
  • 32
  • 136
  • 233