シューティング : リストと配列

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
メンマ

シューティング : リストと配列

#1

投稿記事 by メンマ » 4年前

シューティングゲーム製作中の初心者です。
現在シューティングでの弾幕及び敵を配列で管理しているのですが、これをリストに変更しようと考えています。
しかし、例えば一度に1000発の弾を生成するような処理が起こった場合、1000発分の動的メモリ確保をすることになると思います。動的メモリ確保には時間がかかるものなのかどうかがわからず、処理時間に遅延がでないかを懸念しています。
配列で管理している現在は弾は最初に生成しておき、登録時にフラグ変数を変更するだけの処理になっています。

変数を変更する処理と比較して動的メモリ確保の処理はやはり遅いのでしょうか?トンチンカンなことを聞いているのかもしれませんがその場合は勉強できるサイトなどを教えていただけると幸いです。ご意見、ご回答よろしくおねがいしますm(_ _)m

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 8年前
住所: 東海地方
連絡を取る:

Re: シューティング : リストと配列

#2

投稿記事 by softya(ソフト屋) » 4年前

> 変数を変更する処理と比較して動的メモリ確保の処理はやはり遅いのでしょうか?ト

早くはないですが致命的かはプログラムの組み方次第です。
ただポインタ利用などプログラムの複雑度は上がるので、メンテナンス性は下がり、バグの発生度が上がり、バグ追求の難易度も上がります。
それを超えるメリットや、勉強のためという理由がない限りはデメリットのほうが多いと思います。
動的管理にしなければいけない理由を教えて下さい。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

メンマ

Re: シューティング : リストと配列

#3

投稿記事 by メンマ » 4年前

動的確保のリストにしようと考えた理由としましては

1.配列の場合、毎フレーム配列の最大数分フラグが立っているかどうかを調べなければいけないため、リストにして必要分だけの処理にしたほうが無駄がないのではないか。

2.設定した最大数分以上弾を生成しようとした場合、配列だと生成できないがリストで動的確保をするとその数に縛られず自由に生成できる。また、実際には弾の数は最大数以下の状態が多く、動的確保にしたほうがメモリの節約にもなるのではないか。

以上のように考えたからです。
しかし、質問文のように動的メモリ確保にはどれくらい処理時間がかかるかわからず、弾を同時にたくさん生成した時一気に重くなるのであればやめたほうがいいかなあ・・・と思い質問させていただきました。
ある程度スペックの低いPCでも動かせるようにできるだけ配慮したいと考えています。多少なら複雑度、バグの難易度が上がることは気にしないのですが、一時的にでも処理速度に影響がでるのであればやめておこうと思います。

考えていることがあっているかどうかもわからないので、誤りがあればご指摘くださると幸いです。

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 8年前
住所: 東海地方
連絡を取る:

Re: シューティング : リストと配列

#4

投稿記事 by softya(ソフト屋) » 4年前

1.少なくともフラグ判定よりはnew/mallocのコストは大きいです。メモリが細かく分断されるほどコストアップします。
ただ、メンマさんがリストと呼んでいるもののアルゴリズムによっても変わります。1つづつ確保せずに100個づつ確保するなどテクニックもあります。

【補足】
ちょっと語弊があるので補足です。
new/mallocのコストは大きいですが、new/mallocされていない間はフラグのコストもそれなりにあります。
瞬間コストと継続コストで、どちらが問題に成るか考えてみる必要があります。

2.メモリをどれだけ使っているか計算してみたほうが良いと思います。昔のパソコン(PC98)なら問題でも今のパソコンでは問題にならないことが多いです。

【追記】
あれこれ悩んでいるよりも計測用の弾幕プログラムを作って何パターンか実装を試してみた方が良い経験になります。
計測方法やら、様々なアルゴリズムに触れる良い機会だと思いますけどね。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

アバター
みけCAT
記事: 6198
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: シューティング : リストと配列

#5

投稿記事 by みけCAT » 4年前

両方のいいところを取って、毎回動的にオブジェクト(弾)のデータ領域を確保することはないが、
リストで無駄なくアクセスできるようにする、というのはどうでしょうか?

例えば、このような実装が考えられます。

コード:

#include <cstdio>
#include <iterator>

template<typename T>
class data_supplier {
	private:
		// データの最大数
		size_t max_num;
		T *data; // データ本体
		// データを格納する領域の情報
		struct data_link_t {
			T *data;
			data_link_t *prev; // 前のデータ領域
			data_link_t *next; // 次のデータ領域
		} *data_link;
		// 先頭と末尾のデータの位置
		data_link_t *head;
		data_link_t *tail;
		// データの空き位置を管理するキュー(リングバッファ)
		data_link_t **empty_queue;
		size_t empty_start, empty_end, empty_count;
		// コピー・代入を許可しない
		data_supplier(const data_supplier<T>& d) {}
		data_supplier<T>& operator=(const data_supplier<T>& d) const {
			return *this;
		}
		// キューの操作
		bool is_queue_empty() const {return empty_count == 0;}
		bool is_queue_full() const {return empty_count == max_num;}
		data_link_t *dequeue() {
			if (is_queue_empty()) return 0;
			data_link_t *ret = empty_queue[empty_start];
			empty_start = (empty_start + 1) % max_num;
			empty_count--;
			return ret;
		}
		void enqueue(data_link_t *v) {
			if (is_queue_full()) return;
			empty_queue[empty_end] = v;
			empty_end = (empty_end + 1) % max_num;
			empty_count++;
		}
	public:
		// イテレータの定義
		class iterator : public std::iterator<std::input_iterator_tag, T*> {
			friend class data_supplier;
			private:
				// 参照先のデータの情報
				data_supplier::data_link_t *data;
				data_supplier::data_link_t data_end;
				// 勝手にイテレータを作られないようにする
				iterator(){}
				iterator(data_link_t* d, data_link_t* prev = NULL) {
					data = d;
					data_end.prev = prev;
				}
			public:
				// コピーコンストラクタ
				iterator(const data_supplier& d) {
					data = d.data;
					data_end = d.data_end;
				}
				// 進める
				iterator& operator++() {
					if (data->next == NULL) {
						data_end.data = NULL;
						data_end.prev = data;
						data_end.next = NULL;
						data = &data_end;
					} else {
						data = data->next;
					}
					return *this;
				}
				iterator operator++(int) {
					iterator bak = *this;
					++(*this);
					return bak;
				}
				// データを取得する
				T* operator*() const {
					return data->data;
				}
				// 比較する
				bool operator==(const iterator& it) const {
					data_link_t* d = data;
					data_link_t* itd = it.data;
					if (d == &data_end) d = NULL;
					if (itd == &it.data_end) itd = NULL;
					return d == itd;
				}
				bool operator!=(const iterator& it) const {
					return !(*this == it);
				}
		};

		// 先頭要素のイテレータを返す
		iterator begin() const {
			return iterator(head);
		}
		// 末尾のイテレータを返す
		iterator end() const {
			return iterator(NULL, tail);
		}

		// 初期化
		data_supplier(size_t max = 1) {
			max_num = max;
			// 領域の確保
			data = new T[max];
			data_link = new data_link_t[max];
			head = NULL;
			tail = NULL;
			for (size_t i = 0; i < max_num; i++) {
				data_link[i].data = &data[i];
			}
			// キューの初期化
			empty_queue = new data_link_t*[max];
			empty_start = 0;
			empty_end = 0;
			empty_count = max_num;
			for (size_t i = 0; i < max_num; i++) {
				empty_queue[i] = &data_link[i];
			}
		}
		// 開放
		~data_supplier() {
			delete[] data;
			delete[] data_link;
			delete[] empty_queue;
		}
		// 全消し
		void clear() {
			head = NULL;
			tail = NULL;
			empty_start = 0;
			empty_end = 0;
			empty_count = max_num;
			for (size_t i = 0; i < max_num; i++) {
				empty_queue[i] = &data_link[i];
			}
		}
		// 新しいデータの追加
		T* create_new_data() {
			if (is_queue_empty()) {
				return NULL;
			} else {
				// 次のデータ領域を取得する
				data_link_t *next_data = dequeue();
				// リストの先頭に追加する
				if (head == NULL) {
					head = next_data;
					head->prev = NULL;
					head->next = NULL;
					tail = head;
				} else {
					data_link_t *old_head = head;
					head = next_data;
					head->prev = NULL;
					head->next = old_head;
					old_head->prev = head;
				}
				return next_data->data;
			}
		}
		// データの削除
		iterator delete_data(const iterator& it) {
			if (it == end()) return it;
			data_link_t *prev = it.data->prev;
			data_link_t *next = it.data->next;
			if (prev != NULL) prev->next = next; else head = next;
			if (next != NULL) next->prev = prev;
			enqueue(it.data);
			return iterator(next);
		}
};

int main(void) {
	data_supplier<int> ds(10);
	for(;;) {
		int query = 0;
		puts("1: 追加、2: 削除、    3: インクリメント");
		puts("4: 閲覧、5: リセット、6: 終了");
		fputs(">", stdout);
		if(scanf("%d", &query) != 1) return 1;
		switch (query) {
			case 1: {
				fputs("数値>", stdout);
				if (scanf("%d", &query) != 1) return 1;
				int *next = ds.create_new_data();
				if (next == NULL) {
					puts("容量不足です");
				} else {
					*next = query;
					puts("セットしました");
				}
				break;
			}
			case 2: {
				fputs("数値>", stdout);
				if (scanf("%d", &query) != 1) return 1;
				for (data_supplier<int>::iterator it = ds.begin();
				it != ds.end();) {
					printf("%d : ", **it);
					if (**it == query) {
						puts("YES");
						it = ds.delete_data(it);
					} else {
						puts("NO");
						++it;
					}
				}
				break;
			}
			case 3: {
				for (data_supplier<int>::iterator it = ds.begin();
				it != ds.end(); ++it) (**it)++;
				puts("インクリメントしました");
				break;
			}
			case 4: {
				for (data_supplier<int>::iterator it = ds.begin();
				it != ds.end(); ++it) printf("%d\n", **it);
				break;
			}
			case 5:
				ds.clear();
				puts("リセットしました");
				break;
			case 6:
				return 0;
			default:
				puts("コマンドが不正です");
				break;
		}
	}
	return 0;
}
このサンプルでは、弾データの代わりにintのデータを生成/削除しています。
使いかた

コード:

・変数宣言
data_supplier<管理する型名> 変数名(最大要素数);
・新しいデータの生成
create_new_data() // 新しいデータのポインタが返る
・先頭イテレータの取得
begin()
・末尾イテレータの取得
end()
・データの削除
delete_data(削除するデータを指すイテレータ) // 次の要素を指すイテレータが返る
・データの全消し(初期化)
clear()
この実装だと、データを生成/削除した時にそのデータのコンストラクタやデストラクタは呼ばれないので、
管理するデータはコンストラクタやデストラクタでの処理が必要ないもの(C言語的な「構造体」など)にしてください。
clearすることで前のデータの影響を受けない、std::vectorなどでも大丈夫なはずです。
データの初期化は、コンストラクタではなく生成したデータのポインタが指す先にアクセスすることで行ってください。
オフトピック
ついでにサンプル化しました。
動的確保しないリスト
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

メンマ

Re: シューティング : リストと配列

#6

投稿記事 by メンマ » 4年前

>softya(ソフト屋) さん
1.やはり処理としては変数変更よりもメモリ確保のほうがだいぶコストがかかるんですね。なるほど、アルゴリズムの組み方次第ではありなのかもしれませんね。瞬間コストと継続コストのどちらをとるかの天秤がけなどは現状では決めかねるので、最終的な形が明確になってから改めて考えてみます。
2.メモリについてはおまけ程度で考えていましたが、やはり現状のPCでの環境を考えると無視しても差し支えなさそうですね。処理速度のほうを重視しようと思います。

そのとおりですね(汗)。リアルの時間が限られるので、質問で解決すればと甘えてしまいました。勉強にもなるし自分で計測方法などを調べたり考えたりしてみます。


>みけCATさん
確かに動的に確保はせず、かつランダムアクセスでないリストの長所を活かすのは処理時間で考えるといいかもしれませんね。
おお・・・ソースコードまで・・・ありがとうございます!このソースコードを使用、または参考にさせていただきます。


仕様変更については一長一短がありそうなので、計測したり最終的な形が明確になってから改めて決めてみます。お二方、回答ありがとうございました。

閉鎖

“C言語何でも質問掲示板” へ戻る