1

基本的に、私はこれを持っています：最初に、コードの束は、横断できない迷路を生成します。いくつかのパラメータに基づいて、2D配列の特定のスペースに壁をランダムに設定します。次に、バックトラッキングアルゴリズムを使用して、すべてが通過可能になるまで壁をノックアウトします。問題は、プログラムがスタックに戻っていないように見えることです。

これはかなり標準的なバックトラッキングコードです。アルゴリズムはランダムな場所から始まり、擬似コードで進行します。

move（x、y）{上に移動
でき、まだ行っていない場合：
move（x、y --1）
右に移動でき、まだ行っていない場合：
move（x + 1、y）
。 ..
}

他の方向についても同様です。移動するたびに、ブール値の2つの別々の2D配列（1つは一時的、もう1つは永続的）が座標に設定され、特定の要素にいることを示します。それ以上進むことができなくなると、永続的な2D配列をチェックして、どこにでもあるかどうかを確認します。そうでない場合は、訪問済みスペースと非訪問済みスペースの間にある壁をランダムに選択し（一時的な配列に従って）、それを削除します。このすべてがwhileループで呼び出されるため、迷路のチャンクを通過すると、一時的な2D配列がリセットされ、もう一方は保持され、永続的な2D配列が迷路全体にトラバースされました。moveメソッドのチェックは、永続的な配列ではなく、一時的な2D配列と比較されます。

これはほぼ機能しますが、最終的に生成された迷路の中で到達できない領域をいくつか見つけ続けました。そうでなければ、それは私が望むように迷路を生成するという素晴らしい仕事をしています。問題は、これの理由は、スタックに完全に戻らないことであることがわかりました。

永続的なものではなく一時的な2D配列の完了を確認するように変更すると（したがって、複数の反復にわたって完全な実行を行うのではなく、1回の実行で1回の完全なトラバーサルを実行して、完了をマークします）、継続しますと。私はそれを壊すためにカウンターを設定する必要があります。その結果、非常に多くの壁が削除された「迷路」ができあがります。アルゴリズムがたどるルートを確認すると、アルゴリズムが適切にバックトラックされておらず、スタック内で十分に遠くまで戻っておらず、理由もなく終了したと宣言する前に、単一の要素で数十回の再帰でスタックすることがよくあります。まったく、ゼロの壁を削除する必要があります。

以前のものを2回実行してみましたが、ノックアウトする必要のない壁をノックアウトし続け、迷路をまばらにしすぎています。なぜこれが起こっているのか私にはわかりません。

4

1 に答える 1

1

ラビリンスを作成する方法を作成しようとしたときに、同様の問題が発生しました。迷路を作るときに重要なことは、迷路の中に接続された部屋の孤立した「島」を作成しないようにすることです。これが擬似コードでの私の解決策です

Room r=randomRoom();

while(r!=null){
    recursivelyDigNewDoors(r);
    r=null;
    for(i=0;i<rooms.count;i++){
        if(rooms[i].doors.length == 0 && rooms[i].hasNeighborWithDoor() ){ 
        //if there is a room with no doors and that has a neighbor with doors
        Create a door between the doorless room and the one 
        connected to the rest of your maze
        r=rooms[i];
        }
   }
}

recursivelyDigNewDoorsはmove（）関数によく似ています

実際には、あなたはしたいかもしれません

  • 「ドア」を壁の欠如として説明する
  • と4つの壁を持つ部屋としてのドアのない部屋

しかし、一般的な原則は次のとおりです。

  1. 再帰的アルゴリズムをどこかで開始します
  2. アルゴリズムが停止したとき：未訪問の正方形が1つ、訪問済みの正方形が1つある場所を見つけます。
  3. これら2つをリンクして、以前に訪れたことのない広場から続けます
  4. 2つの正方形が満たされない場合（2）完了し、すべての正方形が接続されます
于 2011-04-11T12:07:51.500 に答える