シンプルなタイルからの手続き世界

この投稿では、単純なカラータイルのセットから、これらのタイルの場所の制限に基づいて、複雑な手続き世界を作成するための2つのアルゴリズムについて説明します。 これらのタイルセットをきちんとデザインすることで、興味深い手順で生成されたコンテンツ、たとえば都市のある風景や複雑な内部構造を持つダンジョンを作成する方法を示します。 以下のビデオは、43色のタイルでエンコードされたルールに基づいて手続き型の世界を作成するシステムを示しています。





以下の画像は、ビデオの世界が生成されるタイルのセット（タイルセット）を示しています。 世界には、実際の環境でのプレゼンテーションに役立つメモが装備されています。









タイリングは、各タイルが独自のグリッドセルにある有限グリッドとして定義できます。 正しい世界を、隣接するタイルの端に沿った色が同じでなければならない世界として定義します。









タイルには鉄則が1つしかありません。タイルのエッジの色は一致する必要があります。 全体の高レベル構造は、このルールに基づいて開発されます。



正しいタイルは次のようになります。









これはタイルであり、水、海岸、草、建物のある都市（青い長方形）、および雪のピークのある山のあるマップを表す必要があります。 黒い線は、タイル間の境界を示しています。



手続き型生成のアルゴリズムでは「トップダウン」アプローチが頻繁に使用されるため、これは世界を記述し作成する興味深い方法だと思います。 たとえば、Lシステムでは、オブジェクトの再帰的な記述が使用されます。この記述では、高レベルの大きな部分が低レベルの部分よりも早く決定されます。 このアプローチには何の問題もありませんが、単純な低レベルの関係のみをエンコードできるタイルのセットを作成することは興味深いと思います（たとえば、海水と草は海岸によって分離されるべきであり、建物は90度の凸角のみを持つべきです）より高いレベルのパターンの出現の背後（正方形の建物など）。

タイリングは制約を満たすNP完全問題です

制約充足問題（CSP）に精通している読者にとって、最終世界のタイリングがCTAであることはすでに明らかです。 ZUOには、多くの変数、各変数（その定義のドメインと呼ばれる）が取ることができる多くの値、および多くの制限があります。 この場合、変数はマップ上の座標であり、各変数のスコープはタイルセットであり、制限はタイルのエッジが隣接のエッジに対応する必要があるということです。



タイルセットは任意の広範な依存関係をエンコードできるため、非自明なタイリングを正しく作成するタスクが複雑であることは直感的に明らかです。 タイルセット全体を考えると、正式な観点からは、これは制限を満たすというNP完全タスクです。 タイルを作成するための単純なアルゴリズムは、タイル空間の徹底的な検索であり、指数関数的な時間で実行されます。 ヒューリスティックによって加速できる検索によって解決されるタイルセットに基づいて、興味深い世界を作成できるという希望があります。 別のオプションは、ほぼ正しいタイルを作成することですが、少数の誤った場所が含まれます。 いくつかの興味深いタイルセットでうまく機能する2つのアルゴリズムを見つけました。それらを以下で説明します。

方法1：逆遷移の貪欲

ランダムな場所を選択し、適切なタイルを配置します。 動けなくなった場合は、それらのいくつかを削除して、再試行してください。











t <-

l <- t,

l

















タイルセットからタイルを作成する最初の試みは、グリッド全体が未解決の状態になった後、適切な場所にランダムなタイルを繰り返し配置したか、適切な場所がなければ、未解決のタイルの隣の小さな領域に「未解決」状態を割り当てました。タイルの貪欲な場所を続けました。 「貪欲な場所」は、既に配置されたタイルを置き換えないと完成できない部分的なタイルをこの配置が作成するかどうかに関係なく、そのエッジが既に配置されたタイルに対応するまでタイルを配置する戦略です。 このような状況が発生し、タイルを配置できなくなった場合、以前に配置されたタイルの一部を削除する必要があります。 問題を解決できれば、おそらく最初にタイルの正しい位置の問題も解決できる可能性があるため、どれを削除するのが最適かはわかりません。 アルゴリズムに特定の領域に適したタイルを見つけるもう1つの機会を与えるために、未解決のポイントの周囲のすべてのタイルに「未解決」状態を割り当て、貪欲な戦略を実行し続けます。 遅かれ早かれ正しいタイリングが見つかることを期待していますが、保証はありません。 アルゴリズムは、正しいタイリングが見つかるまで実行されます。これには無限の時間がかかります。 彼には、タイルセットが解決できないと判断する能力がありません。



アルゴリズムがその作業を完了する保証はありません。 共通の色を持たない2つのタイルを持つ単純なタイルセットは、アルゴリズムに無限ループの実行を強制します。 さらにシンプルなケースは、上下に異なる色の単一のタイルです。 タイルセットが正しいタイルを作成できないかどうかを判断する方法を見つけるのが賢明でしょう。 無限の平面を橋渡しできるなら、タイルセットは間違いなく真実だと言えます。 場合によっては、タイルセットが無限平面を橋渡しする場合としない場合があることを簡単に証明できますが、一般的な場合、この問題は解決できません。 したがって、デザイナーのタスクは、正しいタイルを作成できるタイルセットを作成することです。



このアルゴリズムは、投稿の冒頭のビデオからダンジョンタイルセットの適切なソリューションを見つけることができません。 よりシンプルなタイルセットでうまく機能します。 タイルとさまざまなコード化されたルールの間の多くの可能なタイプの遷移を持つより複雑なタイルセットを解決する方法を学習したいと思います（たとえば、道路は建物の近くで始まり、終わります）。



将来を見据えてタイルの場所を作成できるアルゴリズムが必要です。これらの場所が将来のタイルの場所のために開いているオプションを何らかの形で認識しています。 これにより、複雑なタイルセットを効率的に解決できます。

会議の制限に関して

このアルゴリズムは、逆引きに似ています。 各ステップで、1つの変数を割り当てようとします。 できない場合は、変数と、制約によってそれに関連付けられているすべての変数の割り当てを解除します。 これは「バックジャンピング」と呼ばれ、正しい割り当てを続けることができるまで一度に1つの変数の割り当てを解除するバックトラッキングとは異なります。 戻るときは、通常、変数の割り当てと逆の順序で変数の割り当てをキャンセルしますが、逆にするときは、検討中の問題の構造に従って変数の割り当てをキャンセルします。 特定のポイントにタイルを配置できない場合、隣接するタイルの位置を変更する必要があるのは論理的です。なぜなら、それらの位置は解決できない状況を作り出したからです。 代わりに戻ると、空間的に離れているが最近割り当てられた変数の割り当てを解除する場合があります。



この検索で​​は、ローカル整合性メソッドは使用されません。 つまり、将来の1つの検索ステップでも、後で解決できない状況につながるタイルを配置しようとはしません。 現在のポイントからのいくつかのタイル内の可能な位置に対する位置の影響を追跡するため、検索の高速化が可能です。 同時に、これにより、検索がその作業をキャンセルするのにそれほど時間を費やさないようにすることが期待できます。 これがまさに私たちのアルゴリズムが行うことです。

方法2：制限が最も大きい場所とローカル情報の普及

各ポイントでタイルの確率分布を保持し、場所を決定するときにこれらの分布に非局所的な変更を加えます。 二度と戻りません。









次に、テスト済みのすべてのタイルについて、完了が保証され、視覚的に満足のいく結果が得られるアルゴリズムについて説明します。 さらに、はるかに複雑なタイルセットに対してほぼ正しいタイルを作成できます。 ここでのトレードオフは、このアルゴリズムが、出力が常に正しいタイリングになることを保証しないことです。 「最適化」セクションでは、より大きなタイルセットとマップでもこのアルゴリズムをより高速に実行できる最適化について説明します。



正しいタイルを作成する複雑さは、2種類のタイル間の移行に必要な移行の数に大きく依存します。 単純なタイルセットには、砂、水、草のみを含めることができます。 草と水が互いに接触できない場合、それらの間には砂への移行がなければなりません。 これは、前述のアルゴリズムを簡単に解決できる簡単な例です。 より複雑なケースでは、複数のビルトインレベルのタイルタイプが表示される場合があります。 たとえば、深層水、水、砂、草、高原、山、雪のピークなどがあります。 これらすべてのタイプのタイルをマップに表示するには、指定した順序を除き、これらのタイプが相互に接触できないと想定した場合、7つの遷移が必要です。 特定のタイプのタイルの近くで開始および終了しなければならない道路など、タイル間に自然に広範な依存関係を作成するタイルを作成することにより、さらに複雑さを追加できます。



直感的に、このタスクのアルゴリズムは、「先読み」して、選択した場所の結果である可能性のある少なくともいくつかの遷移を考慮できる必要があります。 これを実現するために、タイルマップを各ポイントのタイルの確率分布と考えることができます。 アルゴリズムがタイルを配置するとき、位置に応じてこのタイル周辺の確率分布を更新し、隣接するタイルの確率が増加するようにします。これはおそらく現在の位置と互換性があります。



たとえば、マップ上に水タイルがある場合、その隣のタイルには水が含まれている必要があります。 それらの隣のタイルにも水が含まれている可能性がありますが、海岸が元の水タイルの隣に配置されている場合、他の確率、たとえば草があります。 配置されたタイルから遠ざかるほど、より多くの種類のタイルが可能になります。 この観察結果を活用するために、元のタイルの隣の各タイルの位置に到達できる方法の数を数えることができます。 場合によっては、特定の距離で1つのタイルから別のタイルへの遷移につながるのは、単一の遷移シーケンスだけです。 他の場合には、多くの異なる遷移シーケンスが存在する場合があります。 タイルの位置を特定した後、隣接ポイントでのタイルの確率分布を決定し、位置を特定したタイルから隣接タイルへの遷移を行う方法の数をカウントします。 このアルゴリズムによって実行される「ルックフォワード」は、このような遷移の数を追跡し、利用可能な新しいタイルを選択できる確率分布として処理します。









各ステップで、アルゴリズムはタイルのすべての未解決の位置を調べます。各位置にはタイル全体に確率分布があり、タイルに収束する位置を1つ選択します。 彼は、最小のエントロピーでマップから分布を選択します。 エントロピーが低い多項分布の場合、確率は通常いくつかのモードに集中するため、最初のモードの収束は、いくつかの制限が既に存在するタイルを配置する効果につながります。 これが、アルゴリズムが最初に決定したタイルの隣にタイルを配置する理由です。



これは、私がこのタスクのために実装した最も効率的なアルゴリズムです。 もう1つの利点があります。実行すると、美しい視覚エフェクトが作成されます。 おそらく、何らかの形式のバックトラッキングを導入することにより、このアルゴリズムを改善する方法があります。 結果のタイリングに間違ったタイリングが存在する場合、隣接するタイルの位置をキャンセルし、そのポイントで結果の分布からリサンプリングすると、このタイリングの修正が見つかる場合があります。 もちろん、正しいタイリングが見つかるまで検索を続けたい場合は、指定された保証ランタイムの制限を超えてください。

最適化

このメソッドの最も重要な操作は、検出されたタイル周辺の確率を更新することです。 アプローチの1つは、タイルが配置されるたびに、配置されたタイルからの「可能な」遷移をカウントすることです。 新しい確率が適用されるマップ上の各ポイントについて、多くの遷移ペアを考慮する必要があるため、これは非常に遅くなります。 明らかな最適化は、マップ全体ではなく配布を実行することです。 より興味深い最適化は、周囲のポイントの各タイルの場所が持つ効果をキャッシュすることです。これにより、各タイルの場所は、その場所が隣接する確率にもたらす変更の種類を確認するために検索し、単純な操作。 以下では、この最適化方法の実装について説明します。



完全に空のカードに置かれたタイルを想像してください。 この場所は、隣接するタイルの確率を更新します。 これらの更新された分布は、以前のタイル位置によって定義された以前の分布を持っていると考えることができます。 複数のタイルが配置されている場合、この以前の配布は共有されます。 この事後確率は、過去の各場所の分布の積として、以前のジョイントで近似します。









これを実現するために、空のマップにタイルを配置すると、隣接するマップポイントの分布が大幅に変化することを想像します。 これらの更新をタイルの球体 、つまり、空のカードに置いたときに周囲に投影されるタイルの影響圏を呼び出します。 2つのタイルが隣り合っている場合、それらの球体は相互作用し、両方の場所の影響を受ける有限分布を作成します。 多くのタイルを特定の未解決の場所の隣に配置できることを考えると、非常に遅いプロセスでこの時点でさまざまなタイルが出現する確率を決定する計算に基づいて決定を行う相互作用する制限が多数存在します。 代わりに、マップ上に既に配置されているタイルの事前に計算された領域間の相互作用の単純なモデルのみを考慮するとどうなりますか？









タイルを配置するときに、各要素の確率マップを更新し、このタイルの球の分布にマップ上の各ポイントを乗算し、マップ上のこのポイントに既に格納されている分布を乗算します。 分布マップでこれができることの例を考えると便利かもしれません。 現在、特定のマップポイントに、草や水を選択する可能性が等しい分布があり、そのポイントの横に水タイルを配置するとします。 水タイル球体は、水タイルの横に水が存在する可能性が高く、草タイルが存在する可能性が低くなります。 これらの分布要素を要素ごとに乗算すると、2つの高い確率の積であるため、結果としての水の確率は高くなりますが、草に含まれる確率は低くなります。









この戦略により、確率マップ上の各タイル位置が持つべき効果を効果的に近似することができます。

制限を満たすという点で

制約充足の問題を効果的に解決するには、特定の変数を割り当てるときに不可能になる他の変数の割り当てを追跡することが賢明です。 この原則は、ローカル互換性条件の導入と呼ばれます。 何らかのローカル互換性の導入により、戻る必要があるときに、隣接する変数に互換性のない値を割り当てるときに、変数に値を割り当てることを回避できます。 このような変換は、ZO文献の制約の伝播方法の分野で言及されています。 このアルゴリズムでは、タイルを配置するたびに、マップの小さな領域に情報を配布します。 配布された情報は、どのタイルが近くで発生する可能性があるか、どのタイルが発生しないかを示します。 たとえば、山のタイルがある場合、そこから2つのタイルに外洋タイルを配置することはできません。つまり、配置されたタイルから2つのタイルのすべてのマップポイントに海タイルがある確率はゼロです。 この情報は、上記で説明した領域に記録されます。 Sphereは、課したいローカルの互換性をエンコードします。



隣接するタイルの可能な割り当ての数を減らすことにより、各位置の後にアルゴリズムが処理する検索スペースを大幅に削減します。 この小さな近傍では、互換性のないタイルの出現の確率はすべてゼロであることがわかります。 これは、これらのポイントで変数定義エリアからこれらの値を削除することに似ています。 つまり、配置されたタイルの周囲のエリアの隣接ポイントの各ペアは、その定義エリアに、まだ隣接の定義エリアにある一部のタイルと互換性のある特定のタイルを持っています。 2つの変数がMA問題の制約によって接続され、それらの定義ドメインに制約を満たす値のみが含まれる場合、それらはアーク互換性があると言われます。つまり、この方法は実際にアーク互換性を導入するための効果的な戦略です。



ZUOでは、指定された部分割り当ての「最も制限された」変数は、定義領域に残っている値が最小の変数です。 マップ上のエントロピーの最小分布を持つポイントにタイルを配置する原理は、ZUOで最も制限された変数の値を割り当てることに似ています。これは、検索を使用してZUOを解決するときに変数を配置するための標準的なヒューリスティックです。

タイルを選択する確率を変更することによるタイル化による操作

ここまでは、正しいタイルの作成方法についてのみ説明しましたが、正確さ以外に、タイルには他のプロパティが必要になる場合があります。 たとえば、あるタイプのタイルと別のタイプのタイルの数に一定の比率が必要な場合や、すべてのタイルが同じタイプであるとは限らないことを保証したい場合があります。 この問題を解決するために、私が説明した両方のアルゴリズムは、入力として各タイルに関連付けられた基本的な確率を受け取ります。 この確率が高いほど、完成したタイルにこのタイルが存在する可能性が高くなります。 両方のアルゴリズムは、タイルのコレクションからランダムに選択します。タイルの基本的な確率に従って、このランダムな選択に単純に重みを追加します。



この原則の使用例を以下に示します。 連続した水タイルが表示される確率を変更することで、地図上の水域のサイズと出現頻度を調整できます。

独自のタイルセットを作成する

要するに：

• GitHubでリポジトリを複製する
• インストール処理
• data / repositoryフォルダーでtiles.pngを変更します
• 処理を使用してwangTiles.pdeを開き、再生ボタンをクリックします

githubに投稿されたコードを使用して（変更できますが、自分の危険とリスクでそれを行います-私はそれをほとんど高校で書いた）、画像エディターを使用して独自のタイルセットを作成し、タイルソルバーがそれらを使用して世界を作成する方法を見ることができます。 リポジトリを複製してdungeon.png画像を編集し、Processingを使用してwangTiles.pdeを起動し、生成されたマップのアニメーションを表示するだけです。 以下に、このタイリングソルバーに必要な「言語」について説明します。

タイルセット仕様

タイルは4x4セルのグリッドに配置されます。 左上の3x3領域の各セルにはカラータイルが含まれ、残りの7ピクセルにはタイルメタデータが含まれます。 タイルの中心の下のピクセルを赤で色付けして、タイルをコメントアウトし、タイルセットから除外できます。 ソルバーはそれをカードに決して入れません。 タイルの右部分の上部ピクセルを黒にペイントして、タイルの4つの回転すべてをタイルセットに追加できます。これは、4方向に存在する角度などを追加する場合に便利な機能です。最後に、マークアップの最も重要な部分は、タイルの左下のピクセルです。これは、タイルがマップに表示される基本的な確率を制御します。ピクセルが暗いほど、タイルが表示される可能性が高くなります。

関連作品

多くの人がWang Tilesを探索しました。WangTilesは色付きの面を持つタイル面であり、私たちが検討しているタイルと同様に、配置された隣のタイルと面を一致させる必要があります。



ファジーアーク整合性ソルバーを使用した最も制約のある配置は、Twitter @ExUtumno Wave Function Collapse プロジェクトに似ています。このアルゴリズムは、「部分的に観測可能な」割り当てのマップを保存し、それらからサンプルを取得して、タイル用に保存した分布に似た最終画像を作成します。これらのアプローチは、いくつかの面で異なります。各マップポイントに対して、このアルゴリズムは多項分布ではなくバイナリポテンシャルを格納します。さらに、彼は計算の高速化に必要な遷移の数のキャッシュされた「球体」を使用しません。これについては「最適化」セクションで説明しました。

結論と謝辞

高レベルの構造を作成するためのローカルルールの適用、たとえば、「道路には行き止まりがない」というルールの導入は、道路が他の道路ではないある地点から通らなければならないシステムの実装につながります。これは、手続き生成のタスクの興味深い外観です。このようにして、驚くほど広範囲の興味深いルールをエンコードできます。結果のタイリングの品質はソルバーに大きく依存するため、タイリングを作成するためのアルゴリズムの改善は、今後の作業の実り多い方向になります。これまでのところ、この問題を解決するために、遺伝的アルゴリズム、シミュレーテッドアニーリング、または制約を満たすための一般的なアルゴリズムについては研究していません。これらのいずれの領域でも、最小限のパラメーター設定で幅広いタイルセットを処理できるタイルセットソルバーを作成できます。



このプロジェクトの作業中に有益な議論をしてくれたキャノンルイスとロニーマクラーレンに感謝します。Ronnieは、タイルで興味深い動作をコーディングする可能性について、多くの興味深いアイデアを思いつきました。キャノンとの通信の結果として波動収束アルゴリズムが発生しました。彼のアドバイスは、記事で説明されている効果的な近似アルゴリズムを作成する重要なステップでした。