2015年10月8日

手続き型のダンジョン生成アルゴリズム

(2015-8-31)by Adonaac

本記事は、原著者の許諾のもとに翻訳・掲載しております。

この投稿では、以前に TinyKeepDev がこちらで述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。

部屋の生成

はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。ここで実行すべき関数は 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

部屋の分離

では、分離のパートに進みましょう。数多くの部屋が1箇所に寄せ集められていますが、重なり合った状態は何とか避けたいですね。TKdevは、分離を誘導するビヘイビアを使ってこれに対処していますが、私はもっと簡単な方法を見つけました。それは物理エンジンを使うことです。全ての部屋を追加した後、各部屋の位置にマッチするように物理的なソリッドボディを追加し、全てのボディがスリープ状態に戻るまでシミュレーションを実行します。gif画像のシミュレーションは通常の速度ですが、レベル間でこれをやる時は、物理シミュレーションを速くすることも可能です。

物理ボディ自体はタイルグリッドに紐付けられていませんが、部屋の位置を設定する際にroundm関数を呼び出してそれをラップすれば、各部屋が重なり合うことなく、かつタイルグリッドも考慮に入れた状態を実現することができます。下のgif画像がこれを示しており、青いアウトラインが物理ボディです。物理ボディと部屋は、常にほんのわずかずれていますが、それは位置の数値が常に丸められていることによります。

ここで問題なのが、部屋を水平あるいは垂直方向に変形させたいような場合です。現在、私が取り組んでいるゲームを例に見てみましょう。

戦闘は主に水平方向で展開されるので、ほとんどの部屋について高さよりも幅を広く取りたいと思っています。問題は、細長い部屋が互いに近づいた時、その衝突を物理エンジンがどのように解決するかということです。

見ての通り、ダンジョンは縦長になりますが理想的とは言えません。これを改善するには、円形ではなく、細長い帯状エリアの中に部屋を生成すればいいでしょう。こうすることで、ダンジョンの縦横比を適切に保つことができます。

帯状のエリアで部屋をランダムに発生させるため、”getRandomPointInCircle”関数を変更して楕円︵ellipse︶内でポイントが生成するようにします︵上のgif画像では、ellipsewidth = 400、ellipseheight = 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*mean、つまりwidthmeanとheightmeanが24であれば、選ばれるのは幅と高さが30以上の部屋です。

ドロネー三角形分割とグラフ

ここでは、選択した部屋の中心点を取り、ドロネーの処理を行います。ご自身で実装されても構いませんし、ソースをシェアしている人を探すという形でも構いません。私の場合はラッキーで、 Yonabaが既にこれを実装していました。インターフェイスをご覧いただければお分かりの通り、これは点を取り込んで三角形を出してくれます。

三角形ができたらグラフを作成します。この作業は、グラフのデータ構造/ライブラリが手元にあれば極めて簡単です。まだ作成していない場合、部屋のオブジェクト/構造には固有のIDがあるので、それらをわざわざコピーする必要はなく、IDをグラフに追加できます。

最小スパニングツリー

次に、グラフから最小スパニングツリーを生成します。これも同じく、あなたが自力で実装してもよいし、既に誰かがあなたの好きな言語で実装したものを探しても構いません。

最小スパニングツリーを使えば、ダンジョン内のメインの部屋が全て確実に到達可能でありながら、これまでのようにメインの部屋が全て繋がっていることがなくなります。普通、デフォルトでは、繋がり過ぎのダンジョンは望ましくありませんが、到達不可能な離れ小島も望ましくないので、これは役に立ちます。ただし、普通は、1本の線形経路しかないダンジョンも望ましくないので、ドロネーのグラフに戻っていくつかのエッジを追加します。

いくつかの経路とループが追加され、ダンジョンがもっと面白くなります。TKdevはエッジを15%追加し直しましたが、私の経験では8～10%程度の方が良い値でした。これは、最後にダンジョンをどのように繋げたいかによって異なります。

廊下

最後に、ダンジョンに廊下を追加しましょう。これを行うには、グラフの各ノードを調べ、次に、互いに繋がっているノードについて、その間にラインを作成します。ノードが水平方向に十分近接している場合は︵y位置が近い︶、水平ラインを作成します。ノードが垂直方向に十分近接している場合は、垂直ラインを作成します。ノードが水平方向にも垂直方向にも近接していない場合は、L字型を形成する2本のラインを作成します。﹁十分近接している﹂かどうかのテストは、両方のノードの中間点を計算し、その中間点のx位置またはy位置の属性がノードの境界内にあるかどうか判定することによって行いました。判定が真の場合は、部屋の中心点からラインを作成しました。判定が偽の場合は2本のラインを作成しました。それぞれが1つの座標軸のみに沿い、各軸上で起点ノードの中心点から到着ノードの中心点へ向かうようにしました。

上の図には、全ての場合の例が示されています。ノード62と47の間には水平ラインがあり、ノード60と125の間には垂直ラインがあり、ノード118と119の間にはL字型のラインがあります。重要なことは、作成しているのは1本のラインだけではないということです。描かれているラインは1本だけですが、廊下の幅を横または縦方向に少なくとも3タイル幅にしたいので、線の両側にタイルサイズ︵tile_size︶の間隔を開けて1本ずつ、2本のラインを追加します。次に、メインでもハブでもない部屋のうち、それぞれのラインと衝突するのはどれかをチェックします。衝突する部屋は、使っている何らかのデータ構造に追加しておき、廊下の骨組みとして使用します。

最初に設定した部屋の均質性とサイズによって、ダンジョンの外観は様々に異なります。廊下を均質にして見た目を良くしたい場合は、低い標準偏差を目指し、かつ部屋がどちらかの方向に薄くなり過ぎないようにする何らかのチェックを行うべきです。最終段階では、1タイルサイズのグリッドセルを追加して欠けている部分を補います。実際には、グリッドデータ構造も手の込んだものも必要ありません。ただ各ラインをタイルサイズに準じて調べ、グリッドに近似された位置︵これが1タイルサイズのセルに相当します︶を、何らかのリストに追加していくだけです。これは、3本(以上)のラインがある場合に起こることであって、ラインが1本の場合には関係ありません。

これで完成です！

終わりに

この手続き全体から得られるデータ構造は、部屋のリスト︵各部屋は、固有ID、xy位置、および幅と高さをもつ単なる構造︶、グラフ、および実際の2Dグリッドです。グラフの各ノードポイントは1つの部屋IDを指し、エッジは部屋間の距離をタイル単位でもちます。2Dのグリッドでは、各セルは空白︵何も入っていない︶であってもよいし、メインまたはハブの部屋を指してもよいし、廊下の部屋を指すことも、廊下のセルであることもできます。これらの3つの構造があれば、レイアウトからどんなタイプのデータでも手に入り、それから、ドア、敵、アイテム、どの部屋にボスがいるかなどを考えることができるはずです。

古川陽介
株式会社リクルート　プロダクト統括本部　プロダクト開発統括室　グループマネジャー株式会社ニジボックス　デベロップメント室室長 Node.js 日本ユーザーグループ代表

複合機メーカー、ゲーム会社を経て、2016年に株式会社リクルートテクノロジーズ(現リクルート)入社。現在はAPソリューショングループのマネジャーとしてアプリ基盤の改善や運用、各種開発支援ツールの開発、またテックリードとしてエンジニアチームの支援や育成までを担う。 2019年より株式会社ニジボックスを兼務し、室長としてエンジニア育成基盤の設計、技術指南も遂行。 Node.js 日本ユーザーグループの代表を務め、Node学園祭などを主宰。

Twitter: @yosuke_furukawa
Github: yosuke-furukawa