プログラマの方に質問です。


《目的》
衝突シミュレーションプログラムを組みたいです。
 ・長方形内に球を任意個数を生成し、それぞれに方向と速度を持たせる
 ・とある時間が経過した後の位置を計算する
 (ビリヤードシミュレーションのようなプログラムを想定)

《思考途中の案》
1)経過時間後の球のベクトルを計算し、ベクトルをリストに登録
2)どれか一つのベクトル(Aとする)を選ぶ
3)ベクトルAと最初に交わる他のベクトル(Bとする)を調べる、交わらないならば2へ
4)Bのベクトルが最初に交わるベクトルがAでないならばBをAに置き換え3へ
5)A、Bのベクトルの衝突後のベクトルを計算し、ベクトルリストに登録する
6)交わるベクトルが無くなるまで2へ

《問題点》
球の個数が少ないうちは総当り的なロジックでも良いが、多くなると計算量が増えて重くなる(万単位)。


そこで、参考になる効率の良いアルゴリズムはないでしょうか?
実装しているサンプルなどありましたら、教えてください。

また、このような問題についてマルチスレッドで処理する方法などありますか?

C、C++、C#、Javaのサンプルですと嬉しいです。
よろしくお願いいたします。

回答の条件
  • URL必須
  • 1人1回まで
  • 登録:2008/12/08 00:46:35
  • 終了:2008/12/15 00:50:03

回答(3件)

id:Mook No.1

Mook回答回数1312ベストアンサー獲得回数3912008/12/08 09:31:27

ポイント28pt

こちらの「ボールの衝突運動のシミュレーション 」が参考になるかと思います。

アルゴリズムの考え方と、C++のサンプルコードが公開されています。

http://www.asahi-net.or.jp/~UC3K-YMD/Sketch/sketch.html

id:anemoto

ある程度参考になりました。

しかしサンプルのソースでは、単位時間内で複数回の衝突は計算しない事になっているようです。


引き続き、良いサンプルやアルゴリズムがありましたら教えてください。

ご解答ありがとうございました。

2008/12/10 00:15:43
id:ita No.2

ita回答回数204ベストアンサー獲得回数482008/12/10 11:54:53

ポイント42pt

この問題は hard sphere とよばれ計算物理の分野で50年の歴史があります。

メトロポリスアルゴリズムを最初に適用された問題でもあります。

まずはアルゴリズムを「イベントドリブン」にして、コメントにもあるようにセル構造を使うのが定石です。

以下に解説とコードがあります。

http://idav.ucdavis.edu/~okreylos/ResDev/Balls/index.html

id:anemoto

英語の文章は読むのに少々時間がかかりそうです。

また、コメントもありがとうございます。

じっくり読ませていただきます。

ご解答ありがとうございました。

2008/12/10 16:58:01
  • id:kn1967
    案だけだからコメントで・・・。

    ライフゲームというのをご存知だろうか?
    その中にグライダー(一定方向に移動する)といのがあるのだけれども
    そのアルゴリズムが流用できると思う。

    ライフゲームだと衝突で変形したり合体したりしてしまうのだけれども
    ビリヤードのように反発させるようにプログラムを変えれば・・・。
  • id:practicalscheme
    私もコード例は無いのでコメントで。

    定番の方法は、空間を分割しておき、各分割空間(cell)にどのオブジェクトが居るかをトラックしておくことです。衝突の可能性があるのは自分と同じcellにいるオブジェクトだけなので、調べる組み合わせの数が劇的に減ります。また、複数のスレッドで別々のcellを調べて行くこともできます。
  • id:ita
    http://www.cs.princeton.edu/introcs/assignments/collisions.html
    プリンストン大学の宿題問題です。下の方に Cell method という記述がありますね。

    http://www.springerlink.com/content/0h5pf2gfp1hak0nr/
    これは教科書。
  • id:anemoto
    to id:kn1967
    ライフゲームについて調べてみました。
    私が求めている球の衝突アルゴリズムとは違うようでした…。
    しかしライフゲームのルールが理解できたので、思わぬ収穫です。

    コメントありがとうございました。
  • id:ita
    もし完成したら、重力も入れて、小さいたくさんの玉の中に比重が重い大きい玉を一個入れて箱をガサガサゆすってみてください。あらふしぎ、重いはずの大きい玉が上に押し出されます。「ブラジルナッツ効果」とよばれる現象です。
  • id:ita
    画像いろいろ
    http://mtrenouf.googlepages.com/simulationresults

  • id:anemoto
    to id:practicalscheme

    各分割空間はこのジャンルでは有効な方法みたいですね。
    この方法を取り入れることにより、随分判定回数が減ることが分かりました。
    ぜひ、空間分割は採用したいと思っています。

    コメントありがとうございました。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません