プログラマの方に質問です。
《目的》
衝突シミュレーションプログラムを組みたいです。
・長方形内に球を任意個数を生成し、それぞれに方向と速度を持たせる
・とある時間が経過した後の位置を計算する
（ビリヤードシミュレーションのようなプログラムを想定）
《思考途中の案》
１）経過時間後の球のベクトルを計算し、ベクトルをリストに登録
２）どれか一つのベクトル(Aとする)を選ぶ
３）ベクトルAと最初に交わる他のベクトル(Bとする)を調べる、交わらないならば２へ
４）Bのベクトルが最初に交わるベクトルがAでないならばBをAに置き換え３へ
５）A、Bのベクトルの衝突後のベクトルを計算し、ベクトルリストに登録する
６）交わるベクトルが無くなるまで２へ
《問題点》
球の個数が少ないうちは総当り的なロジックでも良いが、多くなると計算量が増えて重くなる（万単位）。
そこで、参考になる効率の良いアルゴリズムはないでしょうか？
実装しているサンプルなどありましたら、教えてください。
また、このような問題についてマルチスレッドで処理する方法などありますか？
C、C++、C#、Javaのサンプルですと嬉しいです。
よろしくお願いいたします。
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。
ログインして回答する
みんなの回答
姉本
この質問へのコメント
質問の情報
- 登録日時
- 2008-12-08 00:46:35
- 終了日時
- 2008-12-15 00:50:03
- 回答条件
- 回答にURL必須 1人1回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
同じような体験をしたことがある人はいますか？。 ある日、お葬式の職業に就きたいなあなんて話題にしてい…
匿名質問者
1
-
１９８４年から１９９０年ぐらいの間に、多分コミックボンボンに掲載されていた漫画を教えてください。 主…匿名質問者
2
-
https://hikky-mura.org/t/topic/2523/7 でsma200さんという方に戸塚ヨットスクールを勧められましたが、僕…
hayakushinene
1
-
いつも大変お世話になっています。 アスペルガー精神3級独身会社員34歳男です。 最近心身共に疲れがもの凄…hayakushinene1
-
私の彼氏は毒親育ちで、うつ病を患い、家を追い出された後ホームレスになって、現在は何故か逮捕されて留置…匿名質問者1
ライフゲームというのをご存知だろうか？
その中にグライダー（一定方向に移動する）といのがあるのだけれども
そのアルゴリズムが流用できると思う。
ライフゲームだと衝突で変形したり合体したりしてしまうのだけれども
ビリヤードのように反発させるようにプログラムを変えれば・・・。
定番の方法は、空間を分割しておき、各分割空間(cell)にどのオブジェクトが居るかをトラックしておくことです。衝突の可能性があるのは自分と同じcellにいるオブジェクトだけなので、調べる組み合わせの数が劇的に減ります。また、複数のスレッドで別々のcellを調べて行くこともできます。
プリンストン大学の宿題問題です。下の方に Cell method という記述がありますね。
http://www.springerlink.com/content/0h5pf2gfp1hak0nr/
これは教科書。
ライフゲームについて調べてみました。
私が求めている球の衝突アルゴリズムとは違うようでした…。
しかしライフゲームのルールが理解できたので、思わぬ収穫です。
コメントありがとうございました。
http://mtrenouf.googlepages.com/simulationresults
各分割空間はこのジャンルでは有効な方法みたいですね。
この方法を取り入れることにより、随分判定回数が減ることが分かりました。
ぜひ、空間分割は採用したいと思っています。
コメントありがとうございました。