Wave Function Collapse の解説

背景

5 年前のブログの復刻版です。迷宮生成アルゴリズム "WFC" を紹介します。

オリジナル: mxgmn/WaveFunctionCollapse (23.4k stars)
参考実装: gridbugs/wfc
僕の実装: toyboot4e/wfc.cs

WFC とは何か

WFC のリポジトリにはドラマチックなデモがありました。画像や迷宮をランダム生成しています。これは一体何なのでしょうか？　Web 検索すると、波動関数だエントロピーだと謎めいた解説が目につき、謎は深まるばかりです。

そんな中、実際に WFC を使ったゲームとしては Caves of Qud がありました。開発者のプレゼンテーション Data-Driven Engines of Qud and Sproggiwood には大いに影響を受けましたから、 WFC にも時間を割いて理解してみることにしました。

なぜ WFC に熱狂したのか

WFC のスター数は 23.4k です。 Minecraft の ECS (EnTT) ですら 10.3k ですから、ゲーム開発界隈の中でも特別に注目を浴びたリポジトリと言えます。

僕自身、 WFC の万能性に熱狂しました。マップ生成のアルゴリズムは、通常 1 種類の地形に特化しています。部屋が通路で繋がれた迷宮、入り組んだ渓谷、開けた荒野、等々の地形は、それぞれ専用のアルゴリズムにより生成されます。それぞれのアルゴリズムは、せいぜいパラメータの調整しかできませんから、とても汎用的とは呼べません。

ところが WFC は『入力と類似したマップを生成する』というアイデアですから、新しい地形を作り出すには、新しい入力データを与えるだけで済みます。まるで魔法のアルゴリズム！

注意！

先に水を差してしまいますが、 WFC は万能ではありません。結局のところ、個別の専用アルゴリズムを容易した方が無難だと思います。

マップ生成には非常に長い時間がかかります
WFC の生の出力はゲームマップ向きではありません (足場が一繋がりではないなど)

WFC の『モデル』

WFC の正体は『制約充足問題』であると言われています。グリッドに NxN サイズのパターンを敷き詰めて、かつ制約に違反しない配置をランダムに見つけることで、入力データと類似した出力を生成します。

……と言っても、まったくピンと来ないと思います。より具体的に、ここでは一番面白いモデル、 Overlapping Model を紹介します。

1. パターン生成

WFC のコア・アルゴリズムは、 Solver です。 Solver は、与えられた Pattern 列を Pattern 同士の『接続性』 (AdjacencyRule) を満たすようにランダムに配置します。

Model: Input -> ([Pattern], AdjacencyRule)
Solver: ([Pattern], AdjacencyRule) -> Map

以下では単純な例でデータの流れを紹介します。

入力

このモデルでは、 NxN サイズのタイルの塊を pattern として使います。

User input = map

Model は、入力として与えられたマップから、 [Pattern] と AdjacencyRule を作ります。例として、 3x3 のマップを入力とします。

..#
.##
.#.

『パタン』のサイズを 2x2 として、入力から 2x2 のパタンを展開します。

..  .#
.#  ##

.#  ##
.#  #.

これらの回転 (rotation) や裏返し (flipping/reflection) も考えてみます（2x2 サイズでは、回転だけでも十分です）。

..  ..  #.  .#
.#  #.  ..  ..

.#  #.  ##  ##
##  ##  #.  .#    <-- (duplicated patterns)

.#  ..  #.  ##
.#  ##  #.  ..

重複を除くと、 12 個のパタンができました。 Solver はこのパタンをランダムに配置してマップを生成しますが、その際に以下の制約を設けます。

制約

Overlapping model では次の制約を課します。

出力から展開できるパタンの集まりは、入力から展開したパタンの部分集合である。

たとえば、次のような出力が得られたとします。

...
.#.
###

これを 2x2 に分けていくと、次のように 4 パタンに分かれます。これらは、どれも入力から展開できるパタンです。

(output)                  (patterns)

                            ..  ..
  ...        extract        .#  #.
  .#.    --------------->
  ###    <---------------   .#  #.
             overlap        ##  ##

これが overlapping model における制約です。 Local similarity とも呼ばれます。出力のどの部分 (NxN パタン) も入力のある部分 (NxN パタン) と一致します。

Example

僕が実装した WFC に、迷宮らしき入力を与えてみます。 # が壁、 . が床を表します。

Input (16x16)

###.########.###
###.#####......#
#.....###......#
#.....###......#
#...............
......###......#
#.....###......#
##.######......#
##.########.####
##.########.####
##......##....##
........##......
##............##
##......##....##
##......####.###
###.########.###

パタンサイズを 3x3 として走らせと、次のような出力が得られました。入力と似た風になっています。この出力から任意の 3x3 のパタンを取り出すと、それは上の入力マップからも (回転や鏡写しで) 見つけることができます。

Output (36x36)

...........##.##.##########.###.####
...........##.......#######.###.####
....................####.........###
...........##.......####.........##.
#.###.###.###.####.######.###.#####.
#.###.###.###.####.######.###.######
#.###.###.....##...######.......####
................................##..
.......##.....##...######...........
.......####.####...######.......##..
#.###.#####.####...##..########.##..
#.###.####...########..########.###.
...##.####...############..####.###.
...##.####...##..########..##.......
#.###.#########..##...###..##.......
#.###.#############...###..##.......
#..##.###....######...###..#########
...##.................##############
#......##....#######.#############..
#..###.##.##.#######.#############..
##.###.##.##.#####.....######...##..
##.##..##.......##.....######...##..
...##...........##.....######.......
#......###.###.###..............##..
#..###.###.###.###.....#######.#####
######.###.###.###.....#######.#####
######.###..##.#############.....###
............##.#############........
........##..##...##..#######.....##.
........##.......##..########.#####.
............###.###..########.#####.
........##..###.###..####.......###.
........##.......##..####.......###.
####.#####..##...##..####.......###.
####.#########...########.......###.
##....########...########...........

なお、床は 1 繋がりにはなっておらず、孤立した部分もあります。 ゲームのマップとしては、そのまま使うことはできません 。

Caves of Qud は WFC で円などの形 (segment) を埋めてから、孤立した部分を無くすプロセスを挟んでいるようです。

先ほどの出力を円形に切り出してみると、意味深になります。荒野に配置すれば魔物の巣として使えそうです。

             .......####
          ..........####...
         ..##.......####....
       ##.###.####.######.###.
      ###.###.####.######.###.#
     .###.....##...######.......
    ............................#
    ...##.....##...######........
   ....####.####...######.......##
  ###.#####.####...##..########.##.
  ###.####...########..########.###
  .##.####...############..####.###
 ..##.####...##..########..##.......
 .###.#########..##...###..##.......
 .###.#############...###..##.......
 ..##.###....######...###..#########
 ..##.................##############
 ......##....#######.#############..
 ..###.##.##.#######.#############..
 #.###.##.##.#####.....######...##..
 #.##..##.......##.....######...##..
 ..##...........##.....######.......
 ......###.###.###..............##..
  .###.###.###.###.....#######.####
  ####.###.###.###.....#######.####
  ####.###..##.#############.....##
   .........##.#############......
    ....##..##...##..#######.....
    ....##.......##..########.###
     .......###.###..########.##
      ..##..###.###..####......
       .##.......##..####.....
         #..##...##..####...
          ####...########..
             #...#######

制約充足問題の解き方

Solver は Model が定義した AdjacencyRule を満たすように Pattern 配置のグリッドを作ります。と言っても確実な計算方法があるわけではなく、『試して上手くいったら採用』という形になります。ただし『こうすればよく上手くいく』という『発見的手法 (heuristic)』に頼ります。

ここから解説が投げ槍になります！

The solving loop

出力グリッドを『未確定』の状態で初期化してから、 Solver は走ります:

public class Solver {
    // ~~
    public bool run() {
        while (this.numRemainingCells > 0) {
            var cell = selectNextCellToDecidePattern(); 
            var pattern = selectStiilAvailablePatternForCell(cell); 
            decidePatternOfCell(cell, pattern); 
            this.numRemainingCells -= 1;
            propagateRemovals(); 
        } 
    }
}

パタンが未確定のセルを 1 つ選びます (後述の heuristic を使用)。
そのセルにまだ配置可能なパタンを選びます。
このセルを選んだパタンで確定し、その他のパタンをセルの配置可能パタンから remove します。
パタンが配置不能になった (remove した) 事による影響を伝播 (propagate) させます。すなわち、配置可能パタンのキャッシュを更新します。
ループ開始へ戻り、再び次のセルが選ばれます。すべてのセルのパタンを確定させたら終了です。

ただし、配置可能なパタン数が 0 となるセルが出た場合は、失敗です。そのときは、今は最初からやり直すことにしておきます (後述) 。

各手順を詳しく解説します。

1. Selecting "the most constrained" cell (pattern weight heuristic)

未確定のセルから、次にパタンを確定させる0セルを選びます。このときヒューリスティックとして、最も "制約された" セルを選びます。具体的には、パタンが source に現れた回数をそのパタンの重み付けとし、重みの総和が最も小さなセルを選びます。すなわち重複したパタンの出現回数を増やします。

効率のため、 BinaryHeap に重みづけされたセルを入れて 1 つずつ取り出します:

セル毎に、重さのキャッシュを作ります
セルの重み付けが更新されたとき、そのセルを新たに BinaryHeap に入れます (これで古いデータよりも先に出てくるようになります)
重みの総和に小さな乱数を足すことで、重みの等しいパタンの選出をランダムにします

Wave Function Collapse の解説

背景

WFC とは何か

なぜ WFC に熱狂したのか

注意！

WFC の『モデル』

1. パターン生成

入力

User input = map

制約

Example

制約充足問題の解き方

The solving loop

1. Selecting "the most constrained" cell (pattern weight heuristic)

2. Selecting a pattern

3. Constraint propagation

Enabler counts

Removals of patterns

4. Repeating until solved

Wrapping up