1

2次元迷路を生成するプログラムを作成しようとしています。迷路の本体は 2 次元の int 配列です。境界セルの値は 2 です。ブロックされたセル (壁) の値は 1 で、空のセル (パス) の値は 0 です。最初は、すべてのセルの値を 1 に設定しています。一番上の行のランダムな列で、一番下の行に到達するまで、現在のセルを 0 に設定して迷路を移動します。

これはすべて正常に機能しましたが、1 行のパスではなく、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 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
4

1 に答える 1

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);
    }
 }
于 2013-02-08T14:50:49.470 に答える