リスト構造について

[えあ]

みなさんはじめまして。
私はシューティングゲームの製作を行っております。

敵や弾の管理は配列で行っているのですが、それらを出現させる際に、配列を最初から検索していては膨大な時間がかかることがわかりました。
もちろん、検索方向を交互に変更し検索時間を減らしたり、検索の必要がない場合は検索をしないような仕組みも組み込んだのですが、やはり数万回とループを行うと時間がかかってしまうようです。
私のパソコンでは動作速度に問題はないのですが、たくさんの人にも遊んでもらえるよう、少しでも時間を短くしたいと考えています。

調べてみると、リスト構造というもので構造体同士のアドレスを繋げておくと出現時や処理時のループの時間が短縮できることがわかりました。

○弾などの高速な管理方法（リスト構造）
http://orangeknowledge.jpn.org/tips/game001.html)

こちらのページを参考にプログラムを組んでみたのですが、画面外に出た弾を消去する際に出ていない弾も消去されてしまいます。
おそらく消去する際に、ループに使用するリストポインタ(g_pBulletUse)の位置が変更されてしまう為、それより後の(配列の)弾がスキップされているのだと思いますが、解決方法が見つからないため質問させて頂きました。

ソースを書き込もうとしたのですが、長すぎるということで添付させて頂きます。(サイトのサンプルと変数名が違います。すみません。)

解決の為のヒントを教えていただければ幸いです。
どうぞよろしくお願い致します。

[box]

データの持ち方によっては、リスト構造の方がかえって遅くなることがあります。

もし、配列中の検索キーが昇順または降順に並んでいるのであれば、
二分探索を用いると、今なさっている逐次探索よりも格段に速くなります。

どうしてもリスト構造を使いたいのであれば、
まず、シューティングゲームと切り離して、
書籍やサイトなどでリスト構造そのものを
じゅうぶんに理解してからシューティングゲームに応用する、
という手順を踏んでみてはいかがでしょうか。

[softya]

長いので簡単にしか見てませんが、例えば
if (p->pBack){ // 後方ポインタがあるなら
p->pBack = p->pNext; // 繋ぎ替える
}
なんかは、
if (p->pBack){ // 後方ポインタがあるなら
p->pBack->pNext = p->pNext; // 繋ぎ替える
}
じゃないかなと思ったり。
そもそもデバッガで変数の変化などステップトレースしましたか？
まず、デバッガで追いかけてみてください。
そうすれば分かると思います。
あとは、リスト処理だけテストするプログラムを作ってみるのも良い手段です。

それとboxさんが言うとおり単純にリスト構造を使うと遅くなると思います。今のリストは空き弾の管理の高速化だけが目的でしょうか？

[通りすがり]

>敵や弾の管理は配列で行っているのですが、それらを出現させる際に、配列を最初から検索していては膨大な時間がかかることがわかりました。
>もちろん、検索方向を交互に変更し検索時間を減らしたり、検索の必要がない場合は検索をしないような仕組みも組み込んだのですが、やはり数万回とループを行うと時間がかかってしまうようです。

本当にボトルネックはそこなの？
何故数万回もループする必要があるのかわからないけど、数万回のループがあったとして、
それは全体にどれ位足を引っ張っているの？
通常数万回のループ位では重くはならないでしょう。

[えあ]

>>box さん
>>softya さん
お返事ありがとうございます。
リスト構造は遅いのですか。

私の配列の方法では
生成時にはその配列のデータが使用されているかどうか、というものを検索していき
使用していない要素にデータを入れるという方法をとっていました。
また、弾の移動などの処理時には
for文で配列全てを回し、使用していない要素はcontinueするという方法をとっています。

この方法を使えば、使用している配列の要素だけを順番に処理することができるので
ループ回数が減ると思ったのですが、、、そうではないのですね。
私がしたいことはsoftyaさんの仰る通り
使用されていない弾の管理の高速化だけが目的ですので、管理以外の部分で高速化できる所がないか調べてみます。

[えあ]

>>通りすがり さん
ありがとうございます。

>>本当にボトルネックはそこなの？
特にその部分でゲームが遅くなるというわけではないのですが、
使用していないものも条件分岐を行うのは無駄かな、と思ったので他の方法を調べ
それについて質問させて頂きました。

正確な時間については計っていないのですが、弾の移動処理の部分が最もif文の量やループ回数が多かったので
時間がかかるものだと勝手に推測していました。

こんな無駄な方法をとっているのは自分だけだと思ったのでリスト構造を使用してみようと思った次第です。
もう少し調べてから導入できるかどうか検討してみようと思います。

[たいちう]

> 正確な時間については計っていないのですが、
> 弾の移動処理の部分が最もif文の量やループ回数が多かったので
> 時間がかかるものだと勝手に推測していました。

処理時間の計測が第一です。
経験を積んでいても推測はしばしば外れますから。

配列の大きさにもよりますが、シューティングゲームということならば、
せいぜい数千程度だと思います。弾の構造体の配列だとして、
移動処理や描画が必要かどうかのフラグをチェックするだけならば、
描画処理と比較すれば無視できるはず。

第一、弾の移動処理がボトルネックだったとしても、
それが必要な処理ならば、リスト構造にしても軽くなりませんよ。

[Dixq (管理人)]

私の経験上の話ですが、弾幕を普通にSTLのlistにしたり、線形リスト使ってすごい勢いでmalloc、freeを繰り返すと配列とは比べ物にならない位逆に遅くなります。
ある程度の領域を予め確保し、効率よくポインタを繋ぎ換えるなど工夫が必要かと思います。

一時期こだわってましたけど、色々試して結局私は配列で計算する方法に戻しました。
館で紹介しているコードとは少し違いますが、基本的に同じです。
配列でザックリ領域確保して、フラグの立っている弾を描画する方法です。

弾が千個あったとして、千回フラグチェックしたとしても、
10億回の比較が1秒位だとしたら、千回の比較は100万分の一秒ですよね。
これは仮の数値だし、実際はもっと色んな要素が絡んだり計算が絡んだりするかもしれないので、
これより時間はかかるかもしれませんが、こう考えると「本当にそこがボトルネック？」と思ってしまいます。

確かにプログラマーとしては「無駄は省く」をどこまでも求めるのは基本なので、効率化を図るのは大変良い事だと思いますが、
的確にボトルネックを見つける事がもっと重要なことです。
たいちうさんも仰るようにそのためにはまず時間を測定してみましょう。

[えあ]

>>たいちう さん
>>Dixq さん
ありがとうございます。

時間を計測したところ、全体の処理が最大でも12ms程度なので間に合うようです。
弾の移動や描画よりも弾の生成時の空いている要素を検索するのに1.2msも使用しているようです。
敵の発射パターンを設定しやすくする為、同一フレームの間に数十フレーム先の弾の情報まで
設定している為だと思います。

一度のたくさんの弾を設定させないことや、その検索のあたりの効率を良くさせることで
時間を短くしようと思います。

みなさんどうもありがとうございました。