In Silico

シミュレーション・制御・実機

Wave Function Collapseの仕組み：地図デモで動かして理解

2026/6/29 （更新: 2026/10/10）

🤖 AIを使用して執筆

  • Wave Function Collapse
  • 制約充足
  • Model Synthesis
  • 伝播
  • 収縮
  • 最小エントロピー
  • 隣接規則
  • エントロピー
  • バックトラック
  • 大域リスタート
  • NP困難
  • ソルバ
  • タイル
  • 波動関数
  • 量子力学
  • 情報理論
  • 地図
  • 制御
  • Maxim Gumin
  • Karth & Smith
目次
背景・問い・要点
背景

地図やゲームの面を自動で作るとき、タイルどうしの隣接規則を決め、規則に合う配置をプログラムに埋めさせる方法がある。使う人が求めるのは、規則に合うどれかの配置ではなく、指定した場所に指定したタイルが来る配置である。指定どうしが規則と矛盾していれば、条件を満たす配置はそもそも存在しない。

本稿は、Maxim Gumin が公開した WaveFunctionCollapse（WFC）の手順で動く小さな対話デモを例に取る1。Gumin の README は WFC を、入力画像から取った小さなパターンだけを使い、入力に局所的に似た画像を作るプログラムとして説明している。本稿のデモは、README が「simple tiled model」と呼ぶ、入力画像の代わりにタイルと隣接規則を直接与える型にあたる1。

問い

使う人がセルを固定したとき、隣接規則に従うソルバは固定をどう扱い、固定どうしの矛盾をどの時点で見つけられるのか。

要点

ソルバは固定を動かせない制約として受け取り、残りのセルを規則と矛盾しないように埋め、矛盾した固定には地図を捏造せず「解なし」と返す。タイルが3種類で規則が一つの世界では、探索を始める前の伝播だけで可否が決まる。同じ固定からでも別の地図がいくらでも出るので、難しくて価値があるのは狙った地図を出す制御の側である。

モデル・例示

海・浜・陸の3タイルで地図を埋める

デモの世界は小さい。タイルは海・浜・陸の3種類で、規則は一つだけである。海と陸は上下左右で隣り合えない（必ず浜を挟む）。

セルをクリックすると、未指定 → 海 → 浜 → 陸 → 未指定 と切り替わる。読み込んだ時点で海と陸が一つずつ固定してあり（紫の枠）、その固定から作った地図がすでに出ている。固定を足したり外したりして「生成」を押してほしい。ソルバはあなたの固定（制約）を尊重して周りを埋め、海と陸を直接隣り合わせるような矛盾した制約には、地図を捏造せず「解なし」と答える。あなたが置く固定が、狙った地図を出すための制御にあたる。

海 浜 陸 =固定

セルをクリック（またはキーボードで選び Enter）して海・浜・陸を固定し、「生成」を押す

ソルバの手順

考え方は単純である。グリッドの各セルは、最初「海・浜・陸のどれにでもなれる」という未確定の状態で始まる。効く規則は一つだけで、海と陸は上下左右で隣り合えない（あいだに必ず浜が要る）。規則が見ているのは上下左右の4方向だけなので、斜めは対象外である。生成した地図では、海のマスと陸のマスが角で接している箇所がいくつも残る。この一行の制約だけで、地図全体の形が決まっていく。

ソルバの手順は次の通りである。

  1. 最も迷いの少ないセルを選ぶ。 まだ複数の候補が残るセルのうち、選択肢が最も少ないもの（情報理論でいう「エントロピーが最も低い」セル）を一つ選ぶ。最も確定に近いところから手をつける、という発想である。ただしタイルが3種類しかない世界では、候補が複数残っているセルの候補数は3か2のどちらかにしかならない。だからこの基準は実質「海か陸に決まったセルの隣（候補が2つに減ったセル）を先に片づける」と同じ意味になる。
  2. そのセルを一つに決める（収縮＝collapse）。 残った候補の中から一つを無作為に引き、そのセルのタイルを確定させる。Wave Function Collapse という名前は、この手順を波動関数の収縮になぞらえたものである。名前は比喩で止まる。Gumin 自身が、重ね合わせの係数は「実数であって複素数ではないので、実際の量子力学をやっているわけではない。ただ QM に着想を得た」と断っている1。
  3. 制約を周りへ伝える（伝播＝propagation）。 確定したセルに隣接するセルから、規則に反する候補を消す。たとえば海に確定したセルの隣からは「陸」が消え、「海」か「浜」だけが残る。仕組みの上では、候補が減ったセルからさらにその隣へ、と影響が玉突きに広がることもありうる。ただしこの規則では広がらない。浜はどのタイルとも隣り合えるため、未確定のセルから浜が消えることはなく、浜を残したセルは隣のどの候補も支えてしまうからだ。伝播は直接の隣で必ず止まる。浜に確定した場合に至っては、隣の候補は一つも減らない。
  4. 1〜3を、すべてのセルが確定するまで繰り返す。 一般の WFC では、探索の途中でどこかのセルの候補がゼロになることがある。それはそこまで選んできた道が行き詰まったということであって、「この制約では整合する地図が存在しない」ことの証明ではない。素の WFC は行き詰まっても後戻り（バックトラック）せず、種を変えて最初からやり直すだけだからである2。海・浜・陸のソルバにも同じ仕掛けが入っていて、行き詰まったら乱数列を振り直して最大40回まで試す。

「解なし」が探索の前に決まる理由

行き詰まったときの引き直しは、海・浜・陸のソルバでは一度も動かない。3タイルで規則が一つしかない世界では、探索を始める前の一段階で可否が決まってしまうからだ。固定だけを見て制約を伝播させ、その時点で候補が尽きたセルがあれば、残りをどう埋めても矛盾する。ソルバは、海と陸を直接隣り合わせた固定をこの段階で検出する。逆に、その事前の伝播を生き延びた固定からは、一つずつ決めていけば行き詰まらずに最後まで埋まる。だから「解なし」は探索を始める前に言い切れるし、「今回は見つかりませんでした」という三番目の返事には出番がない。

行き詰まりと引き直しが効いてくるのは、タイルも規則もずっと多い世界である。そちらでは可否の判定そのものが重い。ある入力が非自明な出力を許すかを決める問題は NP困難で、「常に停止する速い解法を作ることは不可能」だと Gumin は書く。ただし同じ場所で「実際には、このアルゴリズムが矛盾に行き当たることは驚くほど稀である」とも続けている1。最悪計算量の重さと、実務での当たりやすさは別の話だということだ。大域制約を足すと、矛盾が稀でなくなる場面がある。Karth & Smith は、WFC を解答集合プログラミングで書き直した代理実装に、入力のどのパターンも出力で最低1回は使うという制約を足した。Gumin の場面から選んだ3つ（Flowers・Platformer・Skyline）のうち、衝突が数百件に増えたのは Skyline だけで、そこでは衝突のたびに大域リスタートする設定だと1分以内に解けず、後戻りを許すとすぐ解けたと報告している2。

セルを固定するという行為は、手順1の前にいくつかのセルを先に確定させておくことに等しい。Gumin も README で、WFC は制約を扱えるので人が途中まで作った面の残りを埋めさせる使い方ができると書き、最小エントロピーの選び方はあらかじめ制約を置いた問題に向くとしている1。ソルバはその固定を動かせない制約として受け取り、残りをその制約と矛盾しないように埋める。だから固定が穏当なら、固定したセルを守った地図が出るし、海と陸を直接隣り合わせるような固定を置けば、探索を始める前の伝播で矛盾が見つかり「解なし」と返ってくる。重い数式は要らない。「最も迷いの少ないところから決め、決めたら周りに伝える」、本質はそれだけである。

同じ固定から別の地図が出る

制約の伝播は決定論的だが、収縮のたびに引く一手は無作為だ。種を決めれば地図は一意に定まる。ただし海・浜・陸のソルバは種を表に出さない。「生成」も「種を変えて再生成」も、押すたびに新しい種を引く。だから同じ固定のまま押し直せば、固定していないセルの配置が引き直され、未固定のセルが多い盤面では地図はほぼ毎回変わる。同じルールから別の地図がいくらでも出るのに、狙った地図を出すことだけが難しい。

WFC の出自

アルゴリズムを広めた実装は Maxim Gumin の WaveFunctionCollapse である。ただし先行があり、Gumin 自身が README でポール・メレルの Model Synthesis（2009）を挙げ、その手法を一般化したと書いている（Karth & Smith も、Gumin がメレルの手法に着想を得たと記している）。これが実質的に制約充足問題の解法であることは Karth & Smith が論じている2。

出典2件

  1. M. Gumin「WaveFunctionCollapse」README, GitHub（2026-08-06 取得）. https://github.com/mxgmn/WaveFunctionCollapse — Merrell の Model Synthesis（2009）をパターン単位へ一般化し、最小エントロピーで選ぶと書く。係数は実数で量子力学そのものではないこと、判定は NP困難だが矛盾は稀だとも書く。 ↩ ↩2 ↩3 ↩4 ↩5

  2. Karth & Smith「WaveFunctionCollapse is Constraint Solving in the Wild」FDG 2017. https://dl.acm.org/doi/10.1145/3102071.3110566 — WFC を制約解法として読み直し、大域リスタートのみの設計は元の画像生成には妥当だが、大域制約を足すと局所的な後戻りとの併用が要ると論じる。著者ホスト版 https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf ↩ ↩2 ↩3

この記事はAIを使用して執筆されました。内容には誤りが含まれる可能性があります。事実や数字の出典は脚注から確かめられます。