Проблемы с созданием лабиринта с использованием алгоритма обратного отслеживания DFS

Question

Я пытаюсь реализовать алгоритм обратного отслеживания DFS, который включает использование стека (а не рекурсивного алгоритма), найденного в Википедии. Я пытаюсь создать лабиринт из 0 и 1, где 1 представляют стену, а 0 представляют доступный путь. Для любого данного пространства в лабиринте, который не является стеной, всегда должен быть действительный путь, по которому он может быть достигнут из любой другой непустой ячейки.

Я начинаю с лабиринта, который представляет собой двумерный массив лабиринта размера [15] [20], и следую алгоритму, отмечая ячейки, которые должны быть помечены как посещенные соответствующим образом. Первоначально все ячейки (исключая внешние границы) помечаются как «не посещенные». Все ячейки инициализируются со значением '1', и ожидается, что алгоритм будет копать уникальные пути по всему лабиринту.

Ссылка на алгоритм (2-я реализация рекурсивного обратного отслеживания, использующая стек):

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

Код, который я написал:

public void innerMaze() {
        List<Coordinate> listOfCoordinates = new ArrayList<>();
        List<Coordinate> coordinatesToBeRemoved = new ArrayList<>();
        Stack<Coordinate> DFS_Stack = new Stack();

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

        int randomInteger = 0;
        int cx = 0;
        int cy = 0;
        int gx = 0;
        int gy = 0;

        while (!DFS_Stack.empty()) {
            Coordinate currentCoordinate = DFS_Stack.pop();
            cx = currentCoordinate.getX();
            cy = currentCoordinate.getY();

            if ((cx - 2) >= 1) {
                Coordinate up = findCoordinate((cx - 2), cy);
                up.setDirection('N');
                listOfCoordinates.add(up);

            }
            if ((cx + 2) <= MAX_ROW) {
                Coordinate down = findCoordinate((cx + 2), cy);
                down.setDirection('S');
                listOfCoordinates.add(down);
            }
            if ((cy - 2) >= 1) {
                Coordinate left = findCoordinate(cx, (cy - 2));
                left.setDirection('W');
                listOfCoordinates.add(left);
            }
            if ((cy + 2) <= MAX_COL) {
                Coordinate right = findCoordinate(cx, (cy + 2));
                right.setDirection('E');
                listOfCoordinates.add(right);
            }
            for (Coordinate s : listOfCoordinates) {
                if (checkIfVisited.get(s) == true) {
                    coordinatesToBeRemoved.add(s);
                }
            }
            listOfCoordinates.removeAll(coordinatesToBeRemoved);

            if (!listOfCoordinates.isEmpty()) {
                DFS_Stack.push(currentCoordinate);
                randomInteger = ThreadLocalRandom.current().nextInt(0, listOfCoordinates.size());
                Coordinate temp = listOfCoordinates.get(randomInteger);
                char direction = temp.getDirection();
                Coordinate newWall;

                if (direction == 'N') {
                    newWall = findCoordinate((cx - 1), cy);
                } else if (direction == 'S') {
                    newWall = findCoordinate((cx + 1), cy);
                } else if (direction == 'W') {
                    newWall = findCoordinate(cx, (cy - 1));
                } else {
                    newWall = findCoordinate(cx, (cy + 1));
                }
                System.out.println(newWall);
                gx = newWall.getX();
                gy = newWall.getY();
                completeMaze[gx][gy] = 0;
                checkIfVisited.put(temp, true);
                checkIfVisited.put(newWall, true);
                listOfCoordinates.clear();
                DFS_Stack.push(temp);
            }
        }
    }

В моей текущей реализации каждая ячейка будет представлять собой стену или путь, поэтому я изменил алгоритм немного приближается к тому, где удаление стены между двумя ячейками становится удалением стены на две ячейки, изменяя одну промежуточную стенку на стену. Пример моего вывода выглядит следующим образом:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1
1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0
1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1
1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0
1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1
1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0
1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0
1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0
1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

На первый взгляд, двумерный индекс массива [1] [1] заключен в стены, поэтому это недоступная область. Это также очень согласуется с многочисленными казнями.

Буду признателен за любую помощь.

Answer 1

Я очень рекомендую использовать другой алгоритм. У меня приличный опыт написания алгоритмов генерации лабиринтов, и рекурсивный возврат всегда приводит к очень длинным путям, и у них практически нет выбора. Я не вижу проблемы в вашем коде, но вот моя собственная Java реализация рекурсивного возврата (извините, если код плохой, ему несколько лет).

public class Maze {

    private int sizeX, sizeY;
    private Cell[][] cells;
    private List<Cell> backtracker = new ArrayList<>();

    public Maze(int sizeX, int sizeY) {
        this.sizeX = sizeX;
        this.sizeY = sizeY;
        this.cells = new Cell[sizeX][sizeY];
        for (int i = 0; i < sizeX; i++) {
            for (int j = 0; j < sizeY; j++)
                cells[i][j] = new Cell(this, i, j);
        }
        generate();
    }

    private void generate() {
        Cell current = cells[0][0];
        current.visit();
        boolean hasUnvisited = hasUnvisited();
        while (hasUnvisited) {
            current = current.pickNext();
            if (!current.isVisited()) {
                current.visit();
                backtracker.add(current);
                hasUnvisited = hasUnvisited();
            }
        }
    }

    private boolean hasUnvisited() {
        for (int i = 0; i < sizeX; i++) {
            for (int j = 0; j < sizeY; j++) {
                if (!cells[i][j].isVisited()) {
                    return true;
                }
            }
        }
        return false;
    }

    public Cell backtrack() {
        if (backtracker.size() == 0) return null;
        Cell cell = backtracker.get(backtracker.size() - 1);
        backtracker.remove(cell);
        return cell;
    }

    public Cell getCell(int x, int y) {
        return cells[x][y];
    }

}

public class Cell {

    private Maze maze;
    private int x, y;
    private boolean visited = false;
    // top, right, bottom. left
    private boolean[] walls = new boolean[]{true, true, true, true};

    public Cell(Maze maze, int x, int y) {
        this.maze = maze;
        this.x = x;
        this.y = y;
    }

    public Cell pickNext() {
        List<Cell> neighbors = new ArrayList<>();
        if (y != maze.sizeY - 1) neighbors.add(maze.getCell(x, y + 1));
        else neighbors.add(null);
        if (x != maze.sizeX - 1) neighbors.add(maze.getCell(x + 1, y));
        else neighbors.add(null);
        if (y != 0) neighbors.add(maze.getCell(x, y - 1));
        else neighbors.add(null);
        if (x != 0) neighbors.add(maze.getCell(x - 1, y));
        else neighbors.add(null);
        boolean hasUnvisitedNeighbor = false;
        for (Cell c : neighbors) {
            if (c == null) continue;
            if (!c.isVisited()) hasUnvisitedNeighbor = true;
        }
        if (hasUnvisitedNeighbor) {
            int random = (int) Math.floor(Math.random() * 4);
            Cell next = neighbors.get(random);
            while (next == null || next.isVisited()) {
                random = (int) Math.floor(Math.random() * 4);
                next = neighbors.get(random);
            }
            this.breakWall(random);
            next.breakWall((random + 2) % 4);
            return next;
        } else return maze.backtrack();
    }

    public void breakWall(int wall) {
        walls[wall] = false;
    }

    public void visit() {
        visited = true;
    }

    public boolean isVisited() {
        return visited;
    }

}