Создание лабиринта без открытых 2х2 комнат / пространств

Question

Я пытаюсь реализовать алгоритм генерации лабиринта в Java с ограничением, при котором в лабиринте размером 2x2 не должно быть пробелов, которые были бы свободно доступны. Моя реализация включает в себя 2D-массив, где каждая ячейка будет представлять либо стену ('#'), доступное пространство (''), предмет, который нужно собрать ('$'), скрытый блок (если еще не обнаружен проходящий лабиринт; ('.')) или вражеский NP C ('!').

Я следовал алгоритму лабиринта, описанному в Википедии следующим образом:

https://en.wikipedia.org/wiki/Maze_generation_algorithm

Под рекурсивным бэк-трекером, использующим стек:

Choose the initial cell, mark it as visited and push it to the stack
While the stack is not empty
    Pop a cell from the stack and make it a current cell
    If the current cell has any neighbours which have not been visited
        Push the current cell to the stack
        Choose one of the unvisited neighbours
        Remove the wall between the current cell and the chosen cell
        Mark the chosen cell as visited and push it to the stack

Пример того, как мой лабиринт будет выглядеть нормально:

# # # # # # # # # # # # # # # # # # # #
# @     #                           ! #
#   #   #   # # # # # # #   #   # #   #
#       #       #           #         #
#   # # # # # # #   # # # # # # #     #
#       #                             #
# # #   #   # # # #     #   # # # #   #
#                                     #
#     # # #   # # #     # # # #   # # #
#             #                       #
#     # # #   # # #     # # #     #   #
#         #                 $         #
#   # #   # # #   # # #   # #   #     #
# !           #                     ! #
# # # # # # # # # # # # # # # # # # # #



    public class Maze {

        private final int ROWS = 15;
        private final int COLS = 20;
        private final int MAX_ROW = ROWS - 1;
        private final int MAX_COL = COLS - 1;
        private char wall = '#';
        private char cheese = '$';
        private char player = '@';
        private char hiddenCell = '.';
        private char catNPC = '!';
        private char availableSpace = ' ';
        private char deadPlayer = 'X';
        private Coordinate cheeseLocation;

        private Map<Coordinate, Boolean> visibleCellsToPlayer = new HashMap<>();
        private Map<Coordinate, Boolean> checkIfVisited = new HashMap<>();
        private Map<Coordinate, Character> mapForCompleteMaze = new HashMap<>();
        private Character[][] playerMaze = new Character[ROWS][COLS];
        private Character[][] completeMaze = new Character[ROWS][COLS];
        private List<Coordinate> listOfAllCoordinates = new ArrayList<>();


        public Maze() {
            this.mazeGenerate();
        }


public void mazeGenerate() {
    int rowIndex = 0;
    int colIndex = 0;

    while (rowIndex < ROWS) {
        while (colIndex < COLS) {
            Coordinate newCoordinate = new Coordinate(rowIndex, colIndex);
            completeMaze[rowIndex][colIndex] = wall;
            mapForCompleteMaze.put(newCoordinate, wall);
            visibleCellsToPlayer.put(newCoordinate, false);
            checkIfVisited.put(newCoordinate, false);
            listOfAllCoordinates.add(newCoordinate);
            colIndex++;
        }
        rowIndex++;
        colIndex = 0;
    }
    innerMaze();
    while (!ValidMaze()) {
        innerMaze();
    }
}


public void innerMaze() {
    List<Coordinate> listOfCoordinates = new ArrayList<>();
    Stack<Coordinate> DFS_Stack = new Stack();
    int directionToGo = 0;
    int currentXCoordinate = 0;
    int currentYCoordinate = 0;
    int adjacentCellX = 0;
    int adjacentCellY = 0;
    int deleteWallAtXCoordinate = 0;
    int deleteWallAtYCoordinate = 0;

    Coordinate initialCell = new Coordinate(1, 1);
    DFS_Stack.push(initialCell);

    while (!DFS_Stack.empty()) {
        Coordinate currentCoordinate = DFS_Stack.pop();
        currentXCoordinate = currentCoordinate.getRow();
        currentYCoordinate = currentCoordinate.getCol();

        if ((currentXCoordinate - 2) >= 1) {
            Coordinate up = findCoordinate((currentXCoordinate - 2), currentYCoordinate);
            if (checkIfVisited.get(up) != true) {
                up.setDirection('N');
                listOfCoordinates.add(up);
            }
        }
        if ((currentXCoordinate + 2) < MAX_ROW) {
            Coordinate down = findCoordinate((currentXCoordinate + 2), currentYCoordinate);
            if (checkIfVisited.get(down) != true) {
                down.setDirection('S');
                listOfCoordinates.add(down);
            }
        }
        if ((currentYCoordinate - 2) >= 1) {
            Coordinate left = findCoordinate(currentXCoordinate, (currentYCoordinate - 2));
            if (checkIfVisited.get(left) != true) {
                left.setDirection('W');
                listOfCoordinates.add(left);
            }
        }
        if ((currentYCoordinate + 2) < MAX_COL) {
            Coordinate right = findCoordinate(currentXCoordinate, (currentYCoordinate + 2));
            if (checkIfVisited.get(right) != true) {
                right.setDirection('E');
                listOfCoordinates.add(right);
            }
        }
        if ((currentYCoordinate + 2) == MAX_COL) {
            Coordinate right = findCoordinate(currentXCoordinate, (currentYCoordinate + 1));
            if (checkIfVisited.get(right) != true) {
                right.setDirection('E');
                listOfCoordinates.add(right);
            }
        }
        if (!listOfCoordinates.isEmpty()) {
            DFS_Stack.push(currentCoordinate);
            directionToGo = ThreadLocalRandom.current().nextInt(0, listOfCoordinates.size());
            Coordinate coordinateOfDirection = listOfCoordinates.get(directionToGo);
            char directionFromCurrentCell = coordinateOfDirection.getDirection();
            Coordinate wallToDelete;

            if (directionFromCurrentCell == 'N') {
                wallToDelete = findCoordinate((currentXCoordinate - 1), currentYCoordinate);
            } else if (directionFromCurrentCell == 'S') {
                wallToDelete = findCoordinate((currentXCoordinate + 1), currentYCoordinate);
            } else if (directionFromCurrentCell == 'W') {
                wallToDelete = findCoordinate(currentXCoordinate, (currentYCoordinate - 1));
            } else {
                wallToDelete = findCoordinate(currentXCoordinate, (currentYCoordinate + 1));
            }

            adjacentCellX = wallToDelete.getRow();
            adjacentCellY = wallToDelete.getCol();
            completeMaze[adjacentCellX][adjacentCellY] = availableSpace;

            deleteWallAtXCoordinate = coordinateOfDirection.getRow();
            deleteWallAtYCoordinate = coordinateOfDirection.getCol();
            completeMaze[deleteWallAtXCoordinate][deleteWallAtYCoordinate] = availableSpace;

            checkIfVisited.put(coordinateOfDirection, true);
            checkIfVisited.put(wallToDelete, true);
            listOfCoordinates.clear();
            DFS_Stack.push(coordinateOfDirection);
        }
    }
}

Я включил различные примеры написанного мной кода, однако суть его в том, что мой конструктор класса Maze вызовет mazeGenerate (), который будет генерировать лабиринт со стеной, присутствующей в каждой ячейке. На этом этапе будет вызываться innerMaze (), алгоритм, упомянутый в Википедии. Мой код затем запустит проверку, чтобы увидеть, существуют ли какие-либо квадраты 2x2 (ValidMaze ()) на теперь завершенном лабиринте, и если он вернется как ложный, он продолжит восстанавливать лабиринт, пока не будет создан правильный лабиринт.

Мне интересно, является ли мой лог c ошибочным, моя реализация совершенно неверна, или моя проверка ошибок недействительна. Я был бы очень признателен за любую помощь в решении этой проблемы, и я благодарен за любой сделанный вклад. Спасибо всем заранее!