1行のコードでランダム迷路を生成し、確率的プログラミング言語はGitHubのホットリストに載っています。作者は有名なWFCアルゴリズムを開発しました。

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載しています。転載の際は出典元にご連絡ください。

ゲーム内の迷路を探索するのは楽しいですが、やりすぎると飽きてしまいますか？

そうです、ゲームの迷路があまり変わらないと、しばらくするとマップに慣れてしまい、探索の楽しさが減ってしまいます。

現在、この問題を解決するために、確率的プログラミング言語 MarkovJunior が登場しました。

マルコフアルゴリズムを使用すると、迷路のバッチがランダムに生成され、どれも繰り返されないため、次にプレイする迷路がどのようなものになるかはわかりません。

2D 迷路だけでなく、複数のレイヤーのマップの構築を必要とする 3D 迷路もランダムに生成できます。

このプロジェクトはリリースされるとすぐに GitHub で話題となり、1 週間足らずで 2.6k スターを獲得しました。

一部のネットユーザーは、このプログラミング言語はRPGゲームやアクションゲームの建物を直接生成するために使用できると嘆いた。

Keras の作者もこの確率的プログラミング言語に興味を持っています。

その原理と、さまざまな迷路をランダムに生成する方法を見てみましょう。

マルコフアルゴリズムに基づく

著者によれば、この確率的プログラミング言語はマルコフアルゴリズムを利用しています。

(MarkovJuniorという名前も、マルコフアルゴリズムを提唱した数学者、アンドレイ・マルコフにちなんで名付けられました)

具体的には、この確率的プログラミング言語は、順序付けられたリストである一連の特定のルール (書き換えルール) で構成されています。

(迷路)モデルを生成する過程で、マルコフアルゴリズムを使用して「ランダム生成」を実現し、その後、迷路、地形図、回路図などの一連の特定のルールを定式化することで、生成されたモデルのカテゴリを決定します。

マルコフ連鎖には「記憶なし」の特性があります。つまり、次の状態の確率分布は現在の状態によってのみ決定され、時系列内のそれ以前のイベントは無関係です。

では、これらの特定のルールは具体的にどのようなものなのでしょうか?

たとえば、最も単純なルールの 1 つは、モデル全体が埋められるまで「黒」のブロックを「白」のブロックに書き換えることです。

別の例として、「白-黒」カラーブロックを「白-白」カラーブロックに書き換えるルールを実行し、それをマルコフアルゴリズムと組み合わせると、確率的生成モデルが得られます。

別の例として、「プッシュボックスゲーム」のルールに基づいて、

△ プッシュボックスゲーム

この小さな赤い点のバッチを使用して、白いブロックを指定された場所にランダムに「移動」することができます。

このような具体的なルールは他にもたくさんあり、すべて MarkovJunior に含まれています。

では、これらのルールを使用してランダムなモデル (迷路、回路図など) を生成するにはどうすればよいでしょうか?

2D / 3D迷路、地形図、回路図を描くことができます

2D 迷路をランダムに生成する例を見てみましょう。

写真から、この迷路アルゴリズムは「出発点」として赤い点を自動的に生成し、黒い地図上で経路をランダムに探索して書き換え、最終的に地図全体を埋めて、始まり、終わり、そして道の分岐がある「迷路」を完成させることがわかります。

MarkovJunior は、次の 2 つのルールに基づいて、このようなランダムな迷路を簡単に多数作成できます。

最初のルールは、「赤-黒-黒」のカラー ブロックを「緑-緑-赤」のカラー ブロックにランダムに書き換えます。

2 番目のルールは、最初のルールが「スタック」している場合、つまり条件を満たすオプションがない場合に、「赤 - 緑 - 緑」カラー ブロックを「白 - 白 - 赤」カラー ブロックに自動的に書き換えます。

このようにして、アルゴリズムは最初のルールを通じてランダムなパスを生成し、2 番目のルールを通じてまだ通っていないパスに戻って分岐を生成し、最後にブラック マップ全体を横断して一連の「2D 迷路」を生成します。

もっと単純なアイデアもあります。それは、すべての「白-黒-黒」を「白-A-白」に置き換えるというものです。ここで、A は中間状態であり、開始点としては使用されません。迷路が生成された後、白に置き換えられます。

作者によると、このルールを使用すると、1 行のコードで 2D または 3D の迷路をランダムに生成できるとのことです。

▲ 3D迷路はこんな感じ

この考え方に基づいて、ルールの組み合わせ方法を変更することで、ランダムな地形マップを生成することもできます。

たとえば、川の地図を生成したい場合は、上記の生成モデル メソッドを使用し、他の書き換えルールをいくつか追加するだけで、ランダムな川の地図を作成できます。

地形図や単純な 2D/3D 迷路に加えて、2 つの 2D「迷路」レイヤー間のランダムな場所に「階段」のバッチを生成することで、より複雑な 3D 建物も処理できます。

まあ、回路図も描けるんですけどね…

作者によれば、これらのルールを柔軟に使用すれば、MarkovJunior を使ってさまざまな建物や絵をランダムに生成できるとのこと。

非常に使いやすいと言えます。

彼は有名なWFCアルゴリズムの作者でもある。

この確率的プログラミング言語の作者である Maxim Gumin は、独立したゲーム開発者です。

彼が取り組んだ最も有名なプロジェクトは、おそらく「Wave Function Collapse Algorithm」(WaveFunctionCollapse、WFC) と呼ばれる一連のプロジェクトであり、現在 GitHub で 18.7k のスターを獲得しています。

この WFC アルゴリズムは、量子力学の「波動関数の崩壊」の概念にヒントを得て、彼によって作成されました。このアルゴリズムは、「Townscaper」などのいくつかのゲームに適用されています。

マキシム・グミンは自分自身について詳しい情報を明かしていないが、彼のホームページを見ると、この人物は自らを「確率モデルの王、プログラム生成の救世主、マルコフ連鎖を飼いならした者」と呼んでいることがわかる。(手動犬の頭)

GitHub から判断すると、彼は近年、さまざまな数学的アルゴリズムを手続き型生成に適用して、さまざまな興味深いモデルを作成することに注力しているようです。

おそらくあなたがプレイしたゲームのいくつかは、彼が開発したアルゴリズムを使用していたでしょう。

プロジェクトアドレス:

https://github.com/mxgmn/MarkovJunior