ゲーム開発プロジェクトⅠ -2Dゲーム制作-

Appearance

特別授業 オブジェクトを沢山出す ​

前回: 第13回 C++実践 独自ゲームの制作 4 / ブラッシュアップ

今日のテーマ ​

大量のオブジェクトをどう扱うか ​

  • 大量のオブジェクトを更新し、描画し、削除する場合 ただ配列で管理するだけではあまり効率が良くありません
  • 非アクティブなオブジェクト相手にも都度 isActive で生存確認したり 空きオブジェクトを探してisActive の確認を行うのは無駄かもしれません
  • 今回の特別授業では 配列の使い方を変えて空きの要素を探さない形にすることで 大量のオブジェクトを扱う場合の効率化を考えます

今日の目的 ​

実装の工夫からデータ構造を学ぶ ​

  • isActive を使った管理の復習
  • オブジェクトを大量に出したとき何が問題なのかを考える
  • 単なる配列を、大量のオブジェクトを効率よく扱う構造に置き換え データ構造と最適化の基本的な考え方に触れます

今日の授業内容 ​

オブジェクト管理の考え方を学ぶ ​

  • isActive 方式でのチェック方式の復習
  • オブジェクトが大量化したときの問題とは
  • isActive の虫食いを解消する方法
  • 末尾と入れ替えて削除する方法

これまでの管理 ​

isActive で 使用中かどうかを調べる ​

まずは基本形から ​

これまでのオブジェクト管理 ​

使用中かどうかのフラグを持たせる ​

  • isActive == true なら使用中 isActive == false なら使っていない
  • この構造体を配列で扱えば 複数のオブジェクトを管理できます
  • 弾、敵、エフェクトで便利に使える 基本的な考え方のひとつです
cpp
struct Particle
{
    // 位置
    float x;
    float y;

    // 移動量
    float vx;
    float vy;

    // 残り寿命
    int life;

    // 使用中かどうか
    bool isActive;
};

オブジェクトの生成 ​

isActive をチェックして 空いている場所を探す ​

  • オブジェクトの配列を for で走査して、 空き場所を見つけたら再利用します
cpp
for (int i = 0; i < particleMax; i++)
{
    // isActive == false の場所を探す
    if (particles[i].isActive)
        continue;

    // 見つけた場所に新しいオブジェクトを作る
    particles[i].x = (float)GetRand(640);
    particles[i].y = (float)GetRand(480);
    particles[i].vx = (float)(GetRand(5) - 2);
    particles[i].vy = (float)(GetRand(5) - 2);
    particles[i].life = 120 + GetRand(120);

    // ここから使用中にする
    particles[i].isActive = true;
    break;
}

オブジェクトの更新 ​

使用中かどうかを毎回調べる ​

  • 配列全体を走査して、 使用中のオブジェクトだけを更新します
  • 寿命の確認をして、尽きたオブジェクトは isActive = false で無効化します
  • まだ寿命が残っている、 有効なオブジェクトだけを更新します
cpp
for (int i = 0; i < particleMax; i++)
{
    // 使っていない場所は処理しない
    if (particles[i].isActive == false)
        continue;

    // 寿命が尽きたら無効にする
    particles[i].life--;
    if (particles[i].life <= 0)
    {
        particles[i].isActive = false;
        continue;
    }

    // 有効なものだけ更新
    particles[i].x += particles[i].vx;
    particles[i].y += particles[i].vy;
}

オブジェクトの描画 ​

描画時にも使用中かをチェックする ​

  • 無効なものは描画しません ここでも isActive を調べています
  • 更新でも描画でも、配列全体にアクセス するしかありません
cpp
// 描画処理
for (int i = 0; i < particleMax; i++)
{
    // 使用中のものだけ描画する
    if (particles[i].isActive)
    {
        DrawCircle(
            (int)particles[i].x,
            (int)particles[i].y,
            3,
            GetColor(255, 220, 80),
            TRUE);
    }
}

何が問題か ​

オブジェクト数が増えれば確認回数も増える ​

  • 実際に使用しているオブジェクトの数が少なくても、 配列全体を調べなければなりません
  • オブジェクト生成時にも、空きを探すために配列の 全体を調べなければなりません
  • 1,000個のオブジェクトを出す場合、毎フレーム1000回の確認が必要です 10,000個のオブジェクトを出す場合なら、毎フレーム10,000回です
  • オブジェクトの総数が少ない間は問題になりづらいですが 総数が増えるにつれて確認量が無視できなくなります

オブジェクトの虫食い問題 ​

生成順に消えるとは限らない ​

ABCDEF
虫食い例■□■□■□
左詰め例■■■□□□
  • ゲーム中のオブジェクトは、 寿命、当たり判定、画面外に出るなどの理由で 無効化される場合があります
  • 無効化される順番は生成順とは限りません この場合、配列の中に無効なオブジェクトが 虫食い状に点在することになります
  • これをどうにか先頭方向に詰めることが できれば、無効なオブジェクトをチェックする 必要がなくなります

オブジェクトを詰めて配置するには ​

配列の前半だけを使用中にする ​

  • パーティクルを配列で管理するとします ここでは現在使用中のオブジェクトの数を particleCount で覚えておきます
  • 0 から particleCount - 1 までが使用中 particleCount 以降は空きという形にします
  • 配列の前から particleCount 個だけが有効です 個々のオブジェクトに isActive を持たせる 必要はありません
cpp
struct Particle
{
    // 位置
    float x;
    float y;

    // 移動量
    float vx;
    float vy;

    // 残り寿命
    int life;
};

const int particleMax = 10000;
Particle particles[particleMax];

// 使用中のパーティクル数
int particleCount = 0;

オブジェクトを生成する ​

末尾に追加するだけで対応 ​

  • 現在使用中のオブジェクトの数は particleCount で覚えています
  • つまり particles[particleCount-1] までが 使用中です
  • よって、新しいオブジェクトは particles[particleCount] に 追加すればよいことになります
cpp
void SpawnParticle()
{
    // 上限に達していたら生成しない
    if (particleCount >= particleMax)
        return;

    // 末尾に追加
    Particle& p = particles[particleCount];
    p.x = (float)GetRand(640);
    p.y = (float)GetRand(480);
    p.vx = (float)(GetRand(5) - 2);
    p.vy = (float)(GetRand(5) - 2);
    p.life = 120 + GetRand(120);

    // 使用中の数を1増やす
    particleCount++;
}

オブジェクトを更新する ​

使用中のオブジェクトの数だけループ ​

  • オブジェクト配列の前半だけが使用中です
  • よって、更新は particleCount まで 回せばよいことになります
  • もはや isActive を調べる必要はありません
cpp
for (int i = 0; i < particleCount; i++)
{
    // 使用中の範囲だけ更新する
    particles[i].x += particles[i].vx;
    particles[i].y += particles[i].vy;
    particles[i].life--;
}

ここで困ること ​

途中のオブジェクトが消えたらどうするか ​

  • 更新のループの中で、寿命が尽きたオブジェクトを消すとします
  • 左詰めでオブジェクトを扱うことができれば、 新規の追加も更新も簡単になります
  • ですが通常、オブジェクトが消える順番は生成順とは限りません 途中のオブジェクトが消えると、配列の中に虫食い状の空きができてしまいます
  • これをどうにかして詰めることができれば、空きの要素を探す必要がなくなります

末尾と入れ替えて削除する ​

順番を気にしないなら高速に消せる ​

  • オブジェクトを削除する際は、 配列の末尾のオブジェクトを削除位置に コピーする形で、要素数を1減らす方法が あります
  • これで配列の虫食い問題は解消されます
  • ただし副作用としてオブジェクトの順番が 変わってしまいます
cpp
// 使用中の数を1減らす
particleCount--;

// 減らした後の particleCount が末尾のインデックス
particles[index] = particles[particleCount];

ループ内での利用の注意 ​

入れ替えた要素をスキップしない ​

  • オブジェクトを削除した際は 削除位置に末尾のオブジェクトが移ってきます
  • ループ内で削除したときは、i++ せずに 同じ i をもう一度確認しなければ 入れ替えたばかりの末尾のオブジェクトの 更新処理がスキップされてしまいます
cpp
void UpdateParticles()
{
    int i = 0;

    while (i < particleCount)
    {
        particles[i].life--;

        // 寿命が尽きた
        if (particles[i].life <= 0)
        {
            // 削除はする、インデックスは進めない
            RemoveParticle(i);
            continue;
        }

        particles[i].x += particles[i].vx;
        particles[i].y += particles[i].vy;
        i++;
    }
}

描画のループも簡単に ​

使用中の数だけ描画する ​

  • 描画は particleCount まで ループを回すだけでよくなります
  • もはや isActive の判定は必要ありません 随分とすっきりしました
cpp
void DrawParticles()
{
    for (int i = 0; i < particleCount; i++)
    {
        // 使用中の範囲だけ描画する
        DrawCircle(
            (int)particles[i].x,
            (int)particles[i].y,
            3,
            GetColor(255, 220, 80),
            TRUE);
    }
}

アクティブなオブジェクト数の表示 ​

数値での確認も大事 ​

  • パーティクルがいくつ出ているかを 表示してみましょう
  • パーティクル数が上限に張り付いていないか 消滅処理が動いているかなども確認してみま しょう
cpp
// 現在のパーティクル数と最大数を表示
DrawFormatString(
    20, 20,
    GetColor(255, 255, 255),
    L"particles: %d / %d",
    particleCount,
    particleMax);

比較計測の準備 ​

ウインドウ名・FPS・VSync の設定 ​

  • SetMainWindowText で実行中の実装を ウインドウ名で見分けられるようにします
  • DrawFormatString でFPSも表示し、 パーティクル数と一緒に確認します
  • SetWaitVSyncFlag(FALSE) でVSyncを切ると 画面の更新速度で律速されなくなり、 処理速度を比較しやすくなります
cpp
// 初期化前にウインドウ名を設定
SetMainWindowText(L"ManyParticles - Fast");

if (DxLib_Init() == -1)
    return -1;

// 初期化後、ループ前にVSyncを切る
SetWaitVSyncFlag(FALSE);

// ここから下は毎フレームの描画処理内に書く

// 1フレームの時間からFPSの目安を出す
static int prevTime = GetNowCount();
int nowTime = GetNowCount();
int frameTime = nowTime - prevTime;
if (frameTime < 1)
    frameTime = 1;
float fps = 1000.0f / frameTime;
prevTime = nowTime;

DrawFormatString(20, 20, GetColor(255, 255, 255),
    L"particles: %d / %d", particleCount, particleMax);

DrawFormatString(20, 40, GetColor(255, 255, 255),
    L"fps: %.1f", fps);

今回の工夫で得られたメリット ​

オブジェクトの管理が効率化された ​

  • 生成時に、空きオブジェクトを探す必要がなくなりました
  • 更新と描画で、無効なオブジェクトを確認する必要がなくなりました
  • 配列の前半に使用中のオブジェクトがまとまるため、 処理対象の範囲が分かりやすくなりました
  • コンピューターのハードウエアに関係するやや複雑な話ですが、 使用中のデータが連続して並ぶことで、CPUのキャッシュ効率がよくなり 処理が高速化される可能性もあります
  • わずかに配列の使い方を変えただけで様々な処理を効率化できました

計算量の改善 ​

得られる結果が同じでも、過程には効率の良し悪しがある ​

  • 同じ結果を得られる処理でも プログラムの書き方やデータの持ち方で効率が変わる場合があります
  • 使用中のオブジェクトを調べるために配列の全部を走査する手法は わかりやすくはありますが、配列が大きいほど確認回数も増えてしまいます
  • 今回の工夫で、空きオブジェクト探しや有効無効のチェックを減らして 必要な分だけ処理することで、より効率のよいプログラムに改善できました
  • プログラミングは経済的な行いです ただ動作するだけでなく、より効率的に動作させる方法も考えてみましょう

データ構造とアルゴリズム ​

データの持ち方で処理も変わる ​

  • データ構造とは、データを目的にあわせて効率的に処理するための形式です
  • アルゴリズムとは、そのデータをどのように処理するかという手順です
  • 今回は同じ配列でも、isActive で有効無効を管理する形から 使用中のものだけを前に詰めて管理する形へ変えました
  • それに合わせて、生成、更新、削除の手順も変わりました
  • データの持ち方が変わると、処理の書き方や効率も変わります 扱う問題に合わせて、適切なデータ構造とアルゴリズムを選びましょう

注意点 ​

効率はよくなったが、これが本当に正解？ ​

  • 今回の例では、空きオブジェクトを探すのをやめて、 使用中のオブジェクトだけを前に詰める方法をとりました
  • 結果として、末尾のオブジェクトが削除されたオブジェクトの位置に 移動することになるためオブジェクトの順番が変わってしまいます
  • 背景のパーティクルや敵の弾などの単純な表示では問題になりづらいですが 処理や描画の順序が重要なものには注意が必要です また、構造体のサイズが大きい場合にはコピーが負担になるかもしれません
  • 全てにおいて正解というアルゴリズムはありません 状況に応じて適切な方法を選びましょう

isActive で管理する素朴な実装例 (1/3) ​

cpp
#include "DxLib.h"

struct Particle
{
    // 位置
    float x;
    float y;

    // 移動量
    float vx;
    float vy;

    // 残り寿命
    int life;

    // 使用中かどうか
    bool isActive;
};

const int particleMax = 10000;
Particle particles[particleMax] = {};
cpp
void SpawnParticle()
{
    // 配列全体から空きを探す
    for (int i = 0; i < particleMax; i++)
    {
        if (particles[i].isActive)
            continue;

        // 空いている場所に新しい値を入れる
        particles[i].x = (float)GetRand(640);
        particles[i].y = (float)GetRand(480);
        particles[i].vx = (float)(GetRand(5) - 2);
        particles[i].vy = (float)(GetRand(5) - 2);
        particles[i].life = 120 + GetRand(120);
        particles[i].isActive = true;

        // 1個作ったら終了
        break;
    }
}

isActive で管理する素朴な実装例 (2/3) ​

cpp
void UpdateParticles()
{
    // isActive を確認しながら配列全体を調べる
    for (int i = 0; i < particleMax; i++)
    {
        if (particles[i].isActive == false)
            continue;

        // 寿命が尽きたら未使用に戻す
        particles[i].life--;
        if (particles[i].life <= 0)
        {
            particles[i].isActive = false;
            continue;
        }

        particles[i].x += particles[i].vx;
        particles[i].y += particles[i].vy;
    }
}
cpp
int DrawParticles()
{
    int activeCount = 0;

    // 描画時にも配列全体を調べる
    for (int i = 0; i < particleMax; i++)
    {
        if (particles[i].isActive == false)
            continue;

        // 表示中の数を数えながら描画する
        activeCount++;
        DrawCircle(
            (int)particles[i].x,
            (int)particles[i].y,
            3,
            GetColor(255, 220, 80),
            TRUE);
    }

    return activeCount;
}

isActive で管理する素朴な実装例 (3/3) ​

cpp
int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
    SetMainWindowText(L"ManyParticles - Basic");
    ChangeWindowMode(TRUE);
    SetGraphMode(640, 480, 32);

    if (DxLib_Init() == -1)
        return -1;

    SetWaitVSyncFlag(FALSE);
    SetDrawScreen(DX_SCREEN_BACK);

    while (ProcessMessage() == 0 &&
           CheckHitKey(KEY_INPUT_ESCAPE) == 0)
    {
        for (int spawn = 0; spawn < 20; spawn++)
            SpawnParticle();

        // すべてのパーティクルを更新する
        UpdateParticles();
cpp
        ClearDrawScreen();

        // 描画した数を受け取る
        int activeCount = DrawParticles();

        // 現在のパーティクル数と最大数を表示
        DrawFormatString(20, 20, GetColor(255, 255, 255),
            L"particles: %d / %d",
            activeCount, particleMax);

        // FPS を表示
        int fps = GetFPS();
        DrawFormatString(20, 50, GetColor(255, 255, 255),
            L"FPS: %d", fps);

        ScreenFlip();
    }

    DxLib_End();
    return 0;
}

隙間を詰めて効率化した実装例 (1/3) ​

cpp
#include "DxLib.h"

struct Particle
{
    // 位置
    float x;
    float y;

    // 移動量
    float vx;
    float vy;

    // 残り寿命
    int life;
};

const int particleMax = 10000;
Particle particles[particleMax] = {};

// 使用中のパーティクル数
int particleCount = 0;
cpp
void RemoveParticle(int index)
{
    // 末尾の要素を削除位置に移して数を減らす
    particleCount--;
    particles[index] = particles[particleCount];
}

void SpawnParticle()
{
    // 上限に達していたら生成しない
    if (particleCount >= particleMax)
        return;

    // 使用中の範囲の末尾に追加する
    Particle& p = particles[particleCount];
    p.x = (float)GetRand(640);
    p.y = (float)GetRand(480);
    p.vx = (float)(GetRand(5) - 2);
    p.vy = (float)(GetRand(5) - 2);
    p.life = 120 + GetRand(120);

    // 使用中の数を1増やす
    particleCount++;
}

隙間を詰めて効率化した実装例 (2/3) ​

cpp
void UpdateParticles()
{
    int i = 0;

    // 使用中の範囲だけ調べる
    while (i < particleCount)
    {
        particles[i].life--;
        if (particles[i].life <= 0)
        {
            // 削除後は同じ i をもう一度確認する
            RemoveParticle(i);
            continue;
        }

        // 生きているものだけ移動する
        particles[i].x += particles[i].vx;
        particles[i].y += particles[i].vy;
        i++;
    }
}
cpp
void DrawParticles()
{
    // 使用中の範囲だけ描画する
    for (int i = 0; i < particleCount; i++)
    {
        DrawCircle(
            (int)particles[i].x,
            (int)particles[i].y,
            3,
            GetColor(255, 220, 80),
            TRUE);
    }
}

隙間を詰めて効率化した実装例 (3/3) ​

cpp
int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
    SetMainWindowText(L"ManyParticles - Fast");
    ChangeWindowMode(TRUE);
    SetGraphMode(640, 480, 32);

    if (DxLib_Init() == -1)
        return -1;

    SetWaitVSyncFlag(FALSE);
    SetDrawScreen(DX_SCREEN_BACK);

    while (ProcessMessage() == 0 &&
           CheckHitKey(KEY_INPUT_ESCAPE) == 0)
    {
        for (int spawn = 0; spawn < 20; spawn++)
            SpawnParticle();

        // 使用中の範囲だけ更新する
        UpdateParticles();
cpp
        ClearDrawScreen();

        // 使用中の範囲だけ描画する
        DrawParticles();

        // 現在のパーティクル数と最大数を表示
        DrawFormatString(20, 20, GetColor(255, 255, 255),
            L"particles: %d / %d",
            particleCount, particleMax);

        // FPS を表示
        int fps = GetFPS();
        DrawFormatString(20, 50, GetColor(255, 255, 255),
            L"FPS: %d", fps);

        ScreenFlip();
    }

    DxLib_End();
    return 0;
}

今日のまとめ ​

今日のポイント ​

  • オブジェクトの有効無効を isActive で都度確認する方式でも 少数のオブジェクトが相手なら特に問題になりません
  • ですが都度配列全体を走査する必要があるため、 扱うオブジェクトが大量化すると無駄なチェックが増えてしまいます
  • 今回は使用中のものだけを前に詰める形にすることで、 空きの要素を探す必要がなくなり、 大量のオブジェクトを効率的に扱えるようになりました
  • データ構造とアルゴリズムを適切に選ぶことで プログラムの動作を効率化できることがわかりました

おつかれさまでした！ ​

ゲーム内の弾や エフェクトに 応用してみましょう ​