algorithm - パックマンの迷路をランダムに作成する方法

Question

こんにちは、ランダムな pacman 迷路を生成するアルゴリズムに取り組んでいます。いくつかの記事を見てきましたが、ロジックを分解できませんでした。迷路アルゴリズムの深さ優先検索を使用してから、迷路をミラーリングして各迷路を対称にします。行き止まりを片付けるなどの問題に直面しています。これが不可能な場合、誰かがランダムな迷路を生成する独自のロジックを持っている場合は、別のアルゴリズムも試します。どんな助けでも大歓迎です。ありがとう

Answer 1

私は自分の問題を解決し、共有したいと思いました。手始めに、一番上の行と最初の列と最後の列を壁の障害物として設定し、次に、2 番目の列、最後から 2 番目の行、2 番目の列にパスを設定して、外壁を囲みます。また、迷路の 50% しか作成していないので、完了したら迷路をコピーして両側が等しくなるようにします。次に、ゴーストがスポーンするエリアのために、壁に囲まれた中央セクションを作成しました。次に、迷路のまだ見ていない部分は、深さ優先探索アルゴリズムを使用してパスを生成しました。これが完了した後、パックマンの迷路には行き止まりがないことがわかりました。私がしたことは、パックマンが移動できるパスの一部であるすべてのセルをチェックすることでした. いずれかのセルに隣接するセルが 1 つしかない場合、それは行き止まりです。行き止まりの場合は、別のパスに接続できるかどうかを確認してください。行き止まりを壁として設定しない場合は、迷路に行き止まりがないか再度確認します。これらの手順に従うと、典型的なパックマンの迷路に似た、行き止まりのないランダムな迷路ができあがります。

Answer 2

私はかなり前に C=64 で深さ優先と行き止まりの除去を使用してランダム PacMan 迷路ジェネレーターを作成しましたが、最近、友人からもう一度やり直すように要求されました。より良い方法を見つけました。私のサイトでそれをチェックしてください

基本的に、各方向にドアが開いている部屋のグリッドを作成し（トンネルが通る場所を除いて境界で閉じられています）、隣接するドアには閉じたドアが1つ以上あるべきではないというルールに従ってドアをランダムに閉じ始めます2 つのドアが閉じている場合、3 番目のドアは行き止まりになります。すべての潜在的なドアがルールによって閉じられるか開かれるまで、これをランダムに繰り返します。

ミラーリングはもう少し手間がかかりましたが、基本から始めて、ミラーリング、ゴースト ハウスの場所、最小の壁の長さ (単一の壁で囲まれたラウンドアバウトはありません)、最大の壁の長さなどを許可するルールを作成しました...

Answer 3

クリーンエリアでdfsによるランダムウォークを実行することを提案します（壁なし、0のn * nマトリックス）。その後、ランダムウォークでカバーされていない領域を埋めます（壁として作成します）、これも未使用のスペースが発生する可能性がありますが、これにより長い散歩が保証されます。walk のサイズを任意に設定できます (たとえば、walk のサイズが (n^2)/2 に達したら、walk を停止できます)。