弾が最大300発、敵が最大60体。総当たりだと毎フレーム18,000回の距離くらべになります。これは減らしたい。
素直な手は「画面をマス目に区切って、弾の近くのマスにいる敵だけを見る」です。書いて、測って、遅くなりました。
16倍
切り出すと速い
100ms → 6ms
7倍
ゲームの中では遅い
1ms → 7ms
1,200
切り替える境目
弾 × 敵
0件
結果の違い
5つの種で突き合わせ
まず、切り出して測った
マス目だけを取り出して、敵の数を変えながら測ります（弾300発・200フレームぶん）。
敵数 弾数 総当たり(ms) マス目(ms) 60 300 100 6 150 300 210 9 400 300 382 17 1000 300 420 28 3000 300 501 62
数字だけ見れば、マス目の勝ちです。敵60体でも16倍、3000体なら8倍。ここで満足して差し替えると、次の落とし穴に落ちます。
ゲームの中では負けた
同じ実装で、実際の1プレイ（30秒ぶん・同じ種・同じ入力）を回して測ると、逆転しました。
マス目（7ms）
- 敵が消えるたびにマス目を作り直す
- 作り直しは「全部のマスを空にする」ところから
- 敵が数体しかいなくても、その手間は変わらない
総当たり（1ms）
- 実際に出ているのは数体〜十数体
- 弾も20発前後。かけ算しても数百回
- 下ごしらえが要らない
理由ははっきりしています。切り出した測定では、敵が消えません。実際のゲームでは、弾が当たるたびに敵が消え、並びが変わり、マス目は作り直しになります。
速くするための下ごしらえが、いちばん多い場面で毎回捨てられていた。
直し方：捨てずに、数で選ぶ
マス目が悪いわけではありません。数が増えれば逆転することは、切り出した測定で分かっています。そこで両方を残し、その場の数で選ぶようにしました。
bool useGrid = Mode == HitMode.Grid ||
(Mode == HitMode.Auto && _shotCount * _enemyCount > GridThresholdPairs);
境目の 1,200 は実測から決めた数字です（この機械で、総当たり1回ぶんの手間とマス目の下ごしらえが釣り合うあたり）。
片方を消さない
速くするときに古いほうを消してしまうと、比べる相手がいなくなります。残しておけば、数が変わったとき・機械が変わったときに測り直せます。残すコストは、このゲームでは数十行でした。
結果が変わっていないことを、テストで固定する
速さのために実装を変えたときに怖いのは、答えが変わることです。当たり判定は「どの弾がどの敵に当たるか」なので、少し違うだけでスコアが変わります。
そこで、同じ種・同じ入力で1プレイぶん回し、結果を文字にして突き合わせています。
return $"点{battle.Score} 撃破{battle.Kills} 敵{battle.EnemyCount} 弾{battle.ShotCount} 残機{battle.Lives} 時間{battle.Time:0.000}";
[Test]
public void 総当たりとマス目で結果が同じ()
{
for (int seed = 1; seed <= 5; seed++)
{
Assert.That(Play(HitMode.Grid, seed, 40f), Is.EqualTo(Play(HitMode.BruteForce, seed, 40f)), $"種 {seed} で結果が違う");
}
}
マス目にすると、見つける順番が変わる
- 症状
- 同じ場面なのに、当たる敵が入れ替わって点がずれる
- 原因
- マス目は「近くのマスにいるもの」をまとめて返すので、総当たりの「添字の小さい順」とは違う順で見つかる
- 対処
- 返ってきた候補のうちいちばん小さい添字を採る。これで総当たりと同じ答えになる
下ごしらえの回数を数えていない
- 症状
- 1回あたりは速いのに、全体では遅い
- 原因
- 対象が消えるたびに作り直していると、1フレームに何度も下ごしらえが走る
- 対処
- 作り直しが必要になった回数も測る。減らせないなら、その規模では使わない
まとめ
- 切り出した測定は上限の目安。実際の場面では前提（消える・数が少ない）が違う
- この規模（敵が数体〜十数体）では、総当たりで足りた
- 速くした実装は捨てずに残し、数で切り替える
- 実装を変えたら、結果が同じであることをテストで固定する