java - java迷宫生成器中的算法错误

Question

我正在尝试编写一个生成二维迷宫的程序。迷宫的主体是一个二维 int 数组。边界单元格的值为 2。被阻挡的单元格(墙壁)的值为 1，空单元格(路径)的值为 0。最初，我将所有单元格的值设置为 1。然后，从顶行的随机列开始，我在迷宫中移动，将当前单元格设置为 0，直到到达底行。

这一切都工作得很好，除了我经常得到大范围的 0 而不是单行路径。因此，我尝试添加到 if 语句中，以防止它在周围的单元格已经为零的情况下将单元格标记为零。不幸的是，我的逻辑存在一些缺陷，导致程序永远运行，当我运行它时不打印任何内容。请帮我找出那个缺陷。

我对编程相当陌生，并且将其作为学习练习，因此我也愿意接受其他算法建议。谢谢

我的代码:

package RoboProj;

import java.util.Random;


public class Maze {
public int[][] grid;
final int width, height;

public Maze() {
    width = 20;
    height = 20;
    grid = new int[width][height];

    makeMaze();
}


public void makeMaze() {
    //* empty = 0, wall = 1, border = 2, travelled =3;

    //mark borders
    for (int curr = 0; curr < height; curr++) {
        grid[0][curr] = 2;  //top
        grid[curr][0]=2; //left
        grid[height -1][curr] = 2; //bottom
        grid[curr][width-1] = 2; //right
    }
    //initially mark all cells as walls
    for (int row = 1; row < height-1; row++){
        for (int col = 1; col < width-1; col++){
            grid[row][col]=1;
        }      
    }

    int row = 0;
    Random r = new Random();
    int col =  r.nextInt(width);

    grid[row][col] = 0;

    while (row != height-1){
        int next = r.nextInt(4);
        if (next == 0 && row-1 > 0 && grid[row-1][col-1] == 1 && grid[row-1][col+1] == 1){
            grid[row-1][col]=0;
            row = row-1;
          //  System.out.print(next);
        }
        if (next == 1 && grid[row+1][col-1] == 1 && grid[row+1][col+1] == 1){
            grid[row+1][col]=0;
            row = row+1;
           // System.out.print(next);
        }      
        if (next == 2&& col-1 > 0 && grid[row+1][col-1] == 1 && grid[row-1][col-1] == 1){
            grid[row][col-1]=0;
            col = col-1;
                  //     System.out.print(next);
        } 
        if (next == 3 && col+1 < width-1 && grid[row-1][col+1] == 1 && grid[row+1][col+1] == 1){
            grid[row][col+1]=0;
            col = col+1;
                   //     System.out.print(next);
        } 
    }
}
}

@ Anupam Saini:我正在寻找这样的东西，其中“路径”永远不会超过一个单元格宽度。

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

Answer 1

我对您的代码进行了一些修改，以使其更具可读性。我使用 switch case 语句来指示迷宫中的移动，0 表示左转，i 表示右转，2 表示向下移动。

isValidTurn()

和

moveMouse()

是感兴趣的方法。

    import java.util.Random;

    public class Maze {
    private final int[][] grid;
    private final int width, height;

    public static void main(String args[]) {
        Maze mz = new Maze(20, 20);
        mz.moveMouse();
    }

    private void generateDefaultMaze() {
        System.out.println(this);
        // * empty = 0, wall = 1, border = 2, travelled =3;

        // mark borders
        for (int curr = 0; curr < height; curr++) {
            grid[0][curr] = 2; // top
            grid[curr][0] = 2; // left
            grid[height - 1][curr] = 2; // bottom
            grid[curr][width - 1] = 2; // right
        }
        // initially mark all cells as walls
        for (int row = 1; row < height - 1; row++) {
            for (int col = 1; col < width - 1; col++) {
                grid[row][col] = 1;
            }
        }

        System.out.println(this);
    }

    public Maze(int width, int height) {
        this.width = width;
        this.height = height;
        grid = new int[width][height];
        this.generateDefaultMaze();
    }

    /**
     * Overridden method to generate a human readable maze state.
     */
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer(1024);
        for (int i = 0; i < this.width; i++) {
            for (int j = 0; j < this.height; j++) {
                sb.append(this.grid[i][j]).append(",");
            }
            sb.append("\n");
        }
        sb.append("\n");
        sb.append("**************");
        sb.append("\n");
        return sb.toString();
    }

    /**
     * Row pointer can either move left or right and it's value should be
     * between 0 and width. In case of 0 value at this grid[row][col] do not
     * move the pointer.
     * 
     * @param row The row pointer value.
     * @param col The column pointer value.
     * @return
     */
    private boolean isValidTurn(int row, int col) {
        if (row >= 0 && row < width && !(this.grid[col][row] == 0)) {
            return true;
        }
        return false;
    }

    public void moveMouse() {
        Random r = new Random();
        int row = r.nextInt(width);
        int col = 0;

        grid[col][row] = 0;
        // System.out.println(this);
        while (col < (this.height - 1)) {
            // Assuming the mouse moves in only 3 directions left right or down
            // in the maze. 0 indicates left turn 1 indicates right turn and
            // 2 indicates down movement in the maze.
            int nextDir = r.nextInt(3);
            switch (nextDir) {
            case 0: // left turn
                if (this.isValidTurn((row - 1), col)) {
                    --row;
                    this.grid[col][row] = 0;
                }
                break;
            case 1: // right turn
                if (this.isValidTurn((row + 1), col)) {
                    ++row;
                    this.grid[col][row] = 0;
                }
                break;
            case 2: // down movement
                ++col;
                this.grid[col][row] = 0;
                break;
            }
            System.out.println("turn : " + nextDir);
            // System.out.println(this);
        }
        System.out.println(this);
    }
 }