Objectを大量に描画したいが…重い。なにかが悪い。

[やっくる]

ソフト屋さん、突き止めました！！！！！

アルゴリズムの二分探索をご存知ですか？

はい、知っています。真ん中で区切って探索し
的を絞って行く方法ですよね？
ただ、プログラムの前半後半とかよくわからないので
手間でもわかりやすい関数単位で調べるという方が
自分向きだと思いましたので時間食いましたが調べていました。

とりあえず、
TimeStart = GetNowCount(); // 現在時刻
〜ここに計測したい処理〜
TimeEnd = GetNowCount(); // 現在時刻
といった形で関数をはさんで、
TimeSpan = TimeEnd - TimeStart;
といった感じです。
(それぞれdouble型で宣言しております)

で、結果ですが、時間がかかっている処理をつきとめました。
それは、オブジェクト同士の衝突判定を行う処理(関数)でした。

ここから、重要な質問なのですが、
自分はHitCheckというクラスをシングルトンで生成しており
そのHitCheckクラスにて
オブジェクトlist内のオブジェクト同士の衝突判定をする
関数(名をhitcaseとします)を作っています。

ややこしいのですが、そのhitcase関数の中で扱っている
オブジェクトlistは、オブジェクトを管理させているObjectMgrクラスが持っています。
ObjectMgrクラスもシングルトンで作っているのですが
（そこではオブジェクト用のlistを作り、そこに作ったオブジェクトを入れたり、
中のオブジェクトを削除したり、オブジェクトの更新をさせたりしています）
そのhitcase関数をステージの更新関数内にて実行させているときに
オブジェクトが増えると遅延する様です。

しかし、ここで疑問があります。
オブジェクトlistのサイズがただ増加すれば
重くなるわけでありません。
処理時間計測で調べたのですが、
ObjectMgrクラスの更新関数や、描画関数でも
オブジェクトlist内の更新や描画処理をさせているので
イテレータを作ってまわしておりますが、
オブジェクトが増えたところで、
その処理速度はまったく変わりません。

目に見えて時間がかかるようになるのは
オブジェクトリストを扱っているhitcase関数だけなのです。
そしてここでも疑問があるのですが
そのhitcase関数内の衝突処理を空っぽに、つまりは↓

コード:

//HitCheckクラスの、オブジェクト同士の衝突判定をする関数
void HitCheck::hitcase(){

	list<sObject*>::iterator it, it2;//ふたつのイテレータ宣言

	for(it = ObjectMgr::getInstance()->objectlist.begin(); it !=ObjectMgr::getInstance()->objectlist.end(); ++it)
	{
			for(it2 = ObjectMgr::getInstance()->objectlist.begin(); it2 !=ObjectMgr::getInstance()->objectlist.end(); ++it2)
		{

　　　　　本来ここでオブジェクトを抽出して、
　　　　　ダラダラと衝突確認をしているわけですが、
　　　　　すべてを削除して、ここにはなにも無い、空っぽの状態にしています。

		}
	}
}

こういう状態にしても遅延が起きるのです。
つまり、これは
衝突処理の内容では無いということですよね？

そこでさらに、イテレータ宣言や、多重for文を削除して
本当に空っぽにすると↓

コード:

void HitCheck::hitcase(){
　なにも無し
}

遅延がまったく無くなるのです。。。

これは、どういうことでしょう？？？

オブジェクトlistに入ってる数が問題ならば
衝突判定処理だけで無く、オブジェクトlist更新処理なども
増加に比例し、時間がかかってくるはずです。
しかし衝突判定関数以外はすべて正常時間です。

また、衝突判定処理の内容が問題で
オブジェクトが増加とともに遅延が発生するなら
そのhitcase関数の中でイテレータ宣言と多重for文を残していようが
その中の衝突処理を削除すれば遅延は起きないはずです。
なのにオブジェクトが増えると遅延が起きます。

hitcase関数をコメントアウトするか、
hitcase関数内の全処理をコメントアウトすると
遅延はまったく発生しません。

つまり、犯人はこの部分です。
↓これはそんなに遅延を誘発するような処理なのでしょうか？？？

コード:

	for(it = ObjectMgr::getInstance()->objectlist.begin(); it !=ObjectMgr::getInstance()->objectlist.end(); ++it)
	{
			for(it2 = ObjectMgr::getInstance()->objectlist.begin(); it2 !=ObjectMgr::getInstance()->objectlist.end(); ++it2)
		{


                }
       }

[やっくる]

複数の種類の敵をどうやって互いに影響し合うことなく実装するか、
については簡単なサンプルコードを書いてみようと思います。
気長にお待ちください。ソースコードのほうも。

ありがとうございます。
その辺を熟練者の方ならどのようにされるのか
非常に気になりますし、学びたいです。
自分の中では自分の様な形しか無いはずだと思っていますので
楽しみです。待ってますのでぜひお願い致します。

ひとつのリストに放り込んで回すのはふつうだと思いますよ。

ありがとうございます。
誰も答えて下さらなかったので助かります。
自分のこの部分の方法は間違っていないのですね。

[softya（ソフト屋)]

２重ｆｏｒの内側で、大体何回ぐらいループしてますか？
list要素数次第では恐ろしい回数回りそうです。

[やっくる]

２重ｆｏｒの内側で、大体何回ぐらいループしてますか？
list要素数次第では恐ろしい回数回りそうです。

「２重ｆｏｒの内側で大体何回ぐらいループしているか」
すみません、これはどう調べればいいでしょうか？
ちなみにイテレーターの初期化はこのfor文の頭でしか行っておりません。

コード:

 for(it = ObjectMgr::getInstance()->objectlist.begin(); it !=ObjectMgr::getInstance()->objectlist.end(); ++it)
    {
            for(it2 = ObjectMgr::getInstance()->objectlist.begin(); it2 !=ObjectMgr::getInstance()->objectlist.end(); ++it2)
        {
　　　 LoopCount++;　　　←こんな感じで設置すればいいですか？

 
        }
    }

あと、オブジェクトlistに入っているオブジェクトを
２重for文を使って、比較対象を二つ抽出し、
衝突判定させるって普通は使わない方法なんでしょうか？
すごく驚かれた感じですが、、、

[softya（ソフト屋)]

> LoopCount++;　　　←こんな感じで設置すればいいですか？

そんな感じですが、大体の数も予想出来ていませんか？
例えばリストに100個あれば100x100で10000回まわるわけですよね。

>衝突判定させるって普通は使わない方法なんでしょうか？
>すごく驚かれた感じですが、、、

やらないことは無いですよ。
ただ、恐ろしい回数行きそうなら敵と自分はリストを分けるなど工夫します。
ObjectMgr::getInstance()も毎回やらないて良いかなとは思います。

[やっくる]

そんな感じですが、大体の数も予想出来ていませんか？

調べました。
list内に約60以上、オブジェクトが入ると遅延して来ます。
調査ということでわざと100以上オブジェクトを突っ込んでみましたが
list内のオブジェクト数に比例してどんどん遅延します。

loop数ですが、これがまたすごいスピードで増加しまして、
これが処理として少ないのか多いのかわかりませんが
その遅延状態にはloop数が2,3秒もしないうちに
1000000以上も増加するレベルになってますね。
いや、そうでなくても普段から
loopの部分は相当回ってました。
1フレームに二重for文全部回るわけですから。
これが、二重for文の弊害なんですね。

完全に、今回の遅延は
これが原因の様です。

がしかし、ISLe()さんも言った通り
ひとつのlistにすべてのオブジェクトをまとめて
衝突判定させてやる方法は
ゲームプログラムにおいて
別に特殊でもなんでも無いと思うんです。
そして、ひとつのlistで管理するならば
抽出させる時に二重for文を利用するのは
避けられないはずです。

結局、今回の問題は
オブジェクトクラスの更新の量の問題でも無く、
自分のプログラム文のミスでも無く、
60以上ものオブジェクトを画面内に出現させる様なゲームで、
すべてのオブジェクトをひとつのlistに入れる方法を取った事が問題、
というのはちょっと現代の言語処理速度にガッカリな感じです。。
それは仕方ないとして、これも疑問なのですが
ソフト屋さんのアドバイス通り、弾や敵用のlistを別に増やし、
objectlistAと、objectlistBとでオブジェクトをわけて放り込んだとしても
結局は、こんな感じになりませんか？
大きく見れば、これも二重for文の様な気がするのですが
これで、解消されるのでしょうか？
↓

コード:

 for(it = ObjectMgr::getInstance()->objectlistA.begin(); it !=ObjectMgr::getInstance()->objectlistA.end(); ++it)
    {
　　　if((*it)->ID==プレイヤー){   //プレイヤーを抽出
            
                 for(it2 = ObjectMgr::getInstance()->objectlistB.begin(); it2 !=ObjectMgr::getInstance()->objectlistB.end(); ++it2)
                 { 
　　　　　　　敵や敵の弾を抽出し、衝突判定
　　　　　　　〜割愛〜　
                 }
        }
    }

ObjectMgr::getInstance()も毎回やらないて良いかなとは思います

待って下さい、シングルトンしたクラスの変数や関数を
他クラスで利用する場合
"ObjectMgr::getInstance()->"は必須記載事項じゃ無いんですか？？？

[やっくる]

補足します。

>list内に約60以上、オブジェクトが入ると遅延して来ます

厳密にはトピの質問内容通り、約30以上から遅延は始まっており、
60以上では完全にゲームプレイに支障をきたしているレベルの
遅延となっています。

[ISLe()]

がしかし、ISLe()さんも言った通り
ひとつのlistにすべてのオブジェクトをまとめて
衝突判定させてやる方法は
ゲームプログラムにおいて
別に特殊でもなんでも無いと思うんです。
そして、ひとつのlistで管理するならば
抽出させる時に二重for文を利用するのは
避けられないはずです。

わたしの場合、衝突判定は更新処理の中にあって、衝突判定のための独立したループはありません。
衝突判定の相手も、そもそもする必要のない無駄な判定などを省きます。
総当りなんて無茶は最初から除外しますね。
コストの増加が常に線形になるように考えます。
リストそのものを分けなくても、グループ化のオブジェクトを作ればメインのリストはひとつのままで拡張できます。

No.20の赤字で書かれた部分は、わたしには
ひとつのリストで更新処理を一回だけ回す
という意味に見えました。
ことあるごとに何回もループを回すという発想はありませんでした。

[softya（ソフト屋)]

>1000000以上も増加するレベルになってますね。

100要素だと３重ループ以上している計算になりますね。２重ループだと数学的に計算がおかしいのでコードの流れの見直しが必要かと思います。
100要素なら２重ループで100の２乗なので１万のはずです。

>すべてのオブジェクトをひとつのlistに入れる方法を取った事が問題、
>というのはちょっと現代の言語処理速度にガッカリな感じです。。
ちなみに速度にがっかりされるのは、Releaseビルドされてからのほうが良いと思います。こういうパターンは劇的に早くなるでしょう。
まぁ、パワーに任せて解決しても根本的にアルゴリズムに問題があると思うのでDebugビルドでも問題なく動くようにするのが鉄則です。
Releaseビルドに頼るのは最後の手段ですからね。
8bit時代なら、こんな事したら数秒に１コマも動かない激遅ゲームだと思いますよ。
コードを見直すことが必要です。

>待って下さい、シングルトンしたクラスの変数や関数を
>他クラスで利用する場合
>"ObjectMgr::getInstance()->"は必須記載事項じゃ無いんですか？？？

動作中にインスタンスが変化するはず無いので、forループ２つでgetInstance()が４回も出てくる必要性は無いんじゃないですか？
それとも動的に変化するのですか？

[やっくる]

No.20の赤字で書かれた部分は、わたしには
ひとつのリストで更新処理を一回だけ回すという意味に見えました。
ことあるごとに何回もループを回すという発想はありませんでした。

ことあるごと、の指している意味がわかりませんが、
二重for文にしても、当たり判定なのですから
無駄なループをさせているわけではないはずです。
そのオブジェクトが、
list内のすべてのオブジェクトと今衝突しているか判断する
それを毎フレーム行っているだけです。
それは縦横無尽にドット単位で動くシューティングにおいて
必ず行い続けなければならない処理のはずですよね？

衝突判定の相手も、そもそもする必要のない無駄な判定などを省きます。

自分も抽出している時に、相手に条件をつけているので
それで違う対象は弾くわけですが、
それがISLe()さんのいう「する必要のない相手を省く」
ということにはならないのでしょうか、意味違っていますか？
同じlistにいる相手から条件に合う合わないと調べて抽出すること自体
「する必要のない無駄な判定」なのでしょうか？
listの中を対象だけに絞っていれてれば、そんな判定すらいりませんが
すべてのオブジェクトをいれたlistを扱う方法では、それでは無理な話なはずです。

ひとつのリストで更新処理を一回だけ回す

更新処理は当然として、衝突判定も
自分は、毎フレーム１回だけ回しています。
それが、二重for文だから、量が多い？というだけで
すべての要素を毎回通らせるのは、無駄な処理では無いと思うのですが
自分は思い違いをしているのでしょうか？

衝突判定は更新処理の中にあって、衝突判定のための独立したループはありません。

listにあるオブジェクトたちの更新関数の中で衝突判定を？？？
それとも、ObjectMgrの更新の中ででしょうか？いや、
でもそれなら、HitCheckの更新でやろうと一緒ですよね、、
どいうことでしょうか。
別のところの更新ループを利用して
衝突相手のlistをまわすなんて、どういう仕組みなんでしょうか？

[やっくる]

100要素だと３重ループ以上している計算になりますね
２重ループだと数学的に計算がおかしいので

いや、すみません、すごいスピードでloop回数が増加するので
自分が計算苦手なのでアバウトに話しただけです。
３重ループはしてないでしょう、
for文は２カ所しかないのですし。
イテレータの初期化も最初だけですから、
毎回list内の要素をすべて通るだけですよね？

ちなみに速度にがっかりされるのは、Releaseビルドされてからのほうが良いと思います。
こういうパターンは劇的に早くなるでしょう。

そうなんですか？
それだとありがたいです。。

Releaseビルドに頼るのは最後の手段ですからね。

ですよね。

動作中にインスタンスが変化するはず無いので、
forループ２つでgetInstance()が４回も出てくる必要性は無いんじゃないですか？
それとも動的に変化するのですか？

えっと、ふたつのイテレータを宣言し、
for文の条件式にて、objectMgrのlistの
各イテレータの位置をlistの頭にセット(初期化)するのと
listの最後(終わり)の判断させるとで、それがイテレータ二つ分ということで
その4回はどうしようもないと思うんですが、、、、？

コード:

for(it = ObjectMgr::getInstance()->objectlist.begin(); it !=ObjectMgr::getInstance()->objectlist.end(); ++it)
    {
            for(it2 = ObjectMgr::getInstance()->objectlist.begin(); it2 !=ObjectMgr::getInstance()->objectlist.end(); ++it2)
        {

↑
この四つの箇所は絶対必要じゃないですか？
わからなくてすみません。

[うずら]

判定をやっている最中終わり位置のイテレーターが変化しないなら(判定のチェック中にlistに項目の追加がない)
終了位置のイテレーターは最初に取得すれば使いまわせるということではないでしょうか。

僕もそこの改善でかなりループを軽くできたことがあります。

こんな感じに。(書きなれてるvectorで書いちゃいましたがlistでも同じように書けば大丈夫でしょう)
第一式のunsigned intのところをlist<type>::iteratorに書き換えれば。

コード:

vector<char> Array;

for (unsigned int i = 0, n = Array.size(); i < n; i++)
{
    // 処理
}

[softya（ソフト屋)]

そんな難し話じゃないですよ。

コード:

ループ中イテレータが変化する場合

list<sObject*>&loopObjectlist = ObjectMgr::getInstance()->objectlist;	
for(it = loopObjectlist.begin(); it !=loopObjectlist.end(); ++it) {
            for(it2 = loopObjectlist.begin(); it2 !=loopObjectlist.end(); ++it2) {

イテレータがループ中は固定の場合
list<sObject*>::iterator it_st, it_end;
it_st = ObjectMgr::getInstance()->objectlist.begin();
it_end = ObjectMgr::getInstance()->objectlist.end();
for( it=it_st ; it!=it_end ; ++it ) {
	for( it2=it_st ; it2!=it_end ; ++it2 ) {

[softya（ソフト屋)]

>いや、すみません、すごいスピードでloop回数が増加するので
>自分が計算苦手なのでアバウトに話しただけです。
>３重ループはしてないでしょう、
>for文は２カ所しかないのですし。

プログラムで確認できるのでループ数と付きあわせてみてください。
１フレーム辺りでリスト数xリストの数と等しくなるはずです。
こういう所は手を抜かないでくださいね。
※　自分を信じないようにしましょう。

[usao]

オフトピック

衝突判定って双方向
（A,B という二つのオブジェクトがあったら
A→B
B→A
みたく２回やる）
なんですか？
（速度がやたら遅いという話とは直接関係ない話です）

[ISLe()]

ことあるごと、の指している意味がわかりませんが、
二重for文にしても、当たり判定なのですから
無駄なループをさせているわけではないはずです。
そのオブジェクトが、
list内のすべてのオブジェクトと今衝突しているか判断する
それを毎フレーム行っているだけです。
それは縦横無尽にドット単位で動くシューティングにおいて
必ず行い続けなければならない処理のはずですよね？

キャラの移動処理などを含む更新処理のループが別にあるのではないのですか？
そうであれば、わたしの感覚として、ことあるごとにループを組んでいるということになるのですが。

当たり判定には、『当たっているかどうか』『当たっていたらどうするか』の2段階あります。
『当たっているかどうか』を総当りで求めるのは無駄でしかありません。
「当たり判定 高速化」「当たり判定 軽量化」などでネットを検索してみてください。
空間分割などさまざまな手法が見付かるはずです。
メジャーなテーマなのです。

同じlistにいる相手から条件に合う合わないと調べて抽出すること自体
「する必要のない無駄な判定」なのでしょうか？
listの中を対象だけに絞っていれてれば、そんな判定すらいりませんが
すべてのオブジェクトをいれたlistを扱う方法では、それでは無理な話なはずです。

既にいくつもヒントを出しました。

タイルマップは同じ大きさのマスが格子状に並んでいるので、どのマスと重なっているかは簡単な計算で求められます。
重なっているマスにあるオブジェクトとだけ当たり判定をすれば良いのです。

例えば、敵の弾グループというオブジェクトを用意します。
ひとつのリストに登録するということは共通のインターフェースを持っているはずですよね。
敵の弾は、敵の弾グループにリスト登録します。
敵の弾グループをメインのリストに登録して、敵の弾グループは自分に登録された敵の弾に処理を委譲します。
敵の弾同士は当たらないとすれば、敵の弾グループで弾くことができ、同様にグループ化することでループ回数を減らせます。

空間分割手法などを使う場合も同様です。
『誰と』当たっているかを求める方法はいくらでも工夫の余地があります。
工夫の余地が入るようにコーディングすべきだと思います。

更新処理は当然として、衝突判定も
自分は、毎フレーム１回だけ回しています。
それが、二重for文だから、量が多い？というだけで
すべての要素を毎回通らせるのは、無駄な処理では無いと思うのですが
自分は思い違いをしているのでしょうか？

更新処理で回し、衝突判定で回しているわけですよね。
それぞれ1回ずつ。
わたしの感覚ではそれは無駄です。

[やっくる]

ソフト屋さん
listをわけて、衝突判定処理をNo: 36の方法に変えたところ
遅延がまったく起きなくなりました。問題自体は解決しました。
結局、総当たりさせる自分の衝突判定方法と
ひとつのlistでオブジェクトを管理するということの
相性の悪さで起きた遅延だったということですね。
勉強になりました。

usaoさん
いいえ、違います。
そういうことではありません。


ISLe()さん

キャラの移動処理などを含む更新処理のループが別にあるのではないのですか？

はい、別にあります。
オブジェクトlist管理のクラスにて、list内の更新をしているのです。
そこでついでにオブジェクト同士の衝突判定もしろ、ということでしょうか？
確かに、自分は癖というか、衝突判定するクラスを作るやり方を最初に覚えたので
なんの疑問も無く、すべての製作ゲームで衝突判定はクラスで作ってます。
そのメリットもあるわけでもありません、
衝突判定もlisit内の更新をするループを利用してやった方がいいですよね、、、
考えてみます。

当たり判定には、『当たっているかどうか』『当たっていたらどうするか』の2段階あります。
『当たっているかどうか』を総当りで求めるのは無駄でしかありません。

空間分割は初めて聞きました。
こことか読んでみましたが、頭が爆発しそうです。
http://marupeke296.com/COL_2D_No8_QuadTree.html
ゲーム制作を続けて行く上で必要な知識だというのは
理解出来ますので勉強してみます。

タイルマップは同じ大きさのマスが格子状に並んでいるので、
どのマスと重なっているかは簡単な計算で求められます。
重なっているマスにあるオブジェクトとだけ当たり判定をすれば良いのです。

ああ、タイルマップで衝突の判断をするんですね。
衝突判定処理は、オブジェクトの座標はしったこっちゃ無くて
オブジェクトがいるマスを認識していればいいと。
イメージは見えましたが、碁盤感覚でシュミレーションゲームのイメージです。
それをアクションゲームやシューティングにも利用するイメージを
持つようにならなければならないのですね。
意識していこうと思います。

あと、No: 27の件をお待ちしております。

Enemyクラスがインターフェースとして働くことになるのでそれに関する部分は自ずと共通化されることになります。
各キャラクタの固有部分が分離されて、オブジェクト別に状況に応じた柔軟な設計が可能になります。

自分の中ではENEMYクラス内でswitch文で分けて処理する方法以外考えられないので
ソレ以外の方法？でどうされてくるのか楽しみです。

[usao]

何やらコードを修正したら現象が収まったとのことですが，
もともとの void HitCheck::hitcase() で，
listの要素数がNのとき，ループの中身は結局何回走ってたんですか？　というのが読み取れないのですが…

本当に「１本のリストだったから」が原因だったのでしょうか？
まぁ，何かいじってるうちに解消して結果オーライと言う話も有りなのかもしれませんが…

オフトピック

単純比較はできないでしょうが，こんなのをdebugビルドで動かしても１秒もかからないわけで．

コード:

int Loop( int N )
{
	int counter = 0;
	for( int i=0; i<N; i++ )
	{
		for( int j=0; j<N; j++ )
		{
			++counter;
		}
	}
	return counter;
}

//
int main( int argc, char **argv )
{
	const int N = 1000;

	for( int i=0; i<60; i++ )
	{
		std::cout << i << ", " << Loop( N ) << std::endl;
	}

	std::cin.ignore();
	return 0;
}

[usao]

オフトピック

>usaoさん
>いいえ、違います。
>そういうことではありません。

そういうこと　になっているように見えたのですが，
ループ内で何か判定して一方のパターンでしか処理しないようなことをしていたのでしょうか？

まぁ，言いたかったことは　単純に，

コード:

for( int i=0; i<N; i++ )
{
  for( int j=0; j<N; j++ )
  {
    i<j のときのみ，{i,j}の組み合わせについて処理
  }
}

とか書くのであれば，こう↓すればいいんじゃ？　ってだけのことだったのですけど．

コード:

for( int i=0; i<N-1; i++ )
{
  for( int j=i+1; j<N; j++ )
  {
    {i,j}の組み合わせについて処理
  }
}

[やっくる]

usaoさん
自分は最初、あなたのいう↓の処理方法でやっていました。
ですが、それで遅延が起きていたんですよ。

コード:

for( int i=0; i<N-1; i++ )
  for( int j=i+1; j<N; j++ )
  {
    {i,j}の組み合わせについて処理
  }
}

厳密にはこう↓ですが、回し方は一緒ですよね？

コード:

for(it = ObjectMgr::getInstance()->objectlist.begin(); it !=ObjectMgr::getInstance()->objectlist.end(); ++it)
  for(it2 = ObjectMgr::getInstance()->objectlist.begin(); it2 !=ObjectMgr::getInstance()->objectlist.end(); ++it2)
  {
    {it,it2}の組み合わせについて処理
  }
}

それで遅延が起きていたんです。

itをメインとして、it2で対象を探すわけですが
it==A、it2==Bの衝突判定をしている場合は
もちろん重複するようなit==B、it2==Aの衝突判定はしていません。
Aに関係無いit==B、it2==Cはしますけど。

[usao]

offtopicな「２重ループの書き方」は，まぁわりとどうでもいいのですが，
【本題の側（本題だった側）の　遅延が起きていた理由　が，明確にされなかった】ように見受けるのですが，
その点はどうなんでしょうか？

No.31の書き込みによれば，「ループ内で何もしなくても遅延が起きていた」とのことでしたから，遅延の原因としては

(1)そこに書かれている
　・ObjectMgr::getInstance()
　・ObjectMgr::getInstance()->objectlist.begin()
　・ObjectMgr::getInstance()->objectlist.end()
　のいずれかが問題を起こしていた

(2)この　特別何も仕事をしない２重ループ　が単にとんでもない回数回っていて，結果として遅かっただけ

くらいが推測されるわけです．

で，後者側の回数を問われていたわけですが……
仮にこれが　「リスト要素が100個なら，100x100回ですよね？」　という問いかけ通りの回数であった　のならば，
原因は(1)側にある可能性もあったわけで，
「リストが一本だった」ことが遅延の直接の原因ではなかった可能性もあるのでは…？　と思うのです．


＃…といった感じで，私には　何で遅延してたのか？　が未だ明確でないように見えるのですが……
　そんなことはなくて，この点は既にしっかりと解明済み　ということなのであれば，スルーしてください．

[softya（ソフト屋)]

私も２重ループが遅い原因でした！って片付けるのは何かが違うと言うかゴーストがささやくと言うか、もう少し具体的な数字などの情報がほしいです。
このトピック見ている人のためにも必要な情報だと思います。

２重ループの場合、NxNでM万回ループしていて処理時間はQmsでした。　→　これはループだけの処理時間です、
ループ改善後は、M2回ループしていて処理時間はQ2msでした。
って感じで情報を出せませんでしょうか。

[usao]

まぁ，元のソースがもうありません　とかいう状況だったりすると今さら再検証とか無理なのかもしれませんが．

一応，補足しておきますと，

>loop数ですが、これがまたすごいスピードで増加しまして、
>これが処理として少ないのか多いのかわかりませんが
>その遅延状態にはloop数が2,3秒もしないうちに
>1000000以上も増加するレベルになってますね。

これが

「HitCheck::hitcase()　という関数を【１回呼ぶと】，
　時間にして　2,3 秒ほどを要し，　ループ回数は1000000以上」

ということだったのか，それとも

「プログラムを 2,3 秒 動かすと，（HitCheck::hitcase()は，その間に何回も呼ばれて）
　HitCheck::hitcase()内のループ回数の　総数　が1000000以上」

とかいうことだったのか　がはっきりしない感じの書き方になってしまっているのですよね．
後者みたいな事柄であったならば，調査方法が的外れであったことになりますし，
前者であったならば，プログラムにバグがあったのだと思います．
（例えば，別スレッドが悪さしてるとか，ObjectMgr::getInstance()の実装がバグってるとか…？）

オフトピック

例えば，VGAサイズ画像をデータとして扱ったりすると
640x480回の２重ループが必要な全画素走査処理をＮ種類適用してどうの…とかを30fpsとかで普通にやるわけで，
100x100の空ループ１個書いたら遅延がやばい　とかいう話は信じられないんですよね．

[やっくる]

usaoさん、ソフト屋さん

まず、

(1)そこに書かれている
　・ObjectMgr::getInstance()
　・ObjectMgr::getInstance()->objectlist.begin()
　・ObjectMgr::getInstance()->objectlist.end()
　のいずれかが問題を起こしていた

についてですが、
ソフト屋さんがNo.43で教えてくださった、

コード:

list<sObject*>&loopObjectlist = ObjectMgr::getInstance()->objectlist;   
for(it = loopObjectlist.begin(); it !=loopObjectlist.end(); ++it) {
            for(it2 = loopObjectlist.begin(); it2 !=loopObjectlist.end(); ++it2) {

を真っ先に導入したのですが、遅延状態は変わりませんでしたので
これはObjectMgr::getInstance()の書き方の問題では無いのだなと思いました。
(が、一応No.39でのソフト屋さんの「４回も出てくる必要性は無い」との言葉を重んじて
遅延状態の改善は見られなかったのですが、教えてもらったこの方法を使ってfor文は書いています)

で、僕が発言しました
>loop数ですが、これがまたすごいスピードで増加しまして、
>これが処理として少ないのか多いのかわかりませんが
>その遅延状態にはloop数が2,3秒もしないうちに
>1000000以上も増加するレベルになってますね。
についてですが、
ループ数を計るカウントはusaoさんのソースでいうところの

コード:

for( int i=0; i<N-1; i++ )
  for( int j=i+1; j<N; j++ )
  {
　　LoopCount++;　← ここが通る数を計った
   　 {i,j}の組み合わせについて処理
  }
}

の場所です。
ですので、調べたのはHitCheck::hitcase()が呼ばれた数ではありません。
二重for文でjを通った数(list内のソレが対象かどうか探した回数)です。
で、その増え方ですが、総当たりなので
list内のオブジェクト(要素数)が増えれば、当然通る数も増加しますが
その増加の量が1要素数に対し、なぜか尋常ではない量でした。
list内の要素数が少ないと遅延は起きません。でもlistに沢山入ると遅延するのです。

ちなみに、↓のような感じで書いてました

コード:

 for(it = ObjectMgr::getInstance()->objectlist.begin(); it !=ObjectMgr::getInstance()->objectlist.end(); ++it)
    {
            for(it2 = ObjectMgr::getInstance()->objectlist.begin(); it2 !=ObjectMgr::getInstance()->objectlist.end(); ++it2)
        {
　　　 if((*it)->ID==プレイヤー ){//判定メイン側をitで抽出
 　　　　　if((*it2)->ID==敵){//判定対象側をit2で抽出
　　　　　　衝突判定
 　　　　　}
　　　　　if((*it2)->ID==敵の弾){//判定対象
　　　　　　衝突判定
             　 }
　　　　　if((*it2)->ID==アイテム){//判定対象
　　　　　　衝突判定
　　　　　}
　　　 }
　　　//次の判定メイン側
　　　 if((*it)->ID==プレイヤーの弾 ){
 　　　　　if(割愛==敵){
　　　　　　衝突判定
 　　　　　}
　　　　　if(割愛==敵の弾){
　　　　　　衝突判定
             　 }
　　　　　if(割愛==アイテム){
　　　　　　衝突判定
　　　　　}
　　　 }
　　　//次の判定メイン側
　　　 if((*it)->ID==オプション ){
 　　　　　if(割愛==敵){
　　　　　　衝突判定
 　　　　　}
　　　　　if(割愛==敵の弾){
　　　　　　衝突判定
             　 }
　　　　　if(割愛==アイテム){
　　　　　　衝突判定
　　　　　}
　　　 }
　　　//次の判定メイン側
　　　 if((*it)->ID==オプションの弾 ){
 　　　　　if(割愛==敵){
　　　　　　衝突判定
 　　　　　}
　　　　　if(割愛==敵の弾){
　　　　　　衝突判定
             　 }
　　　　　if(割愛==アイテム){
　　　　　　衝突判定
　　　　　}
　　　 }
　　　//以下、同じ様に衝突判定させたいものを並べて行く(衝突のケースは重複しない様に)

        }
    }

これを、listを二つ(objectlistA,objectlistB)にわけ、
衝突判定処理の部分で、player側のオブジェクトはobjectlistAに、
enemy側のオブジェクトはobjectlistBに入れるようにして、

コード:

 for(it = ObjectMgr::getInstance()->objectlistA.begin(); it !=ObjectMgr::getInstance()->objectlistA.end(); ++it)
    {
　　　if((*it)->ID==プレイヤー){   //listAからプレイヤーを抽出
            
                 for(it2 = ObjectMgr::getInstance()->objectlistB.begin(); it2 !=ObjectMgr::getInstance()->objectlistB.end(); ++it2)
                 { 
　　　　　　if((*it2)->ID==敵){//listBから判定対象を探す
　　　　　　　衝突判定
 　　　　　　}
　　　　　　if((*it2)->ID==敵の弾){//listBから判定対象を探す
　　　　　　　衝突判定
             　　 }
　　　　　　if((*it2)->ID==アイテム){//listBから判定対象を探す
　　　　　　　衝突判定
　　　　　　}
                 }

　　　if((*it)->ID==プレイヤーの弾){   //プレイヤーの弾を抽出
            
                 for(it2 = ObjectMgr::getInstance()->objectlistB.begin(); it2 !=ObjectMgr::getInstance()->objectlistB.end(); ++it2)
                 { 
　　　　　　if((*it2)->ID==敵){
　　　　　　　衝突判定
 　　　　　　}
　　　　　　if((*it2)->ID==敵の弾){
　　　　　　　衝突判定
             　　 }
　　　　　　if((*it2)->ID==アイテム){
　　　　　　　衝突判定
　　　　　　}
                 }

　　　if((*it)->ID==オプション){   //オプションを抽出
            
                 for(it2 = ObjectMgr::getInstance()->objectlistB.begin(); it2 !=ObjectMgr::getInstance()->objectlistB.end(); ++it2)
                 { 
　　　　　　if((*it2)->ID==敵){
　　　　　　　衝突判定
 　　　　　　}
　　　　　　if((*it2)->ID==敵の弾){
　　　　　　　衝突判定
             　　 }
　　　　　　if((*it2)->ID==アイテム){
　　　　　　　衝突判定
　　　　　　}
                 }

　　　if((*it)->ID==オプションの弾){   //オプションの弾を抽出
            
                 for(it2 = ObjectMgr::getInstance()->objectlistB.begin(); it2 !=ObjectMgr::getInstance()->objectlistB.end(); ++it2)
                 { 
　　　　　　if((*it2)->ID==敵){
　　　　　　　衝突判定
 　　　　　　}
　　　　　　if((*it2)->ID==敵の弾){
　　　　　　　衝突判定
             　　 }
　　　　　　if((*it2)->ID==アイテム){
　　　　　　　衝突判定
　　　　　　}
                 }
        }
    }

としたら、まったく遅延が起きなくなりました。

listBにオブジェクトを200ほど入れても遅延は起きません。
なので、自分としてはこれで解決したと思ったのです。

確かに、数値として出して無いのはうやむや？っぽくて
アレですが、皆さんの言われる数値の出し方が自分はちょっとハッキリわかりません。
ループ数も凄いスピードで増え続けていますし、
時間を置く場所もわかりませんし、
どの状態でいつの数値をどう説明すればいいのか、ちょっとわからないのです。
それは自分がまだプログラムの初心者で、その辺のテクというか、
知識というか技術というか、それらが不足しているからでしょうね。
その辺の手ほどきをして頂ければ、正確に実行し、お伝えしたいと思いますが。。

usaoさん、とりあえず、
ソフト屋さんも回答で"２重ｆｏｒ文のループ数は場合によっては脅威"だと言ってらっしゃいます
↓

２重ｆｏｒの内側で、大体何回ぐらいループしてますか？
list要素数次第では恐ろしい回数回りそうです。

実際、二重for分のjの場所に設置したカウンターは
毎フレーム凄まじい増加量が見て取れました。
数千のレベルではありません。数万、いや、数十万のレベルで増え続けてました。

[softya（ソフト屋)]

>その増加の量が1要素数に対し、なぜか尋常ではない量でした。

やっくるさんの予想と、その数に大幅なズレが有るなら想定外の動作をしている証拠です。
今回一見直ったように見ますが、実はプログラムは思っても見なかった動作をしている可能性があります。
やっくるさんが１フレームに１回だけこ当たり判定の２重ループが動作すると説明してますが、そう思い込んでいるだけの可能性が高いです。

>アレですが、皆さんの言われる数値の出し方が自分はちょっとハッキリわかりません。
>ループ数も凄いスピードで増え続けていますし、
>時間を置く場所もわかりませんし、
>どの状態でいつの数値をどう説明すればいいのか、ちょっとわからないのです。
>それは自分がまだプログラムの初心者で、その辺のテクというか、
>知識というか技術というか、それらが不足しているからでしょうね。

プログラムの動きを書いたのはご自身ですから、１フレームに通る回数、１フレームにループするであろう回数、処理として許容できる時間を想定できるはずです。
想定できないなら、一度じっくり考えてみてください。
そしてそれを検証できる方法を考えます。検証する方法を考えるのはプログラムを組むこととなんら変わりがありません。
プログラムを考えれたなら、検証する方法も同様に考えられるはずです。

テストとデバッグは、プログラムの工程の大半を占める非常に大事な作業です。
これが出来ないとプログラムは完成しませんので身につけましょう。今がその時だと私は思います。

[ISLe()]

あと、No: 27の件をお待ちしております。

Enemyクラスがインターフェースとして働くことになるのでそれに関する部分は自ずと共通化されることになります。
各キャラクタの固有部分が分離されて、オブジェクト別に状況に応じた柔軟な設計が可能になります。

自分の中ではENEMYクラス内でswitch文で分けて処理する方法以外考えられないので
ソレ以外の方法？でどうされてくるのか楽しみです。

省メモリを意識したサンプルコードにしてみました。

コード:

#include "DxLib.h"
#include <list>
using std::list;

struct Object;
struct ObjectOp {
	virtual void Update(Object *o) = 0;
};
struct Object {
	int  x,  y;
	int vx, vy;
	ObjectOp *op;
	Object(int x, int y, ObjectOp *op) : x(x), y(y), vx(0), vy(0), op(op) {}
	virtual void Update();
	virtual void Render();
};
void Object::Update() {
	op->Update(this);
}
void Object::Render() {
	DrawCircle(x, y, 4, GetColor(255,255,255), TRUE);
}
struct BoundOp : public ObjectOp {
	virtual void Update(Object *o);
};
void BoundOp::Update(Object *o) {
	if (o->vx == 0) o->vx = GetRand(1) ? 1 : -1;
	o->x += o->vx;
	o->y += o->vy;
	if ((o->vx > 0 && o->x > 640-4) || (o->vx < 0 && o->x <= 0+4)) o->vx =-o->vx;
	if ((o->vy > 0 && o->y > 480-4) || (o->vy < 0 && o->y <= 0+4)) o->vy =-o->vy;
	else o->vy += 1;
}
struct ReflectOp : public ObjectOp {
	virtual void Update(Object *o);
};
void ReflectOp::Update(Object *o) {
	if (o->vx == 0) o->vx = GetRand(1) ? 1 : -1;
	if (o->vy == 0) o->vy = GetRand(1) ? 1 : -1;
	o->x += o->vx;
	o->y += o->vy;
	if ((o->vx > 0 && o->x > 640-4) || (o->vx < 0 && o->x <= 0+4)) o->vx =-o->vx;
	if ((o->vy > 0 && o->y > 480-4) || (o->vy < 0 && o->y <= 0+4)) o->vy =-o->vy;
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
{
	ChangeWindowMode(TRUE);
	if (DxLib_Init() != 0) return 0;
	SetDrawScreen(DX_SCREEN_BACK);

	list<Object*> l;
	BoundOp   bound_op;   // 跳躍オペレータ
	ReflectOp reflect_op; // 反射オペレータ
	for (int i=0; i<100; i++) {
		ObjectOp *op;
		if (GetRand(1) == 0) op = &bound_op; else op = &reflect_op; // オペレータ選択
		l.push_back(new Object(GetRand(640-40-1)+20, GetRand(480-40-1)+20, op));
	}

	while (ProcessMessage() == 0 && ScreenFlip() == 0 && ClearDrawScreen() == 0) {
		for (Object *o : l) { o->Update(); o->Render(); }
	}
	
	DxLib_End();
	return 0;
}

クラスのインターフェースとインプリメント(実装)の分離は、これも検索すれば山ほど記事が見付かると思います。
デザインパターンとしても有名ですしね。

このサンプルでは全部パブリックにしてしまってますが、
オブジェクトのメンバ周りやそのアクセスをどうするかといったあたりはいろんな方法があるので調べてみてください。

[usao]

何かがおかしい　ときに，その原因はこうではないか？　という仮説を立てたら，
その仮説を実証（あるいは棄却してよいことを実証）するためにはどのようなことを調べればよいか？　という話ですね．
証拠集めですから，ぼんやりした調査ではなく，
「もし△△であるならば，○○という変数の値はこのタイミングでは××でなければならない」
といったように具体的でなければなりません．

例えば，↓のようなプログラムがおかしな動きをしていて，
「※」の箇所の処理が想定回数以上繰り返されている「のかもしれない」と怪しんだとき，
それを確かめるにはどうするか，ということですよね．

コード:

void F( int N )
{
  for( i=0; i<N; i++ )
  {
    //※
  }
}

//
int main()
{
  while( 1 )  //メインループ
  {
    ...
    F( 100 );
    ...
  }
  ...
}

ここでの想定回数とは，　100回/メインループ内処理１回　です．
（メインループ内の処理が１回行われるごとにF()が１回だけ呼ばれて，
　結果として「※」の箇所は，メインループ内の処理１回ごとに，N=100回だけ行われる）

「※」の箇所が想定以上に実行されるとしたら，考えられる原因は以下の２つです

(A)本当に　メインループ内処理１回に対して，F()は１回しか呼ばれていないのだろうか？
　これが２回呼ばれていたら，想定回数の２倍の回数だけ「※」の箇所が実行されてしまう．
(B)関数F()の１回のコールに対して，本当に「※」の箇所はN=100回だけ処理されているのだろうか？
　何かが間違っていて，N+5回だとか，3*N回だとかになってたりしないのだろうか？

これらを確認するとしたら，例えば，以下のように確認のための表示などを入れてみれば良いわけです．
（ (A)を調べるための記述には//(A), (B)を調べるための記述には//(B) と注釈を添えました　）

コード:

void F( int N )
{
  printf( "F()に入った\n" );  //(A)F()が呼ばれたことがわかるように
  int counter = 0;  //(B)「※」の箇所の処理回数をカウントする用
  for( i=0; i<N; i++ )
  {
    //※
    ++counter;  //(B)
  }
  printf( "※の箇所は%d回走った\n", counter );  //(B) F()を１回コールすると何回「※」の箇所が走るのかを表示
}

//
int main()
{
  while( 1 )  //メインループ
  {
    printf( "メイン処理\n" );  //(A)メイン処理の各回の開始がわかるように．
    ...
    F( 100 );
    ...
  }
  ...
}

想定通りに動いていれば，
(A) 繰り返される「メイン処理」なる表示の間には，常に１回だけ「F()に入った」という表示がされるハズ
(B) そしてその際には 常に，「※の箇所は100回走った」と表示がされるハズ
ですよね．
（想定通りの流れで動いていれば，「※」の箇所が100回走るハズ　ということを調査．
　これがそうなっていなければ，「※」の部分を走る仕組みが想定外の流れになっている．
　それがわかったら，次は，「じゃあどうして想定外になってるのか？そうなる原因として考えられるのは…」
　という感じで追及してく．）

もちろん，必要に応じて
・F()から抜ける箇所でも「F()から抜ける」とか表示する
・F()に入った箇所で，引数Nの値も表示する
等々，物事をはっきりさせるために必要だと思う物が他にもあれば追加します．
（とにかく，表示した内容を見ることで知りたいことが明確にならなければ意味がありませんので，
　足りないのは×．　十分すぎるほどに情報を吐かせるくらいでよいです．）

＃例えば表示が流れるのが早すぎたりとかで（今回は逆に遅いという話ですが）
　プログラム動作中に表示を追うのがつらいとかいう時は fprintf()にしてファイルに吐くとか，
　あるいはリダイレクトしてprintf()の内容を適当にテキストファイルにでも吐かせるとか．

[Tatu]

カウンターを0に戻す処理がなかったから
カウンターが増え続けたということはないですよね？

[やっくる]

ISLe()さん
自分なりに努力したのですが
大変申し訳ないのです。
書かれているソースが私のレベルでは
まったくトレース出来ませんでした。

自分が勉強している(駆け出し用の)参考書でも
覗いているネットのサイトでも
見た事も無い様なプログラム文も多々ありますし、
なによりどこもかしこも書かれてあることが複雑すぎて、
結局ISLe()さんは自分と同じ状況に立たされたとき
なにをどうやってまとめるのか、
理解することが出来ませんでした。

自分のレベルとで天と地の差があるのは最初から承知していますが
そのISLe()さんにわざわざソースを書いてもらったにも関わらず
なにひとつ得られなかったことが自分は残念でなりません。
「初心者相手にこんな難解なレベルにしあげてさ、この意地悪！」なんて
申しません。どのレベルまでいけばISLe()さんのこのソースを
トレース出来るようになるのかまったく検討がつきませんが、
いつか今回のISLe()さんのソースを見て、
理解出来る自分がいたらいいなと思います。
ありがとうございました。

[ISLe()]

おそらく、「実装を分離する」という概念そのものを受け入れられないでいるのではないでしょうかね。

No.7で、制御関数を外から繋ぐようなことを本で読んだと書いておられますが、たぶんそこに書いてあったのと同じようなものだと思いますが。

No.56のコードは、あくまでも、概念の説明のために、基本的な文法だけを用い、単独で動作するように、書き下ろしたものです。