5分で覚える Flutter Flameで作る Wave Function Collapse – 波動関数崩壊アルゴリズム
2023.12.20
この記事は最終更新日から1年以上が経過しています。
どもです。
な、何ヶ月ぶりか。。
いつの間にかに時間も過ぎ、気がつけば年末。本当に時間が経つのが早いですよね。。
振り返れば、前半はDart、Flutter、Flame、後半は業務でもがっつりRustと。
色々と変化もありました。
今回は、アドベントカレンダーもあることから、波動関数崩壊アルゴリズムについてつらつらと書かせて頂こうかと思います。
波動関数崩壊アルゴリズム
名前から凄そうな、Wave Function Collapse – 波動関数崩壊アルゴリズムってなんなのかですが、
Maxim Gumin氏が 2016年に 開発、公開した ランダム生成アルゴリズムとなっており、昔から存在するアルゴリズムと比較すると、比較的新しいアルゴリズムとなっています。（とはいえ7年経っておりますが。）
では、そのアルゴリズムは主にどういった風に活用するのかですが、まずはMaxim Gumin氏のGithub レポジトリを見てみましょう。
見た感じ、「タイルマップのイメージ」を入力データとして「膨大にあるパターンからランダムに選択して生成されたグラフィック」が出力されているのが確認できます。
と聞くと、ディープラーニングなどニューラルネットワークをイメージされるところもありますが、そういった機械学習とは異なり、シンプル且つ容易に活用できるアルゴリズムとなっております。
実際にどの様なところで利用されるかですが、「ランダムに生成」となると、ゲーム内で利用されるシーンが多く、ローグライクゲームのダンジョンやボクセルゲームのワールドマップなど多種多様で、生成方法のアルゴリズム自体もゲームによっても異なります。
簡易で有名なアルゴリズムとして棒倒し法などがありますが、波動関数崩壊アルゴリズムはそれら同様に活用できるアルゴリズムとなっております。
ゲームによって、レベルジェネレーターが存在し、魅力のあるマップを生成するためノイズ関数などを用いて生成するのですが、ダンジョンの部屋によっては、大きな部屋の中心に特定のオブジェクトが存在する必要があるとか、水が溶岩やその他のものと隣接してはいけないとか、マップ生成における制約を与えより細かく制御し、特定のオブジェクトが配置される場所に制限を加えてレベルを生成したい時にWave Function Collapse （以下 WFCとする）は有用とされています。
レポジトリのサンプルでもあるように、RPGであるマップを描くことも可能です。
アルゴリズム自体、C#で記述されていることもあって、Unity用のプラグインが作成されたり、Unityで作成されたゲームで活用されているのを多く見かけますが、Unityだけに限らず、Unreal Engine、PICO-8といった様々なゲームエンジンにも用いられ、2Dゲームのみならず3Dゲームにも応用でき、実際にレポジトリのサンプル画像にも掲載されている迷路や、SteamなどのプラットフォームでリリースされているゲームのTownscaperなどにも適応されており、言語、ゲームエンジン、ジャンルを問わない故に活用実績も多く範囲も幅広いです。
Tile ModelとOverlapping Model
といったところで、WFCの概要は分かったところで中身について見ていきましょう。
WFCには大きく2つの生成モデルがあります。Tile ModelとOverlapping Modelです。
Overlapping Model
入力画像から取得した小さな部分の集合を使用して、出力画像を生成。セグメントがどのように重なり合うかに重きを置いている。基本的に、このモデルは入力画像内で見つかるすべての可能な N×Nピクセルのパターンを分析し、これらのパターンの重なりを考慮して新しい大きな画像を生成。
特徴：
- 詳細な出力: 元の画像の微細な特徴をキャプチャし、出力に反映させる。
- 非周期的なテクスチャの生成: 入力画像から繰り返しのないパターンを生成に適している。
- 複雑な構成: 入力画像の様々な部分からの情報を組み合わせることで、より複雑で詳細な出力を生成可。
Tile Model
予め定義されたセットのタイルを使用して画像を生成。これらのタイルは、特定のルールに基づいて隣接することができ、連続した画像が形成される。タイルは通常、辺や角が他のタイルと一致するように設計されており、それらが合わさって一貫性のある全体像を作成。
特徴：
- 規則性と一貫性: タイルが持つ明確な規則と一貫性によって、均一なパターンや構造を生成するのに適している。
- ゲームデザインでの応用: タイルベースのゲームデザインに特に適しており、マップやレベルの自動生成に用いられる。
- シンプルな設計: タイルモデルは、Overlappingモデルに比べて実装が比較的シンプルで、特定の種類のタイルに基づいてパターンを作成。
ということで、今回はOverlappingモデルよりシンプルなTile Modelに注目していきたいと思います。
Entropy （エントロピー）
では、中身を見ていきたいのですが、その前に、そもそも、Wave Function Collapse – 波動関数崩壊アルゴリズムっていう名前の由来は？と思う方も少なくないかと思いますが、こちら量子力学が元になっているようで、量子力学での名称は「波動関数の収縮または波動関数の崩壊」となっています。
用語自体は量子力学に由来しているみたいですが、その波動関数の崩壊とはどういう事か考えていくのですが、ここで出てくるの大事な要素が「Entropy （エントロピー）」となります。
wikipediaを見てみることにしましょう。
エントロピー（英: entropy）は、熱力学および統計力学において定義される示量性の状態量である。 熱力学において断熱条件下での不可逆性を表す指標として導入され、統計力学において系の微視的な「乱雑さ」を表す物理量という意味付けがなされた。 統計力学での結果から、系から得られる情報に関係があることが指摘され、情報理論にも応用されるようになった。 物理学者のエドウィン・ジェインズ（英語版）のようにむしろ物理学におけるエントロピーを情報理論の一応用とみなすべきだと主張する者もいる。
はい。よくわかりませんね。w
今回のWFCでは、後半の情報理論の方の応用に該当し、ある事象が起きた際、それがどれほど起こりにくいかを表す尺度となります。
例えば散歩していて、ありふれた出来事として「風の音」が起きた事を知ってもそれは大した「情報」にはならないが、「曲の演奏」が聞こえてくれば珍しい出来事としてより多くの「情報」を含んでいると考えられます。
つまり、情報量はその出来事が本質的にどの程度の情報を持つかの尺度としてみなされます。
その「Entropy （エントロピー）」と情報理論を用いて、数年前に流行ったゲーム「Wordle」を、より少ない試行回数で当てる方法の解説動画が面白かったのですが、こちらまで見ていくと5分を過ぎてしますので興味ある方で観ていただければと思います。
Solving Wordle using information theory
（1分4秒経過）
数独 （sudoku）
今回のWFCで用いられる概念として、数独 （sudoku）があります。
数独（ナンバープレイス、通称ナンプレ）は、始めるとやめられないですよね。コンビニの雑誌コーナーとかでも販売されていて、昔はよく朝になるまでやっていたり、わざわざゲームソフトとしてリリースしている数独を購入したりとハマっていた時期もありました。
と、話は逸れてしまいましたが、Entropy （エントロピー）」に関しては数独 （sudoku）が理解しやすいのでそれに置き換えてみていきましょう。
まず、数独 （sudoku）のルールとして、9×9のグリッドに3×3の小さなボックスと呼ばれる9つのセクションに分割されていて、行、列、ボックスに1から9までの数字が一度ずつ現れるルールとなっています。
もし、セルすべて空白の場合、セルには1〜9の数字が埋められています。
この時の平均エントロピーは9となります。
以下のセルに5が入った場合、行、列、ボックスに影響しエントロピーが減少します。
同じ行、列、またはボックスにある他のセルには5が含まれないことがわかります。
その情報より影響を受けるセルに伝播し、重ね合わることにより、5の数字を削除することができます。変化したセルは8つの数字の可能性を持った状態となります。
また、ここに9の数字が入ったとすると、先程同様に、行、列、ボックスに影響しエントロピーが減少します。
この様に、数字が確定すると、他のセルにその状態が伝播し折りたためられていきます。
5や9などを選択した例の様にその状態が1つの選択肢に確定すると、隣接するセルのエントロピーが減少し、そこから推測を開始します。
数独を解くまで推測、崩壊、推測、崩壊…が繰り返されていきます。
この様に波動関数崩壊アルゴリズム内に存在するプロセスと、数独を解くプロセスは同じで、エントロピーが少ないタイル、つまりその中に入る可能性のある数値が最も少ないタイルを探していきます。
すべての可能な状態から1つに崩壊させること、システムの単一変数から全てのエントロピーを削除する事を波動関数の崩壊と言います。
（1分37秒経過）
隣接性を持ったソケットシステム
数独のプロセスを参考にWFCのプロセスを見えきましたが、では実際にタイルマップがどの様に確定していくかを見ていきたいと思います。
特定のセルが折りたたまれ、そのセルが確定した場合隣接するセルのエントロピーが減少していく。ということは、つまり隣接しているセルの選択肢が接続可能なセルに絞られていくこととなります。
上記のプロセスの特定のセルが1つの選択肢に確定、隣接するセルのエントロピーが減少していく様子がタイルマップを用いて視覚的に理解しやすく試せるデモがこちらにあります。
https://bolddunkley.itch.io/wfc-mixed
タイルマップをクリックで選択すると、隣接するセルの情報も減少し選択肢も絞れていき、タイルマップを確定してく様子が確認できるかと思います。
もっとシンプルなタイルマップに置き換え見ていきましょう。以下の様なタイルマップ画像を用いてグラフィックを生成するとします。
単色で塗りつぶされたBlank画像、上下左右に回転されたT画像。各タイルでコネクトされる関係性をタイルのエッジに接続可能を示す何らかの識別子を持たせます。その識別子を0、1と数字のソケットとして持った場合、以下の様になるかと思います。 
単色で塗りつぶされたBlank画像の各エッジのソケットは全て0。T画像の持つソケットは0と１で、0は0とコネクトし、1は1とコネクトし、0と１のコネクトは無効となります。用意したBlank画像とT画像の隣接関係は以下の様になるかと思います。
もちろん、0と1のみならず、2や3と増やすことも可能で、制約の与え方も様々です。
なにより重要なポイントは、セル境界で一致しないタイルの隣接関係を無効にする。というところになります。
Oskar Stal Berg氏の有名なデモでは、タイルのエッジに沿った 3つの固定点のピクセルによってソケットは決定され、隣接するタイルの色が3つの点で一致するかどうかでを検証し隣接関係の無効、有効化を行っています。
https://oskarstalberg.com/game/wave/wave.html
拡大すると、各エッジに3つの色情報を持っているのが確認できます。
この様に、セルの各エッジのソケットを1つではなく、3つにすることによってより詳細な隣接関係の制約を持たせることができ、複雑なグラフィックな色彩に沿った滑らかなグラフィックも生成することが可能となっております。
今回は、色情報をベースとし、色情報ではなくA、B、Cとアルファベットで識別することにします。
結局のところ、タイルモデルにおける隣接関係で重要なポイントは、
どのモジュールがどのモジュールとスロットできるか、できないか、また、それらはどの方向が有効か無効化が大事となります。
（2分11秒経過）
実装
それでは、仕様も出揃ったところなので実装に入って行きたいと思います。
今回は、Flutter、Flameを用いての実装となり、環境は以下の通りです。
- Dart SDK version: 3.2.2
- Flutter 3.16.2
- flame: ^1.11.0
今回は、FlutterのゲームエンジンFlameを用いて作成します。
WFCの大きな流れとしては、初期設定とし
- タイルの画像、制約情報を入力データとする
- グリッド内にセルとして全ての可能性として保持
WFC実行フローとして、
- エントロピーの低いセルを優先するため、グループ化して取得
- タイルをランダムに選択、セルを1つの選択肢に確定。
- 隣接するセルのソケットを評価し、各セルのエントロピーを減少
- 伝播し終わると再度処理を実行
となり、全てのセルが崩壊、つまり1つの選択肢に確定となるとWFCの処理は終了となります。
タイルの画像、制約情報を入力データとする
まず、タイルの画像と制約情報を持ったデータの作成を行います。
JSONフォーマットで、用意します。スキーマの詳細は以下の通り。
- src: 画像のパス
- edges: 各エッジのソケット条件
- isRotate: 回転可能か否か
"tileList": [
{
"src": "simple/blank.png",
"edges": ["AAA", "AAA", "AAA", "AAA"],
"isRotate": false
},
{
"src": "simple/t.png",
"edges": ["AAA", "ABA", "ABA", "ABA"],
"isRotate": true
}]
}
edgesは、上、右、下、左の順番で記述しています。
上部の端は、「左、中、右」、右部の端は、「上、中、下」、下部の端は、「右、中、左」、左部の端は、「下、中、上」といった順番で形でedgesに配列で記述していきます。
isRotateに関しては、「回転して利用できるか否か」になります。
単色のblankは回転して利用しても向き、形が何も変わりませんので回転する必要がなく、逆にT画像に関しては全ての向きの画像分の種類の用意の必要がなく、1つを時計回りに90度ずつ3回回転させて流用することで、1枚の画像で4パターン生成することが可能です。
なので、以下のパターンを網羅するには、2枚の画像があればカバーできますので2枚の画像で回転を含めた5パターンのタイルマップを用意することになります。
Grid、Tile classの作成
今回のディレクトリ構造は以下の様にしました。
ファイル構成
lib/
├── components
│ ├── cell.dart
│ └── tile.dart
├── constants
│ └── defines.dart
├── core
│ └── wfc.dart
├── game.dart
├── main.dart
├── main_game_page.dart
└── utility
└── utility.dart
各ディレクトリの概要は、
- components: コンポーネントディレクトリ。主にcell、tilesコンポーネント
- constants: 定数、コンフィグなど定義ファイル
- core: WFCメインの処理
- utility: その他の処理
- game.dart: 描画含めたゲームループ
となっております。
それでは、実ソースの方を見ていきます。
まず、今回はFlutter、Flameを用いているのもあり、以下の様にFlameGameを継承したMainClassのMainGameを用意し、Cellの配列を格納するgridとTileの配列を格納するtilesのフィールドを用意します。
gridはタイルマップ全体となっており、タイルのマス分Cellが格納されます。
また、tilesは先程JSONファイルで用意したデータを元に生成されたTile classを格納することになります。
class MainGame extends FlameGame with KeyboardEvents, TapCallbacks {
List<Cell> grid = [];
List<Tile> tiles = [];
...
Tile Classは以下の様になります。
JSONファイルで定義したedges、isRotateを保持し、imageのpathを元にSpriteComponentを生成します。また、回転が必要であればangleの値も計算。
その他に、コネクトできるTileのindexを保持する配列、 up、right、down、leftを intのListで用意します。
class Tile {
double angle = 0.0;
SpriteComponent img;
bool isRotate = false;
List<String> edges;
List<int> up = [];
List<int> right = [];
List<int> down = [];
List<int> left = [];
...
initTiles関数で、JSONよりTileのインスタンスを生成します。
Future<void> initTiles() async {
await createTilesFromJson(tiles);
createRotateTiles(tiles.length);
}
Future<void> createTilesFromJson(List<Tile> tiles) async {
var tileListData = await loadJsonData(jsonFileName);
for (int i = 0; i < tileListData['tileList'].length; i++) {
var tileData = tileListData['tileList'][i];
tiles.add(await Tile.load(tileData['src'],
List<String>.from(tileData['edges']), tileData['isRotate']));
}
}
isRotateのフラグが立ったものに関しては回転バージョンのTileインスタンスを生成します。
90度、180度、270度の回転の3種類を追加するので、1/2π * n が行えるようにfor文は1始まりとします。
void createRotateTiles(int tileLength) {
for (int i = 0; i < tileLength; i++) {
if (tiles[i].isRotate) {
for (int j = 1; j < 4; j++) {
tiles.add(tiles[i].rotate(j));
}
}
}
}
こちらの処理を終え、全てのTileインスタンスの生成は行えました。
各タイルの隣接性を作成
generatingAdjacencyRules関数にて、全タイルの隣接関係の評価を行いそのタイルは 上、右、下、左にどのタイルとコネクト可能かを調べます。
void generatingAdjacencyRules() {
for (var tile in tiles) {
tile.analyze(tiles);
}
}
自分自身のedgesの0番目は上なので、他のタイルとは、下部にあたるedgesの2番目と接続となるので、edges[0]とedges[2]を評価します。
void analyze(List<Tile> tiles) {
for (int i = 0; i < tiles.length; i++) {
Tile tile = tiles[i];
// UP
if (compareEdge(tile.edges[2], edges[0])) {
up.add(i);
}
// RIGHT
if (compareEdge(tile.edges[3], edges[1])) {
right.add(i);
}
// DOWN
if (compareEdge(tile.edges[0], edges[2])) {
down.add(i);
}
// LEFT
if (compareEdge(tile.edges[1], edges[3])) {
left.add(i);
}
}
}
その際、edgesに格納されたままだと評価できないので、文字列を逆にする処理を入れています。
String reverseString(String s) {
return s.split('').reversed.join('');
}
bool compareEdge(String a, String b) {
return a == reverseString(b);
}
例えば、以下の様なタイルチップがあった場合、
※1 このタイルが保持するedgesは[”AAB”, ”BBB”, ”BAA”, ”ACA”]となります。
※2 絵から、同じタイルの上部と下部でコネクトできそうなのがわかります。
※3 実際に上部と下部は「AAB」と「AAB」
※4 しかしながら下部で保持しているedgesは「BAA」となるので片方文字列を反転し評価する必要があります。
左右の評価も同様となります。
Grid 作成
最初に記述した、「グリッド内にセルとして全ての可能性として保持」のフローとなります。
まず、Grid全体の大きさを決めたいので定数DIM（dimension）を定義し、こちらでグリッド全体の大きさを決定します。
DIM * DIM（縦 * 横）で、Grid作成と同時に Cellを作成します。
const int DIM = 15;
fromValueファクトリーメソッドで、Cellのインスタンスを生成します。
void initGrid() {
grid = List.generate(DIM * DIM, (index) => Cell.fromValue(tiles.length));
}
CellのsocketsはTileのindexとなります。つまり、初期状態は「全ての可能性を持った」状態となり、エントロピーも最大のTileの全体数となります。
class Cell {
bool collapsed = false;
List<int> sockets = [];
Cell.fromValue(int value)
: collapsed = false,
sockets = List<int>.generate(value, (i) => i);
Cell.fromList(List<int> value)
: collapsed = false,
sockets = value;
}
（3分21秒経過）
Wave Function Collapse – 波動関数崩壊アルゴリズム メインフロー
準備は整いましたので、ここからWave Function Collapse – 波動関数崩壊アルゴリズム のメインフローとなります。
@override
void update(double dt) {
super.update(dt);
mainLoop();
}
void mainLoop() {
List<Cell> lowEntropyGrid = pickCellWithLeastEntropy(grid);
if (lowEntropyGrid.isEmpty) {
return;
}
if (!randomSelectionOfSockets(lowEntropyGrid)) {
initGrid();
return;
}
grid = waveCollapse(grid, tiles);
}
再度流れを振り返ると、
- エントロピーの低いセルを優先するため、グループ化して取得
- pickCellWithLeastEntropy
- タイルをランダムに選択、セルを1つの選択肢に確定。
- randomSelectionOfSockets
- 隣接するセルのソケットを評価し、各セルのエントロピーを減少
- waveCollapse
となります。
pickCellWithLeastEntropy
「エントロピーの低いセルを優先するため、グループ化して取得」を行っていきます。
まず、現在のgridの状態をシャローコピーしgridCopy変数に格納します。
そのcell自身がcollapsed、つまりセルが確定しているのであれば無視し、セルが確定していないものでフィルタリングします。
その後、セルのsocketsの数が少ない順、つまりエントロピーの低い順にソートを行います。
通常であればきちんと計算や重みつけなども考慮しますが、今回は単純に低エントロピーはsocketsの少ない順とします。
List<Cell> pickCellWithLeastEntropy(List<Cell> grid) {
List<Cell> gridCopy = List<Cell>.from(grid);
gridCopy = gridCopy.where((a) => !a.collapsed).toList();
if (gridCopy.isEmpty) {
return [];
}
gridCopy.sort((a, b) => a.sockets.length - b.sockets.length);
int len = gridCopy[0].sockets.length;
int stopIndex = 0;
for (int i = 1; i < gridCopy.length; i++) {
if (gridCopy[i].sockets.length > len) {
stopIndex = i;
break;
}
}
if (stopIndex > 0) {
gridCopy.removeRange(stopIndex, gridCopy.length);
}
return gridCopy;
}
その後、最小エントロピーのグループ化として、最初のcellのsocketsの数を調べそれを超える場合は排除します。
つまり、[1,2],[1,2],[1,2],[1,2,3] となった時点でそのindexを取得しremoveRangeでカットを行います。
randomSelectionOfSockets
「タイルをランダムに選択、セルを1つの選択肢に確定」を行っていきます。
ここでは、見つからない場合の考慮も行います。
「見つからない場合」とは、制約ルールによってはコネクトできずパターンがなくなる事も発生することがあります。その際、再度最初からやり直すため Gridを初期化します。
if (!randomSelectionOfSockets(lowEntropyGrid)) {
initGrid();
return;
}
randomSelectionOfSockets関数は最小エントロピーのグループからcellをランダムに選択し、collapsedをtrueに確定フラグを立てます。そのcellのsocketsからどのタイルにするかもランダム選択し、タイルを確定させます。
bool randomSelectionOfSockets(List<Cell> gridTarget) {
Random random = Random();
Cell cell = gridTarget[random.nextInt(gridTarget.length)];
cell.collapsed = true;
if (cell.sockets.isEmpty) {
return false;
}
var pick = cell.sockets[random.nextInt(cell.sockets.length)];
cell.sockets = [pick];
return true;
}
（4分9秒経過）
waveCollapse
いよいよ、WFCのコアの部分に迫ってきました。
最後のフロー「隣接するセルのソケットを評価し、各セルのエントロピーを減少」となります。
改めて、ここで行っている事は、グリッド全体の左端から上下左右のセルのsockets、すなわちコネクトできるタイルのindexを見て、自分自身のcellの状態を変化させることです。
各セルの状態は、配置可能なtileを絞られることになるのですが、それがエントロピーの減少となります。
waveCollapseには、gridとtilesを引数に渡します。
grid = waveCollapse(grid, tiles);
waveCollapse関数
List<Cell> waveCollapse(List<Cell> grid, List<Tile> tiles) {
List<Cell?> nextGrid = List.filled(DIM * DIM, null);
for (int j = 0; j < DIM; j++) {
for (int i = 0; i < DIM; i++) {
int index = i + j * DIM;
if (grid[index].collapsed) {
nextGrid[index] = grid[index];
} else {
List<int> sockets = List.generate(tiles.length, (i) => i);
// Look up
if (j > 0) {
cellCollapse(grid[i + (j - 1) * DIM], "down", sockets, tiles);
}
// Look right
if (i < DIM - 1) {
cellCollapse(grid[i + 1 + j * DIM], "left", sockets, tiles);
}
// Look down
if (j < DIM - 1) {
cellCollapse(grid[i + (j + 1) * DIM], "up", sockets, tiles);
}
// Look left
if (i > 0) {
cellCollapse(grid[i - 1 + j * DIM], "right", sockets, tiles);
}
nextGrid[index] = Cell.fromList(sockets);
}
}
}
return nextGrid.where((cell) => cell != null).cast<Cell>().toList();
}
まず、次のGridの状態に書き換え用の空の配列nextGridを用意。
List<Cell?> nextGrid = List.filled(DIM * DIM, null);
チェックするセルの順番ですが、グリッドの左端から確認していくこととなります。
for (int j = 0; j < DIM; j++) {
for (int i = 0; i < DIM; i++) {
もし、対象のセルが確定していればそのセルはそのまま次のグリッドの状態に渡します。
if (grid[index].collapsed) {
nextGrid[index] = grid[index];
}
配置できるsockets（エントロピー）を、まずは全可能性を持った状態で初期化を行います。tilesの数だけ indexのListを作成し、そこから絞っていきます。
List<int> sockets = List.generate(tiles.length, (i) => i);
続いて、今のセルの上、右、下、左の順番で隣合うセルをチェックしていきます。
if (j > 0) {
cellCollapse(grid[i + (j - 1) * DIM], "down", sockets, tiles);
jは行となり、j= 0は一番上の行となるので、最初の行に関してはこちらはスキップされます。まず一番最初に行われるセルは左上端のセルとなり、隣り合う右のセルをチェックすることになります。
cellCollapse関数で実際にcellの折りたたみを行うこととなります。
右のセルをチェックする場合、grid[i + 1 + j * DIM]で右側のcellを参照します。
自分自身に対して右側なので、そのセルは左側にコネクト可能なタイルを検証することになります。
cellCollapse(grid[i + 1 + j * DIM], "left", sockets, tiles);
...
void cellCollapse(
Cell cell, String direction, List<int> sockets, List<Tile> tiles) {
List<int> validSockets = getValidSockets(cell, direction, tiles);
checkValid(sockets, validSockets);
}
cellCollapse関数で行っていることは、getValidSocketsでコネクトsockets（コネクト可能なタイルインデックス）を取得し、checkValidで比較し存在しなければ引数で渡されたsocketsのindexは削除。となります。
getValidSockets関数
List<int> getValidSockets(Cell cell, String direction, List<Tile> tiles) {
List<int> validSockets = [];
for (int socket in cell.sockets) {
List<int> valid = tiles[socket].valid(direction);
validSockets.addAll(valid);
}
return validSockets;
}
cellはチェック対象（流れ的に 最初は右側）のセルとなり、そのセルの持つsockets（タイルインデックス）分、tileのvalidメソッドで確認していきます。
右側のセルの場合は “left”となり、tileインスタンス生成時設定したleft、つまり左側にコネクト可能な tileのindexの配列を返却します。
List<int> valid(String direction) {
switch (direction) {
case 'up':
return up;
case 'right':
return right;
case 'down':
return down;
case 'left':
return left;
default:
return [];
}
}
チェック対象のcellのsockets（tile）の数だけ、コネクト可能な tileのindexを追加します。
validSockets.addAll(valid);
最後に、checkValidで先程作成したコネクト可能なtileのindex全てが追加されたvalidSocketsと、チェック時に作成したsocketsを比較し、存在しなければ削除します。
void checkValid(List<int> sockets, List<int> validSockets) {
for (int i = sockets.length - 1; i >= 0; i--) {
if (!validSockets.contains(sockets[i])) {
sockets.removeAt(i);
}
}
}
ここで、エントロピーの減少が発生したことになります。
上下左右チェックし、一つでも置けない可能性があるのであれば崩壊することとなります。
※ 一方が「2, 4」しかコネクトの可能性がない例
この様に、自分の上下左右のセルをチェックし、そのセルの影響で自分自身のエントロピーが減少し、伝播していくことが波動関数の崩壊となります。
グリッド全てのセルのチェックが終わると、grid自体を崩壊後のグリッドを返却し置き換えます。
return nextGrid.where((cell) => cell != null).cast<Cell>().toList();
この様に、waveCollapse関数では隣り合うセルの状態を確認し、セルの持つsocketsの可能性を絞って行くことでエントロピー減少させて、再び低エントロピーからランダムに選択しタイルを確定。またwaveCollapse関数では隣り合うセルのチェック。
と繰り返すことで、崩壊は伝播していきます。
描画
最後に描画処理となります。
FlutterのFlameのadd()で、コンポーネントとして追加も試したのですが、すごく重かったので、（そりゃそうだ）canvasにrenderする方法としました。
cell.collapsedの状態を監視し描画するかどうかを振り分けています。
@override
void render(Canvas canvas) {
final w = size.x / DIM;
final h = size.y / DIM;
for (int j = 0; j < DIM; j++) {
for (int i = 0; i < DIM; i++) {
Cell cell = grid[i + j * DIM];
if (cell.collapsed) {
int index = cell.sockets[0];
Tile tile = tiles[index];
tile.img.size = Vector2(w, h);
canvas.save();
double dx = i * w + w / 2;
double dy = j * h + h / 2;
canvas.translate(dx, dy);
canvas.rotate(tile.angle);
canvas.translate(-tile.img.size.x / 2, -tile.img.size.y / 2);
tile.img.render(canvas);
canvas.restore();
} else {
Rect rect = Rect.fromLTWH(i * w, j * h, w, h);
canvas.drawRect(rect, Paint()..color = Colors.white);
}
}
}
}
それでは実行してみましょう。
はい。
いい感じにできましたね。
その他のサンプルも試してみましょう。
おお。いい感じですね。
こちらは部屋の図面ぽいですね。
いい感じですが、ちょっと調整が必要そうですね。
これは、あっているのか。違いますよね。
RPGマップも良い感じではありますが、調整が必要そう。
と、意図した通りに表示したのと、ちょっと違かったのと、制約の調整が必要そうなものもありましたが、取り敢えずは完成。制約の付け方で表示も異ってくるのも確認できました。
今回作成したソースはこちらになります。
https://github.com/flame-games/wave-function-collapse
実は、Rust版も作成したのですが、こっちの方が（当たり前ですが）爆速ですね。
https://github.com/webcyou-org/wave-function-collapse-rust
こちらに関しても、次回説明できればと思います。
（5分12秒経過）
最後に
という訳で、今回はWave Function Collapse – 波動関数崩壊アルゴリズムのTile Modelを実装してみました。
5分を大幅に過ぎてしまうんじゃないかと思っていましたが、5分12秒となんとか5分代に収められて良かったです。
この冬休みは、Overlapping Modelも含めトライしてみてはいかがでしょうか。
来年こそは、作ろうと思っていたアプリと、3Dボクセルゲームエンジンの作成を行いたいと思っております。
最近記事書く時間も取れなくなって来たので、Dev log的な形で投稿できればと思っております。
ではではぁ。
