- 1 名前：名前は開発中のものです。 mailto:sage [2007/02/02(金) 12:44:13 ID:ep4hr9qd.net]
- わからなかったらここで聞けばいいじゃない
なるべく詳しく日本語で質問してね
- 191 名前：名前は開発中のものです。 mailto:sage [2021/06/29(火) 08:48:54.68 ID:5rduNUaF.net]
- 昨日は、上手く説明が書けなかったので反論しなかったが、整理できたぜ。朝風呂ってすげぇなｗ
ここで考えないといけないのは、ツリー構築コスト。
N個の物体のツリーを作成するのに必要なコストは、O(N logN)だ。（合ってる？）
N個「同士」の当たり判定をする場合、
総当たり‥‥ O(N^2)
ツリー‥‥ツリー構築に O(N logN)、当たり判定で O(N logN)。
総合で O(N logN)になるので、Nが大きい場合はツリーのほうが圧倒的有利
ここまでは、お互いに、大きな認識相違はないと思う。
一方、N個と自機（1個）の当たり判定の場合は、
総当たり‥‥ O(N)
ツリー‥‥ツリー構築に O(N logN)、当たり判定に O(1 * logN)。総合でO(N logN)になるはず。
これが、ツリーなんて作らないで総当たりでいいんじゃね？の根拠だ。
（ツリー構築コストのオーダーが間違ってたらすまん）
- 192 名前：名前は開発中のものです。 mailto:sage [2021/06/29(火) 08:51:54.02 ID:5rduNUaF.net]
- つまり、
>毎フレーム10000回と毎フレーム7回は全然違う
この書き方に倣うなら、
総当たりが毎フレーム100回に対して、ツリーは毎フレーム350回+7回、ってこと
- 193 名前：名前は開発中のものです。 mailto:sage [2021/07/27(火) 16:16:55.84 ID:xy40X6uH.net]
- 反論が来ないので、自己反論でもするか。
190は、敵が多数vs自機１機の場合だけど、
自機だって、当たり判定が必要な弾を撃つ。
敵100機と自機＋弾２発の場合
総当たり＝100*3=300回、ツリー＝350+7*3=371回（総当たり有利）
敵100機と自機＋弾３発の場合
総当たり＝100*4=400回、ツリー＝350+7*4=378回（ツリー有利）
ツリー構築コスト350ってのはツリーに有利に設定した値だけど、
10発も弾を撃てればツリーのほうが確実に有利になる。
（自弾と敵弾の当たり判定が不要なら、総当たりがもうちょい有利になるけど）
とはいえ、10,000回の当たり判定をやったって 1ms〜2ms程度（俺の7年前のLetsNoteで計測）
自機がべらぼうに弾を撃つんじゃなければ、どっちでもいいやｗ
- 194 名前：過去ログ ★ [[過去ログ]]
- ■ このスレッドは過去ログ倉庫に格納されています
|
 |
