《目的》
衝突シミュレーションプログラムを組みたいです。
・長方形内に球を任意個数を生成し、それぞれに方向と速度を持たせる
・とある時間が経過した後の位置を計算する
(ビリヤードシミュレーションのようなプログラムを想定)
《思考途中の案》
1)経過時間後の球のベクトルを計算し、ベクトルをリストに登録
2)どれか一つのベクトル(Aとする)を選ぶ
3)ベクトルAと最初に交わる他のベクトル(Bとする)を調べる、交わらないならば2へ
4)Bのベクトルが最初に交わるベクトルがAでないならばBをAに置き換え3へ
5)A、Bのベクトルの衝突後のベクトルを計算し、ベクトルリストに登録する
6)交わるベクトルが無くなるまで2へ
《問題点》
球の個数が少ないうちは総当り的なロジックでも良いが、多くなると計算量が増えて重くなる(万単位)。
そこで、参考になる効率の良いアルゴリズムはないでしょうか?
実装しているサンプルなどありましたら、教えてください。
また、このような問題についてマルチスレッドで処理する方法などありますか?
C、C++、C#、Javaのサンプルですと嬉しいです。
よろしくお願いいたします。
こちらの「ボールの衝突運動のシミュレーション 」が参考になるかと思います。
アルゴリズムの考え方と、C++のサンプルコードが公開されています。
この問題は hard sphere とよばれ計算物理の分野で50年の歴史があります。
メトロポリスアルゴリズムを最初に適用された問題でもあります。
まずはアルゴリズムを「イベントドリブン」にして、コメントにもあるようにセル構造を使うのが定石です。
以下に解説とコードがあります。
英語の文章は読むのに少々時間がかかりそうです。
また、コメントもありがとうございます。
じっくり読ませていただきます。
ご解答ありがとうございました。
ある程度参考になりました。
しかしサンプルのソースでは、単位時間内で複数回の衝突は計算しない事になっているようです。
引き続き、良いサンプルやアルゴリズムがありましたら教えてください。
ご解答ありがとうございました。