p5.jsでマルコフ連鎖を使って生き物っぽいものを作ってみる

こんにちは！
東海メンターのだすです。
この記事は[Life is Tech ! Tokai Advent Calendar 2022](https://qiita.com/advent-calendar/2022/life-is-tech-tokai)の3日目の記事です。

# 最近のメディアアートすごいね
最近メディアアートにハマってます。
作品を見ているとすごい作品ばっかりで見ていて全然飽きないです。
中には生き物を表現しているものもあり本当に永遠に眺めていられそうでアクアリウムのように部屋に置いておきたくなるものもありました。

どうやったらそういう表現ができるのだろう、p5.jsでもできないかなぁというところでマルコフ連鎖を使って生き物を表現してみようという記事になります。


# 生き物をどうやって表現しようか
生き物的なものを作ろうと考えた時、まず生まれて、成長して、仲間を増やして、死ぬみたいなサイクルがあるよなということで状態変化を作ればいいのかと行きつきました。
状態変化・状態遷移と言えば**マルコフ連鎖**かな、ということでまずは生き物っぽいものをマルコフ連鎖を使って作ってみようと思います。

# マルコフ連鎖
まず、マルコフ連鎖（マルコフ過程）をものすごーく掻い摘んで説明すると、
- 状態の移り変わりが確率で決まり
- 今の状態次第で次の状態が決まる
というものです。

状態がS0, S1, S2の３つがあり、
各状態からの遷移確率が

- $S0$から$S1$に30%の確率で遷移
- $S1$から$S2$に50%の確率で遷移
- $S2$から$S0$に20%の確率で遷移
- $S2$から$S1$に10%の確率で遷移
こんな時は下のような状態遷移図になります。

```mermaid
stateDiagram-v2
  direction LR
  [*] --> S0
  S0 --> S0: 60%
  S0 --> S1: 30%
  S1 --> S1: 50%
  S1 --> S2: 50%
  S2 --> S2: 70%
  S2 --> S0: 20%
  S2 --> S1: 10%
```

特に今回の実装で重要なのは、上の状態遷移図をこんな推移確率行列で表現できることです。

```math
P=
\begin{bmatrix}
0.6 & 0.3 & 0.0 \\
0.0 & 0.5 & 0.5 \\
0.2 & 0.1 & 0.7 \\
\end{bmatrix}
```
$Sn$から$Sm$に30%の確率で遷移することを$P_{n,m}=0.3$というように表します。
ex. $S0$から$S1$に30%の確率で遷移 → $P_{0,1}=0.3$

詳しくはこちらなどを読んでいただけると良いと思います。

https://manabitimes.jp/math/1060

# 実装するぞ
## 状態ごとになんか表示する
状態ごとに描画するものとして適当に準備します。
とりあえずこんな感じ
<p class="codepen" data-height="300" data-default-tab="js,result" data-slug-hash="JjBGVBz" data-user="norihirosunada" style="height: 300px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/norihirosunada/pen/JjBGVBz">
  empty-example</a> by Norihiro Sunada (<a href="https://codepen.io/norihirosunada">@norihirosunada</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>

## 状態遷移を実装
ここからが本題です。
状態を変数として制御します。

そして、状態遷移を推移確率行列にしたものを2次元配列にします。
```javascript
let p = [
    [0.995, 0.005, 0],
    [0, 0.99, 0.01],
    [0.005, 0.015, 0.98],
];
```
この時、`p[n][m]`が$Sn$から$Sm$への遷移確率を表すことになります。
ex. `p[0][1]` → $S0$から$S1$

`p[0]`が状態$S0$時の遷移確率を持っているので処理的にも扱いやすいです。

遷移確率の判定はこんな感じ
```javascript
let p_next = random();
let p_action = 0;
for(let i = 0; i < p[state].length; i++) {
    p_action += p[state][i];
    if(p_action > p_next){
        state = i;
        break;
    }
}
```

状態遷移判定をするごとにこれを実行します。
`p_next`には乱数が入り、for文で遷移確率`p_action`と比較し、確率を超える場合に状態を遷移させます。
１状態から他の状態への遷移確率は合計で１となるようにしています。
遷移確率を足し合わせていくことでいずれかの遷移判定に引っかかるようになっています。

# できあがり
状態遷移判定をフレームごとに行い、状態に応じて表示を変えてみます。
こんな感じになりました。

$S0$から$S1$、次に$S2$に変わり、たまに$S1$に戻りつつ、最終的に$S2$の後に$S0$になる様子が見えます。
遷移確率も配列から変えれるので動きを調整するのも簡単です。

<p class="codepen" data-height="460" data-default-tab="js,result" data-slug-hash="GRBobRd" data-user="norihirosunada" style="height: 300px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/norihirosunada/pen/GRBobRd">
  MarcovCreature</a> by Norihiro Sunada (<a href="https://codepen.io/norihirosunada">@norihirosunada</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>

# 最後に
これで生き物っぽいものが表現できるようになったのでもう少し作り込んでみました。
相互に影響したり子孫残したりみたいなもっと生き物っぽい動きを増やしていくのも面白そうです。
いつかやりたいです。

https://twitter.com/DasunaDev/status/1608244468725207041