ComputeShaderで巨大ライフゲームを作る

# はじめに
本記事は[Unity Advent Calendar 2017](https://qiita.com/advent-calendar/2017/unity)の8日目の記事です。
昨日は@sassembla@githubさんの[「実機上でテスト実行／結果収集するツールの紹介」](http://sassembla.github.io/Public/2017:12:07%2000-00-00/2017:12:07%2000-00-00.html)でした。

# ライフゲーム
ご存知の方も多いかとは思いますが、ライフゲームとは数学者のコンウェイさんが考えた生命のプロセスを簡易的なモデルにしたシミュレーションゲームです。二次元グリッドの各セルを生き物に見立てて、以下のようなルールで周囲８近傍のセルの状態により次の状態を決定します。

* 誕生
    * 死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
* 生存
    * 生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
* 過疎
    * 生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
* 過密
    * 生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。


今回は以前作ったComputeShader実装のライフゲームを解説してみようと思います。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="en" dir="ltr">Conway&#39;s Game of Life in Unity Compute Shader.<a href="https://t.co/oLmwlLEOfF">https://t.co/oLmwlLEOfF</a><a href="https://twitter.com/hashtag/unity3d?src=hash&amp;ref_src=twsrc%5Etfw">#unity3d</a> <a href="https://twitter.com/hashtag/madewithunity?src=hash&amp;ref_src=twsrc%5Etfw">#madewithunity</a> <a href="https://twitter.com/hashtag/gameoflife?src=hash&amp;ref_src=twsrc%5Etfw">#gameoflife</a> <a href="https://twitter.com/hashtag/lifegame?src=hash&amp;ref_src=twsrc%5Etfw">#lifegame</a> <a href="https://t.co/qxmL4lPd2a">pic.twitter.com/qxmL4lPd2a</a></p>&mdash; fuqunaga🍣 (@fuqunaga) <a href="https://twitter.com/fuqunaga/status/912257060036685824?ref_src=twsrc%5Etfw">2017年9月25日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

こんな感じでうじゃうじゃします。

![lifegame.png](https://qiita-image-store.s3.amazonaws.com/0/15038/ffc632a2-5c57-489a-10a8-a7f9b6c32637.png)
広くしてみました。細かすぎてわかりにくいですがこの１ドットがセルです。手元の環境で4kサイズでやってみましたが普通に動きます。ComputeShaderばんざい。


プロジェクトはこちら
https://github.com/fuqunaga/GPULifeGame


# 実行処理

## ComputeShader側

コード全体としては以下のような感じになります。

```LifeGame.compute
#pragma kernel Step

#define NUM_THREAD_X 32
#define NUM_THREAD_Y 32
#define NUM_THREAD_Z 1

#include "Data.cginc"

RWStructuredBuffer<Data> _WriteBuf;
StructuredBuffer<Data> _ReadBuf;

inline bool GetAlive(int2 xy)
{
    return (any(xy < 0) || (_Width <= xy.x) || (_Height <= xy.y)) ? false : _ReadBuf[xyToIdx(xy)].alive;
}

////////////////////////////////////////////////////////////////////////////////
// Step
////////////////////////////////////////////////////////////////////////////////
[numthreads(NUM_THREAD_X,NUM_THREAD_Y,NUM_THREAD_Z)]
void Step (uint3 id : SV_DispatchThreadID)
{
	int2 pos = id.xy;
	if ( (pos.x < _Width) && (pos.y < _Height))
	{
		bool alive0  = GetAlive(id.xy + int2(-1,-1));
		bool alive1  = GetAlive(id.xy + int2( 0,-1));
		bool alive2  = GetAlive(id.xy + int2( 1,-1));
		bool alive3  = GetAlive(id.xy + int2(-1, 0));
		bool center = GetAlive(id.xy + int2( 0, 0));
		bool alive4  = GetAlive(id.xy + int2( 1, 0));
		bool alive5  = GetAlive(id.xy + int2(-1, 1));
		bool alive6  = GetAlive(id.xy + int2( 0, 1));
		bool alive7  = GetAlive(id.xy + int2( 1, 1));

        int count = alive0
            + alive1 
            + alive2 
            + alive3 
            + alive4 
            + alive5 
            + alive6 
            + alive7;

		_WriteBuf[xyToIdx(pos)].alive = (count == 3) || (center && (count == 2));
	}
}
```

細かく見ていきましょう！

```
#pragma kernel Step
```
まずはC#側から呼べるカーネルを指定しています。
ここで指定された関数が大量のスレッドで並列実行されるのがComputeShaderの特徴的な挙動です。

```Data.cginc
struct Data{
	int alive;
};

int _Width;
int _Height;

inline int xyToIdx(int2 xy)
{
    return xy.y * _Width  + xy.x;
}
```

ここの定義はビジュアライズ用のシェーダーでも使いたかったのでcgincとして別ファイルにしています。セル一つ分の状態をもつData構造体、セル全体のサイズを入れる変数_Width、_Heightを用意しています。セルの状態を持っているバッファは一次元配列なのでセルの位置xyからインデックスを計算する関数を用意しています。

```
inline bool GetAlive(int2 xy)
{
    return (any(xy < 0) || (_Width <= xy.x) || (_Height <= xy.y)) ? false : _ReadBuf[xyToIdx(xy)].alive;
}
```

指定位置のセルの生死状態を引いてくる関数を用意し、範囲外は死にセル判定にしています。

```
#define NUM_THREAD_X 32
#define NUM_THREAD_Y 32
#define NUM_THREAD_Z 1
```
```
[numthreads(NUM_THREAD_X,NUM_THREAD_Y,NUM_THREAD_Z)]
```
numthreadsでスレッドグループ１つにおけるスレッド数を定義しています。
NUM_THREAD_X * NUM_THREAD_Y * NUM_THREAD_Z 個のスレッドが１グループとして同時に実行されるイメージです。この値はパフォーマンスを見ながら調整しがちなところですので、defineでちょっと書き換えしやすいところに逃しています。
`[numthreads(32,32,1)]`と直で数値を書いても構いません。

```
void Step (uint3 id : SV_DispatchThreadID)
```

さて、メインの関数です。

大量のスレッドで同時実行されるので、現在どのスレッドであるのかを引数idで判断します。id はセマンティクス*SV_DispatchThreadID*指定しているので、id.xyzにそれぞれ通しのスレッド番号が入ってきます。使用できるセマンティクスは他にもいくつかあり、どれも全体の中におけるどの部分のスレッドなのかを知る手がかりとして用意されています。
https://msdn.microsoft.com/ja-jp/library/ee422317(v=vs.85).aspx


```
    int2 pos = id.xy;
    if ( (pos.x < _Width) && (pos.y < _Height))
```
ComputeShaderはスレッドグループ単位で実行されるので、トータルのスレッド数がうまく_Width、_Heightで割り切れるとは限りません。足りないと困るので確実に_Width、_Heightを網羅するだけのスレッドグループ数（C#側で指定します）を実行し、はみ出した分を`if ( (pos.x < _Width) && (pos.y < _Height))`のif文で無視しています。

```
    {
        bool alive0  = GetAlive(id.xy + int2(-1,-1));
        bool alive1  = GetAlive(id.xy + int2( 0,-1));
        bool alive2  = GetAlive(id.xy + int2( 1,-1));
        bool alive3  = GetAlive(id.xy + int2(-1, 0));
        bool center = GetAlive(id.xy + int2( 0, 0));
        bool alive4  = GetAlive(id.xy + int2( 1, 0));
        bool alive5  = GetAlive(id.xy + int2(-1, 1));
        bool alive6  = GetAlive(id.xy + int2( 0, 1));
        bool alive7  = GetAlive(id.xy + int2( 1, 1));

        int count = alive0
            + alive1 
            + alive2 
            + alive3 
            + alive4 
            + alive5 
            + alive6 
            + alive7;

       _WriteBuf[xyToIdx(pos)].alive =　(count == 3) || (center && (count == 2));
    }
```

GetAlive()関数経由で_ReadBufから８近傍の現在の状態を読み取り、ルールに従って次の状態を_WriteBufに書き込みます。単一のバッファで読み書きすると、読んでくるセルの値が現フレームの更新前の値だったり更新後の値だったりと一貫しなくなってしまいます。確実に更新前の値を参照したいので読み取りバッファと書き込みバッファを分けて用意しています。

なにげにライフゲームのルールはワンライナーで済んじゃいました。
`(count == 3) || (center && (count == 2));`





## C#側
まずはComputeShaderで読み書きするComputeBufferを作ります。

```csharp
public struct Data
{
    public int alive;
}
```
```csharp
_readBufs = new ComputeBuffer(gridNum, Marshal.SizeOf(typeof(Data)));
_writeBufs = new ComputeBuffer(gridNum, Marshal.SizeOf(typeof(Data)));
```
ComputeShader側と同じData構造体をgridNum個持つようにしておきます。生死の状態なのでboolでいいのですが、ComputeShader側とサイズが合わないのかうまく行きませんでしたのでintにしています。


```csharp
var initialData = Enumerable.Range(0, gridNum).Select(_ => new Data() { alive = (rand.NextDouble() < _initialAliveRate) ? 1 : 0 }).ToArray();
_readBufs.SetData(initialData);
```

\_reafBufに初期値を入力します。Dataの配列を作って\_readBufに渡しています。動きが面白くなるようにランダムに一定の割合でセルを生かしておきます。


```csharp
public static class COMMONPARAM
{
    public const string WIDTH = "_Width";
    public const string HEIGHT = "_Height";
}

public static class CSPARAM
{
    public const string KERNEL_STEP = "Step";
    public const string WRITE_BUF = "_WriteBuf";
    public const string READ_BUF = "_ReadBuf";
}
```

```csharp
_cs.SetInt(COMMONPARAM.WIDTH, _width);
_cs.SetInt(COMMONPARAM.HEIGHT, _height);

var kernel = _cs.FindKernel(CSPARAM.KERNEL_STEP);

_cs.SetBuffer(kernel, CSPARAM.READ_BUF, _readBufs);
_cs.SetBuffer(kernel, CSPARAM.WRITE_BUF, _writeBufs);

Dispatch(_cs, kernel, new Vector3(_width, _height, 1));
```
ComputeShader.Set~関数でComputeShaderに値を渡しています。ComputeShader側の変数名を文字列で指定しているので変更しやすいようにstatic classで定数として定義しておきます。


```csharp
public static void Dispatch(ComputeShader cs, int kernel, Vector3 threadNum)
{
    uint x, y, z;
    cs.GetKernelThreadGroupSizes(kernel, out x, out y, out z);
    cs.Dispatch(kernel, Mathf.CeilToInt(threadNum.x / x), Mathf.CeilToInt(threadNum.y / y), Mathf.CeilToInt(threadNum.z / z));
}
```
`ComputeShader.Dispath()`はスレッドグループの個数を指定してカーネルを実行する命令です。たいていはスレッド数で指定したいので、そのスレッド数を満たすスレッドグループ数を求めて`ComputeShader.Dispatch()`する関数を作っておくと使い勝手がいい気がします。

```csharp
void SwapBuf()
{
    var tmp = _readBufs;
    _readBufs = _writeBufs;
    _writeBufs = tmp;
}
```
Dispatch()したら今回の結果を次の状態として読み込むのでバッファをスワップしておきます。


# 描画処理
これでComputeShaderでライフゲームを動かせるようになりました。しかしこのままではComputeBufferに結果が入ってるだけで確認できませんのでビジュアライズしましょう。

## Shader側
```LifeGame.shader
Shader "LifeGame/Visualize"
{
	SubShader
	{
		Cull Off ZWrite Off ZTest Always

		Pass
		{
			CGPROGRAM
			#pragma target 5.0
			#pragma vertex vert_img
			#pragma fragment frag
			
			#include "UnityCG.cginc"
			#include "./Data.cginc"

			StructuredBuffer<Data> _Buf;

			fixed4 frag (v2f_img i) : SV_Target
			{
				int2 xy = int2(_Width,_Height) * i.uv;
				Data data = _Buf[xyToIdx(xy)];
				return fixed4((data.alive ? 1 : 0.5).xxx, 1);
			}
			ENDCG
		}
	}
}
```

レンダーターゲット全体をセルが並んでいるグリッドとして、各ピクセルの位置（uv値）に対応するセルが生きてたら白、死んでたら灰色を出力しています。ComputeShaderのときに別ファイルに分けておいたData.cgincをこちらでも使っています。vert_imgやv2f_imgはUnityCG.cgincで定義されています。お決まりのコードを書かなくていいので便利です。

## C#側

```csharp:LifeGame.cs
private void OnRenderImage(RenderTexture source, RenderTexture destinatio
{
    if (_readBufs != null)
    {
        _mat.SetInt(COMMONPARAM.WIDTH, _width);
        _mat.SetInt(COMMONPARAM.HEIGHT, _height);
        _mat.SetBuffer(SHADERPARAM.BUF, _readBufs);
        Graphics.Blit(source, destination, _mat);
    }
}
```
LifeGame.csをカメラにアタッチしておいて、`OnRenderImage()`で、LifeGame.shaderをセットしたマテリアルをGraphics.Blit()しています。ComputeShaderで求めた_writeBuf（`SwapBuf()`されたあとなのでここでは_readBuf）を今度はシェーダーに渡しています。


# まとめ
これでライフゲームをComputeShaderで動かして確認するところまでできました！
githubに上がってるプロジェクトではさらにマウスのインプットからセルを書き換えることもやっていますので、もし興味がありましたらご覧ください。

# プロジェクトを見るにあたって
このプロジェクトは[SyncUtil](https://github.com/fuqunaga/SyncUtil)という、複数のPCを同期するユーティリティを検証するためのComputeShaderサンプルプログラムとして作成しました。その関係でComputeShaderを動かすだけのプロジェクトとしてみると少し遠回りしてるような変なコードになっています。あまり細かいところは気にせずにざっと見てもらえるとよいかと思います。



# 参考資料
https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0
https://msdn.microsoft.com/ja-jp/library/ee422317(v=vs.85).aspx

# 明日
明日は@lycoris102さんの「[Unity] Editor拡張でInspector上で"戻る"を実現する」です。