チャンク式オープンワールドの設計 ― 決定論的な自動生成とパフォーマンス最適化

自作アクションゲームで、プレイヤーがどこまで歩いても草・木・岩が続く広大なフィールドを実装しました。本記事では、その土台になっている チャンク方式 のうち、特に「自動生成」と「パフォーマンス」の設計判断について述べます。

1. はじめに

地形やオブジェクトの配置データを最初から全部メモリに持つのは、フィールドが広くなるほど現実的でなくなります。そこで XZ 平面をグリッド状の チャンク に区切り、プレイヤー周囲の一定範囲だけを実体化し、離れたら捨てる方式を採りました。

この方式を成立させる上で要になったのは、次の 2 つのテーマです。

決定論的なプロシージャル生成 ― 配置をメモリに保存しないのに、同じ場所へ戻ると必ず同じ並びになる
パフォーマンス最適化 ― 生成時のカクつき（ヒッチ）を消し、草を 1 ドローで描き、当たり判定を総当たりにしない

チャンク管理そのもの（座標変換やアクティブ範囲の管理）は前提として軽く触れるだけにとどめ、上記 2 テーマを中心に解説します。

2. 前提：チャンクと「有効チャンク」

まず用語を揃えます。XZ 平面を一辺 chunkSize（本実装では 150 ワールド単位）の正方形グリッドに区切り、各マスを チャンク と呼びます。世界座標からチャンク座標への変換は floor 除算だけで済みます。

ChunkCoord WorldToChunk(float wx, float wz) {
    return ChunkCoord{
        static_cast<int>(std::floor(wx / chunkSize)),
        static_cast<int>(std::floor(wz / chunkSize))
    };
}

プレイヤーがいるチャンクを中心に、片側 radius（本実装では 2）の範囲を 有効チャンク（active set） とします。
毎フレームの冒頭でプレイヤー位置から中心チャンクを求め、中心チャンクが変わったときだけ active set を作り直します。境界をまたいだ瞬間しか働かないので、毎フレーム 25 マスを再計算するムダがありません。
この「有効チャンク」が本記事の全ての土台です。生成も、破棄も、当たり判定も、すべて active set を唯一の基準にして動きます。

3. 決定論的なプロシージャル生成

3.1 なぜ「決定論」なのか

最初は「チャンクに入ったら乱数で木を生やす」だけを考えていました。しかしこれだと、一度離れて戻ってきたときに並びが変わってしまう。フィールドの景観が訪れるたびに別物になるのは、探索ゲームとして致命的です。

かといって、生成した全チャンクの配置を保存し続ければメモリは際限なく増えます。

そこで採ったのが 決定論的生成 です。配置を「チャンク座標を入力とする純粋関数」として定義すれば、

同じチャンクは何度訪れても必ず同じ並びになる
配置を保存しなくていい（座標から毎回再計算できる）
後述する「破壊状態の永続化」が、座標ではなく番号だけで成立する

という三拍子が揃います。これが本設計の背骨です。

3.2 チャンク座標からシードを作る

純粋関数にする鍵は乱数のシードです。チャンク座標そのものをシードに畳み込みます。

草（インスタンシングで大量に生やす方）は、座標とソルト値から seed_seq を作って mt19937 を初期化します。

// 同じチャンク座標なら、毎回まったく同じ乱数列が得られる
std::seed_seq seedSeq{
    static_cast<uint32_t>(chunk.x),
    static_cast<uint32_t>(chunk.z),
    GRASS_SEED_SALT          // 草用の固定ソルト
};
std::mt19937 rng(seedSeq);

木・岩（採集オブジェクト）の方は、座標を 64bit に撹拌（splitmix64 系）してシードにしています。隣り合うチャンク座標でシードが似通うと配置に規則性が出てしまうため、ビットを十分にかき混ぜるのがポイントです。

uint64_t MakeSeed(ChunkCoord c) {
    uint64_t h = kSeedSalt;
    h ^= static_cast<uint64_t>(static_cast<uint32_t>(c.x)) * 0x9E3779B97F4A7C15ull;
    h  = (h ^ (h >> 29)) * 0xBF58476D1CE4E5B9ull;
    h ^= static_cast<uint64_t>(static_cast<uint32_t>(c.z)) * 0xC2B2AE3D27D4EB4Full;
    h  = (h ^ (h >> 32)) * 0x94D049BB133111EBull;
    return h ^ (h >> 31);
}

3.3 棄却法（rejection sampling）で重ねずに配置する

木や岩が地面で重なって生えるとめり込んで見えるので、配置位置は 棄却法 で決めます。「ランダムに座標を引いて、既に置いた円と重なっていたら引き直す」を最大回数まで繰り返すだけです。

for (int attempt = 0; attempt < kMaxPlaceAttempts; ++attempt) {
    const float x = rng.uniformReal(loX, hiX);
    const float z = rng.uniformReal(loZ, hiZ);

    bool ok = true;
    for (const auto& pr : placed) {          // このチャンクに既に置いた円
        const float dx = x - pr.first.x;
        const float dz = z - pr.first.y;
        const float minDist = s.radius + pr.second + kSpacing;
        if (dx*dx + dz*dz < minDist*minDist) { ok = false; break; }
    }
    if (ok) { s.position = Vector3(x, 0, z); s.valid = true; break; }
}

1 チャンクあたりの個数は 2〜6 個、岩になる確率は 35%、といった生成パラメータは一箇所の定数に集約して調整しやすくしています。

3.4 チャンク独立性：境界にマージンを取る

棄却法は「同じチャンク内の重なり」しか見ていません。では隣のチャンクの木とは重ならないのか？ という問題が出ます。

ここで効くのが 境界マージン です。各オブジェクトを、チャンク境界から「自分の半径 + 間隔」だけ内側にしか置かないようにします。

const float margin = s.radius + kSpacing;
const float loX = minX + margin, hiX = maxX - margin;
const float loZ = minZ + margin, hiZ = maxZ - margin;

これにより、各チャンクは完全に独立して生成できます。隣のチャンクの状態を一切参照しないので、「どの順番で生成しても」「プレイヤーがどこから近づいても」結果が同じ ― 決定論が崩れません。

3.5 つまずき：RNG 列を「無効スロットでも」進める

これは地味ですが、決定論を壊しかけた罠でした。

棄却法は失敗することがあります（kMaxPlaceAttempts 回引いても置けなかった＝無効スロット）。最初の実装では、配置に成功したオブジェクトだけ回転・スケールの乱数を引いていました。すると、棄却の成否によって以降の乱数列がズレ、後続オブジェクトの位置まで変わってしまいます。

対策はシンプルで、有効・無効に関わらず必ず同じ回数だけ乱数を引くことです。

// 位置が valid でなくても、回転・スケールは必ず draw して RNG 列を安定させる
s.rotationY = rng.uniformReal(0.0, 2.0 * PI);
const float scaleMul = rng.uniformReal(kScaleMin, kScaleMax);
s.scale = baseScale * scaleMul;

「決定論＝同じシードから同じ列」を守るには、乱数を引く回数まで決定論的でなければならない、というのがここでの教訓です。

3.6 破壊状態を「差分」で永続化する

決定論生成の最大の利点がここで効きます。

採集オブジェクトはプレイヤーが破壊（伐採・採掘）できます。一度切った木が、チャンクを離れて戻るたびに復活したら興ざめです。とはいえ全オブジェクトの状態を保存するのは前述の通りやりたくない。

そこで、「壊したスロット番号」だけを記録します。レイアウトは決定論なので「このチャンクの 3 番目の木」という番号だけで個体を一意に指せるからです。

// チャンクキー → そのチャンクで破壊済みのスロット番号の集合
std::unordered_map<uint64_t, std::unordered_set<int>> m_destroyed;

破壊された瞬間に番号を記録し、

if (owned.object->IsDestroyed())
    m_destroyed[chunkKey].insert(owned.localIndex);

チャンクを再生成するときに、記録済みのスロットは実体化をスキップします。

for (int i = 0; i < slots.size(); ++i) {
    if (!slots[i].valid) continue;
    if (destroyed && destroyed->count(i)) continue;  // 採集済みは復活させない
    // ... 実体化キューへ
}

保存するのは「座標」ではなく「壊した番号の集合」だけ。決定論レイアウトという土台があるからこそ、永続化が極限まで軽くなります。

4. パフォーマンス最適化

ここからは「広いフィールドを 60fps で破綻なく動かす」ための実装です。

4.1 フレーム分散生成（time-slicing）でヒッチを消す

チャンク境界をまたいだ瞬間、新しく有効になったチャンク（最大で 1 列ぶん）のオブジェクトをその 1 フレームで一気に実体化すると、生成コストが集中してカクつきます。コライダー登録などの個体生成コストが積み重なるためです。

そこで実体化を 保留ジョブのキュー に積み、毎フレーム決まった個数だけ消化する方式にしました。

void Update(float dt) {
    SyncActiveChunks();  // active set との差分: 消えたチャンクを破棄 / 新規をキューへ
    ProcessPending();    // 保留ジョブをこのフレーム分だけ実体化
    // ...
}

void ProcessPending() {
    int spawned = 0;
    while (spawned < kMaxSpawnsPerFrame && !m_pending.empty()) {
        const PendingJob job = m_pending.front();
        m_pending.pop_front();
        // ... 消化前に「すでに離れた / すでに壊された」ジョブは捨てる
        obj->Initialize();
        obj->RegisterColliders();
        ++spawned;
    }
}

1 フレームあたりの上限（kMaxSpawnsPerFrame）を小さくするほど 1 フレームの負荷は軽くなりますが、全チャンクが出揃うまでの遅延は伸びます。このトレードオフを 1 定数で調整できるようにしています。

加えて、重い FBX モデルのロードは 共有キャッシュ で 1 回だけに抑え、さらにゲーム開始時にプリロードしておくことで、移動初動のロードヒッチも前倒しで潰しています。

void Initialize() {
    StaticModelCache::Get(Tree::MODEL);   // 最初のチャンク生成時のロードを開始時に前倒し
    StaticModelCache::Get(Rock::MODEL);
}

4.2 GPU インスタンシングで草 1 万本超を 1 ドローで描く

草は 1 チャンクあたり 500 本、有効チャンク 25 個ぶんで 最大 12,500 本 になります。これを 1 本ずつ描いたら描画コールだけで破綻します。そこで GPU インスタンシング で 1 ドローにまとめます。

頂点バッファ（草のメッシュ形状）は全インスタンスで共有し、位置・スケール・回転といったインスタンスごとの差分だけを別バッファに持たせて、頂点入力の 2 スロット目にバインドします。

struct alignas(16) InstanceData {  // per-instance 48 byte
    Vector3 position;  float scale;       // 配置
    float   rotationY; float bendX, bendZ, pad;  // 向き＋キャラに踏まれた曲げ
    Vector3 localWind; float pad2;        // 個別風
};

// slot 0: メッシュ頂点（全インスタンス共有, immutable）
// slot 1: per-instance データ（毎フレーム書き換え, dynamic）
ID3D11Buffer* buffers[2] = { m_vertexBuffer.Get(), m_instanceBuffer.Get() };
UINT strides[2] = { sizeof(VERTEX_3D), sizeof(InstanceData) };
UINT offsets[2] = { 0, 0 };
ctx->IASetVertexBuffers(0, 2, buffers, strides, offsets);

// これ 1 回で全インスタンスを描画
ctx->DrawIndexedInstanced(m_indexCount, m_instances.size(), 0, 0, 0);

インスタンスバッファは D3D11_USAGE_DYNAMIC で確保し、毎フレーム WRITE_DISCARD で丸ごと差し替えます（風による揺れやキャラに踏まれた曲げを反映するため）。

D3D11_MAPPED_SUBRESOURCE msr{};
ctx->Map(m_instanceBuffer.Get(), 0, D3D11_MAP_WRITE_DISCARD, 0, &msr);
memcpy(msr.pData, m_instances.data(), m_instances.size() * sizeof(InstanceData));
ctx->Unmap(m_instanceBuffer.Get(), 0);

ポイントは 2 つです。

再生成は中心チャンクが変わったときだけ。毎フレーム配置を作り直すのではなく、active set が入れ替わった瞬間にだけ全インスタンスを 3.x の決定論ロジックで再生成します。
草専用シェーダーを使い、キャラ用のボーン変形・トゥーン・アウトラインといった重いパスを丸ごとスキップしています。草に法線アウトラインは要りません。

4.3 チャンクを「当たり判定のブロードフェーズ」に再利用する

ここが個人的に一番気に入っている設計です。描画で使っているチャンクグリッドを、そのまま当たり判定の空間インデックス（ブロードフェーズ）として使い回します。

当たり判定を全コライダーの総当たりでやると O(N²) で破綻します。そこで各コライダーを「ワールド AABB が重なる全チャンク」に登録し、チャンクキー → コライダー配列 の逆引きを持ちます。

// チャンクキー → そのチャンクに重なるコライダー群
std::unordered_map<uint64_t, std::vector<Collider2D*>> m_staticChunks;   // 木・岩・設置物
std::unordered_map<uint64_t, std::vector<Collider2D*>> m_dynamicChunks;  // キャラ

静的（木・岩）と動的（キャラ）を分離しているのが要点です。

静的コライダーは生成・破棄のときに一度だけ索引へ登録/解除する
動的コライダーは毎フレーム索引を作り直す（RebuildDynamic）

判定するときは、調べたい形状が重なるチャンクだけを見ます。

bool OverlapAny(const Shape2D& shape, const Vector2& center, ...) const {
    const AABB2D box = shape.Bounds(center);
    bool found = false;
    ForEachOverlappingChunk(box, [&](ChunkCoord cc) {   // 重なるチャンクだけ
        const uint64_t key = PackKey(cc);
        // そのチャンクの静的・動的コライダーだけと判定する
        check(StaticInChunk(key));
        check(DynamicInChunk(key));
    });
    return found;
}

描画・生成・当たり判定が同じグリッド・同じハッシュキーを共有しているので、「描画されているのに当たらない」「当たるのに見えない」といった不整合が原理的に起きません。チャンクという 1 つの空間分割を、システム横断で使い回せたのが大きな利点でした。

5. まとめ

チャンク式の広大フィールドを成立させるにあたり、中心になった設計判断は次の通りでした。

決定論的生成：チャンク座標をシードにした純粋関数で配置を決め、「保存しないのに一貫する」を実現した。境界マージンによるチャンク独立性と、乱数を引く回数まで決定論的にすることが安定の鍵だった。
差分だけの永続化：決定論レイアウトを土台に、破壊状態を「スロット番号の集合」だけで記録した。座標を保存せずに済むため極めて軽量で、そのままディスクセーブへ拡張できる。
フレーム分散生成：実体化を保留ジョブで毎フレーム少しずつ消化し、境界通過時のヒッチを消した。
GPU インスタンシング：草 1 万本超を 1 ドローにまとめ、専用シェーダーで重いパスを省いた。
空間分割の再利用：描画用のチャンクグリッドを当たり判定のブロードフェーズに転用し、システム間の不整合を構造的に排除した。

技術スタック

C++20 / DirectX 11 / HLSL

参考

SplitMix64