投稿では、ランダムダンジョンを生成する手法について詳しく説明しています。 ここで見ることができるメイン生成アルゴリズムは、 TinyKeepゲームの開発者によって使用されます。 開発者からの元の投稿はredditに投稿されました 。
アルゴリズムの元の説明
1.最初に、適切な部屋の数（たとえば150）を尋ねます。当然、数は任意であり、大きいほどダンジョンは難しくなります。
2.各部屋に対して、指定された半径内にあるランダムな幅と高さの長方形を作成します。 半径はそれほど重要ではありませんが、部屋の数に比例するはずであると仮定することは合理的です。
（ほとんどの言語でMath.randomジェネレーターによって生成される）均等に分布する乱数の代わりに、 通常のPark-Miller分布を使用します。 その結果、小さな部屋の確率が大きな部屋の確率を上回ります。 これが必要な理由は、後で説明します。
また、部屋の長さと幅の比率が大きすぎないことを確認します。 完全に正方形の部屋と非常に細長い部屋の両方は必要ありません。
3.そして今、小さなスペースに150のランダムな部屋があります。 それらのほとんどは互いにぶつかります。 次に、分離ステアリング技術に従って分離を実行し、長方形が交差しないように分割します。 その結果、それらは交差しませんが、互いに十分に近接しています。
4.ギャップを1x1セルで埋めます。 その結果、さまざまなサイズの部屋の正方形のグリッドが得られます。
5.そして、主な楽しみが始まります。 格子のどのセルが部屋であるかを決定します。これらは、指定されたものを超える幅と高さを持つセルになります。 Park-Millerの分布により、比較的少数の部屋しか確保できず、その間にかなりの空きスペースがあります。 ただし、残りのセルも有用です。
6.次のステップは、部屋を結合することです。 これを行うには、 Delaunay三角形分割を使用して、すべての部屋の中心を含むグラフを作成します。 現在、すべての部屋は互いに素な線で接続されています。
7.すべての部屋をすべてに接続する必要はないため、 最小限のスパニングツリーを構築します 。 結果は、どの部屋にも到達することが保証されたグラフです。
8.木はきちんとしていましたが、退屈です-閉じた動きはありません。 したがって、以前に除外されたグラフのエッジの約15％をランダムに追加します。 結果は、すべての部屋が到達可能であることが保証され、いくつかの閉じた通路があるグラフです。
9.廊下に変えるために、各エッジに対して、部屋を結ぶグラフのエッジに沿って、一連の直線（Gの形）が作成されます。 ここでは、未使用のままになっているセル（部屋にならなかったセル）が必要です。 L字型の線に重ねられたすべてのセルが廊下になります。 また、セルのサイズがさまざまであるため、廊下の壁は不均一になり、ダンジョンに適しています。
そして、これが結果の例です！
注意-カットの下には、アニメーションGIFの
Gamasutraの投稿で、ユーザーA Adonaacはいくつかの詳細をより詳細に説明するのに苦労しました。 一般に、アルゴリズムの動作は視覚的に次のようになります。
部屋の作成
最初に、特定の円の中にランダムに配置された、特定の高さと幅を持つ複数の部屋を作成する必要があります。 TKdevを使用したアルゴリズムでは、正規分布を使用して部屋のサイズを選択しましたが、これは良いアイデアであると思われます。もっと多くのオプションがあります。 さまざまなタイプのダンジョンは、高さと幅の比と標準偏差を選択することで実現できます。
必要になる可能性がある機能の1つはgetRandomPointInCircleです。
function getRandomPointInCircle(radius) local t = 2*math.pi*math.random() local u = math.random()+math.random() local r = nil if u > 1 then r = 2-u else r = u end return radius*r*math.cos(t), radius*r*math.sin(t) end
ここで彼女の仕事をより詳細に説明します。 その後、次のようなものを取得できます。
タイルグリッドを扱っているため、すべての部屋を1つのグリッドに沿って配置する必要があることに注意してください。 上記のgifでは、タイルのサイズは4ピクセルなので、部屋の位置とサイズはすべて4の倍数でなければなりません。 これを行うために、位置と高さの割り当てを、数値をタイルのサイズに丸める関数で幅でラップしました。
function roundm(n, m) return math.floor(((n + m - 1)/m))*m end -- getRandomPointInCircle : function getRandomPointInCircle(radius) ... return roundm(radius*r*math.cos(t), tile_size), roundm(radius*r*math.sin(t), tile_size) end
シェアルーム
分離に移りましょう。 分割する必要がある部屋がたくさん重なりました。 TKdevは分離ステアリング技術に言及していますが、物理エンジンを使用する方が簡単だと思われます。 一連の部屋を作成したら、物理的な身体を各部屋に割り当て、シミュレーションを開始し、すべてが落ち着くまで待つだけです。 gifは、シミュレーションの例を示しています。
物理的なボディはラティスに関連付けられていませんが、部屋に位置を割り当てることで、ラウンドコールでラップし、ラティス上に重ならない部屋ができます。 GIFはこのプロセスを示します。 青い輪郭は、身体を示しています。 それらと部屋の実際の位置との間にはわずかな矛盾があります。
主に軸の1つに沿って主に部屋を拡張しようとすると、この場合に発生する可能性のある問題の1つが発生する可能性があります。 たとえば、私が取り組んでいるゲームを考えてみましょう。
戦闘は水平方向に行われるため、部屋の高さではなく幅を長くする必要があります。 問題は、物理エンジンが2つの部屋間の衝突をどのように解決するかです。
写真では、縦に伸びたダンジョンが得られますが、これはあまり便利ではありません。 状況を修正するには、最初に部屋の位置を設定して、円の内側ではなく薄い帯の内側に表示されるようにします。 その結果、必要なダンジョンの高さと幅の比率を取得します。
部屋をストリップ状にランダムに分散するには、getRandomPointInCircle関数を変更して、円ではなく楕円にポイントを配置します（表示されたgifでは、ellipse_width = 400およびellipse_height = 20の値を使用します）。
function getRandomPointInEllipse(ellipse_width, ellipse_height) local t = 2*math.pi*math.random() local u = math.random()+math.random() local r = nil if u > 1 then r = 2-u else r = u end return roundm(ellipse_width*r*math.cos(t)/2, tile_size), roundm(ellipse_height*r*math.sin(t)/2, tile_size) end
メインルーム
次のステップでは、メインルームになるルームを定義します。 TKdevアルゴリズムでは、すべてが単純です。高さと幅が指定された値を超える部屋を選択します。 次のGIFでは、1.25 *平均制約を使用しました。つまり、width_meanとheight_meanが24の場合、高さと幅が30を超える部屋がメインの部屋になります。
ドローネの三角形分割とカウント
ここで、選択した部屋の中心を取り、データを処理手順に送ります。 あなたはそれを自分で書くか、完成したものを取ることができます-私は幸運でした、そして私は完成したものを見つけました、ヨナバによって 。 彼女はポイントを取り、三角形を配ります
三角形があると、グラフを作成できます。 ヒント：ルームオブジェクト自体をコピーするのではなく、ルームに一意のIDを割り当てて操作すると便利です。
最小スパニングツリー
その後、グラフに基づいて最小スパニングツリーを作成します。 各部屋が他のすべての部屋にすぐに接続されることはありませんが、すべての部屋が原則として達成可能であることを保証します。
到達できない廊下や部屋はあまり必要ありません。 しかし、それはまた退屈であり、ダンジョンには正しい方法が1つしかありません。したがって、ドローネ伯爵からいくつかのエッジを返します。
これにより、パスが追加され、エンクロージャーが少し生成されます。 TKdevは、エッジの15％を返すことを推奨していますが、個人的には8-10％を返す方が便利だと思いました。
廊下
コリドーを追加するには、グラフのすべてのノードを回って、すべての隣接ノードに接続する線を作成します。 ノードがほぼ同じ水平方向にある場合は、水平線を作成します。 垂直の場合-垂直。 ノードが同じ水平または垂直にない場合、L字型のフォームを形成する2本の線を作成します。
このようなチェックを実行して、2つのノードの位置の間の中点を見つけ、このポイントの座標が部屋レベル（水平または垂直）にあるかどうかを確認しました。 それらが水平であれば、1本の線を引きます。 そうでない場合は、2つ、部屋からポイントへ、ポイントから別の部屋へ。
この写真では、すべてのケースの例を見ることができます。 ノード６２と４７は水平線で接続され、ノード６０と１２５は垂直であり、ノード１１８と１１９はＬ字型である。 写真に示されている線に加えて、描画された線の両側にtile_sizeの距離で2つ追加作成します。これは、少なくとも3セルの幅の廊下が必要だからです。
その後、どの非メインルームが構築されたラインと交差するかを確認します。 これらの部屋は構造に追加され、廊下システムの基礎になります。
部屋の均一性と最大サイズに応じて、結果として非常に異なるダンジョンを得ることができます。 より均一な廊下が必要な場合は、標準偏差を制限し、部屋のサイズと部屋の高さと幅の比率をさらにチェックする必要があります。
最後に、行に1x1セルを追加し、欠落している部分を置き換えます。 ここで、先に追加された追加の線が役立ち、廊下が狭くなりすぎないようにします。
それはみんなだ！
その結果、次のようなデータ構造が得られます。
- 部屋のリスト（それぞれが一意のID、x / y位置、および高さ/幅を持つ構造です）
- 各ノードが部屋のIDを指し、エッジがセル内の部屋間の距離を含むグラフ
- 2Dグリッド。各セルは空にでき、メインルーム、廊下システムに属する部屋、または狭い廊下のセルをポイントできます。
これら3つの構造を使用して、必要なデータセットを表すことができます。 それらに基づいて、ドア、敵、物などの場所で作業することはすでに可能です。
