大量のデータを扱うときのアルゴリズムについて

[ティエ]

はじめまして。ゲームを製作している端くれですが、詰まったので質問させていただきます。
初心者は最初はシューティングゲームが一番ということで、シューティングゲームを作りました。
弾幕の数は多くて1000個程度なので、以下のような構造体を作り、配列を生成しました。

struct Enemy {
	int flag; // 使用中フラグ 最初に0を入れておく
	double x,y, bx, by;
};
struct Enemy enemy_list[1000];

そして、以下のような関数で配列を走査させ、空き領域を取得していました。

int getSpace () {
	for (int i=0;i<1000;++i)
		if (!enemy_list.flag) // 未使用なら
			return i; // その配列の添字を返す
	return -1; // ループを抜けた＝空きがないことを-1を返して知らせる
}

次に、エフェクトを派手にしようと粒子を飛ばせようとしました。
敵を倒したときに破片のように沢山飛び散らせようと思っています。
上の弾幕のように実装しようと思いましたが、ちょっと困っています。
沢山飛ばすので弾幕より多くのスペースを必要とし、
その上に生成と削除を頻繁に行うので毎回forループで走査させると速度が低下します。
連結リストを使うことも考えましたが、配列と比べて全体的に少し遅めです。
このような大量のデータを扱うとき、どのようなアルゴリズムで実装するのがよいのでしょうか？
様々なエフェクトは普通に配列を使って実装しているのでしょうか？
長くなりましたが、よろしければ先人の経験談を聞かせてほしいです。

[御津凪]

処理順序を気にしないのであれば、以下の処理方法が高速かと思われます。

// 敵構造体
typedef struct {
    double x,y, bx, by;
} Enemy;
#define ENEMY_MAX 1000

// 管理（無名構造体でまとめている）
struct {
    Enemy  list[ENEMY_MAX]; // 配列
    Enemy *next;            // 追加時の配列ポインタ位置
    Enemy *last;            // 配列の終端（list + ENEMY_MAX の箇所）
} gEnemyList;

// 初期化処理
void InitEnemyList( void ){
    memset(gEnemyList.list,0,sizeof(gEnemyList.list));
    gEnemyList.next = list;
    gEnemyList.last = list+ENEMY_MAX;
}

// 新規データ用意
Enemy* NewEnemy( void ){
    if(gEnemyList.last == gEnemyList.next) return NULL;
    return gEnemyList.next++;
}

// データ削除
void DelEnemy( Enemy* enemy ){
    if(enemy){
        // 削除対象部分を最後のデータで上書きすることで行なう
        *enemy = *(--gEnemyList.next);
    }
}

// 移動処理
void MoveEnemy( void ){
    Enemy* enemy = gEnemyList.list; // 走査ポインタ
    int delfrag;                    // 削除フラグ
    while(enemy < gEnemyList.next){
        delfrag = 0;
        /* 移動処理本文 */
        if(delfrag != 0){
            DelEnemy(enemy); // 削除フラグが立ったら削除
            continue;
        }
        ++enemy;
    }
}

処理順序が削除のたびに変わるので、表示処理に優先をつけないと、
前後の入れ代わりが起きて違和感が出るので注意です。

[Justy]

＞様々なエフェクトは普通に配列を使って実装しているのでしょうか？

　こういうのにあまり普通というのもあれなのですが、結論から言えば
よほどチープな環境での動作を想定しているとか、サンプルプログラムである、とかの
特殊な条件でもない限り、リストを使うのが推奨されると思います。

　ただリストを使う場合メモリの確保に関して通常の malloc/newを使うかどうかは
状況によります。

　このご時世エフェクトは派手になる一方で、激しいオブジェクトの生成・破棄が
行われるようであれば、そのコストも馬鹿にならないので（エフェクト専用の）高速な
アロケータを用意することがあります。
（ちょうど、御津凪さんのコードもそんな感じになっていますね）



＞その上に生成と削除を頻繁に行うので毎回forループで走査させると速度が低下します

　配列を使うのであれば、せめて現在使用中の最大要素数を覚えておいて、
配列内の走査はそこまでにしてはどうでしょうか？

[ティエ]

返事遅れて申し訳ありません。
＞処理順序が削除のたびに変わるので、表示処理に優先をつけないと、
＞前後の入れ代わりが起きて違和感が出るので注意です。
この方法はいいですね。参考にさせていただきます。
余談ですが、C言語のこういう低級さもいいですね。
それぞれに適したアルゴリズムを考えてリストなどを自作するのは楽しいです。

＞特殊な条件でもない限り、リストを使うのが推奨されると思います。
リストの可変さはやっぱり便利ですね。

答えていただきありがとうございます。
解決の糸口が見つかりました。あとは自分で試行錯誤してやってみたいと思います。
また、詰まった時にはよろしくお願いします。