Netwalkゲームで迷路を生成するアルゴリズムは何ですか?
1957 次
1 に答える
18
ソース コードは Google Code で入手できるので、自分で読んで調べてください。迷路は、行 78ff の関数によって生成されgenerate_mazeますgame.c。
Netwalk は、Prim のアルゴリズムのランダム化されたバージョンを実行して最小スパニング ツリーを見つけることにより、迷路を生成します。Prim のアルゴリズムは、ソース ノード (またはノード: この場合は「サーバー」、濃い青色のダブルハイト ボックス) から開始して、一度に 1 ブランチずつツリーを繰り返し成長させます。アルゴリズムの実行中の任意の時点で、データ構造は次のようになります。
緑色で着色されたセルは、成長する枝の先端にあるセルです。これらのセルには、成長する可能性のある空の隣接セルがまだ少なくとも 1 つあります。各ステップで、アルゴリズムはこれらの緑色のセルの 1 つを選択し、次に空の隣接セル(1)の 1 つを選択して、その隣接セルにブランチを追加します。この新しい枝は、隣接する枝がその方向に成長するのをブロックします。枝に空の近隣がなくなると(2)、緑のセルのリストから削除されます。
最終的に、グリーン リストは空になります。ネットワークのどのブランチにも空のネイバーはありません。これは、ボードがいっぱいで、すべてのセルが単一のパスでサーバーに接続されていることを意味します。
[私はいくつかの場所で詳細を理想化しました: (1) 実際、Netwalk アルゴリズムは少しナイーブであり、ランダムな方向を選択するだけであり、その方向の隣人が空でない場合、何もせずに続行します次の反復へ。(2) 近隣に空のブランチがないブランチはタイムリーに検出されません。それらがたまたま選択された場合にのみ、グリーン リストから削除されます。デモでは、これらのマイナーな問題が修正されています。]
于 2011-07-07T09:45:04.503 に答える