最強のアルゴリズム「Wave Function Collapse」でヘックスマップを自動生成しよう！

Wave Function Collapse（WFC）アルゴリズムを活用して、プロシージャル（手続き型）なヘックスマップ（六角形グリッド）を構築する手法についての投稿です。タイル同士の隣接ルールを定義するだけで、複雑で矛盾のないマップを自動生成できるWFCの魅力と実装のヒントが詰まっています。

めっちゃ刺激を受ける内容だね。下の方にレジェンド（OG）たちの素晴らしいリファレンスがたくさんあるし、ソースも公開されてる。あとは、この https://heredragonsabound.blogspot.com/ の見た目や雰囲気と統合できたら最高じゃない？ ;)

これ最高。余談だけど、もし作者がこれを読んでたら、重ね合わせ状態（タイルで選べる選択肢）にビットフィールドを使うのは検討したかな？ 前にWFCを実装したとき、途中でビットフィールドに変えたら爆速になったんだよね。インナーループがほぼ完全にブランチレスになったから、バックトラックするよりチャンクをゼロから再計算したほうが早いくらいだった。自分のときは100タイル立方くらいのチャンクだったと思う。

Dorfromantik[0]を思い出すね。

[0] https://store.steampowered.com/app/1455840/Dorfromantik/

スレ主はもう知ってるかもしれないけど、このサイトにはコード例付きで六角形グリッドの計算例がたくさん載ってるよ。 https://www.redblobgames.com/grids/hexagons/

Oskar StålbergがTownscaperとかいろんなゲームで波動関数崩壊（WFC）を使ってるよね。ここでそれについて語ってるよ： https://www.youtube.com/watch?v=Uxeo9c-PX-w&pp=ygUhdG93bnNjYXBlciB3YXZlIGZ1bmN0aW9uIGNvbGxhcHNl0gcJCa4KAYcqIYzv (SGC21- Oskar Stålberg - Beyond Townscapers)

Jasper FlickのUnityでのヘックス地形チュートリアル[0]を思い出した。あれも同じくらい詳細で素晴らしいんだよね。面白い対比なのは、このプロジェクトは既製のタイルと制約解消で境界を合わせているのに対して、あっちはタイルの境界（ジオメトリやブレンディングとか）をその場で動的に生成している点。どっちも読み応えあって楽しい！

[0] https://catlikecoding.com/unity/tutorials/hex-map/

記事では「バックトラッキング」をさらっと流して500ステップに制限してるって書いてるけど、実際、制約プログラミングってめちゃくちゃ面白くて奥が深い分野だし、かっこいいアルゴリズムやトリックもたくさんあるんだよね。今回の場合なら、Dancing Linksを使ったクヌースのアルゴリズムX [1]で解けるかも。これはバックトラッキングの特殊なやつ。理論上、アルゴリズムXなら記事の「レイヤー2」にある境界領域を、86%より高い成功率で解けるはずだね。

あと、色んなヒューリスティックを使えば、総当たり的な手法よりバックトラッキングを大幅に高速化できる。数独ソルバーを作ったことがある人ならわかると思うけど、単純なバックトラッキングは実装は楽だけど、すぐ重くなって詰んじゃうからね。

[1] https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

制約を満たす配置を見つけるのが一番の難所みたいだね。代替案として、SATソルバーを使うのはどうなんだろう？ そのやり方の問題点は、ソルバーがランダムに見えない「簡単な」解ばかり見つけてしまうことかな。一部のSATソルバーは変数の初期値をランダムに設定できるけど、それでランダムな解が得られるとは限らないし。誰か似たようなアプローチを試したことある？

正方形じゃないグリッドでのWFCの探求、面白いね。制約伝播の課題は「標準的な」例よりもかなり複雑なはず。こういう複雑なトポロジーだと、別の制約ソルバー（例えば制約論理プログラミングとか）を使ったほうが、表現力やパフォーマンスの面でメリットがあるのかも、なんて考えちゃうな。

手元のラップトップ（第11世代Core i5、Iris Xeグラフィックス、Chrome最新版）だと、デモが5 FPSしか出ない。GPUがボトルネックになってるみたい。記事にはモバイルで60 FPS出たってあったから、もっと効率的なのを期待してたんだけどな。

マップは綺麗だけど、WFCを使ったタイルごとの制約だと、局所的じゃない影響を考慮するのが難しいから、結構不自然な生成結果になっちゃうね。タイルを1枚ずつ探索していくようなゲームならいいかもしれないけど、フルマップのジェネレーターとしては微妙だし、もっといい解決策がある。個人的にはRed Blob Gamesが書いてたノイズベースの手法のほうが優れてると思う。川には湿気追跡のアプローチを使えるし、道路や橋とかの人工物は別パスで配置すれば、もっと速くて堅牢になるはず。ただ、WFCはプログラミングの課題として面白いから、実装自体は楽しかっただろうね。

とはいえ、素晴らしい解説記事だったし、デモも印象的だったよ。