Java Recursive Backtracker Algortithm, создающий ошибочные и неразрешимые лабиринты - PullRequest
0 голосов
/ 17 октября 2019

Следующая реализация алгоритма рекурсивного обратного отслеживания в Java создает ошибочные и неразрешимые лабиринты. Мне не хватает умения и времени, чтобы исправить это правильно. Ниже приведен код и изображение созданного лабиринта.

Maze.java, класс, управляющий логикой генерации.

public class Maze 
{
    public int xSize = 0;
    public int ySize = 0;
    public int totalDimensions = 0;

    Random randomGenerator = new Random(System.currentTimeMillis());

    public Cell[][] cellData;

    public Stack<Cell> cellStack = new Stack<Cell>();

    Cell tempCell; // Temporary variable used for maze generation

    // METHODS
    // RBT = 0 (default)
    // Prim = 1
    // Kruskal = 2
    public Maze(int xSize, int ySize, int method) 
    {
        cellData = new Cell[xSize][ySize];
        this.xSize = xSize;
        this.ySize = ySize;
        this.totalDimensions = this.xSize * this.ySize;
        //cellStack.setSize(xSize * ySize);

        // Initialize array objects
        for (int i = 0; i < this.xSize; i++) 
        {
            for (int j = 0; j < this.ySize; j++) 
            {
                cellData[i][j] = new Cell();
                // Initialize the walls of the cell
                cellData[i][j].hasNorthWall = true;
                cellData[i][j].hasSouthWall = true;
                cellData[i][j].hasEastWall = true;
                cellData[i][j].hasWestWall = true;
            }
        }

        // Assign x and y positions
        for (int i = 0; i < this.xSize; i++) 
        {
            for (int j = 0; j < this.ySize; j++) 
            {
                cellData[i][j].xPos = i;
                cellData[i][j].yPos = j;
            }
        }

        initBoundries();

        if (method == 0) 
        {
            generateMazeRBT();
        }
    }

    private void initBoundries() 
    {
        // Initialize the border cells as visited so we don't go out of bounds
        for (int i = 0; i < this.xSize; i++) 
        { 
            for (int j = 0; j < this.ySize; j++) 
            { 
                if (i == 0 || j == 0 || i == this.xSize - 1 || j == this.ySize - 1) 
                    cellData[i][j].hasBeenVisited = true;
            } 
        } 
    }

    private void generateMazeRBT(int x, int y) 
    {
        // Set current cell as visited
        cellData[x][y].hasBeenVisited = true;

        // While there are unvisited neighbors
        while (!cellData[x][y+1].hasBeenVisited || !cellData[x+1][y].hasBeenVisited || !cellData[x][y-1].hasBeenVisited || !cellData[x-1][y].hasBeenVisited) 
        {
            // Select a random neighbor
            while (true) 
            {
                int r = randomGenerator.nextInt(4);
                if (r == 0 && !cellData[x][y+1].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasNorthWall = false;
                    cellData[x][y+1].hasSouthWall = false;
                    generateMazeRBT(x, y + 1);
                    break;
                }
                else if (r == 1 && !cellData[x+1][y].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasEastWall = false;
                    cellData[x+1][y].hasWestWall = false;
                    generateMazeRBT(x+1, y);
                    break;
                }
                else if (r == 2 && !cellData[x][y-1].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasSouthWall = false;
                    cellData[x][y-1].hasNorthWall = false;
                    generateMazeRBT(x, y-1);
                    break;
                }
                else if (r == 3 && !cellData[x-1][y].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasWestWall = false;
                    cellData[x-1][y].hasEastWall = false;
                    generateMazeRBT(x-1, y);
                    break;
                }
            }
        }

        // There are no unvisited neighbors
        if (!cellStack.isEmpty()) 
        {
            tempCell = cellStack.pop();
            generateMazeRBT(tempCell.xPos, tempCell.yPos);
        }
    }
}

Cell.java:

public class Cell 
{
    public boolean isCurrentCell;
    public boolean hasBeenVisited;
    public boolean hasNorthWall;
    public boolean hasSouthWall;
    public boolean hasEastWall;
    public boolean hasWestWall;
    public int xPos;
    public int yPos;
}

У меня есть отдельный драйвер и графический интерфейс для визуализации лабиринта:

enter image description here

Как видите, он очень нерегулярный и не решаемый. Что не так?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...