2020-11-08

いろいろな確率を求める話その2

前回に引き続いて、確率の計算をしていきます。今回は主に配置に関係するものを扱います。

まず、天罰の穴を見ていきます。このフロアは三つの広場からなり、端にポッドが置かれるところまでは確定しています。三つの広場のすべてに間欠泉が置かれる可能性があるのですが、その確率はどうなっているのでしょうか。

確率を求めるためには各部屋のスコアを計算する必要があります。間欠泉を置く時点では敵が存在しないので、敵が関係する部分はすべて $0$ となります。そのため、ポッドがある、一番端の部屋のスコアは $0$ 、その隣の部屋は $1$ となります。最後の部屋のスコアですが、これを求めるためには真ん中の部屋の入口から出口までの距離が必要になります。この値を知るために、天罰の穴で使われている部屋の種類の情報を見ます。

天罰の穴のページを見ると、使われている部屋の種類が2_MAT_sak1_sak2_snowであることがわかるので、https://github.com/JHaack4/CaveGen/tree/master/files/gc/unitsでそのページを開くことで、天罰の穴で使うことのできる各部屋の名前と内部数値(の一部)を見ることができます。

今回知りたいのは、大きさ $5 \times 5$ で接続口が二つある部屋の、二つの接続口間の距離でした。今挙げた特徴から、一番下に載っているroom_saka2_2_snowがこの部屋のことであるとわかります。接続口の番号は、上辺の左にあるものから時計回りに0、1、...となっているので、0から1までの距離(逆でも可。数値が微妙に異なることもあるが影響しない)を見ればよいです。そのためには、indexが0でdoor-idが1となっているところを見つけてdistの値を調べればよく、今回の場合は $967.089539$ であることがわかります。

よって、最後の部屋のスコアは $967.089539$ を $10$ で割って小数点以下を切り捨てたものに $1$ を足して、 $97$ と求まります。

間欠泉を置く確率は $\sqrt{S} + 10$ (小数点以下は切り捨て)で重み付けられるものだったので、ポッドがある側から順に $10$ 、 $10$ 、 $19$ となります(ゲーム内の計算では $\sqrt{1} \lt 1$ となっていることに注意)。よって、たとえばポッドがある部屋に間欠泉が置かれる確率は $\frac{10}{39}$ となります。

次に、グリーンホール2階を見ていきます。このフロアでは低確率でタマゴが置かれることが知られているので、その確率を求めてみます。

地形は固定、ポッドやヤキチャッピーの置かれる場所も固定で、間欠泉とアカコチャッピーの置かれる場所は固定ではないですが影響しないので適当に決めてしまうと、次の画像のようになります。

f:id:fuji_luck:20201108160514p:plain — お宝を置く直前のグリーンホール2階

ここにお宝を置いていきます。やはり各部屋のスコアが必要になるのでそれを計算しますが、ヤキチャッピーはSpecial Enemyなのでスコアには影響しません。アカコチャッピーはHard Enemyなので $+10$ の値を持っており、ポッドがある広場のスコアは $10$ 、各袋小路のスコアは $11$ となります。その結果、お宝を置く確率の重み付けは、各袋小路では $1 + 10 \times 11$ で $111$ 、広場にはお宝を置くことのできる場所が二つあるので、 $1 + \frac{10}{2}$ で $6$ となります。

お宝を置いた後、袋小路にテンコチャッピー、ユキチャッピー、タマゴの順に置いていくので、タマゴが置かれるのは、二つのお宝のうち少なくとも一方が袋小路以外の場所に置かれた場合であり、その確率は

$1 - \frac{444}{456} \times \frac{333}{345} = 0.060183$

ということで $6.0183\%$ となります。

ちなみに、一部のステージでは余った袋小路の数だけタマゴが置かれるということがありますが、ここではそのようなことは起きません。それはタマゴのweightが $0$ だからです。そのことは、いつも参照しているhttps://github.com/JHaack4/CaveGen/tree/master/output/!caveinfoでも確認できますが(m1の後に何も書かれていない)、内部の情報(https://github.com/JHaack4/CaveGen/tree/master/files/gc/caveinfo-jpn)を直接見た方が早いかもしれません。どのファイルがどのステージに相当するかはhttps://pikmintkb.com/wiki/Pikmin_2_Challenge_Mode_settingsで確認できます。これを見ると、一番下のEggのところに10と書いてあるのがわかりますが、左の1が個数で、右がweightとなっています。

なので、グリーンホール2階ではお宝が二つとも広場に出ることがありますが、その場合でもタマゴは一つまでしか置かれないということです。

最後に、コンクリート迷路3階でタマゴが置かれない確率を駆け足で見ていきます。タマゴが置かれなくなるのは、袋小路が足りない地形を引いたときのみで、その地形を引く確率は $\frac{1}{4} \times 0.240551$ です(前回、S字の確率を求めたのと同じ感じでできます)。

f:id:fuji_luck:20201108164036p:plain — 例の地形

ポッドを置ける場所が二つあるのですが、どちらに置いても間欠泉の位置などに影響が出ることはありません。間欠泉を置く確率の重み付けは次のようになります。

f:id:fuji_luck:20201112150719p:plain — 奥三つの袋小路は行き方が二通りありますが、右を経由する方がスコアが小さくなります

また、お宝を置く確率の重み付けは次のようになります。

間欠泉とカギと二つの石像のうち二つ以上が袋小路以外に出ればタマゴを置くことができ、その確率は $0.002309$ となります(間欠泉が袋小路に出るとそこにはお宝を置けなくなることに注意)。

よって、タマゴが置かれない確率は

$\frac{1}{4} \times 0.240551 \times (1 -0.002309) = 0.059999$

で $5.9999\%$ となります。
(全数調査によると $5.9995\%$ だそうです。)

2020-10-31

いろいろな確率を求める話その1

前回までは洞窟生成についての一般論を中心に書いてきました。今回からは、ゲーム中に登場する具体的なフロアに洞窟生成アルゴリズムを適用する方法や、それによって得られる知識について書いていきます。

洞窟生成アルゴリズムを理解すると、特定の地形や配置が生成される確率を計算で求めることができます。いくつか具体的な確率を求めてみましょう。

最初は、炎と水の試練場2階に焦点を当てます。

このフロアは、大きなプールがある部屋にポッドが置かれ、それとは別に、坂と水槽がある部屋と、入口が一つだけある小さな部屋の二つが存在します。

f:id:fuji_luck:20201030205631p:plain — ポッドが置かれる部屋

f:id:fuji_luck:20201030205708p:plain — 水槽部屋

f:id:fuji_luck:20201030205726p:plain — 小部屋

接続のしかたは様々ですが、移動距離の観点から、ポッドのそばにある二つの接続口(図の左下)に水槽部屋と小部屋が一つずつ接続している地形がタイムを残しやすいと言われています。このような地形を俗に両隣接と言います。

それでは、両隣接の地形を引く確率を実際に求めてみます。便宜的に、プールがある部屋の接続口に、図の上にあるものは1、そこから時計回りに2、3、4、5と番号を付けます。

過去の記事で説明したように、広場を置く順番は図の列をシャッフルすることで決まります。

f:id:fuji_luck:20201030211017p:plain — 左上が列の先頭。右下が最後尾

シャッフルのしかたをおさらいしておくと

1.ランダムに一つ選びそれを一番後ろに移す
2.同じことを全部で $4n$ 回行う

というものでした。

ただし、今回の場合、ポッドを置くことができるのはプールがある部屋だけなので、シャッフルの結果どのような列が得られても最初にプールがある部屋が置かれることになります。

それでは、シャッフルの結果がどのような意味を持つのかというと、プールの次に置かれるのが水槽部屋か小部屋かというところに関係してきます。

いま仮に、四つのプール部屋のうちシャッフル前に先頭にあったもの(図の9番目)がシャッフル後にも先頭にあったとし、次の部屋を置く接続口が3番になったとします(後半の確率は $\frac{1}{5}$ です)。

このような状況で問題なく置くことができる水槽部屋及び小部屋は次の三つが考えられます

f:id:fuji_luck:20201030212824p:plain — 上に接続口を持つ(かつ既に置かれた部屋とぶつからない)この三つが候補となる

この三つのうちシャッフル後に先頭に来ているものを置くことになります。

ここで、プール部屋の向きがどうであっても、また、部屋を置く接続口がどれであっても、次に置く部屋の候補は小部屋一つと水槽部屋二つであることがわかります。三つの候補のうち先頭にあるものが小部屋であるという確率は、プール部屋の向きによって変わりますが、部屋を置く接続口がどれであるかにはよりません。なぜなら、シャッフル前はすべての小部屋がすべての水槽部屋よりも前にあるからです。そのため、候補として選ばれる一つの小部屋と二つの水槽部屋が常に同じものであると仮定してもかまいません。すると、三つの候補のうち先頭が小部屋である確率をプール部屋の向きごとに求めてそれを合計したものは、結局その三つのうち小部屋が先頭である確率ということになるので、その確率は比較的楽に計算で出すことができて、 $43.4931\%$ と求まります。

今回は両隣接の確率を求めたいので、ここで置いた小部屋または水槽部屋は、プール部屋の3または4番の接続口に接続しているとして話を進めます。すると、両隣接になるためには次に選ぶ接続口は必ずプール部屋の3または4番のうち余っている方でなければなりません。

f:id:fuji_luck:20201030215250p:plain — たとえばこんな感じ

先に小部屋を置いた場合は次に水槽部屋を、先に水槽部屋を置いた場合は次に小部屋を(置けない場合を除いて)置くことになっており、今回考えている条件では部屋が置けないことはないので希望の接続口さえ選ぶことができれば自然と両隣接になるのですが、先に小部屋を置いたか水槽部屋を置いたかによってこの時点での開いた接続口の数が一つだけ異なり、希望の接続口が選ばれる確率がそれぞれ $\frac{1}{4}$ 、 $\frac{1}{5}$ と、同じではないことに注意が必要です。

両隣接の確率はここまででたどった道筋の確率を求めればよく

$\frac{2}{5} \times ( 0.434931 \times \frac{1}{4} + 0.565069 \times \frac{1}{5} ) = 0.088699$

ということで $8.8699\%$ となります。

良地形の確率を求めたので、次は悪地形の確率を求めます。

新参者の試練場2階では、そんなに低くない確率で図のような地形(通称S字)でプレイする羽目になり、多くのプレイヤーを悩ませています。

f:id:fuji_luck:20201030222039p:plain — S字

このフロアのように広場が2種類の場合、原則として2種類が交互に置かれるのでこのような地形は本来あり得ないのですが、交互に置こうとすると図のように重なりが生じてしまうため、Y字型の部屋を連続で置くことになり結果としてS字が誕生してしまうのです。

f:id:fuji_luck:20201030222456p:plain — 二つの円形が重なってしまう
(どう見ても重なっていないけど内部的にはアウト扱い)

それではこのような地形の確率を求めましょう。このフロアは円形部屋にもY字部屋にもポッドを置くことができるのですが、S字を作るためにまず円形部屋にポッドを置くことから始めます。シャッフル前の列は次のようになっており、シャッフル後の先頭に円形部屋のどれかがあればよく、その確率は $86.4186\%$ となります。

f:id:fuji_luck:20201030223327p:plain — 左が先頭

円形部屋には接続口が一つしかなく、向きによらずY字部屋のうち二つが候補となります。そのうち片方がS字を作るために置くべきものです。ここで注意が必要なのが、S字を作るために置くべきY字部屋とそうでない方のY字部屋のシャッフル前の順番が、初めに置いた円形部屋の向きによって入れ替わるということです。

f:id:fuji_luck:20201030224429p:plain — 円形部屋が元々の向きのときは、S字のために必要なものは列の後ろにある

f:id:fuji_luck:20201030224530p:plain — 円形部屋の向きによっては、S字を作るためのものが列の前にある

そのため、単にポッドが円形部屋にある確率 $86.4186\%$ を求めるのではまずく、円形部屋の向きまで考慮する必要があります。

具体的には

シャッフル後の列の先頭が円形部屋のうち元々前にあった二つのうちどちらかであって、かつ、置くことができる二つのY字部屋の候補のうち元々後ろにあったものがシャッフル後に前に来ている確率と

シャッフル後の列の先頭が円形部屋のうち元々後ろにあった二つのうちどちらかであって、かつ、置くことができる二つのY字部屋の候補のうち元々前にあったものがシャッフル後も前に残っている確率を

合わせたものを求める必要があります。

上記のうちたとえば、シャッフル後の列の先頭が円形部屋のうち元々2番目にあったものであって、かつ、置くことができる二つのY字部屋の候補のうち元々後ろにあったものがシャッフル後に前に来ている確率を求めてみます。その円形部屋をA、二つのY字部屋の候補を元々前にあった方からB、Cと名付けて

1. $8$ 回の操作でAもCも一度も選ばれない
2.Aは一度も選ばれないがCが一度以上選ばれる
3.Aは一度以上選ばれるがCが一度も選ばれない
4.AもCも一度以上選ばれる

の四つに分けて考えると

1は、AとC以外の六つのみが選ばれ続け、かつ、元々先頭にあったものとBがどちらも一度以上選ばれる確率
2は、A以外の七つのみが選ばれ続け、かつ、元々先頭にあったものとBとCがすべて一度以上選ばれる確率の $\frac{1}{2}$
3は、あり得ないので $0$
4は、すべてが一度ずつ選ばれて、かつ最初の $1$ 回がAである確率の $\frac{1}{2}$

をそれぞれ求めればよいとわかります。

ほかの場合についても同じように考えることで、求める確率は $42.5055\%$ と計算できます。

Y字の二股に分かれている部分のうち、どちらが接続されるかはわかりませんが、どちらであっても左右が反転するだけなのでS字の確率を求めるだけであれば気にする必要はありません。
(補足すると、二股に分かれていない側の接続口を1、そこから時計回りに2、3として、1、2、3の列を乱数で並び替えて2と3のうち左に来たものを接続します。並び替え方は、

1.ランダムに一つ選びそれを一番左と交換する
2.ランダムに一つ選びそれを真ん中と交換する
3.ランダムに一つ選びそれを一番右と交換する

となっており、この結果、2が接続される確率は $\frac{14}{27}$ 、3が接続される確率は $\frac{13}{27}$ となります。)

ここまで来れば後は、二つある接続口のうち二股の側を選べばS字が完成するように3部屋目が置かれますから、 $\frac{1}{2}$ をかければよいです。よってS字の確率は

$0.425055 \times \frac{1}{2} = 0.212528$

ということで $21.2528\%$ となります。
(ちなみに全数調査によると正しい確率は $21.2524\%$ だそうです。)

ついでに、ここまで来ればほかの地形の確率も簡単に出すことができて

円形スタート奥二股 $43.9131\%$
円形スタート手前二股 $21.2528\%$
円形スタートS字 $21.2528\%$
Y字スタート $13.5814\%$

となります。

(Y字スタートの確率を細かく分類した図も作ったので一応載せておきます。

f:id:fuji_luck:20201121140513p:plain — 同じ矢印が伸びているところは、すべてその確率で等しいという意味です(合計ではない)

3部屋目を置くときの向きが二通りある場合、1部屋目と同じ向きになる確率が $50.1953\%$ であることを使っています。)

最後に、ポッドを置くことができる広場が複数あるフロアにおける、ポッドが特定の広場に出る確率をまとめて今回は終わりにします。

2020-10-13

ピクミン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の説明のときと同様の理屈でそれらのうち最初に生成されたものとします。)

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

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

2020-07-12

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

ピクミン2に出てくる洞窟の生成アルゴリズムが、海外のピクミンプレイヤーであるJHawk氏によって解明されました。本当に感謝しております。現在その内容を日本語で解説したものが存在しないので、まとめておきます。

僕自身が解析したわけではなく、以下の内容には誤りが含まれる可能性があります。あらかじめご了承ください。アルゴリズムそのものはhttps://github.com/JHaack4/CaveGen/blob/master/CaveGen.javaを、JHawk氏本人による解説を読みたい場合はhttps://www.twitlonger.com/show/n_1sr6vmnをご参照ください。

全体の流れは以下のようになっています。

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

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

それでは地形について書いていきます。地形はいくつかの部屋をパズルのように組み合わせていくことによって決まります。ここで部屋と言っているものは広場、通路、袋小路の3種類に分けることができます。広場は大きくていろいろなものが置ける部屋(ほとんどこれ)、通路は大きさ $1\times 1$ の一本道、カーブ、三叉路、四叉路及び大きさ $1\times 2$ の一本道、袋小路は接続口が一つしかない大きさ $1\times 1$ の部屋という認識でよいです。
(ちなみに広場、通路、袋小路はそれぞれroom、corridor、alcoveを日本語にしたもので、それらの総称としての部屋は英語ではmap unitと表記されています。部屋と広場が適切な訳か微妙なところですがここではこのまま進めます。)

f:id:fuji_luck:20200711224544p:plain — 広場の例。これの大きさは $4\times 4$

f:id:fuji_luck:20200711225116p:plain — やたらと大きいがこれで一つの広場。大きさは $14\times 14$

f:id:fuji_luck:20200711232547p:plain — 通路

f:id:fuji_luck:20200711232516p:plain — 袋小路

フロアごとに使える部屋の種類は限られており、それをまず大きさが小さい順に並べ替えます。大きさが同じ場合は接続口の数が少ない順に並べます。各フロアにおける具体的な順番はhttps://github.com/JHaack4/CaveGen/tree/master/output/!caveinfoで確認できます。

その後、各部屋を時計回りに $90^\circ$ 、 $180^\circ$ 、 $270^\circ$ 回転させたコピーを作り回転させる前のその部屋の直後に並べます。完成した部屋の列を、広場、通路、袋小路の三つのグループに(列の順番はそのままで)分けます。

通路と袋小路については全体に与える影響が小さいのでこれ以降細かい点は割愛して、広場を中心に説明します。

この時点で $4n$ 個の広場からなる列ができているはずです。この列を次のような方法でシャッフルします。

1.ランダムに一つ選びそれを一番後ろに移す
2.同じことを全部で $4n$ 回行う

このシャッフルを行った後の列は完全にランダムなものではなく、元々前の方にあったものがシャッフル後も前の方に出やすいという特徴があります(シャッフルを行う前に一番前にあった四つのうちのいずれかがシャッフル後の一番前に残っている確率が大体 $85\%$ )。

ここまでで準備が完了したので、ここから実際に地形を生成していきます。

まず初めに、広場の列の中で、ポッドを置くことができるもののうち一番前にあるものを取り出し、それをマップの上に置きます。配置の説明のときにも言及しますが、この時点でこの部屋にポッドが置かれることが確定します。

広場を一つ置いた後は、広場の列をまた並べ替えます。この操作は初めだけではなく広場を置くたびに行います。具体的には次の通りです。

1.(回転して重なるものは同じとみなして)1回以上置いた広場はすべて広場の列から取り除く
2.取り除いたもののうち置いた回数が最も少ないものを広場の列の後ろに加える(同じ回数のものは、先にその回数になったものを優先する)
3.列に加えるときは回転して重なる四つの順番をシャッフルしておく(ここでいうシャッフルとは上述した方法によるシャッフルであって、やはりランダムなものではありません)
4.2と3を繰り返す

この操作は、同じ広場をできる限り出さないようにするという効果を持ちます。

次に、その時点でマップにある接続口のうち、閉じていないものをランダムに一つ選びます。ここにつながるように次の部屋を置いていきます。この操作を、広場の数が定められた数になるまで繰り返していきます。

ただし、ここでは必ず広場が置かれるわけではなく、通路や袋小路が置かれることもあり得ます。基本的には、広場の列を前から順に探していって、回転しなくてもそこに置くことができるものを見つけ次第置く。どの広場も置くことができなければ通路の列をやはり前から探し、それでも見つからなければ袋小路の列を前から探す。このような方法で次に置く部屋を決めるのですが、これとは違う方法をとる場合があります。

各フロアにはルートの割合(CorridorVsRoomProb)という $0$ から $1$ の値が定まっており、この値と同じ確率(ただし、ランダムに選んだ接続口が広場のものである場合はこの値の2倍の確率)で、通常は広場→通路→袋小路という順で探すところを、通路→広場→袋小路という変則的な順番で探します。ルートの割合は基本的に小さい値が設定されていることが多く、 $0$ であることも珍しくないのですが、大きいところではシャワールーム7階の $0.5$ などがあります。各フロアのルートの割合は、たとえば先ほどのリンク先で確認できます。
(ルートの割合が $0$ であることが、広場と広場が必ず直接結ばれるということを意味するのではないことに注意。)

ちなみに、新しい部屋を置こうとするときに置き方が複数あるときは(ほぼ)ランダムでそのうちの一つを選びます(正確には、新しく置こうとする部屋の接続口に対して乱数で順番を決めて置けるかどうかをその順に見ていくのですが、その順番の決め方が等確率ではないのです)。また、一度地形の大きさが縦または横に $36$ マス以上になった後はルートの割合を $0$ として進めます。

先ほども書いたように、広場は一つ置くたびに、同じものをできるだけ出さないような工夫を挟むので、基本的に特定の種類の広場だけがいっぱい出るということは起きません。ただし、既に置いた部屋の位置によっては、まだ一度も置いていない広場を置こうとしてもどうやっても置くことができず、既に置いた広場をまた置かざるを得ないということが起きます。これが起きると完成した地形に特定の種類の広場ばかり存在してしまい、フロアによっては敵やお宝が消失することもあります(炎と水の試練場1階のヤキチャッピーの消失が好例、コレクタールーム6階の完全不眠土器カフェオレが消えるのもほとんど同じような理由)。

f:id:fuji_luck:20200711222740p:plain — こういう広場の置き方をすると
完全不眠土器カフェオレが消える可能性が出てくる

広場を定められた数まで置いた後は、まだ閉じずに残っている接続口を閉じることを目指します。そのため、地形の概形はこの時点で完成していることになります。
(つまりここからしばらくはあまり重要ではない。)

しばらくは、単に接続口と言っていても閉じずに残っているもののみを指します。

ここではまず初めに、接続口のうちいくつかを、通路を作らないようにマークします。マークは各接続口に対して、キャップ最大数(CapVsHallProbの訳。意味が分かりにくい気がしますが慣習的にこう呼ばれているようなので従います)と同じ確率で行います。マークされた接続口から通路が生成されることはありません(ただしほかの接続口から生成された通路の受け手となってしまい、見た目上マークされた接続口から通路が生成されているのと区別がつかなくなることはあります)。また、マークされる接続口の数は必ず $16$ 個以下にします。

マークされていない接続口に対して、それとは別の部屋にある接続口のうち(いわゆるマンハッタン距離の意味で)最も近いもの(マークされていてもよい)を探し、それが元の接続口から左(右)に $9$ マス以内かつ前に $9$ マス以内にある場合、その二つの接続口の位置(及び周囲にある既に置かれた部屋の存在)に応じて大きさ $1\times 1$ の通路のうちのいずれかを元の接続口の目の前に置きます。この操作を(マークされていない)どの接続口に対しても行えなくなるまで繰り返します。
(少し注意が必要なのが、接続口の位置は、その接続口の右側で定める場合と左側で定める場合があり、それによって見た目上は同じ位置関係であっても通路を生成する場合としない場合があるということです。マニアックな話なので詳細は余力があれば書きます。
書きました→洞窟生成アルゴリズムの補足 - fuji_luckのブログ)

ここまで終わったら、仕上げに、残っている接続口の前に袋小路を置きます。袋小路が置けない場合は通路を置きます。

この時点で地形はほぼ完成したと言えますが、ここから2種類の修正をして本当の完成とします。

一つ目は、各袋小路に対して、その真後ろに通路が置かれている場合、袋小路の方を大きさ $1\times 1$ の一本道に置き換えるというものです。真後ろにあった通路の方も整合性のとれる部屋に置き換えます。

二つ目は、大きさ $1\times 1$ の一本道が二つ連続で置かれている場合、それらを大きさ $1\times 2$ の一本道に置き換えるというものです。

これで地形が完成したので次に配置について説明していきたいのですが、長くなったのでここで一旦区切ります。