波動関数崩壊

ひとことで

マス目の各マスに「置ける可能性のあるタイルの候補」を持たせ、候補が一番少ないマスから 1 つずつタイルを決め、その影響（隣に置けなくなったタイル）を周りへ次々に伝えていくことで、隣り合わせのルールを必ず守った配置を作る方法です。「隣にはこのタイルしか置けない」という局所的なルールだけで、全体としてまとまりのある地形や街並みができます。名前は量子力学のたとえ（重ね合わせの状態が観測で 1 つに決まる）から来ています。

ゲームでの使いどころ

• タイルマップの自動生成：地形、ダンジョン、街の道路や建物の並びを、タイルのつながりのルールだけで作る（『Townscaper』『Bad North』『Caves of Qud』などで知られる）。
• 3D のモジュール配置：壁・床・階段などの 3D パーツを、つなぎ目が合うように組み立てる。
• サンプル画像からの生成：小さな見本の絵から「どの模様が隣り合うか」を学び、似た雰囲気の大きな絵を作る（オーバーラップモデル）。
• レベルの穴埋め：デザイナーが一部を手で置き、残りを WFC で埋める。すでに置いたタイルも制約として扱える。

しくみ

各マスの候補の集合を $D(c)$ とし、最初はすべてのタイルが候補です。

1. 観測：候補が 2 つ以上あるマスのうち、候補の数（エントロピー）が最も少ないマスを選び、タイルの出やすさの重みに従って 1 つに決めます。
2. 伝播：決めたマスの隣について、「今の候補のどれかと隣り合えるタイル」だけを残します。

候補が減ったマスについても同じことをくり返し、変化がなくなるまで伝えます。3. 矛盾：途中で候補が 0 のマスが出たら、その配置は行き詰まりです。最初からやり直すか、直前の選択に戻ってやり直します（バックトラック）。4. すべてのマスの候補が 1 つになったら完成です。

候補が最も少ないマスから決めるのは、選択肢が少ないマスほど後回しにすると矛盾しやすいからです。数独を解くときに、候補の少ないマスから埋めるのと同じ考え方です。

実装のポイント

• ビット集合で持つ：タイルが 32 種類以下なら、候補を 1 つの整数のビットで表すと、共通部分や和集合が一瞬で計算できます。
• 辺の種類（ソケット）でルールを書く：タイルごとに 4 辺の「接続の種類」を決め、向かい合う辺の種類が合えば隣り合えるとすると、ルールを 1 つずつ書かずにすみます。
• 重みで雰囲気を調整：出やすさの重みを変えると、空き地の多い街や、森の多い地形など、全体の雰囲気が変わります。すでに決まった隣と同じタイルを選びやすくすると、まとまった地域ができます。
• 外周の制約：マップの外へ道が伸びないよう、外周のマスから外向きに接続するタイルを最初に除いておきます。

つまずきやすい点

• 全体の構造は作れない：WFC は隣どうしのルールしか見ないので、「入口から出口まで必ずつながる」「部屋がいくつある」のような全体の条件は保証できません。必要なら後から検査し、満たさなければ作り直します。
• 矛盾が多すぎる：ルールが厳しいと、何度やり直しても完成しません。バックトラックを入れるか、ルールをゆるめます。
• 単調・ばらばらになる：局所のルールだけだと、大きな地形のまとまりができにくいことがあります。ノイズなどで大まかな地域を先に決め、それを制約として与えると自然になります。

デモで試すこと

1. 「地形」では、紫のマス（まだ決まっていない）が、明るい（候補が少ない）所から順に決まっていきます。赤いマスが今決めたマスです。
2. 完成した地形で、海の隣に山が来ていないこと、海と草原の間に必ず砂浜があることを確かめてください。1 段違いまでしか隣り合えないルールだけで、こうなります。
3. 「道路」に切り替えると、辺の接続がそろうタイルしか置けないので、途切れない道路網ができます。外周から外へ道が出ていないことも確かめてください。
4. 「1 秒に決めるマスの数」を小さくすると、1 マス決めるたびに周りの候補が減っていく（明るくなる）様子がよく見えます。