WaveFunctionCollapseについて
概要
WaveFunctionCollapse（WFC）はMaxim Gumin氏が公開している描画ライブラリで、用意したタイル画像を自動で繋ぎ合わせて新たな画像を生成する機能を持つ。
もとはC#で書かれたライブラリであり、現在は多数の他言語に移植されているが、この記事では本家のWFCの特徴と内部のアルゴリズムについて解説を行う。
WFCを利用している代表的なアプリケーション
Steam等で公開されている上記2つのゲームはWFCを内部で利用している。特に下側の、水上で町を作るゲームである「Townscaper」は2021年12月にブラウザ向けのデモ版が無料で公開されたことにより話題になった。
WFCのモード
WFCには SimpleTiledModel と OverlappingModel の2つのモードがあり、それぞれのモードに合わせて素材となる画像を用意する必要がある。
SimpleTiledModel
このモードは1つ以上のタイル画像と、タイルを繋ぐためのルールを用意する。ルールはたとえば a というタイルの右側に b のタイルを置いていい、のようなタイル間の繋がりを表すもので、本家のWFCでは下記のようなXMLにルールを追加していく。
<set size="9"> <!-- 下記で指定したタイルサイズは全て9x9である -->
<tile name="a" weight="1" /> <!-- a.png 重み1 -->
<tile name="b" weight="2" /> <!-- b.png 重み2 -->
<neighbors>
<neighbor left="a" right="b"/> <!-- ルール1 -->
<neighbor left="a 1" right="b 2"/> <!-- ルール2 -->
</neighbors>
</set>
指定するタイル画像は全て縦横同じサイズでなければならない。そのサイズを <set> の size に指定する。
png形式のタイル画像を用意して <tile> の name に拡張子を抜いたファイル名を、weight に重みを指定する。重みによってタイルが選ばれる確率が決まり、アルゴリズムは重み付き抽選で、上記XMLの設定例だとタイルaが 1/3、タイルbが 2/3 の確率で選ばれることになる。重みは指定しなければデフォルトで 1 になる。
次にルールの設定を行う。<neighbors> の下に <neighbor> を置くことで1つずつルールを設定することができる。
上記XMLの1つ目のルールは、タイルaが置かれている場所の右側にタイルbを置いていい、もしくはその逆の立場である、タイルbが置かれている場所の左側にタイルaを置いていい、という意味になる。
2つ目のルールには a 1, b 2 のようなタイル名の後に数字が書かれており、これは数字の回数だけ45度回転させるという意味になる。なので、(45*1)度回転させたタイルaが置かれている場所の右側に(45*2)度回転させたタイルbを置いていい、というルールになる。（上と同じで逆の立場も含める）
このモードでは上記のように、タイルとルールをユーザー側で作成して、あとは生成をWFCに任せるというものになる。タイル間の繋がりを自由に決めれるので細かいカスタマイズ向けのモードだが、活用するにはかなりの量のルールを定義する必要がある。
OverlappingModel
先程の SimpleTiledModel と違い、この OverlappingModel というモードでは、1枚の画像を用意するとタイル画像、タイルの重み、ルールを自動生成するというものになる。
まずタイル画像を生成するために N という値を別途指定する。たとえば N=3 の場合、用意した画像から、考えられるすべてのパターンの 3*3 の領域を切り抜いてタイル画像が作られる。デフォルトの設定では切り抜いたタイルを回転あるいは反転したものもパターンに含めるのでかなりの数のタイルが生成される。
切り抜いたタイルの重複を除いたものがこのモードで使用されるタイル画像になる。切り出したタイルの重みは 1 になるが、重複があったタイルはその重複分の数が重みとして設定される。
次にタイル間の繋がりを決めるルールを自動で作成する。SimpleTiledModel の場合と違い、ルールはユーザー側から指定されない以上、タイル間に共通部分があるかどうかで繋がりの判定を行う必要がある。
### | ###
#.# | .##
### | ###
上記は # と . で作られた2つの3x3のタイルだ。これらが左右に繋がっているかは、左タイルの右側N-1列と、右タイルの左側N-1列が一致しているかを確認する。
123 | ABC 1 [2=A] [3=B] C
456 | DEF => 4 [5=D] [6=E] F
789 | GHI 7 [8=G] [9=H] I
もう少し詳しく説明すると、右タイルの A を左タイルの 2 の位置に重ねるように配置して、重なっている部分が同じ値ならタイル間に繋がりがあると判定される。
// 左右に繋がっている例
### | ###
#.# | .##
### | ###
// 左右に繋がっていない例
### | ###
.## | #.#
### | ###
上側の例では左右に繋がっているが、タイルの位置を入れ替えた下側の例では左右に繋がっていない。なので、左側のタイルをA、右側のタイルをBだとすると、A-B の繋がりと B-A の繋がりは別々にチェックする必要がある。
123 1 2 3
456 [4=A] [5=B] [6=C]
789 [7=D] [8=E] [9=F]
--- => G H I
ABC
DEF
GHI
上下の繋がりの判定も同様で、上タイルの下側N-1行と、下タイルの上側N-1行が一致していたら上下に繋がりがあると判定される。
// aの右側n-1列とbの左側n-1列が一致しているか？
function checkRight(n: number, a: Tile, b: Tile): boolean {
for (let x = 0; x < n - 1; x++) {
for (let y = 0; y < n; y++) {
if (a.get(x + 1, y) !== b.get(x, y)) {
return false;
}
}
}
return true;
}
AAだけでは分かりづらいので、筆者がTypeScriptに移植した際に書いたコードを載せておく。
切り出した全てのタイル同士を上下左右に繋がっているかを比較して、繋がっているならその情報をルールに追加する。
ここまでで各モード毎にタイル、タイル毎の重み、ルールを作ることができた。以降は描画を行うまでモードに依存しない共通処理になる。
waveの作成
// 0 = #
// 1 = .
1,0,0,1 .##.
1,1,0,0 => ##..
0,1,1,1 .###
2Dゲームのマップを作る場合、マップ用の配列を用意してタイル番号を入れておき、そのタイル番号に応じたタイルを描画する、というケースが多い。
WFCでも同じように、最終的に出力する画像用の配列を用意するが、自動生成によってタイルが配置されるので、配列内の各位置の値がこれである、と最初に決めることが出来ない。
なので配列内の各要素には「この位置に入る可能性がある全てのタイル番号」を格納しておく。この配列のことを wave と呼び、wave 内の要素のことを今後はセルと呼ぶ。
[0,1,2], [0,1,2], [0,1,2]
[0,1,2], [0,1,2], [0,1,2]
[0,1,2], [0,1,2], [0,1,2]
上記は3x3の wave 配列、タイルが3種類ある場合の例で、どのセルも初期の段階では全てのタイルが入る可能性があるので [0, 1, 2] と全てのタイル番号を格納している。
最小のエントロピーを持つセルを選択
1つのセルに複数のタイル候補があると、どのタイルを描画すればいいのかが分からないので、あるセルの中のタイルを確定させる必要がある。
WFCでは1回のイテレーションで1つのセルを選び、そのセルのタイルを確定させる処理を行う。
なので、まずはどのセルを選ぶのかを決めよう。
セルA = [1, 1, 1]
セルB = [1, 1, 2]
上記は2つのセルの中にあるタイルの重みリストになる。セルAの方は重みが全て 1 なので、3つのタイルはどれも等確率で選ばれる可能性がある。それに比べてセルBは最後のタイルだけ重みが2倍になっている。
セルA、セルB共にまだ利用されるタイルが確定していないが、セルBの重みに偏りがある以上、どちらかというとセルBの方がこのタイルが選ばれるだろうなという予測が付くだろう。つまり、どのセルも確定していないなら、せめて一番「曖昧でない」セルを選びたい。
これを感覚的な判断ではなく、ちゃんとした数値による尺度で測りたい。ここでエントロピーという概念を利用する。エントロピーの尺度では曖昧な事象ほど値が大きくなるので、セルAよりセルBの方がエントロピーが小さくなる。今は一番曖昧でないセルを選びたいので、最もエントロピーが小さくなるセルを選択すればいい。
具体的なエントロピーの計算式は後で詳しく説明する。
選択したセルのタイルを確定
最小のエントロピーを持つセルを選択した後は、そのセルの中身を確定させる必要がある。セルの中にはそこに入り得るタイル番号が書かれており、そのタイル毎に重みが付いているが、この重みによってタイルをランダムに選ぶ。たとえばタイル毎の重みが [1, 2, 3] であった場合、各タイルが選ばれる確率は [1/6, 2/6, 3/6] になる。
他セルのタイル候補の削減
[0,1,2], [0,1,2], [0,1,2] [1], [0,1,2], [0,1,2]
[0,1,2], [0,1,2], [0,1,2] => [0,1,2], [0,1,2], [0,1,2]
[0,1,2], [0,1,2], [0,1,2] [0,1,2], [0,1,2], [0,1,2]
上2つの手順により、たとえば左上のセルが 1 で確定したとする。このとき、ルールを確認して、もし 1 の右側に来るタイルが 0 しかない場合、1つ右側のセルが 0 以外になることはない。
[1], [0,1,2], [0,1,2] [1], [0], [0,1,2]
[0,1,2], [0,1,2], [0,1,2] => [0,1,2], [0,1,2], [0,1,2]
[0,1,2], [0,1,2], [0,1,2] [0,1,2], [0,1,2], [0,1,2]
なので、1つ右側のセルのタイル番号が 0 だと確定される。右だけではなく他の3方向も同じようにタイル間の矛盾があればタイル候補を削減していく。
上記例のように、周りのセルから候補が1つ以上減った場合、更にそのセルの周りである上下左右のセルを見てルールと適合していないタイル候補があれば削減、と再帰的にセルを確認していく。
[1], [0], [2]
[0,2], [0,1,2], [0,1]
[1], [0], [2]
この再帰的な処理により、ある程度タイル候補が絞られた。しかし、確定していないタイルがあるため、また最小のエントロピーを持つセルを選び、今までの処理を繰り返す。
[1], [0], [2]
[0], [2], [1]
[1], [0], [2]
これらの処理を繰り返すと、wave 配列の全てのセルのサイズが 1 になり、各セルにおけるタイル番号が確定する。
描画
全てのセルのタイル番号が確定したので、その番号をもとに描画を行う。
SimpleTiledModel
SimpleTiledModel の場合はタイル番号をもとにタイル同士が重ならないように普通に描画を行う。
OverlappingModel
OverlappingModel の場合は各タイルの左上1x1ピクセルだけを描画する。
123 | ABC 1 [2=A] [3=B] C
456 | DEF => 4 [5=D] [6=E] F
789 | GHI 7 [8=G] [9=H] I
なぜ左上1x1ピクセルだけを描くのかを考えるために、OverlappingModel における左右の繋がりの例をまた見てみよう。3*3のタイルの場合、端の2列が一致していると繋がっているということなので、この共有している部分は多重に描く必要がない。なので、上記例で見ると、左側タイルを描く場合は 1 だけを、右側タイルを描く場合は A のピクセルだけを描画すればいい。
処理の流れ
ここまでの流れをまとめると以下の通りになる。
1. タイル画像の用意
SimpleTiledModel の場合は利用するタイル画像を1つ以上用意する。複数枚用意する場合はすべて縦横のサイズが同じになるように統一する。
OverlappingModel は1枚の画像だけを用意する。
2. ルールの作成
SimpleTiledModel の場合はルールをXMLに書き込む。
OverlappingModel は自動生成されるので必要ない。
3. タイル毎の重みを作成
SimpleTiledModel の場合はタイル毎の重みをXMLに書き込む。
OverlappingModel は自動生成されるので必要ない。
4. waveの作成
最終的に出力する画像のサイズがたとえば10x10だとすると、その領域が入る wave 配列を用意。配列の要素には全てのタイル番号が入った配列を入れる。
5. イテレート
すべてのセルが確定するまで、以下5-1～5-3の処理をセットで繰り返す。
5-1. 最小のエントロピーを持つセルを選択
各セルのタイル候補の重みをみて、一番曖昧でないセル、つまり最小のエントロピーを持つセルを選択する。
5-2. 選択したセルのタイルを確定
選択したセルから、重みつき抽選によりタイル候補からタイルを確定させる。
5-3. 周りのタイルの候補を減らす
今確定したセルの周りを見て、ルールと矛盾しているセルがあるなら、そのセルのタイル候補を削減する。更にそのタイルから周りを見て・・・と再帰的に削減処理を行う。
6. 描画
確定したタイル情報をもとに画面に描画を行う。
エントロピーの計算
function calcEntropy(cell: Cell, weights: number[]): number {
let sumOfWeights = 0;
let sumOfWeightLogWeights = 0;
for (const tileIndex of cell) {
const weight = weights[tileIndex];
sumOfWeights += weight;
sumOfWeightLogWeights += weight * Math.log(weight);
}
const entropyA = -sumOfWeightLogWeights / sumOfWeights;
const entropyB = Math.log(sumOfWeights);
const entropyC = 0.000001 * Math.random();
return entropyA + entropyB + entropyC;
}
本家で書かれているセル毎のエントロピーを求める計算を、筆者なりに噛み砕いてわかりやすくしたTypeScriptのコードが上記になる。この関数では entropyA, entropyB, entropyC の3つのエントロピーを求めてそれらの合計がセルのエントロピーになる。まずは entropyA の計算を見てみよう。
エントロピーA
前にも説明したとおり、セルの内容が曖昧であるかないかを数値として表現するためにエントロピーを使用する。その計算式が下記のとおりになる。
// 上記式をコードに落とした例
let ent = 0;
for (const E of Ω) {
ent += P(E) * Math.log(P(E));
}
const H = -ent;
タイルごとに
エントロピーB
エントロピーBの式は Math.log(sumOfWeights) で、sumOfWeights はそのセルにおけるタイルの重みの合計であり、その値の対数を取ったものがエントロピーBになる。本家のコードにコメントが書かれていないので推測になるが、このエントロピーが必要なのは「詰み防止」のためだと思われる。
選ばれたセル内のタイルは、上下左右にある既に確定したタイルと繋がっていなければならないので、毎回バラバラの位置のセルが選ばれると、後に選ばれるセルのタイル候補が極端に減り、上下左右のタイルとマッチしないという詰み条件が出る可能性が高まるので、次に選ばれるセルは既に確定したセルに直接繋がっているものだと都合がいい。sumOfWeights はセル内のタイル候補が消えるたびに値が減っていくので、このエントロピーを加味すると確定したセルの回りにあるセルが選ばれやすくなる。
エントロピーC
上記2つのエントロピーだけだと、初期のイテレーションを行っているときに、最小のエントロピーを持つセルが複数出る場合が多くなる。この場合、左上や右下など、セルの走査方向に依存した特定のセルが選ばれやすくなるので、若干のランダム値を付け加えたい。ただし、既存のエントロピーに影響が出ると困るので 0～0.000001 のような非常に小さなランダム値を付け加えるだけでいい。
WFCを扱う上での注意点
必ずしも生成が成功するわけではない
あるセルのタイル候補が無くなると 、それに立て続けて、繋がっているセルのタイル候補も無くなり、結果すべてのセルのタイル候補が無くなる。
なので1つのセルでもタイル候補が無くなるとWFCでは生成が失敗扱いとなる。これは稀にではなく結構な頻度で起こり得るので、内部では繰り返し実行するシステムが存在する。
実行速度
OverlappingModel でタイルを切り出す際、たとえばもとの画像サイズが 30x30、切り出すタイルサイズが N=3 という小さなものでも、最大で900種類のタイルが作られ、回転や反転を含めると数千単位のタイル数になる可能性がある。本家で実装されているタイル候補を削減するアルゴリズムはそれなりに最適化されているとはいえ、指定した値が少しでも大きくなると応答が返ってこなくなることがよくある。そのため、画像サイズはできるだけ小さくして、回転や反転を行わない、画像は単純なパターンが入ったものにする、などの工夫が必要になる。
Discussion