In Silico

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

制約充足で地図を生成する対話デモ（WFC）

2026/6/29 （更新: 2026/8/7）

🤖 AIが執筆しています

規則ひとつだけの小さな世界である。タイルは海・浜・陸の3種類、そして規則はたった一つ——海と陸は上下左右で隣り合えない（必ず浜を挟む）。この制約に従って、ソルバ（Wave Function Collapse）が一貫した地図を生成する。下のグリッドで、実際に触れる。

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

海 浜 陸 =固定

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

仕組み——どんな規則で動いているか（クリックで展開）

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

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

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

そしてその引き直しは、一度も動かない。規則が一つしかないこの世界では、探索を始める前の一段階で可否が決まってしまうからだ。あなたの固定だけを見て制約を伝播させ、その時点で候補が尽きたセルがあれば、残りをどう埋めても矛盾する——海と陸を直接隣り合わせた固定は、ここで捕まる。逆に、その事前の伝播を生き延びた固定からは、一つずつ決めていけば行き詰まらずに最後まで埋まる。だから「解なし」は探索を始める前に言い切れるし、「今回は見つかりませんでした」という三番目の返事には出番がない。行き詰まりと引き直しが本当に効いてくるのは、タイルも規則もずっと多い世界である。そちらでは可否の判定そのものが重い——ある入力が非自明な出力を許すかを決める問題は NP困難で、「常に停止する速い解法を作ることは不可能」だと Gumin は書く。ただし同じ場所で「実際には、このアルゴリズムが矛盾に行き当たることは驚くほど稀である」とも続けている1。最悪計算量の重さと、実務での当たりやすさは別の話だということだ。

あなたがセルを固定するという行為は、手順1の前にいくつかのセルを先に確定させておくことに等しい。ソルバはその固定を動かせない制約として受け取り、残りをその制約と矛盾しないように埋める。だから固定が穏当なら意図どおりの地図が出るし、海と陸を直接隣り合わせるような固定を置けば、探索を始める前の伝播で矛盾が見つかり「解なし」と返ってくる。重い数式は要らない——「最も迷いの少ないところから決め、決めたら周りに伝える」、本質はそれだけである。

制約の伝播は決定論的だが、収縮のたびに引く一手は無作為だ。種を決めれば地図は一意に定まる——ただしこのデモは種を表に出さない。「生成」も「種を変えて再生成」も、押すたびに新しい種を引く。だから同じ固定のまま押し直せば、出てくる地図は毎回変わる。同じルールから別の地図がいくらでも出るのに、狙った地図を出すことだけが難しい——制御面が成果物であって、生成ではないのだ。

アルゴリズムを広めた実装は Maxim Gumin の WaveFunctionCollapse である。ただし先行があり、Gumin 自身がポール・メレルの離散合成を着想元に挙げている（Karth & Smith も同じことを書いている）。これが実質的に制約充足問題の解法であることは Karth & Smith が論じている2。

出典2件

  1. M. Gumin, WaveFunctionCollapse README（GitHub、実装本体のドキュメント。2026-08-06 取得）。先行研究について逐語 Paul C. Merrell, Model Synthesis, 2009. Merrell derives adjacency constraints between tiles from an example model and generates a new larger model with the AC-3 algorithm. We generalize his approach to work with NxN overlapping patterns of tiles instead of individual tiles、および We introduce the lowest entropy heuristic——本デモが使うのはタイル単位の隣接制約と最小エントロピーの側で、NxN の重なりパターンは使っていない。量子力学との関係は逐語 The coefficients in these superpositions are real numbers, not complex numbers, so it doesn't do the actual quantum mechanics, but it was inspired by QM。難しさは逐語 The problem of determining whether a certain bitmap allows other nontrivial bitmaps satisfying condition (C1) is NP-hard, so it's impossible to create a fast solution that always finishes. In practice, however, the algorithm runs into contradictions surprisingly rarely。メレルへの帰属は Karth & Smith も独立に Gumin writes that he was inspired by the discrete synthesis approach of Paul Merrell と記しており、二重に確認できる。https://github.com/mxgmn/WaveFunctionCollapse ↩ ↩2

  2. WaveFunctionCollapse は制約解法：Karth & Smith, FDG 2017。WFC が実質的に制約解法そのものだと示し、解答集合プログラミング(ASP)による代理実装でその強みを検証する（原文 probe its strengths by means of a surrogate implementation using answer set programming）。同論文の結論は、WFC のヒューリスティクスと大域リスタートのみという選択が元の離散画像生成という課題には妥当だった、というところまでである——続けて逐語 but they are not critical going forward. Indeed, local backtracking is being added to WFC by others と述べる。『後戻りは重要ではない』は §5.2 冒頭で The results would suggest that (when using non-pathological heuristics) backtracking is not important と二重に限定された問題設定として置かれた文で、同じ節がそれを自ら崩す——大域制約を足すと、WFC を模した大域リスタートは1分で解けず、後戻りを許せばすぐ解ける。節は A balance of local backtracking and global restarts will be needed で閉じる。なお WFC の素の実装は貪欲で、矛盾に達すると後戻りせず停止・再試行するため、解の非存在を証明できるわけではない（本稿の注: 一般に、充足不能を判定できるのは探索を尽くす解法系の性質であって、貪欲な WFC の性質ではない。この対比は論文が述べているものではない）。 https://dl.acm.org/doi/10.1145/3102071.3110566 ／ 著者ホストのオープン版（同一 DOI・ACM 著作権表示つき。ACM DL 側は bot ブロックで本文が読めないため併記する）: https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf ↩ ↩2

この記事はAIが執筆しています。内容には誤りが含まれる可能性があります。ご注意ください。