3

プリム迷路生成アルゴリズムを実装しようとしています:

  • 壁でいっぱいのグリッドから始めます。
  • セルを選択し、迷路の一部としてマークします。セルの壁を壁リストに追加します。
  • リストに壁がある場合:
    • リストからランダムな壁を選択します。反対側のセルが
      まだ迷路に入っていない場合:
      • 壁を通路にして、反対側のセルを迷路の一部としてマークします。
      • セルの隣接する壁を壁リストに追加します。
    • 反対側のセルが既に迷路内にある場合は、リストから壁を削除します。

いくつかの実装の詳細を削除すると、私の実装は次のようになります。

Cell[][] maze

セルを含むマトリックスです。各セルには、左/右/上/ボタンの壁があります。とマークされたフロンティアの壁boolean frontierは実装の一部ではありません。迷路の枠を維持したいからです。

public Cell[][] prim(){
    List<Wall> walls = new ArrayList<Wall>();

    //Pick a cell, mark it as part of the maze
    int initialCellI = rnd(sizeX)-1;
    int initialCellJ = rnd(sizeY)-1;
    Cell randomCell = maze[initialCellI][initialCellJ];
    randomCell.setPartOftheMaze(true);

    //Add the walls of the cell to the wall list.
    if ((randomCell.getLeft() != null) && (!randomCell.getLeft().isFrontier()))
        walls.add(randomCell.getLeft());
    if ((randomCell.getRight() != null) && (!randomCell.getRight().isFrontier()))
        walls.add(randomCell.getRight());
    if ((randomCell.getButtom() != null) && (!randomCell.getButtom().isFrontier()))
        walls.add(randomCell.getButtom());
    if ((randomCell.getUp() != null) && (!randomCell.getUp().isFrontier()))
        walls.add(randomCell.getUp());

    //While there are walls in the list:
    while (!walls.isEmpty()){

        //Pick a random wall from the list.
       Wall randomWall = randomElement(walls);
       //pick the cell opposite to this wall. 
       Cell opositeSideCell = getNeightbourCell(randomWall, maze);
       if (opositeSideCell.isPartOftheMaze()){
           //If the cell on the opposite side already was in the maze, remove the wall from the list.
           walls.remove(randomWall);
       }
       else{
          // Make the wall a passage and mark the cell on the opposite side as part of the maze.
           this.removeWall(randomWall, maze);
           opositeSideCell.setPartOftheMaze(true);

            //Add the walls of the cell to the wall list.
            if ((opositeSideCell.getLeft() != null) && (!opositeSideCell.getLeft().isFrontier()))
                walls.add(opositeSideCell.getLeft());
            if ((opositeSideCell.getRight() != null) && (!opositeSideCell.getRight().isFrontier()))
                walls.add(opositeSideCell.getRight());
            if ((opositeSideCell.getButtom() != null) && (!opositeSideCell.getButtom().isFrontier()))
                walls.add(opositeSideCell.getButtom());
            if ((opositeSideCell.getUp() != null) && (!opositeSideCell.getUp().isFrontier()))
                walls.add(opositeSideCell.getUp());   
       }
    }
    return maze;
}

私の問題は、迷路が完成しておらず、すべてのセルが横断されていないことです。場合によっては、少数のセルのみが通過し、ほとんどすべてのセルが完了します。私は何かが欠けていると信じています。バーは何がわからないのですか。

助けてください。

部分横断迷路については、下の図を参照してください。

ここに画像の説明を入力

4

1 に答える 1

1

さて、私はこの問題を解決しました。これは純粋な Java の問題であり、アルゴリズムとは何の関係もありません。2つの壁を比較しました。

public class Wall{

    Point p1;
    Point p2;
    }

    public class Point{
    int x;
    int y;
    }

p1とp2を使用してWallクラスのequals（）とhashCode（）を実装するとします。次に、 leftCell.rightWall は rightCell.leftWall と等しくなり、それが問題でした。

于 2012-07-12T22:06:24.543 に答える