ゲームNetwalkで迷路を生成するアルゴリズムとは何ですか？

ゲームで迷路を生成するアルゴリズムは何ですかNetwalk？ Google CodeのでゲームNetwalkで迷路を生成するアルゴリズムとは何ですか？

Netwalk game screenshot

出典

2011-07-07 boring

投稿された回答の質に鑑みて、これを再開しました。しかし、コミュニティは私の決定に自由に同意することができます。私の推論は、答えはこの質問が確かに建設的な方法で客観的に答えることができることを証明しています。 –

@Tim：ありがとう。 –

@Gearth Rees :) –

source code is available、あなた自身のためにそれを読んで見つけることができるように！迷路は、関数generate_mazeによってgame.c、行78ffに生成されます。

Update: try the demo!

Netwalkはminimum spanning treeを見つけるためにPrim's algorithmのランダム化されたバージョンを実行して、迷路を生成します。 Primのアルゴリズムは、ソースノード（またはノード：この場合は「サーバー」、ダークブルーの2倍の高さのボックス）から始めて、一度に1つずつ分岐するツリーを反復的に成長させます。アルゴリズムの実行中に任意の時点では、データ構造は、このようなものになります。

enter image description here

を緑に着色された細胞は、細胞が成長している枝の先端である：彼らはまだ、少なくとも1つの空の持っています彼らが成長するかもしれない隣人。各ステップで、アルゴリズムはこれらの緑色セルの1つを選択し、次に空の隣接セルの1つを選択して^（1）とし、その隣接セルにブランチを追加します。この新しいブランチブロックは、隣接ブランチがその方向に成長することを阻止する。ブランチに空のネイバーがなくなった場合は、^（2）、緑のセルのリストから削除されます。

最終的に緑色のリストは空です。ネットワークのブランチのどれもが空のネイバーを持っていません。これは、ボードがいっぱいであり、すべてのセルが単一パスでサーバーに接続されていることを意味します。

enter image description here

[私は場所のカップルで詳細を理想化しました：（1）実際にNetwalkアルゴリズムは少しナイーブで、ちょうどランダムな方向を選び、その方向での隣人がある場合空ではなく、何もせずに次の繰り返しに進みます。（2）空のネイバーがないブランチは、適時に検出されません。選択された場合、緑のリストからのみ削除されます。デモでこれらの軽微な不具合が修正されました。]

出典

2011-07-07 09:45:04

ゲームとデモの背後にあるアイデアを指摘してくれてありがとう。カッコいい。 – boring

これは本当に幅広い質問に対する素晴らしい、客観的な答えです。貢献していただきありがとうございます。 –

ゲームNetwalkで迷路を生成するアルゴリズムとは何ですか？

答えて

関連する問題