ピクミン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のブログ)