[GAME001] 弾などの高速な管理方法（リスト構造）

弾などの高速な管理方法（リスト構造）

Home → Programming Tips → Game Tips → [GAME001]

　ダウンロード　：　弾管理プログラムサンプル(2005/03/20)　

ゲームを作る場合、弾を発射するために構造体配列の空きエリアを探すことになります。
あまり深く考えないでプログラムを作ると構造体配列から空きを探すようなプログラムになります。

これは検索という処理が入るため、頻繁に使用／未使用状態が切り替わるゲームの場合、
実行速度の明らかな低下に繋がります。
どのような処理をしようが毎回検索をするのが問題なのです。

そこで探さなくても良いようにリスト構造で管理することにします。
構造体定義をリスト構造向けに変更します。

// 弾管理構造体
struct TBullet {
    TBullet*    pNext;      // 双方向リストポインタ
    TBullet*    pBack;
    CPoint      pos;        // 座標
    EStatus     status;     // 状態
};

グローバル変数で弾の最大数分、構造体配列を静的宣言します。
未使用リストポインタと使用中リストポインタの先頭管理ポインタ変数も宣言します。

const DWORD c_dwMaxBullet = 10000;  // 弾の最大数
TBullet g_bullet[c_dwMaxBullet];    // 弾の配列
TBullet* g_pBulletEmpty = NULL;     // 未使用リストポインタ
TBullet* g_pBulletUse   = NULL;     // 使用中リストポインタ

初期化では、使っていない要素は先頭から連続して繋がっていることにします。

// 初期化する
void InitBullet()
{
    // リストをつなぐ
    for (DWORD dwID = 0; dwID < c_dwMaxBullet; dwID++){
        g_bullet[dwID].pNext = &g_bullet[dwID + 1];
        g_bullet[dwID].pBack = &g_bullet[dwID - 1];
    }

    // リストの終端設定
    g_bullet[dwID - 1].pNext = g_bullet[0].pBack = NULL;

    g_pBulletEmpty = g_bullet;              // 空きリストは配列の先頭から
    g_pBulletUse   = NULL;                  // 最初は何も使っていない
}

弾を発射するときは空きリストからポインタを取得します。
取得したポインタは使われたものとして、未使用リストから外し、使用中リストに連結します。

// 弾発射登録用ポインタを取得する
TBullet* GetEmptyBullet()
{
    if (!g_pBulletEmpty) return NULL;       // 空きがなければ終了する
    TBullet* pUse  = g_pBulletEmpty;        // 空きポインタを取得する
    g_pBulletEmpty = pUse->pNext;           // 空きポインタは次の場所を先頭とする
    pUse->pNext    = g_pBulletUse;          // 次に現在の使用中ポインタを入れる
    pUse->pBack    = NULL;                  // 新しい先頭ポインタとする
    g_pBulletUse   = pUse;                  // 新しい使用中ポインタに更新する
    return pUse;                            // 使用するポインタを返却する
}

この方法なら弾の出現数に関わらず常に一定の速度で空きポインタを取り出すことができます。
弾が画面外に消えたなど、不要になったら未使用ポインタに戻します。

// 弾を未使用にする
void ClearBullet(TBullet* pBullet)
{
    // 自分を使用中リストから外す
    if (pBullet->pBack)                     // 後方ポインタがあるなら
        pBullet->pBack = pBullet->pNext;    // 繋ぎ替える
    else                                    // 無い（つまり先頭なら）
        g_pBulletUse = pBullet->pNext;      // 先頭を次のポインタに変更する

    // 未使用ポインタリストに戻す
    pBullet->pNext = g_pBulletEmpty;        // 自分の次を空きポインタの先頭とする
    pBullet->pBack = NULL;                  // 自分が先頭になるため前はない
    if (g_pBulletEmpty)                     // 今までの空きポインタがあるのなら
        g_pBulletEmpty->pBack = pBullet;    // そのポインタの前を自分とする
    g_pBulletEmpty = pBullet;               // 自分が新しい空きポインタの先頭とする
}

このリスト管理手法は弾の移動処理に関しても良い結果をもたらします。
使用中リストを追いかけて処理すればよいので、ループは必要最小限となります。
結果、プログラム全体の実行速度が向上します。

// 弾の処理
void MoveBullet()
{
    TBullet* pNext;
    for (TBullet* pBullet = g_pBulletUse; pBullet; pBullet = pNext){
        pNext = pBullet->pNext;             // 先に次のポインタを取得しておく

        // 弾の処理を行う
        // 弾の消去タイミングなら ClearBullet(pBullet); とする
    }
}

注意点としては、弾は処理の最中に使用中から未使用に切り替わるということです。
そのため、ループの開始直後に次の使用中ポインタを保存しておきます。

なお、STL コンテナ等、動的確保をすれば良いと思うかもしれませんが、
new と delete のオーバーヘッドは異常なほど重いです。
そのため、使わない方がよいです。