ゲームプログラミング相談室【Part7】

初歩的な質問ですみません。
C++でWindowsのシューティングゲームを作っているのですが、
弾を発射する処理時の数値管理をうまくやる方法が思いつきません。

1つや2つの弾ならいいのですが、多数の弾を画面上に表示させるときに
弾の座標や速度などはどのように管理し、計算するのがいいんですか？

構造体かクラスに詰め込むんだ！

>>536
・弾の座標や速度を持ったクラスを作る
・そのクラスをリストに追加していく

>>537-538
レスありがとうございます。
構造体はやってみたんですが、どうも上手くいかなくて・・・。
自分が指定した弾数を表示するのは可能なんですが、
弾を敵から次から次へと発射させていき、そして画面外の弾は消してってのが難しいです。
クラスを使ってみてもう少し悩んでみます。

敵の弾をvectorにpush
↓
vectorを走査して処理
↓
いらない弾をpop
↓
戻る

vectorだと最後尾以外のpopにオーバーヘッドが発生するんでlistのがいいとおも。

敵の弾が順番に出て、消えてくならvectorでよいんだけどね

大昔(フラグメントとか馬鹿にならなかった頃)のくせで、listは一瞬、躊躇ってしまう俺

無事作ることができました。
感動です！ありがとうございました。

>>543
> 大昔(フラグメントとか馬鹿にならなかった頃)
　
それどういう条件下での話だ？
　
大昔も小昔も現在も何も、メモリプールなアロケータを使った
弾リストがメモリ断片化で問題になるなんて聞いたことねー。

>>545
> メモリプールなアロケータ

そんな前提が加わったら何も言えんｗ

フラグメント気にする前に当然考慮すべき解決法じゃないのか。。。

ただ、俺だったら最初に配列で確保する。リスト不要。
弾が消えたら、配列の末尾の弾データで上書きする。
でその上書きしたところから弾(が消えるかかどうか)の処理。
弾程度のデータ量なら上書きなんて大した負荷じゃないし、
配列上のどの位置にあったも問題無い。

全部机上で考えた。実際上手く動かなくても反省しない。

>>543は古参っぽく振舞ってみたかったんだよ、きっと。

俺なんか内部が動的配列のリストを自作して使ってる。

ArrayListですかそうですか

そういや、Win9x系を使ってた頃に
弾1個に1mallocな富豪的プログラミング実験したら
ばっちり不具合起こした憶えがあるんだが
NT系主流の現在はどうなのかは知らん。

>>550
そりゃ、お前のバグだろｗ
newじゃなくて、mallocってるところが怪しいｗ

>551
Cの何が悪い。
いや俺自身はC++にどっぷり浸かってもう戻る気無いですけど。
あと「お前のバグだろ」には同意。

>>547-548
まてまて、そうじゃなくて、どうみてもSTLのlistの話だったよな？
STLならまず、そんな実装はしないっしょ

で、俺が「STLのlist」を使うのを一瞬、躊躇う話（でも今時そりゃないよな！）だったのに、
なぜか「メモリ管理した自作list」なんてのが出てきたじゃない。なんだそりゃと思うわ。

WindowsMeでnew/delete使って毎フレーム6万発を生成したり
破棄したりするプログラムを作ったことあるが、これ実行して放置しておくと
そのうち動きがカクカクになったよ。
同じ条件で自前配列からメモリを割り当てると何も問題なかった。

>>553
まてまて。
STL使うときに自前のアロケータを用意するのは
珍しくも何とも無いと思うんですけど。

>>555
だから流れ見てくれ。一般的なvectorとlistの違いの話をしてたんじゃないのか
自前で用意するなら、vectorでもlistでも良いわな。オーバーヘッドも似たようなもんだ。

>>543必死だなｗ

必死で何が悪い

>>558
頭が悪い
性格が悪い
状況が悪い
言葉が悪い
考え方が悪い
環境に悪い

DirectXとかにVRAMへの配置任せてると
長時間ゲームを起動した時にVRAMが断片化したりしないすかね

>>556
あのー、自前でアロケータ用意したって、例えばvectorの
insertやeraseを使えば相変わらずO(n)なんですがー。
listとvector、それぞれの得意不得意は変わらないですよ。

>>561
逆逆、listで自前アロケータ用意して、vectorより有利になれるか答えてみせてくれ

>>560
しない。

理由は自分で考えてみろ。

>>554
本当かよ。
Win95のころからゲーム作ってるが、毎フレーム生成、破棄で何の問題もなかったが
ま、昔話はどうでもいいが。

>>563
> 理由は自分で考えてみろ。
知らないんなら黙ってろ

>>565
お前が黙ってろボケ

ここは俺様のメモ帳だ。おまえ等のチャットじゃない。
だから俺様のような第三者にもわかるように、
ちゃんと判りやすく説明しろ。
それが駄目なら配列についてのみ語れ。

コッペパンとかどうかな

GBKごめん

>>562
あのー、末尾以外の要素をinsert/eraseするとき
vectorはO(N)、listはO(1)なのですが。
アロケータを用意するとこの差が埋まると？
すんげー都市伝説だね。

うぜぇ

>DirectXとかにVRAMへの配置任せてると
>長時間ゲームを起動した時にVRAMが断片化したりしないすかね

DirectXとかにVRAMの配置を「任せているからこそ」断片化しない。

Q.じゃあ、C/C++のmallocやnewはなんで断片化するんですか？任せてるのに。
A.C/C++はポインタの所為で確保された領域を移動させることが出来ないから。
　C#なんかではコンパクションもしてくれる。

Q.VRAMを勝手に移動させて大丈夫なんですか？
A.直接テクスチャ等にアクセスするとき、ワザワザ浮動させないようにlockしているでしょう。

>>570
…おまいだけはまともだと思っていたのだが

おまいの主張だと、listで「断片化が起きないように」、自前アロケータを用意するんだろ？
その時のオーバーヘッドは、vectorより有利になるのかよ。どう実装してるんだ。

・メモリの断片化
・要素の検索

> listで「断片化が起きないように」
　
んなこと言ってねー！
自前アロケータを用意したってメモリプール内で断片化するじゃねーか。

自前でも大きく確保して固定長で切り出すなら断片化起きないよ。
それはともかく、ＩＤが変わったんで誰がどういう主張してるかわからないんですけどｗ

>>574
…いや、ありえないだろ。なんでそこが抜ける。>>555のレスはなんだったんだ。
実は少し期待してたんだが、マジで寝ておけばよかった

つかなんだ、メモリプール内でも断片化って言うのか。プール内ならしたっていいよ。全然いいよ。
で、どうだろ、まだ行ける？

まてまて、一応言っておくが、STLの範囲で頼む
自前listなんてなんでもありだからな

＞メモリプール内でも断片化って言うのか。
　
言わんと思う。
アロケータ内部では廃棄ノードのリストと使用中のノードのリストがある状態。

廃棄ノードのリストだけ。

どうも、メモリの管理と弾の管理が混乱してるみたいだけど
そもそもが弾をlistで管理するか、vectorで管理するかと言う話だよね？

vectorはpopのオーバーヘッドで最後尾じゃなかったらメモリを詰める
動作が入るはずだから、listがいいと思うと言ったわけで・・・

>>580
そそ

>>561の書き込みに、>>562のレスがそもそも痛い

>>578
俺は最初から煽る気は全くないからな
で、いやそれは…今度はその廃棄ノードのリストの断片化は…っつう話に
決め打ちとなるとやっぱり、オーバーヘッド変わらないしなぁ

それなら、どこかのタスク説明サイトで、上手い実装があったな

std::vectorで弾管理ってことは
弾が画面外に出たらそれをeraseするみたいな使い方でしょ？
末尾以外のeraseは内部で一個後ろから末尾をコピーするでしょ。
　
これはアロケータを自作しようが標準のアロケータを使おうが
変わらないんだけど。

×一個後ろから末尾をコピーするでしょ。
○一個後ろから末尾までの要素をコピーするでしょ。

ちなみに俺は弾管理には>>547と同じ方法使ってる。
消去する要素に末尾の要素をコピーする。

断片化考えてた頃を思うと、STLのlist使うのって一瞬、躊躇うのよね。でも今時断片化なんて気にしないよな
　↓
断片化させないlist使えば、断片化なんて問題になるわけないじゃんｗ
　↓
いやSTLのlistの話だから。一般的なSTLの話してたんだぜ？
　↓
STLのlistでも、自前でアロケータ使えば断片化無しにできるじゃん
　↓
マジで？アロケータだけで、断片化が無くなるような実装できるの？
結局オーバーヘッドがvectorと同じ様な処理になるか、一般的なSTLの範囲超えね？

なんで話逸れていくんだろうな。寝るわ。

>>570
勘違いして、ここ書き間違えてる。
vectorはO(1)、listはO(N)だよね。

>>582
で>>583のとうり、vectorはアクセスはO(1)だけど、コピー動作が入るので
実質listよりオーバーヘッドが出る。


なるほどねぇ。>>547のような方法があったのか。
たしかにポインタ繋ぎ変えと比べてもそれほどでもないね。
いつか使ってみよう。

俺も寝る。

>>588
>>586で流れ分かったと思うし、本当に出来るなら明日でも良いから書いてくれよ
何度も言うが最初から煽る気はない

ついでにLyPqDceo = 1NV1OMlGvな

>586
>マジで？アロケータだけで、断片化が無くなるような実装できるの？
できる。

>587
>vectorはO(1)、listはO(N)だよね。
違う。
vectorはそれ以後の要素（平均してN/2個）を移動しなければならないからO(N)。
listは前後のポインタの繋ぎ換えだけなのでO(1)。

>>590
ああ、そうか、移動はそうだね。スマソ
アクセスと勘違いしてた。

だめだ>>582のサイト見つからないわ

>>590
いや誓っても良いが、たぶんどこかで断片化は起こるって。それなら何故普通に使わないんだと。
違うならさわりだけでも書いてくれ。何故皆、出来る出来るばかりで、内容を書かないんだ。

「断片化」の意味が確定してないんじゃね？

１．メモリ上に隙間ができる。（メモリ参照の局所性が低下してパフォーマンスに影響）
２．連続空き領域が小さくなってしまう。（大きなメモリ要求がエラーになる）

list のアロケータを差し替えることで２は回避できるが、１は回避できない。
１を回避するのは >>547 のような方法だが、これは list ではできない。

それなら、listのアロケータも変更したとしたら
１.も解決済みと思うけど。固定長なら。

>>594
list 内の三個の要素 A, B, C がメモリ上で ABC と連続しているとき、
B が破棄されたら A_C となって隙間ができるよね？
これもアロケータで解決できるの？

そこまで考えると確かに無理だけど、問題はOSが管理するメモリでしょ？
>>574
>>576

断片化じゃなくてパフォーマンスの問題になるね。

ただ、パフォーマンスもポインタを参照する程度だから
ぜんぜんおっけーだと思う。

なんでSTLコンテナの比較の話に
断片化の話を混ぜてるやつがいるんだ？

>>595
Bはまたすぐに使われるだろ
「固定長なら」という条件ならな

>593
確かに１でメモリプール全体がキャッシュに入りきらない場合、リストを先頭からなめるだけでも、
あっちこっちにアクセスしてキャッシュミス連発する可能性があるから、地味に効いてくるかもしれない。

ID:1NV1OMlGの断片化の定義待ち

そんなに、わからないならSTL使わなきゃいいじゃん

飲み過ぎて頭が痛いぜ。いや待ってくれ、
俺は元々「STLのlist使うなら、普通は断片化なんか気にしないだろうよ」っつう立場なわけよ。

俺がコーディングしてた頃は、断片化を考えたときに、STLのlistを改良して使うっつう考えは無かったしな
（そもそもそんな選択すら出来なかったが）。キャラ数なんざ決め打ち頭打ちだ。

なので、俺が勝手に定義しても良いが、それより>>545に聞いた方がいいんじゃね

ここまでのまとめ：配列で済ますのが超COOL

>>551 ： 「そりゃ、お前のバグだろｗ 」
>>552 ： 「お前のバグだろ」には同意。」

　　　 　ｒ ⌒ヽ
　　　　　(´ ⌒｀)　ﾎﾟｯﾎﾟｰ !
　　 　 　 　 l l
　ｶﾀｶﾀ　∧＿∧　　／￣￣￣￣￣￣￣￣￣￣￣
　　　　 （・∀・＃）＜　 くっそーもうあったまきた！
　　 ＿|￣￣||＿）＿＼＿＿＿＿＿＿＿＿＿＿＿
　／旦|――||/／ ／|
　|￣￣￣￣￣|￣| . |
　|＿＿＿＿＿|三|／

おまえだったのかよｗ
なんだこのカイザー・ソゼ以来の意外性

ちょｗｗｗｗ

一晩寝て頭を冷やして学校行って頭シャッキリして帰ってきた。
スレ読み直したんだが、やっぱりまた頭に来た！くっそー！！
　
昨晩色々書いたけど
　
> 大昔(フラグメントとか馬鹿にならなかった頃)
　
これ。ここ。これがどういう条件下の話なのかやっぱり理解できん。

ちなみに、俺が知ってる大昔てのはWindowsMe以降の世界。
あと、GBSDKは触ったことあるのでそういう環境下の苦労は
ほんの少し理解してるつもり。

s/GBSDK/GBDK/

まてまてまてｗ
>>551に怒ってるのは解ったけど、>>543は>>551じゃないぞ？

「くっそー、こうなったらみんな敵だ！」という厨房の発作です。

私です。

>>611
ことの発端はあんたのvectorでしょうーがっ！ｗｗｗ

って、>>545なら言いだしっぺ違うわな。
ID変更は鬼門だ・・・

うん、551は俺じゃないね

>>607
学生さんか、てっきり同世代かと。いや昔のコンシューマ機の話よ。Meとかですら無かったりで。
STLどころかC++が笑い話で、恐ろしく少ないメモリをやりくりしてたような。もう守秘義務もないかね。

しかし煽る気はなかったんだが、随分気分を害したらしいな。
ここはひとつ、上手いlistのアロケータを書いて締めるってのはどうよ。俺が知りたいだけだが

で、俺は>>585で書いたとおり、やり方に落ち着いちゃってるんだけど
それ以前は弾を双方向リストで管理してたんだ。

そんときの自前アロケータは内部に2048発分の配列。
それと破棄リスト（要素番号256単位でバケツ分け）。
　
弾を破棄するときはその要素番号が帰るべきバケツにポイ。
弾を発行するときは、バケツを若い順に調べる。
（バケツは自分に弾が何個入ってるかの情報を持ってる）
中身の入ってるバケツを発見したらこいつから弾を取り出して使う。
　
このやり方でメモリプール内の使用状況を可視化したら
弾発行数の増減が激しいと
後部に虫食い（フラグメンテーション？）が発生するけど
配列全体に虫食いが発生することは防げた。
　
で、次にこれがオナニー実装かどうかを知りたくなった。
配列全体にわざと虫食いを起こすアロケータを作って比較した。
パフォーマンスはほとんど変わらなかった。

この過程で、弾ごときに双方向リスト使ってガンバっても
くだんねーな。必死なのって流行じゃないよね。もてないじゃん。
リストノード用に余分なメンバ変数増えるのももったいねーし。
もう配列でいいや。という心境になり、>>547の言ってるような実装に
発見的に行き着いた。
　
これを思いついたときは
「すんげー俺って天才？ｷﾞｬﾊｰｶｯｹｰｗｗｗｗｗ」
と思って我が世の春を謳歌しようかなと考えた。
でもWEB上でこんなの↓発見して
　
http://www.aya.or.jp/~sanami/peace/#CODE44
　
あーやっぱ既知のテクなんだ。と知った。

素人がメモリアロケータ作っても無駄。それどころか、状況が悪化するだけ。

ゴキブリを殺すのにショットガンは要らない。

>>618-619
無駄、状況が悪化する例は？
それだけじゃ、煽りにしか聞こえない。

・メモリの断片化は、自前アロケータである程度防げる。
・listとvectorの検索のオーバーヘッドはどうやっても防げない。

>615
STLのアロケータとしての要件を満たしてないけど、boostのpoolなんかはどう？
もっと単純なのがありそうだけど探すのがめんどくさい。

>>615
俺の気分は気にしなくていいです。
守秘義務を盾にはぐらかされるのはちょっと納得いかないけどね！
（相当する公知のハードウェア環境で説明できるはずだしね）

>>620
例だと？

お前がもしメモリアロケータを作っていたら、それが例だ。

あのさー、固定長のメモリプールなら超単純実装だから
誰が組んでも大した差はでねーよ。

じゃあアップしてみろ。

どれだけ悪い例か指摘してやるよ。

アップされないのは目に見えてるときしか強気になれないなんてぷぷぷー

はぁ？

>超単純実装だから

とか言ってる奴がアップもできないなんてアホ話があるか。

すまん

WJoYJdwqの明日のレスを大胆予想。

>>626 ： どれだけ悪い例か指摘してやるよ。
>>629 ： すまん

　　　 　ｒ ⌒ヽ
　　　　　(´ ⌒｀)　ﾎﾟｯﾎﾟｰ !
　　 　 　 　 l l
　ｶﾀｶﾀ　∧＿∧　　／￣￣￣￣￣￣￣￣￣￣￣
　　　　 （・∀・＃）＜　 くっそーもうあったまきた！
　　 ＿|￣￣||＿）＿＼＿＿＿＿＿＿＿＿＿＿＿
　／旦|――||/／ ／|
　|￣￣￣￣￣|￣| . |
　|＿＿＿＿＿|三|／

>>624
なるほどな。わかった。俺の実装が悪いわけだな。

で、おまえはどうしてるんだ？
まず、自前のアロケータを使っているのか、いないのか明確に答えて貰おう。
話はそれからだな。

今の時代にアロケータを自作するのはただのバカ。

そうか。バカ、と言える理由は？理由が無いなら話にならん。

だから、お前のメモリアロケータが理由だって。本当に頭悪ー。

>>632
うそー。弾1個に1new？ｶｯｹｰ

VvPaAfBSが馬鹿なんやない
VvPaAfBSを見るlosLwqMAの心が馬鹿なんや

>>635
アホ解釈来たな。まぁ1弾に一回newしても問題ないが。

それよりお前はさっさとアップしろよ。

>>634
それは理由になってない。

メモリリークが発生しやすくなるとか、速度が遅いとか
そういう理由じゃないと納得できない。

>>637
ところで、newを使わないなら、STL使ってないわけだな？
弾の管理はやっぱ順序なしリストなわけ？

今、即席で弾1個に1newタイプの実験プログラム作って
自作メモリプールと比較した。俺のメモリプール勝った。寝る。

今、即席で日本代表チームを作って
ワールドカップに出場した。日本が優勝した。寝る。

うｐしたところで「車輪の再発明はするな」パターンだなｗ
こんな池沼は構わないほうがいい。

メモリープールなんて言葉を勝手に作るな。世の中には、
ガーベージコレクションという概念が既に存在している。
メモリー管理を考えるなら、誰もが一度は通る道だ。あと、
メモリーの断片化に関しては、フラグメンテーションで調べてみ？

Windowsの場合は、GlobalAlloc()でGMEM_MOVEABLEを使えば済む問題やね

>>638
>ところで、newを使わないなら、STL使ってないわけだな？
はぁ？バカかコイツ。newを使わないとかダレが言ってんだ死ねよ。

>>639
はいはい、作ったけどアップは出来ないと。
ドアホ。やってもねーのにやったふりすんなボケ！

>>642
>メモリープールなんて言葉を勝手に作るな。世の中には、
>ガーベージコレクションという概念が既に存在している。
メモリプールという言葉も世の中に既に存在しているけど。
お前の世界は一体なんなんだ？

>メモリー管理を考えるなら、誰もが一度は通る道だ。あと、
前の文章とまったく繋がっていない。なんの道も提示されていないし。

>メモリーの断片化に関しては、フラグメンテーションで調べてみ？
なんだコレ。過去最高のアホ発言を見てしまった。
フラグメンテーションに関しては、メモリーの断片化で調べてみたら宜しいかね？

>Windowsの場合は、GlobalAlloc()でGMEM_MOVEABLEを使えば済む問題やね
弾一個にそんな糞重いの使ってられるか。死ね。

クールにいこうぜ

ここまでのまとめ：配列で済ますのが超COOOOOOOOOL!!




苦労していろいろ知識を獲得したんだろうし、
それに対するこだわりがあるのは認めるが、
あんま最適解でもない手法でｇｄｇｄするのはどうかと。

可能な限りシンプルな方法を取るべきだ

>>644
>アホ解釈来たな。まぁ1弾に一回newしても問題ないが。
ということは、お前の場合は弾にnewを使わないと暗に言ってるだろ。

>はぁ？バカかコイツ。newを使わないとかダレが言ってんだ死ねよ。
結局どっちなんだよｗｗｗ

おまえがどの方法を取っているか解らないから
弾の管理をどうしているか聞いているんだよ。

>>647
俺も配列がいいと思うが、もしかしたらID:losLwqMAが画期的な方法を使っているかもしれないだろう？

ID:WJoYJdwq
ID:losLwqMA
ID:VvPaAfBS
この中でさっさと寝た(振りしてる)ID:WJoYJdwqが一番マトモに見えるメルヘン。


お前等煽るのに夢中になって議論に向いてないからROMマジおすすめ。

なんかもうム板でやってもいいような内容になってる気がする。

一体どの辺が発端か、ざっと戻ってみたけど >>536->>542 あたりか？
「（とりあえず最初は）配列とforループで何とかすればおｋ」って回答すれば十分なレベルの質問に見えるけど・・・

"末尾で穴埋め式vector" vs "list" については、
vectorの、末尾の値を移動することで処理順序が変化する問題と
listの、各ノード情報(prevとかnextとか)を持つ手間を秤にかけるとして、
他のノードとの相関のない、ただの弾なら前者でいいんじゃないの？
断片化うんぬんはどうにでもなりそうね。

一夜明けたら部外者に

>>623
いやいや、はぐらかす気は無いんだけど、こっちの話になると折角の流れが変になるぜ。
締めといった以上、616への突っ込みは避ける。乙。

で、615に書いた通りなのよ。メモリが恐ろしく少なかったから。難しい話じゃない。
適当にやってると、すぐメモリ取れなくなって止まるのよ。Win機の話じゃないぜ。
たぶん今のコンシューマ機でも、全くメモリ断片化は気にしない！なんて所はまず無いんじゃないかね。

コンソールプログラムをＣ++言語でやっているのですが…
Ｃ++言語でどうやったらゲームを作れるんでしょうか？
ライブラリを利用するしかないんでしょうか？

ライブラリ利用してそれで絵が出るならおｋ

S　　サッと
T　　Throughして
L　　楽になろう

>>652
流れを補足しておくね。

"vector" vs "list"
ここではvectorの最後尾以外のpop&pushが問題点となる
↓
"vector" vs "自前アロケータ list"
ここではlistのノード作成時の断片化が問題点となる
↓
"末尾で穴埋め式vector" vs "自前アロケータ list"
おそらく一番COOLと思われる。キャッシュ部分でもlistより有利。

流れぶった切って>>618 >>632
ID:losLwqMAは弾の処理以外の話も含めて言っているらしい？

いまここ。
メモリ管理に関して割と有益な話が聞けそうなんで、自分としてはスルーしたくないｗ