for文の高速化の為にするべきこととは？

Question

前提・実現したいこと

node.jsでブラウザゲームを作っています。今回はサーバー側の処理についてです。

プレイヤーや敵などのエンティティの処理はfor文でエンティティの数分をループしているのですが、
エンティティ同士のあたり判定や最短距離のエンティティの取得などでは、
さらにfor文でエンティティの数分をループしています。
自分のゲームではエンティティの数は推定でも1,000以上は出ると思うので、
仮に1,000回ループを行うと、1,000×1,000=1,000,000回ループしなければならない計算になります。

そこで、for文の高速化の為にするべきことを教えてほしいです。
簡潔に言えばコードの最適化、でしょうか？よろしくお願いします。

該当のソースコード

let entities = /*エンティティの情報*/;
for (let key in entities) { // 1000回(仮定)の処理
	for (let _key in entities) { // 1000回の処理 を 1000回 行う
		if (_key != key) {
			/* あたり判定などの処理 */
		}
	}
}

試したこと

######エンティティの数：50
→　FPS：55～60前後
→　ループ回数：250
######エンティティの数：500
→　FPS：5～6前後
→　ループ回数：25,000
######エンティティの数：1000
→　ほぼ動いてない
→　ループ回数：1,000,000

######※FPS・・・サーバー側のFPS

Answer 1

まず考えることは、すべてチェックしなければいけないかどうかです。遠く離れたエンティティ同士は当たり判定の必要がないので、それを省くことでループ回数が減らせます。

空間分割をしよう - Qiita

それと質問のアルゴリズムでは、エンティティ同士の無駄な比較を何度も行っています。例えばエンティティが A B C の三種類だとして、A と A の衝突判定、B と B の衝突判定は不要なはずです。また、A と B を比較した後、B と A を比較する意味もありません。1000 個のエンティティをすべて比較しなければならないとしても比較回数は 1000 × 1000 = 1,000,000 回ではなく、999 + 998 + 997 + ... + 1 = 499,500 回で済むはずです。

次に考えるのは、JavaScript でループしなければならないかどうかです。スクリプトでループするよりも、集合を扱うメソッドを使う方が一般に高速です。実際に高速になるかどうかはやってみなければわかりませんが、filter メソッドを使うことを検討してみてください。

Array.prototype.filter() - JavaScript | MDN

追記

参考：

JavaScriptで大量のオブジェクトの当たり判定を効率的にとる
衝突判定(JavaScript)

Comments

[退会済みユーザー]

確かによく考えてみたら無駄な比較がありますね。
ありがとうございます。

Answer 2

特にゲームに詳しくはありませんが、例えば、「グラディウス」のようなSTGを考える場合。

まず、第一に考えるべきは**「当てる方」と「当てられる方」のどちらで判定させるか**、です。
全てのエンティティに判定処理を持たせようとしているようですが、自機が敵弾で被弾する場合、「敵弾の当たり判定」と「自機の当たり判定」を2回こなす必要はありません。
例えば、次のロジックを組んだ場合、

• 自機が他と接触した場合、敵弾or敵機ならダメージ処理を行う(被弾処理)
• 自機が放った弾道に敵が存在したら、ダメージ処理を行う(攻撃処理)

当たり判定を持たせるのは「自機」と「自機が放つ弾道」だけで、他は不要になります。

重要なのはロジックの最適化で、「コードの最適化」はその後で考えるべきかと思います。

Re: CantRunRiver さん

Answer 3

真っ正直に「ループを高速化する」という発想では、おそらく解決できません。アルゴリズムから変える必要があります。

Comments

[退会済みユーザー]

アルゴリズムから変える必要があるということは、計算処理の高速化ということですかね？
効率を求める為にもコードを計算処理部分を一度見直した方がいいですね。
ありがとうございます。

Answer 4

「本当にforを使わなければ実現できないか」を検討するところからだと思います。
ループは便利ですが条件にそって全てループさせます。
それだけ遅いです。必要な情報を必要なだけ操作するように考え直した方が高速化につながると思います。

Comments

[退会済みユーザー]

自分的にはループは必要だと思っていましたが、まずはそこから考えたほうがいいですね。
ありがとうございます。