ピクミン2 洞窟生成アルゴリズム後編

前編の公開から非常に時間が空いてしまいましたが、洞窟生成アルゴリズムの続きを書いていきます。

全体の流れを再掲しておきます。

1.地形を決める
1-1.定められた数まで広場を置く
1-2.広場と広場の間の一部を通路で結ぶ
1-3.袋小路を置く

2.配置を決める
2-1.探査ポッドを置く
2-2.穴及び間欠泉を置く
2-3.敵を置く
2-4.お宝を置く
2-5.Cap Itemを置く
2-6.土の壁を置く

前編では1の地形を決める部分について書いたので、ここからは配置について書いていきます。地形に関する用語などは前編を参照してください。

最初に探査ポッドの位置を決めますが、これは非常に単純です。地形を決めるときに最初に置いた部屋の中には必ずポッドを置くことができる場所が一つ以上あるので、その中からランダムに一つ選んで決めます。以下、簡単のためにこの部屋を部屋Pとします。

次に穴及び間欠泉の位置を決めるのですが、その前にここで、配置の決定に関して重要な概念である「スコア」について説明します。

各部屋(＝広場&通路&袋小路)には、スコアという整数値が定められます。これは、次の三つの要素を考慮して計算されるものです。

1.部屋Pから対象の部屋までたどり着くための道の長さ
2.1の道をたどるときに通る部屋にいる敵の多さ
3.その部屋にポッドがあるかどうか

1について。これはより厳密に書くと、部屋Pの接続口から対象の部屋の接続口までの道の長さ(の $\frac{1}{10}$ )ということで、目安として、1区画分で $+17$ に相当します。ただし部屋P、及び部屋Pと隣り合っている部屋に関しては $+0$ とします。

f:id:fuji_luck:20201011232435p:plain — 1区画というのは、この袋小路の縦及び横の長さのことを言っていて
実際の距離は $170$ となっています

1区画というのは、この袋小路の縦及び横の長さのことを言っていて
実際の距離は $170$ となっています

2について。これはより厳密に書くと、1で考えた道が通っている部屋(両端、すなわち部屋P及び対象の部屋も含む)にいる敵の数ということになります。ただし、一口に敵と言っても、実は内部的にはいくつかのタイプに分かれていて、タイプごとに加算される値が異なることに注意が必要です。敵のタイプについては、敵の位置を決めるときに詳しく説明するとして、ここでは結果だけ書くことにすると、

Hard Enemy → $+10$
Door Enemy → $+5$
Easy Enemy → $+2$
それ以外 → $+0$

となります。

3については簡単で、対象の部屋にポッドがなければ $+1$ 、あれば $+0$ となります。すなわち、部屋P以外に一律に $+1$ が加算されるということです。

ここまでからわかるようにスコアは基本的にポッドから遠い部屋ほど高くなるように設計されています。ただし、これだけでは部屋にたどり着くまでに複数の道があるときにどの道を計算に用いればよいかわからないので、もう少し詳しく知りたい人向けに具体的なスコアの算出方法を書いておきます(興味ない人はスコアの説明の残りの部分は飛ばしてください)。

各部屋のスコアを計算するために、便宜的に各接続口にもスコアを定義します(接続口のスコアは最後の方にちょろっと出てくるくらいで、基本的には各部屋のスコアを計算するためにしか使いません)。接続口は部屋と部屋の境界なので、各接続口はある部屋のものであると同時に別の部屋のものでもあることに注意してください。

まず、部屋Pのスコアは部屋Pにいる敵(接続口にいるDoor Enemyは含まない)だけから決まるのでこれを確定します。次に、部屋Pのすべての接続口のスコアを、部屋Pのスコアに $+1$ し、その接続口のDoor Enemyの有無によって $+5$ または $+0$ して確定します。その後はまず、部屋Pと隣り合っている各部屋のスコアを、その部屋の接続口のうち既にスコアが確定しているもの(すなわち部屋Pとの境界)でスコアが最小のものを考え、その接続口のスコアにその部屋の敵のスコアを足して確定します。これで部屋P、及び部屋Pと隣り合っている部屋のスコアは計算できました。

残りのスコアについてですが、まず、まだスコアが確定していない接続口のスコアを確定することを目指します。そのために、既にスコアが確定している接続口と確定していない接続口の組であって、二つの接続口が同じ部屋に属しているものをすべて持ってきます。そして、スコアが確定していない方の接続口のスコアを

確定している方の接続口のスコア
二つの接続口間の距離を $10$ で割ったもの(小数点以下切り捨て)
二つの接続口がどちらも属している部屋の敵によるスコア
スコアが確定していない方の接続口のDoor Enemyの有無( $+5$ or $+0$ )

の和として(仮に)計算し、先ほど持ってきたすべての組の中でこの値が最小となるもののみ確定したスコアとします。これを繰り返すことによってすべての接続口のスコアを確定することができます。

最後にまだスコアが確定していない部屋について、その部屋の接続口のうちスコアが最小のものを考え、そのスコアにその部屋の敵のスコアを足して確定します。

これで、スコアの説明が終わったので、ここからは各部屋のスコアを使って配置を決めていきます。

まず、穴と間欠泉の位置を決めます。穴も間欠泉も存在するフロアについては、穴→間欠泉の順に決めていきます。

広場及び袋小路の中で穴(間欠泉)を置くことができるすべての地点に対して、次の値を計算します。ただし、その地点が存在する部屋のスコアを $S$ とします。

【本編】 $S$
【チャレ】 $\sqrt{S} +10$
(小数点以下は切り捨て)

【本編】ではこの値が最も大きい地点の中からランダムに一つ決めます。【チャレ】では各地点がこの値で重み付けられた確率で一つ決めます。ただし、ポッドとの距離が $150$ 未満でかつ広場の中にある地点に穴(間欠泉)を置くことはできません。

もし、広場にも袋小路にも穴(間欠泉)を置くことのできる地点が一つもない場合は、通路の各地点(各通路の中央に一つずつあります)に対して上と同様のことをして決めます。逆に言えば、通路に穴(間欠泉)が出るのは、広場にも袋小路にも間欠泉を置くことができないときに限るということです。

ここでは穴(間欠泉)の位置を決めるのに各部屋のスコアを使っていますが、この時点では敵は1体も配置されていないので、スコアのうち敵が関係している部分はすべて無視できることに注意してください。

(上記のように、穴と間欠泉の位置を決める際に平方根を用いるのですが、このゲームの内部で行われている平方根の計算には少々癖があり、結論から言うと実際の値とは異なる場面がいくつかあります。たとえば、本来であれば $\sqrt{1} = 1$ なのですが、ゲーム内では $\sqrt{1} \lt 1$ となっており、小数点以下を切り捨てると $0$ になってしまいます。これは計算の誤差によるもので、 $\sqrt{1}$ のように値が小さくなってしまうものばかりなら話は単純だったのですが、 $\sqrt{49} \gt 7$ のような例もあります。マニアックなので詳細は余力があれば書きます。
書きました→洞窟生成アルゴリズムの補足 - fuji_luckのブログ)

次に敵を置いていきます。まず、スコアの説明のときに少し触れたとおり、敵は内部的にはいくつかのタイプに分かれているのでその説明をします。各フロアにおいてどの敵がどのタイプに属しているかは、前編でも紹介したhttps://github.com/JHaack4/CaveGen/tree/master/output/!caveinfoで確認できます。

リンク先で灰色で示されているのがDoor Enemyです。接続口にしか出ません。基本的に間欠炎などの障害物が設定されていますが、スナイパールームのテンテンチャッピーのような例もあります。

リンク先で紫色で示されているのがSpecial Enemyです。特別な場所にしか出ないようなイメージです。三色試練場のタマコキンなどが該当します。

リンク先で赤色で示されているのがHard Enemyです。これといって特徴のない普通の敵ですが、スコアに与える影響は最も大きいです。

リンク先で桃色で示されているのがEasy Enemyです。小さくて弱い敵が設定されるようなイメージで、同じ地点に2体以上置くことができるという特徴があります。

リンク先で緑色で示されているのがPlantです。文字通り植物が設定されていることが多いですが、炎と水の試練場のアオケダタラのような例もあります。ポッドの近くにもお構いなしに出ます(辺境の洞窟1階のオナラシなど)。

敵は上で書いた順番に置いていきます。基本的に候補地点の中からランダムに置いていくだけなのですが、注意すべき点がいくつかあるのでそれを書いていきます。

まず、各フロアには敵の最大数が設定されていてDoor Enemy、Special Enemy、Hard Enemy、Easy Enemyの数の合計はこの値以下でなければなりません。それとは別に各敵には出すべき最小数が設定されていて、これらの合計はほとんど先ほどの最大数と一致するのですが、まれに下回るフロアがあります。そのようなフロアで、かつweightという値が $0$ 以外に設定されている敵がいる場合(土とんの洞窟1階など)は、weightの値で重み付けられた確率で、敵の最大数に足りない分だけ増やす敵を決めます。決め方は、まず増やす敵のタイプを決定し、実際に配置する段階になってどの敵にするかを決めます。増えた敵の位置は、そのタイプの中で最後に決められます。

Door Enemyは、その接続口が広場、通路、袋小路のどれに属しているかによって、それぞれ $100$ 、 $1$ 、 $0$ が重み付けられた確率で配置されます。ただし、各接続口は二つの部屋に属しているので正確には $200$ 、 $101$ 、 $100$ 、 $2$ 、 $1$ のいずれかで重み付けられることになります。

Special Enemyは、ポッドからの距離が $300$ 未満の地点、穴(間欠泉)からの距離が $150$ 未満の地点には出ません。

Hard Enemyは、ポッドからの距離が $300$ 未満の地点、穴(間欠泉)からの距離が $200$ 未満の地点には出ません。

Easy Enemyは、ポッドからの距離が $300$ 未満の地点には出ません。

また、Easy Enemyは唯一一つの地点に2体以上置くことができるので少し特殊な事情があります。Easy Enemyの各候補地点には最小匹数と最大匹数が設定されており、またそれぞれの敵にも同時に出せる匹数が設定されています。敵を置く地点を決めた後、その地点の最大匹数と、その敵を同時に出せる匹数を比べて、少ない方を真の最大匹数とします。真の最大匹数が、その地点の最小匹数以下のときは、真の最大匹数だけその地点に置き、次からは別の敵を置いていきます。真の最大匹数がその地点の最小匹数より多いときは、最小匹数から真の最大匹数までにある整数値の中からランダムに一つ選んでその匹数だけ置き、余った分を次に置く敵として持ち越します(同時に出せる匹数は、今置いた分だけ減らします)。ただし、フロアの敵最大数が過剰であるために、最小数より余分に出すように設定された分に関しては、「同時に出せる匹数」は常に(敵の最大数) $-$ (既に置いた敵の数)とし、余ったとしても次には持ち越さずどの敵を出すかは毎回抽選します。

次にお宝を置いていきます。お宝の位置は、穴(間欠泉)と同様に各部屋のスコアに基づいて決めていきます。
(この時点では敵の配置が決定しているので、スコアには敵の存在も反映されることに注意)。

広場及び袋小路の中でお宝を置くことができるすべての地点に対して、次の値を計算します(通路に置くことはできません)。ただし、その地点が存在する部屋のスコアを $S$ とします。

・広場
【本編】 $\dfrac{S}{1+N_i}$
【チャレ】 $1+\dfrac{S}{N_s}$
(小数点以下は切り捨て)

ただし $N_i$ は既にその部屋に置いたお宝の数(the number of Items in the room)、 $N_s$ はその部屋に置くことができるお宝の数(the number of Spawnpoints in the room)を表します。

・袋小路
【本編】 $1+S$
【チャレ】 $1+10\times S$

【本編】ではこの値が最も大きい地点の中からランダムに一つ決めます( $N_i$ はお宝を置くたびに変わることに注意)。【チャレ】では各地点がこの値で重み付けられた確率で一つ決めます。

次にCap Itemを置いていきます。Cap Itemというのは、この時点で余っている袋小路(物を置くことができるものに限る)に置かれるものの総称で、各種ポンガシグサやタマゴが代表的です。

Cap Itemには下と上の2種類があります。下というのは、袋小路に普通に置かれているもののことで、上は、何らかの条件(近づくなど)を満たすと上から降ってくるもののことです。先に下のCap Itemを置いていき、それが済んでから上を置いていきます。ただし、各種ポンガシグサに関してだけは、上であっても下と同じタイミングで置かれます。

Cap Itemの配置は比較的単純で、地形を生成したときにできるのが早かった順番(袋小路の前にある接続口ができた順番と思ってよい)に置いていきます。ただし、下のCap Itemと各種ポンガシグサ(上であっても)は、既に穴(間欠泉)やお宝が置かれている袋小路に置くことはできません。また、上のCap Item(各種ポンガシグサは除く)は、既に穴(間欠泉)や各種ポンガシグサ(下であっても)が置かれている袋小路に置くことはできません。

複数の接続口をもつ部屋が存在するために、袋小路(の前にある接続口)の生成が同時に行われることがありますが、そのような場合の優先度は、次のようにして決めます。

1.その部屋を回転させる前の向きを考える(先ほどのリンク先に載っているものがそうです)
2.1の向きで、上にある接続口のうち最も左にあるものから時計回りで生成されたことにする

たとえば三色試練場の場合、八つの袋小路は常に次の順番でできたことになります。

f:id:fuji_luck:20201013021025j:plain — これを知っていればタマゴムシの位置をある程度予測することができます

袋小路が余ってしまう場合、weightが $0$ でないCap Itemがあればそれらで残りの袋小路を埋めていきます。

最後に土の壁を設置して完成とします。土の壁の位置は、初めは規則に基づいて決定され、途中から乱数がかかわってきます。大概は前半の部分で完結するので後半については深入りしないことにします。

最優先で壁が置かれるのは、袋小路のうち下に何らかのものが置いてあるところです。ただし、既にDoor Enemyが置かれている袋小路は対象外とします。これらの条件を満たす場所が複数ある場合は、ランダムな順番で置いていきます。
(各種ポンガシグサ(上)は置くときこそ下と同じような扱いでしたが、ここでは実態通りに上のCap Itemとして扱うため含まれません。)

次に、部屋P以外の広場それぞれについて、その接続口のうち最もポッドから近いものを選び、そこにDoor Enemyが置かれていない場合のみ壁を置きます。広場はできるのが早かった順番に見ていきます。
(最もポッドから近いものというのは、厳密には各接続口のうちスコアが最も低いものということです。スコアが同じ場合は、Cap Itemの説明のときと同様の理屈でそれらのうち最初に生成されたものとします。)

ここまで終わってまだ設置できる壁が余っている場合は、乱数で場所を決めていきます。ざっくり言うと、ポッドから近いところに置かれやすいようです。

以上で地形・配置ともに完成したので洞窟生成は完了です。お疲れさまでした。