💨

【C++】弾幕STGでの効率的なデータ管理

2026/01/01に公開

弾幕STGを作るとき、扱う弾が単に直線移動するだけでは面白くありません。加速度的な動きをさせたり、円を描くように動かしたり、ホーミングを入れてみたりするなど、弾1つでもいろいろな動きをさせる余地があります。今回はそういった多彩な仕様を持つ弾を効率的に(かつ拡張性を持って)管理する方法を紹介します。

前提: 弾の構造体

ここでは、次のIBulletを継承した構造体を扱うようにプログラムを行います。

struct IBullet
{
	virtual ~IBullet() = default;
	virtual bool update() = 0;
};

特に、update()は自身を削除する必要のある時にtrueを返します。

A. 種類ごとに弾の配列を用意する

もっとも単純なのは継承関係を何も意識せず、弾の種類毎に配列を用意することです。


struct BulletManager0
{
	std::vector<BulletA> bulletA;
	std::vector<BulletB> bulletB;
	std::vector<BulletC> bulletC;

	void update()
	{
		updateType(bulletA);
		updateType(bulletB);
		updateType(bulletC);
	}

	template <class BulletType>
	void updateType(std::vector<BulletType> &bullets)
	{
		for (int i = 0; i < bullets.size();)
		{
			bool del = bullets[i].update();
			if (del)
			{
				std::swap(bullets[i], bullets.back());
				bullets.pop_back();
			}
			else
			{
				i++;
			}
		}
	}

	template <class BulletType, class... Args>
	void add(Args&&... args)
	{
		if constexpr (typeid(BulletType) == typeid(BulletA))
		{
			bulletA.emplace_back(std::forward<Args>(args)...);
		}
		else if constexpr (typeid(BulletType) == typeid(BulletB))
		{
			bulletB.emplace_back(std::forward<Args>(args)...);
		}
		else if constexpr (typeid(BulletType) == typeid(BulletC))
		{
			bulletC.emplace_back(std::forward<Args>(args)...);
		}
	}
};

実装上の工夫として、constexpr if文によって型の評価をコンパイル時に行うことでコンパイルが通るようになります。

この場合は単純な分、後の二つと比較してもとても高速に動作してくれます。
しかし、弾の種類を追加するごとにManagerの実装の変更も要求されて、拡張性はあまり良くありません。実際にゲームを作るとなると沢山の種類の弾を作りたいですから、可読性的にもこのコードは避けるべきでしょう。

Tips: swap and pop イディオム

このプログラムでは弾の削除には「swap and pop」と呼ばれる書き方を用います。
これは削除対象を配列の末尾の要素と交換した後、配列の末尾を削除する、という方法で要素の削除を実現します。std::vectorは末尾の値の削除は定数時間で行うことができるので、そのまま値を削除するよりも時間計算量的に有利に削除処理を行うことができます。

B. ポインタを用いた多態性実装

プログラミングに慣れ、ポインタによる多態性(ポリモーフィズム)を学んだことのある人は、IBulletへのポインタを配列で管理して処理を行う方法が思い浮かぶと思います。

struct BulletManager1
{
	std::vector<std::unique_ptr<IBullet>> bullets;

	void update()
	{
		for (int i = 0; i < (int)bullets.size();)
		{
			bool del = bullets[i]->update();
			if (del)
			{
				swap(bullets[i], bullets.back());
				bullets.pop_back();
			}
			else
			{
				i++;
			}
		}
	}

	template <class BulletType, class... Args>
	requires std::derived_from<BulletType, IBullet>
	void add(Args&&... args)
	{
		bullets.push_back(std::make_unique<BulletType>(std::forward<Args>(args)...));
	}
};

かなりすっきりしたコードで書けました。emplace_backのような使用感のために可変引数テンプレートを用いていますが、特にこれと言って複雑な点もありません。

C++11以降にはstd::unique_ptrによるポインタ管理が可能なので、これを用いています。bulletsのポインタをどこかに置くわけでもないので、std::shared_ptrを使う必要はありません。案外、std::shared_ptrはstd::unique_ptrよりもコストが1.2倍くらい高いです。

問題点

この実装は単純でわかりやすい方法ですが、パフォーマンス的には良いとは言えません。
ポイントとなるのが、弾の保存を行うための配列です。

std::vector<std::unique_ptr<IBullet>> bullets;

この場合、bulletsに格納されるのは各弾の実体へのポインタとなります。つまり、弾の実体はヒープ上に点在することになります。メモリ上のデータの局所性はCPUのキャッシュ効率につながるので、まだこの実装にはパフォーマンス上の向上の余地があります。詳しくは次の章で説明します。

C. プールを用いた実装

メモリの連続性を発揮するには実装Aのように種類ごとに配列を用意するのが良いです。この実装の欠点は拡張性の低さでした。これに対応したのが実装Cです。こうした実装はECSと呼ばれるゲームシステムの設計手法に見られるそうです。

実装方針としては、1)まず型テンプレートを用いて種類ごとのプールを用意し、2)それらを基底クラスのポインタとして保持(型消去)、3)型ごとにIDを割り振ってそれらにアクセスします。

プールの作成

まずは弾のためのプールを定義して、種類ごとに用意したプールに弾を格納させます。後で型消去を行うため、IBulletPoolを継承する形で実装します。

struct IBulletPool
{
	virtual ~IBulletPool() = default;
	virtual void update() = 0;
};

template <typename BulletType>
struct BulletPool : IBulletPool
{
	std::vector<BulletType> bullets;
	void update() override
	{
		for (int i = 0; i < bullets.size();)
		{
			bool del = bullets[i].update();
			if (del)
			{
				std::swap(bullets[i], bullets.back());
				bullets.pop_back();
			}
			else
			{
				i++;
			}
		}
	}
};

もっとかっちりやるのなら、addメンバ関数を追加して弾の追加処理も書くと良いです。今回は単純さのために割愛します。

弾の管理

定義したプールはstd::unique_ptr<IBulletPool>として管理します。
必要に応じてこれらをキャストして使用します。static_castを使うことでコンパイル時にキャストの型安全性をチェックしてくれます。

struct BulletManager2
{
	std::vector<std::unique_ptr<IBulletPool>> pools;
	void update()
	{
		for (auto& pool : pools)
		{
			 pool->update();
		}
	}

	template <class BulletType, class... Args>
	void add(Args&&... args)
	{
		const int typeId = getTypeId<BulletType>();
		if ((int)pools.size() <= typeId)
		{
			pools.resize(typeId + 1);
		}
		if (!pools[typeId])
		{
			pools[typeId] = std::make_unique<BulletPool<BulletType>>();
		}
		auto pool = static_cast<BulletPool<BulletType>*>(pools[typeId].get());
		pool->bullets.emplace_back(std::forward<Args>(args)...);
	}
};

getTypeIdは後述する型名に対して一意な整数値(0始まり)を割り当てる関数です。これによってIBulletPoolをstd::vectorに格納することができます。特に、一度も追加されたことのない種類の弾が追加される場合には、std::unique_ptr<IBullet>をpoolsに新しく追加するだけで良いです。

メモリ配置の違い

この実装をメモリ配置に着目して実装Bと比較してみます。

実装BはBulletManager1のbulletsメンバ変数に弾の情報が格納されます。しかしこれはポインタなので、実体はヒープ上のどこか別のところにあります。前述のとおり、ヒープ上に弾の実体が散らばっているのです。イメージとしてはこう：

+-----+------------+------------+-----+--------------+-----+
| ... | bullets[0] | bullets[1] | ... | bullets[n-1] | ... |
+-----+------------+------------+-----+--------------+-----+
別のどこか
+-----+----------+-----+----------+-----+
| ... | BulletsA | ... | BulletsB | ... |
+-----+----------+-----+----------+-----+
また別のどこか
+-----+----------+-----+----------+-----+
| ... | BulletsC | ... | BulletsB | ... |
+-----+----------+-----+----------+-----+

配列アクセスなどをするとき、CPUは自動でその先のメモリも一緒に読み取り、CPUが速く読み書きできるキャッシュにそれらを記憶します。弾の更新処理では弾の実体をいじるので、CPUにはそれがキャッシュされているのが理想です。しかし実装Bでは弾の実体はbulletsそのものにはないので、bulletsの内容(=実体へのポインタ)をキャッシュしてもそこまで利点がないのです。

一方で実装Cでは弾の種類ごとにプールを用意し、その中のbulletsに弾の実体を格納します。つまり各種類に関して弾の実体はメモリ上に連続に配置されます。イメージとしてはこう：

+-----+----------+----------+-----+------------+-----+
| ... | pools[0] | pools[1] | ... | pools[n-1] | ... |
+-----+----------+----------+-----+------------+-----+
別のどこか (pools[0]の実体)
+-----+----------+----------+----------+-----+----------+-----+
| ... | BulletsA | BulletsA | BulletsA | ... | BulletsA | ... |
+-----+----------+----------+----------+-----+----------+-----+
また別のどこか (pools[1]の実体)
+-----+----------+----------+----------+-----+----------+-----+
| ... | BulletsB | BulletsB | BulletsB | ... | BulletsB | ... |
+-----+----------+----------+----------+-----+----------+-----+

実装Cにおける弾の更新では、各種類で設けたプールに対して更新処理を行わせます。そしてプールは各弾の実体を直接配列で持っているので、これをforループで順にみていくと、CPUでは先の弾の実体をキャッシュできます。これによって更新処理をより速く行えることが期待できます。

型名と整数値との紐づけ

getTypeIdは以下のような実装になっています。

inline int nextTypeId()
{
	static int id = 0;
	return id++;
}

template <class Ty_>
inline int getTypeId()
{
	static int id = nextTypeId();
	return id;
}

これでちゃんと機能するのには、C++のテンプレート型引数(ジェネリクス)の実現方法が関わってきます。C++はテンプレートを用いて定義された関数については、その関数に与えられるすべての型の組み合わせの定義を展開・コンパイルします。つまり、getTypeId<BulletA>とgetTypeId<BulletB>が呼び出されたとき、

inline int getTypeId_BulletA()
{
	static int id = nextTypeId();
	return id;
}

inline int getTypeId_BulletB()
{
	static int id = nextTypeId();
	return id;
}

のように展開されます(実際の厳密な実装とは異なりますが、イメージとして)。

そして、staticで宣言された変数は、その関数が呼ばれる初回でのみ初期化され、その後は初期化処理は行われません。これにより、getTypeId_Xxx()は常に同じ値を返します。一方、getTypeId_Xxx()の呼ぶnextTypeId()は共通なので、各getTypeId_Xxx()が初めて呼ばれるごとにnextTypeId()が呼ばれ、内部の静的変数idがインクリメントされます。以上の仕組みによって、getTypeId<Ty_>()は型ごとに一意な整数値を割り当てることができるのです。

実行速度比較

これまで紹介した3つの方法について、実行時のパフォーマンスをざっくり比較します。
シナリオとしては、10,000件のオブジェクトを作成し、そのうち1割を削除、新しく作成する処理を100回行い、作成・更新処理の実行時間を計測します。これを100回繰り返して、その平均値を取ります。

使用したプログラム

const int Iterations = 100;
const int NumBullets = 10000;
const int NumFrames = 100;
const double DeletionRate = 0.1;

const int maxLife = int(1 / DeletionRate);

template <class MgrType>
void PerfTest(String Name)
{
	Console << U"===== {} ====="_fmt(Name);
	Console << U"NumBullets   : {}"_fmt(NumBullets);
	Console << U"NumFrames    : {}"_fmt(NumFrames);
	Console << U"DeletionRate : {}"_fmt(DeletionRate);
	Console << U"Iterations   : {}"_fmt(Iterations);

	// 平均計測のため累積時間を保持
	long long totalCreateUs = 0;
	long long totalUpdateUs = 0;

	for (int iter = 0; iter < Iterations; ++iter)
	{
		MgrType manager;
		auto createStart = std::chrono::high_resolution_clock::now();

		const auto addBullet = [&](int i) {
			const int life = i % maxLife;
			switch (i % 3) {
			case 0:
				manager.add<BulletA>(life, Vec2{ i, i });
				break;
			case 1:
				manager.add<BulletB>(life, Vec2{ i, i }, Vec2{ i, i });
				break;
			case 2:
				manager.add<BulletC>(life);
				break;
			}
		};

		for (int i : step(NumBullets))
		{
			addBullet(i);
		}
		auto createEnd = std::chrono::high_resolution_clock::now();

		auto updateStart = std::chrono::high_resolution_clock::now();
		for (auto frame : step(NumFrames))
		{
			manager.update();
			for (auto i : step(int32(NumBullets * DeletionRate)))
			{
				addBullet(i);
			}
		}
		auto updateEnd = std::chrono::high_resolution_clock::now();

		totalCreateUs += std::chrono::duration_cast<std::chrono::microseconds>(createEnd - createStart).count();
		totalUpdateUs += std::chrono::duration_cast<std::chrono::microseconds>(updateEnd - updateStart).count();
	}

	const auto avgCreateUs = totalCreateUs / Iterations;
	const auto avgUpdateUs = totalUpdateUs / Iterations;

	Console << U"Avg Creation Time : {} μs"_fmt(avgCreateUs);
	Console << U"Avg Updates Time  : {} μs"_fmt(avgUpdateUs);
}

実行結果

実装	平均作成時間	平均更新時間計
A (ナイーブ)	86 μs	1915 μs
B (多態性)	247 μs	5547 μs
C (プール)	89 μs	1931 μs

作成・更新ともに、実装A、Cが最速で、次いでBの順になりました。特に、実装Cは実装Bの2-3倍速いことがわかりました。やはりメモリ上の連続性と、コンパイル時に更新時のループで取り扱う型が確定していることが大きいのでしょうか。また、実装AとCを比較すると速度にほとんど差がないことがわかります。

追記：
最初はstd::unique_ptrをstd::shared_ptrとして実行してみました。すると、BとCでともに実行時間が1.2-2倍ほどになってしまいました。参照カウンタなどを用いたstd::shared_ptrは便利ですが、可能ならstd::unique_ptrを用いるのがよさそうです。

おわりに

今回は弾幕STGでの弾の管理を高速に行う方法について考察してみました。どの実装もBulletManagerとして構造体として実装して、内部の実装は使用者からは理解しなくても良いようになっているので、どの方法を取っても複雑度は変わりません。しかし、その内部実装で最大3倍ほどの速度差になり、実行速度がクリティカルに響いてくるゲーム処理ではそこそこに大きい差なのではないでしょうか。

今回実装したコードはGitHub Gistで公開しています。実行には OpenSiv3D が必要です。

余談:
今回の話題は「Siv3DでECS実現してみたいなぁ」と思いながら勘で書いたECSが、案外ナイーブに書いたコードよりも遅く、設計上の利点を除くとあまり嬉しさないなぁと思っていると思いついたものです。ここで実装したECSミニフレームワークも gistで公開しているので、良ければ見てみてください。参考に、有名なC++のECSライブラリEnTTと比較しても遜色ない(1割以下の差)速度になっています。