simplestarの技術ブログ

目的を書いて、思想と試行、結果と考察、そして具体的な手段を記録します。

CubeWalkGameなだらかな地形生成と永続化

AI Game Programming Unity

このシリーズの続きです。
simplestar-tech.hatenablog.com

１．ECS による動的頂点生成と面生成
２．チャンクをまたぐデータ参照
３．キューブの回転とテクスチャの設定

と階段を登ってきました。

今回は過去記事でいうところのこのあたり
simplestar-tech.hatenablog.com
simplestar-tech.hatenablog.com
を整理しながら新しい知見を交えて、地形生成と永続化の手段を記録します。

過去実装からの移植で考えなければならないのは、
１．近景と遠景の階層化
単純に言えば、近場のチャンクにはコライダーが適用され、様々な相互作用の計算が走ります。
遠景のチャンクはチャンク同士でさえ結合され、コライダーは無く、描画にのみ特化した結合メッシュとなります。

加えて、
２．プレイヤーチャンクを中心に、もしプレイヤーがチャンクをまたいで移動した時は、動的に近景チャンクを追加し世界を広げる必要があり、古い近景チャンクは削除

しなければなりません。
そして、遠景と近景の間の穴が見つかることなくうめなければなりません。

もう一つ、
３．複数のマテリアルを利用して世界を表現

できなければなりません。これは描画レートの制約です。
現在の構想では、マテリアル数を 4 つほどに抑えて、オブジェクトを複数に分けるというものでしたが、はたして…

この三点について具体的な実装を考えていきます。

# 近景と遠景の階層化

3次元空間を扱う List の作成となりますが、5ヶ月前はとても難易度の高い立体 List を作ってこれの変化を管理するということを行いました。

難しいテンソル変形操作で、とても休日の片手間でメンテナンスするものではなくなりました。
（これ、休日に管理したくない）

そこで考えたのがソートとキューです。
計算リソースを使うことで、コードを簡略化することにします。

要するに、プレイヤーの座標 + チャンク幅の真ん中オフセットからチャンク位置までの距離を計算し
あたかもチャンクの中心とプレイヤー座標との距離を計算しているかのようにし
その距離を昇順にソートしてキューに詰めます。

キューの先頭から要素を取り出せば、順にプレイヤーに近いチャンクから処理されていくという動きが想像できます。

ぱっと思いつくのは
キューそのものにソート機能は無い
List には Sort 機能ある
何度もソートするなら、先に距離を計算する
チャンク内のキューブ数を増やして、チャンクの数を減らすとソート時間が短縮される

こう考えていくと、最初にリストに乗せるチャンクはどうやって決めるのか定義しなければなりません。

プレイヤーの座標から、チャンクの位置 int, int, int を決定
そこから立方体を切り出すように int, int, int の配列をつくり

これまでの以下のロジックを使って一意のチャンクキーを決定するのはどうか？

        #region 位置からチャンクキーに変換
        var byteMax = (byte.MaxValue + 1);
        var chunkKeyX = chunkPosition.x % byteMax;
        if (0 > chunkKeyX) chunkKeyX += byteMax;
        var chunkKeyY = chunkPosition.y % byteMax;
        if (0 > chunkKeyY) chunkKeyY += byteMax;
        var chunkKeyZ = chunkPosition.z % byteMax;
        if (0 > chunkKeyZ) chunkKeyZ += byteMax;
        #endregion

近景と遠景で処理を分けるとして
遠景はどのように表現すべきか
以前は 2 x 2 x 2 のチャンクのメッシュを合成していた
ただ、難しいのが近景と遠景の接続部分

贅沢なメモリ利用を考えるなら、メッシュ情報をすべてチャンク単位で持ち
近景と重なる遠景の部分は、場合によりチャンク単位で描画され
まったく重ならない領域では、メッシュを結合して 1/8 チャンクのメッシュとなり
さらに遠方では 3 x 3 x 3 で結合して、さらに遠方では 4 x 4 x 4 で結合する
階層は 1, 2, 3, 4, 5 階層くらいに分けて、結合されたチャンクはいつでも柔軟に
チャンク単位でメッシュを結合できる仕組みを考えます。

計算量も有限なので、階層ごとにコンビネーションを取ることは難しいと考えました。

プレイヤーのカメラを内包するチャンクを中心チャンクとして、これが余白をもって変化したタイミングで
最大チャンク半径について、すべてのチャンクの中心チャンクからの距離を計算し、近い順にソートします。

近い順に処理しながら、チャンク単位のメッシュを作成します。
距離が離れていくにつれて、2x2x2, 3x3x3, 4x4x4, 5x5x5 とメッシュを結合していきます。

外周のチャンクを作っている最中はだんだんパフォーマンスが悪くなりそうな予感がしてますが、どうなんでしょう？
ロジックとしては単純で、チャンクの結合が柔軟に行えて良い気がしています。

結合した後、中心チャンクが移動したときはどうなるでしょうか？
もう一度、すべてのチャンクの中心チャンクからの距離を計算し、近い順にソートします。

近い順にメッシュ情報を再利用しながら、一定距離近づいたにも関わらず 2 x 2 x 2 の結合メッシュに所属しているチャンクは一度、その結合メッシュをチャンク単位で描画するように戻し、結合メッシュを破棄

ふとここまでイメージしていて気づいたことに、視錐台カリングのために密集したチャンク同士でメッシュを結合する必要を考えてきたけど
順に取り出した位置はバラバラのチャンクで結合してもパフォーマンスはいくらか上がるという考え方
これなら距離に応じて結合チャンク数を逐次増やしていけるし、順番に結合済みのチャンクを作っていける
外周チャンクを作っているときに大量のチャンク単位のオブジェクトが作られる問題も解決します。

いや、やはり階層化しつつ、密集したチャンクで一つのオブジェクトとしたいところ
プレイヤーカメラからの距離でチャンクのソートが行えたなら、その順番を数で区切って 1階層2階層、3階層とグループ分けできると考えた
2階層のチャンクについて、中心チャンクから一定の間隔で 2 x 2 x 2 の結合を行っていくで良さそう
結合対象から漏れていたらそのチャンクを結合しなければいい
分解ができるなら、周囲のチャンクのみ分解し、その中心チャックに沿って分解と再結合を行っていく
第6階層の走査で、領域に含まれるチャンクについては削除を行うようにして、メモリの肥大を防ぐというもの

プレイヤーカメラと中心チャンクとの距離だけを毎フレーム見ながら、一定距離離れたら、全チャンクとの距離を計算してソートするようにして
いったんどのような動きとなるか考えていきたいと思います。

実装前の最後に、チャンクの情報をどうやってディスクやインターネットから読み込むかを考えてみます。
階層1の処理が終わったら、階層2のチャンクのデータの作成、保存、次回から読み込みを行うようにする。

イメージどおりに動くか、そろそろ実装します。

…一晩寝かせて気づいたのは、階層構造を立体格子状にループさせれば
チャンクまでの距離ソートがいらないのではないか、ということ

ここまで長く書いてきたことは…無かったことにしてください！

例えばこちらが愚直に書き下した、既存のチャンク処理ループ

            #region 作成対象のエンティティを Enqueue
            if (Input.GetKeyDown(KeyCode.Space))
            {
                for (var x = -15; x <= 15; x++)
                {
                    for (var z = -15; z <= 15; z++)
                    {
                        for (var y = -15; y <= 15; y++)
                        {
                            this.EnqueueCreateEntity(x, y, z);
                        }
                    }
                }
            }
            #endregion

f:id:simplestar_tech:20190619080304p:plain
31 x 31 x 31 チャンクの生成状況 32.52 ms ループ

f:id:simplestar_tech:20190619080434p:plain
タイムライン

遅い…なんとか高速化できないか

高速化について、次のように、中央から順に周辺チャンクを結合していくループを回すのはどうかと考えた

            #region 作成対象のチャンク情報を Enqueue
            if (Input.GetKeyDown(KeyCode.Space))
            {
                var perChunkRadius = 1;
                for (var x = -perChunkRadius; x <= perChunkRadius; x++)
                {
                    for (var z = -perChunkRadius; z <= perChunkRadius; z++)
                    {
                        for (var y = -perChunkRadius; y <= perChunkRadius; y++)
                        {
                            this.EnqueueCreateEntity(x, y, z, 0);
                        }
                    }
                }
                for (var level = perChunkRadius + 1; level <= 2; level++)
                {
                    if (2 > level)
                    {
                        break;
                    }
                    var offset = 3;
                    var geta = level * offset - 3;
                    for (var x = -geta; x <= geta; x += offset)
                    {
                        for (var z = -geta; z <= geta; z += offset)
                        {
                            for (var y = -geta; y <= geta; y += offset)
                            {
                                if (0 != geta - Mathf.Abs(x) && 0 != geta - Mathf.Abs(y) && 0 != geta - Mathf.Abs(z))
                                {
                                    continue;
                                }
                                for (var radiusX = -perChunkRadius; radiusX <= perChunkRadius; radiusX++)
                                {
                                    for (var radiusZ = -perChunkRadius; radiusZ <= perChunkRadius; radiusZ++)
                                    {
                                        for (var radiusY = -perChunkRadius; radiusY <= perChunkRadius; radiusY++)
                                        {
                                            if (0 == radiusX && 0 == radiusY && 0 == radiusZ)
                                            {
                                                continue;
                                            }
                                            this.EnqueueCreateEntity(x + radiusX, y + radiusY, z + radiusZ, 0);
                                        }
                                    }
                                }
                                this.EnqueueCreateEntity(x, y, z, 1);
                            }
                        }
                    }
                }
            }
            #endregion

f:id:simplestar_tech:20190619230359p:plain
geta 飛び配置で描画負荷を低減

f:id:simplestar_tech:20190621225117p:plain
コアで結合した結果

f:id:simplestar_tech:20190621225225p:plain
描画負荷は十分に解決

プレイヤーのいるチャンクを中心に、処理をループさせて、近景は 1 チャンクずつ
遠景は 3x3x3 を一つのチャンクに結合するという処理は、構想から始めて、だいたいいい形で固まりました。

# 適当な地形生成

プレイヤーカメラ移動に際し、今の巨大なキューブでは移動によって結果変化がわかりません。
このままでは先に進めなくなったので、適当な地形生成を行います。

以前調べた snoise を高さ情報として、なだらかな地形を生成してみます。

イメージを形に…

今はチャンク情報を１チャンク分だけ確保して、すべて同じチャンク情報としています。
これをやめて、すべてのチャンクごとにチャンク情報を保持させるようにします。

見た目は同じでも、中身は別

f:id:simplestar_tech:20190621233319p:plain
見た目が同じでも中身が別

参考に今のコード

    void EnqueueCreateEntity(int x, int y, int z, int margeRadius)
    {
        #region チャンク情報の定義
        var chunkData = new int[ChunkManager.ChunkSizeX * ChunkManager.ChunkSizeZ * ChunkManager.ChunkSizeY];
        var nativeChunkData = new NativeArray<int>(chunkData, Allocator.Persistent);
        CreateWorld(nativeChunkData);
        #endregion

        #region ポインターのポインターにチャンクをセット
        int chunkKeyX, chunkKeyY, chunkKeyZ;
        ChunkInt3ToChunkKey(new Vector3Int(x, y, z), out chunkKeyX, out chunkKeyY, out chunkKeyZ);
        var byteMax = (byte.MaxValue + 1);
        int chunkIndex = chunkKeyX * byteMax * byteMax + chunkKeyZ * byteMax + chunkKeyY;
        this.ppChunkData[chunkIndex] = (int*)nativeChunkData.GetUnsafePtr(); // 本来なら Amazon S3 からダウンロード完了後にこれしてから Enqueue とか？
        this.nativeChunkDataArray[chunkIndex] = nativeChunkData;
        #endregion

        #region キーとなる位置情報を Enqueue
        var chunkPosition = new Vector3Int(x, y, z);
        var createChunkInfo = new CreateChunkInfo { chunkPosition = chunkPosition, mergeRadius = margeRadius };
        this.createEntityQueue.Enqueue(createChunkInfo);
        #endregion
    }

    static void CreateWorld(NativeArray<int> nativeChunkData)
    {
        var pChunkData = (int*)nativeChunkData.GetUnsafePtr();
        for (var x = 0; x < ChunkManager.ChunkSizeX; x++)
        {
            for (var z = 0; z < ChunkManager.ChunkSizeZ; z++)
            {
                for (var y = 0; y < ChunkManager.ChunkSizeY; y++)
                {
                    var dataIndex = (x * ChunkManager.ChunkSizeZ * ChunkManager.ChunkSizeY + z * ChunkManager.ChunkSizeY + y);
                    var pData = (byte*)(pChunkData + dataIndex);
                    pData[0] = 1;
                    pData[1] = (byte)Random.Range((int)CubeRotationType.Top000, (int)CubeRotationType.Max);
                    pData[2] = 1;
                    pData[3] = 1;
                }
            }
        }
    }

上記コードの CreateWorld を snoise で作ります。

と、その前に遊ばせている CPU を見つけたので、並列性を高めておきました。

f:id:simplestar_tech:20190622002329p:plain
最低でも論理コア数のオブジェクトを作成するようにして並列計算

f:id:simplestar_tech:20190622111748p:plain
psrnoise 処理 x 1

f:id:simplestar_tech:20190622132048p:plain
pnoise 試験画像

f:id:simplestar_tech:20190622133541p:plain
期待するなだらかな地形

f:id:simplestar_tech:20190622134038j:plain
なだらかな地形

現在の地形生成の実装は次の通り
pnoise の p は periodic （ループする）だそうです。

    static void LoadChunkData(Vector3Int chunkKeyXYZ, Vector3Int chunkPosition, int* pChunkData)
    {
        float amplitude = 64.0f; // 振幅倍率
        float period = 1; // 周期
        float chunkCount = byte.MaxValue + 1;

        for (int x = 0; x < ChunkManager.ChunkSizeX; x++)
        {
            for (int z = 0; z < ChunkManager.ChunkSizeZ; z++)
            {
                float height = 0;
                for (int frequency = 8; frequency < 10; frequency++)
                {
                    var power = Mathf.Pow(2f, frequency);
                    var bAmp = Mathf.Max(amplitude / power, 2);
                    height += bAmp * noise.pnoise(new float2(
                        (chunkKeyXYZ.x * ChunkManager.ChunkSizeX + x) / (float)(ChunkManager.ChunkSizeX * chunkCount),
                        (chunkKeyXYZ.z * ChunkManager.ChunkSizeZ + z) / (float)(ChunkManager.ChunkSizeZ * chunkCount)
                        ) * (period * power), new float2(period * power, period * power));
                }
                for (int y = 0; y < ChunkManager.ChunkSizeY; y++)
                {
                    float cubeHeight = chunkPosition.y * ChunkManager.ChunkSizeY + y;
                    byte sideType = (cubeHeight < height) ? (byte)1 : (byte)0;

                    var dataIndex = (x * ChunkManager.ChunkSizeZ * ChunkManager.ChunkSizeY + z * ChunkManager.ChunkSizeY + y);
                    var pData = (byte*)(pChunkData + dataIndex);
                    pData[0] = 1;
                    pData[1] = (byte)Random.Range((int)CubeRotationType.Top000, (int)CubeRotationType.Max);
                    pData[2] = sideType;
                    pData[3] = sideType;
                }
            }
        }
    }

# 地形データの永続化

移動を実装する前に、今の地形をファイルにセーブして
次回起動時に、同じキーのチャンク情報が保存されているなら、計算で作らずにファイル読み込みから地形を生成するようにします。

先にポインターでファイルデータをやり取りするクラスを作りました。
参考にした記事はこちら
qiita.com

ちょっとだけ使いたい方向に修正した、ほぼ同じコードがこちら

using System.IO;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.IO.LowLevel.Unsafe;

internal unsafe class UnsafeFileUtility
{
    /// <summary>
    /// 呼び出し元は fileData.Buffer に対し ReleaseReadData で開放する責任あり
    /// </summary>
    public static void ReadData(string filePath, out ReadCommand fileData)
    {
        var fileInfo = new System.IO.FileInfo(filePath);
        long fileSize = fileInfo.Length;

        var readCommand = new NativeArray<ReadCommand>(1, Allocator.Persistent);
        readCommand[0] = new ReadCommand
        {
            Offset = 0,
            Size = fileSize,
            Buffer = UnsafeUtility.Malloc(fileSize, UnsafeUtility.AlignOf<byte>(), Allocator.Persistent),
        };

        var readHandle = AsyncReadManager.Read(filePath, (ReadCommand*)readCommand.GetUnsafePtr(), 1);
        readHandle.JobHandle.Complete();
        fileData = readCommand[0];
        
        readHandle.Dispose();
        readCommand.Dispose();
    }

    /// <summary>
    /// データの書き込み
    /// </summary>
    public static void WriteData(string filePath, ReadCommand fileData)
    {
        byte* pFiledata = (byte*)fileData.Buffer;
        using (FileStream fs = new FileStream(filePath, FileMode.Create, FileAccess.Write))
        {
            for (int filePosition = 0; filePosition < fileData.Size; filePosition++)
            {
                fs.WriteByte(pFiledata[filePosition]);
            }
        }
    }

    /// <summary>
    /// データの開放
    /// </summary>
    /// <param name="fileData"></param>
    public static void ReleaseReadData(ref ReadCommand fileData)
    {
        if (0 < fileData.Size && null != fileData.Buffer)
        {
            UnsafeUtility.Free(fileData.Buffer, Allocator.Persistent);
            fileData.Buffer = null;
            fileData.Size = 0;
        }
    }
}

これを利用して先程のなだらかな地形生成アルゴリズムとつなげます。
ファイルがあったら読むだけというコードと共に

    /// <summary>
    /// チャンクデータの読み込み（out int* は呼び出し元で開放責任あり）
    /// </summary>
    static void LoadChunkData(Vector3Int chunkKeyXYZ, Vector3Int chunkPosition, out int* pChunkData)
    {
        var fileName = $"{chunkKeyXYZ.x.ToString("000")}-{chunkKeyXYZ.y.ToString("000")}-{chunkKeyXYZ.z.ToString("000")}.bytes";
        var filePath = Path.Combine(Application.persistentDataPath, fileName);
        if (File.Exists(filePath))
        {
            UnsafeFileUtility.ReadData(filePath, out var fileData);
            pChunkData = (int*)fileData.Buffer;
        }
        else
        {
            var fileSize = sizeof(int) * ChunkManager.ChunkSizeX* ChunkManager.ChunkSizeY * ChunkManager.ChunkSizeZ;
            pChunkData = (int*)(UnsafeUtility.Malloc(fileSize, sizeof(int), Allocator.Persistent));

            float amplitude = 64.0f; // 振幅倍率
            float period = 1; // 周期
            float chunkCount = byte.MaxValue + 1;

            for (int x = 0; x < ChunkManager.ChunkSizeX; x++)
            {
                for (int z = 0; z < ChunkManager.ChunkSizeZ; z++)
                {
                    float height = 0;
                    for (int frequency = 8; frequency < 10; frequency++)
                    {
                        var power = Mathf.Pow(2f, frequency);
                        var ampSize = Mathf.Max(amplitude / power, 2);
                        var repSize = period * power;
                        height += ampSize * noise.pnoise(new float2(
                            (chunkKeyXYZ.x * ChunkManager.ChunkSizeX + x) / (float)(ChunkManager.ChunkSizeX * chunkCount),
                            (chunkKeyXYZ.z * ChunkManager.ChunkSizeZ + z) / (float)(ChunkManager.ChunkSizeZ * chunkCount)
                            ) * repSize, new float2(repSize, repSize));
                    }
                    for (int y = 0; y < ChunkManager.ChunkSizeY; y++)
                    {
                        float cubeHeight = chunkPosition.y * ChunkManager.ChunkSizeY + y;
                        byte sideType = (cubeHeight < height) ? (byte)1 : (byte)0;

                        var dataIndex = (x * ChunkManager.ChunkSizeZ * ChunkManager.ChunkSizeY + z * ChunkManager.ChunkSizeY + y);
                        var pData = (byte*)(pChunkData + dataIndex);
                        pData[0] = 1;
                        pData[1] = (byte)Random.Range((int)CubeRotationType.Top000, (int)CubeRotationType.Max);
                        pData[2] = sideType;
                        pData[3] = sideType;
                    }
                }
            }
            UnsafeFileUtility.WriteData(filePath, new Unity.IO.LowLevel.Unsafe.ReadCommand { Buffer = pChunkData, Size = fileSize });
        }
    }

問題なく動きました。

f:id:simplestar_tech:20190622165740p:plain
なだらかな地形を永続化

CubeWalkGameなだらかな地形生成と永続化ができました。
次のプレイヤーの移動については、長くなったので記事を分けます。

# プレイヤーチャンクの特定

# プレイヤーチャンク移動タイミングの定義

# 既存のチャンクメッシュを利用する再結合処理

続きはこちら
simplestar-tech.hatenablog.com