プロシージャル界隈で話題のMarkovJuniorについての解説

https://github.com/mxgmn/MarkovJunior

先日、ConvChainやWaveFunctionCollpaseの開発で有名なMaxim Gumin氏の新作ライブラリがGitHubに公開された。それはMarkovJuniorというライブラリで、色を置き換えるためのルールを定義しておくことで、プロシージャルに画像を生成するというものになる。

公開から1ヶ月経たずにGitHubスター4,000超えの人気レポジトリだが、この記事公開時点では、ドキュメントの整備が追いついていないようなので、簡易ながらMarkovJuniorの性質や利用方法についての解説を書くことにした。

MarkovJuniorの置き換えルール

grid = [
  [緑, 赤, 緑],
  [赤, 赤, 赤],
  [青, 赤, 青]
]

まず、2Dゲームなどの実装でよく使われる、配列の値をもとに画面にタイルを描画するグリッドベースのシステムがあるとしよう。つまり配列の各要素に色に対応した値を入れると、そのまま画面にその色が描画される。

in = 青, out = 黒
in = 緑赤緑, out = 橙橙橙

次に色を置き換えるためのルールを用意する。
上記は2つのルールが書かれており、in が置き換え元の色で、out が置き換え先の色になる。

上段のルールでは、グリッドの中に青があれば黒に置き換えるというルールになる。
次に下段では、グリッドの中に緑赤緑と並んでいる場所があれば、そこを橙橙橙に置き換えるということになる。

grid = [
  [橙, 橙, 橙],
  [赤, 赤, 赤],
  [黒, 赤, 黒]
]

先程の例で実際に置き換えたのが上記になる。

MarkovJuniorが行う処理は、本質的には上記のような特定のルールに基づいて色を置き換えていくというだけである。しかし、ルールを組み合わせていくと、この記事の最初に貼り付けている画像のような非常に魅力的な形状を生成することができる。

ルールの作成

<sequence values="BRGW">
  <one in="B" out="R" steps="1"/>
  <one in="B" out="G" temperature="4.0" steps="1">
    <field for="G" from="R" on="B"/>
  </one>  
  <one>
    <rule in="RB" out="WR"/>
    <rule in="R*/*B" out="W*/*R"/>
    <observe value="G" from="B" to="R"/>
    <observe value="R" to="W"/>
    <observe value="B" to="BW"/>
  </one>
</sequence>

実際にMarkovJuniorを利用するには、上記のようなXML形式でルールを定義していく。

まずは最も単純なルールであるOneNodeから始めよう。

1マスの置き換え

<one values="BW" in="B" out="W"/>

OneNodeを表す <one/> を用意して、属性の values にはルールで利用する文字を全て書く。in と out は先程説明した、グリッドの色の置き換え元と置き換え先の文字になる。上記の場合、in と out で BW という2つの文字が使われているので、それを values に書かなければならない。

values に書かれた最初の文字でグリッドが塗りつぶされる。上記例だと、B が最初の文字なのでグリッドは最初黒で塗りつぶされることになる。

in="B" out="W" なので、黒を白に置き換えるというルールになるが、OneNodeでは置き換えることができる全ての対象のマスの中から一つだけランダムに選んで置き換えるという処理を行う。

複数マスの置き換え

<one values="BW" in="BB" out="WW"/>

BB という横並びを WW に置き換える例。

上記実行例を見ればわかるが、縦にも置換が行われている。これはルールをテトリスのブロックのように90度回転させて、その回転させた状態でマッチする in があれば out に置き換えるという性質がある。つまり、横の BB だけではなく、縦の BB がグリッド上にあれば縦の WW に置き換えることになる。

複数のルール

<one values="BW">
  <rule in="B" out="W"/>
  <rule in="B" out="R"/>
</one>

1つのノードに複数のルールを適用する場合は、子要素に <rule/> を配置してそこにルールを書き込む。上記例では、グリッドの中で B を W に、あるいは B を R に変換できる場所の中からランダムに1つだけ置換を行う。

これまでの作例はノイズのように画面全体に適用するものだったが、次はある1点の場所から順番にそこから繋がる場所の置き換え処理を行う例を紹介する。

中央に色を描く

<one values="BRW" origin="True">
  <!-- なんかの処理 -->
</one>

ルートノードに origin="True" を記述しておくと、グリッドの中央に values の2番目の色が描かれる。上記例では values="BRW" なので、グリッド中央に2番目の色である赤が塗られる。これはこの色を起点として処理を行う場合に有効になる。

レインボー

<one values="BROYGUIP" origin="True">
  <rule in="RB" out="RO"/>
  <rule in="OB" out="OY"/>
  <rule in="YB" out="YG"/>
  <rule in="GB" out="GU"/>
  <rule in="UB" out="UI"/>
  <rule in="IB" out="IP"/>
  <rule in="PB" out="PR"/>
</one>

origin="True" なので、最初グリッドの中央に赤が塗られる。そして、赤黒ならば赤橙、橙黒ならば橙黄に置き換える…のように、{色A}黒 を {色A}{色B} に置き換えてレインボーカラーを増殖していく作例になる。

余談だが、先細説明した通り、ルールは回転して適用されるので、たとえば in="RB" を定義するとき、左右逆の in="BR" を用意する必要はない。

掘り進める

<one in="RBB" out="WWR" values="BRW" origin="True"/>

これは赤黒黒とあるところを、白白赤のように2マスまたいで赤を移動させて、2マス分移動した軌跡を白で塗る例。

つまり、赤=現在位置、白=今まで掘り進めた場所、黒=まだ掘っていない場所を表現している。

今までは1つのノードで置き換え処理をしていたが、次に複数のノードを扱う例を紹介する。

SequenceNode

<sequence values="BRW" origin="True">
  <one in="RBB" out="WWR"/> <!-- 1つ目のノード -->
  <one in="RWW" out="BBR"/> <!-- 2つ目のノード -->
</sequence>

SequenceNodeを表す <sequence/> の中にノードを入れると、子要素の1つ目のノードを適用できるだけ適用を行い、できなくなったら次のノードに移動し、そのノードを適用できるだけ適用…と順番に処理を行う。子要素のノードを周りきると、親であるSequenceNodeの処理が終了したことになる。

上記例では、1つ目のOneNodeで掘り進めるだけ掘り進んで、進めなくなったら次のノードに移動する。2つ目のノードのルールは赤白白を黒黒赤に置き換える、つまり1つ目で進んできた道を戻りながら白の軌跡を消していくという処理になる。

MarkovNode

<markov values="BRWA" origin="True">
  <one in="RBB" out="WAR"/>
  <one in="WBB" out="WAR"/>
</markov>

MarkovNodeを表す <markov/> はSequenceNodeと似たような機能で、子要素の1つ目のノードを適用できるだけ適用させ、次に2つ目のノードに移動するのだが、2つ目のノードの実行が成功すると、次に実行されるのはまた1つ目のノードに戻ることになる。つまり、子要素のノードの実行が成功するたびに、一番上の子要素からまたイテレートし直すのが特徴になる。

// SequenceNode
for (; i < children.length; i++) {
  if (run(children[i)) {
    return true; // i番目の子要素でルールがマッチした。
  }
}

// MarkovNode
for (i = 0; i < children.length; i++) {
  if (run(children[i)) {
    return true; // i番目の子要素でルールがマッチした。
  }
}

文章だとわかりづらいので、2つのノードの機能の違いを擬似コードで表現したのが上記になる。

上記例では、1つ目のノードで RBB を WAR に置き換えているので、R を移動させながら軌跡を WA の文字で表現している。そのうち掘り進めなくなるので、2つ目のノードに移動して、WBB を WAR に置き換える、つまり途中の軌跡からまた新たな道を1回掘り進めて、また1つ目のノードに戻り、今2つ目のノードで掘った道からまた掘り続けることになる。

AllNode

<all values="BROYGUIP" origin="True">
  <rule in="RB" out="RO"/>
  <rule in="OB" out="OY"/>
  <rule in="YB" out="YG"/>
  <rule in="GB" out="GU"/>
  <rule in="UB" out="UI"/>
  <rule in="IB" out="IP"/>
  <rule in="PB" out="PR"/>
</all>

OneNodeはマッチ候補の中からランダムに一つだけ選択する機能だったが、AllNodeを表す <all/> では、マッチ候補すべてをランダムな順番で適用させる。

ただし、複数あるマッチ候補をランダムに一つずつ適用させていくと、先に選ばれたマッチがグリッドの値を書き換えることによって、後のマッチが不適合になる可能性がある。その場合は後のマッチは捨てられるのでルールの矛盾が起こることはない。

<all in="R" out="G" />

1フレームで同時実行ができるので、上記例のように特定の色を別の色に一瞬で置き換える処理が書ける。

ParallelNode

ParallelNodeを表す <prl/> はAllNodeと似ていて、複数あるマッチ候補を全て適用させる。ただし、AllNodeの場合は先程説明した通り、先行マッチ候補の書き換えによって後のマッチが不適合になる場合は後者のマッチが捨てられるが、ParallelNodeの場合はそれに関係なくその上から更に書き込みを行う。

マッチの不適合によってグリッドの一部がおかしな結果になる可能性があるが、AllNodeより高速に処理を行うことができる特徴がある。

steps

<sequence values="BRGY">
  <one steps="50">
    <rule in="B" out="R" />
    <rule in="B" out="G" />
    <rule in="B" out="Y" />
  </one>
  <all in="BR" out="RR" />
  <all in="RG" out="GG" />
  <all in="GY" out="YY" />
</sequence>

属性である steps に値を入れると、ノードの実行回数がその値分を上限として制限される。

上記例では、黒を赤 or 緑 or 黃に置き換えるOneNodeが実行されるが、steps="50" なので、実行される回数は最大で50回までになる。

改行

<sequence values="BR">
  <one in="BBB/BBB/BBB" out="BBB/BRB/BBB" />
</sequence>

今までは幅か高さが1のルールしか作れなかったが、ルールに / を入れることでルールの改行をすることができる。

つまり上記ルール例では、

BBB    BBB
BBB => BRB
BBB    BBB

に置き換えるというルールになる。

ワイルドカード

<sequence values="BD" origin="True">
  <all>
    <rule in="D*B" out="**D"/>
  </all>
</sequence>

in の中に * を入れると、その場所には何の文字が入っていてもよい、というワイルドカード扱いになる。
out の中に * を入れると、その * がある位置の in の文字がそのまま out の * に入る。

上記例では、利用できる文字が BD なので、DDB => DDD or DBB => DBD という意味になる。

ユニオン

<sequence values="BROYGUIP">
  <one steps="100">
    <rule in="B" out="R"/>
    <rule in="B" out="O"/>
    <rule in="B" out="Y"/>
    <rule in="B" out="G"/>
    <rule in="B" out="U"/>
    <rule in="B" out="I"/>
    <rule in="B" out="P"/>
  </one>

  <union symbol="?" values="ROYGUIP" />
  <one in="?" out="B" />
</sequence>

ユニオンを表す <union/> を利用することで、文字を結合した新たな文字を作成することができる。

たとえば、<union symbol="?" values="WA" /> だと、? という新しい文字を作成し、その ? のマスには W か A どちらが入ってもよいということになる。

上記例では B 以外の文字を ? にまとめて、<one in="?" out="B" /> で B 以外の文字を1つずつランダムに消していく処理になる。

フィールド

<sequence values="BOS">
  <one in="B" out="O" steps="1"/>
  <one in="B" out="S" steps="1"/>
  <one>
    <rule in="OB" out="OO"/>
    <rule in="SB" out="SS"/>

    <field for="S" to="O" on="BS" recompute="True"/>
    <field for="O" to="S" on="BO" recompute="True"/>
  </one>
</sequence>

OneNodeではマッチ候補の中からランダムに1つだけマッチを選びだすが、フィールドを表す <field/> を定義することで、ヒューリスティックにマッチを選択することができる。

これはかなり複雑なルールなので、上記例を通して機能を説明したい。

まず、最初の <one/> 2つで、グリッドのどこかに O と S が1つずつ配置される。
そして、次の <one/> のルールで O と S が増殖していくが <field/> が定義されているので、ランダムにマッチが選択されるわけではない。

<field for="S" to="O" on="BS" recompute="True"/>
in から out に置き換わるときに、置き換わった文字が <field/> の for に入っている場合、評価関数が実行され、その文字にスコアが付けられる。そしてスコアの合計が最も高いマッチが選ばれることになる。

上記 <field/> の場合、for が S なので、<rule in="SB" out="SS"/> の2つ目の文字の置換の際に評価される。具体的な評価内容は、for の文字は on の文字を通って to にたどり着けなければならない。たどり着けるルートが複数ある場合は for から to の（マンハッタン）距離が近いものほどスコアが高くなる。

<rule in="SB" out="SS"/>
<field for="S" to="O" on="BS" recompute="True"/>

本来、<field/> が無ければ、数ある SB の中でランダムに1つだけ SS に置き換わるが、上記 <field/> があると、O に最も近い B が選ばれるようになる。

recompute に True を入れると、毎フレーム上記の計算行われる。

シンメトリー

2Dのルールの場合、デフォルトだとルールを0度（無回転）、90度、180度、270度回転させたものと、それらを反転した計8パターンのマッチが行われるが、勝手に回転してマッチされては困るというケースがあるので、それに対する専用の制御文が用意されている。

<one in="AB" out="CD" symmetry="()"/>

各Nodeに属性 symmetry を付けると回転or反転の制御を行うことができる。上記の () は回転or反転を一切行わないという意味になるので、左から AB の順番で並んでいる箇所だけが置き換え候補になる。

symmetry を付けなければ親Nodeの symmetry の設定が引き継がれる。

symmetry="()" <!-- 回転or反転を一切行わない -->
symmetry="(x)" <!-- x軸の反転だけ許可する -->
symmetry="(y)" <!-- y軸の反転だけ許可する -->
symmetry="(x)(y)" <!-- x軸とy軸の反転だけ許可する -->
symmetry="(xy+)" <!-- 回転だけ許可する -->
symmetry="(xy)" <!-- すべての回転or反転を許可する（デフォルトの設定） -->

その他のルール

上記以外にも多数のルールがあるが、解説ができ次第追加していく。ルールの1つであるWaveFunctionCollapseについては以前に単体の記事を書いているので必要であれば参照してほしい。

https://zenn.dev/baroqueengine/articles/1a40755be9b8ed

実際のMarkovJuniorの使い方

まず、git clone でプロジェクトをローカルにダウンロードする。

次に /models.xml を開く。

<models>
  <model name="Basic" size="20" gif="true"/>
</models>

name に名前を入れると、/models/{名前}.xml が読み込まれる。/models 内には大量のサンプルが用意されているので適当にどれかを入れてみよう。

size はグリッドの縦横サイズで、gif="true" にすると、出力の際にイテレート毎に画像を出力してくれる。

実行は dotnet run で行う。