たくさんの敵の処理

Hey, Scripting Guy!のコラムが楽しくてそっちばかりずっと読んでた。
でも、先週CUI童貞を卒業したばかりなので、PowerShellを有効に使ってるとはいえない。
繰り返し動作は積極的にCUIに任せて行きたい。

閑話休題。

リアルタイム処理なアクションゲームにおいてパフォーマンスは非常に重要だ。
速度こそ命である。
現在MyGameは以下のような問題を抱えている。

・だいたい自機・敵機・弾合わせて500個くらいが限界
・敵機が自機を捕捉した状態だと50～100個くらいが限界
・捕捉すると敵が自機周辺に密集するので50個ぐらいで60fpsを割る

このパフォーマンスはIntel® Core™ i7-960でデバッグモードで実行したときのもの。
その環境で動かないゲームなんて現状産廃にしかならない。

まだ、実際に処理時間を計ったわけではないので計る必要がある。
しかし、だいたいの改善方針を立てた（実のところ実際に計るのが面倒だったため、方針ばかり考えていた。

前提として、敵が適切に分散・停止していれば１万個でも問題ないというのはBox2Dを使い始めた初期に実験して確かめた。
大事なのは不要な処理をしないことと、大きな処理でも1/60秒以内に必ず結論を出すことだ。
この２つはまったく別のアプローチなので分けて考える。

不要な処理をしないというのはヒューリスティクスな問題だ。
いくつか不要と思われる処理がある。

明らかに遠くにいる敵が毎フレーム自機を探索するのは（プレイヤーの体験として）無駄である。幸い自動生成された迷路は部屋ごとの関係性を出力しやすいので、同じ部屋にいる者同士のみが探索を行ったり、少し拡張して探索範囲は隣の部屋まで、といったこともできそう。
現状、近くにいる敵の探索方法も効率的ではない。しかし、機能も充分とはいえないので改善するにはまだ早い。
Box2DのBullet処理も悩みの種だ。Bulletは弾同士がすり抜けないように弾道を再帰的に計算してくれるのだが、当然これが重い（自作するよりも遥かに効率的で素晴らしいのだけどね）。どれくらい重いかというと、経験的には同じ処理時間なら8倍くらい物体の密度に差が出せる。特に密集するとヤバイ。敵に密集させないように行動させるか、Bulletを外すか、敵の数を減らすか、という問題になる。これは一番目の答を選びたい。Box2Dは物体が物体にめり込んだ場合、物体の中心点同士の関係に応じて斥力が働いて上手く距離をとってくれるが、中心点が重なると（充分に近いと）くっついてしまう。深刻なバグというほどでもないが、発生頻度は決して低くないし、Bulletを外すとこの現象はさらに発生しやすくなる。しかも一度発生すると「宇宙の　法則が　乱れる！」ので、そのb2Worldを長期間稼動させるならこれは避けたい。

あと、毎フレーム処理（出力）しないというのも大事な方法だと思う。
これはもう一つのアプローチにも関連する。

大きな処理でも短い時間に分割して処理したり、とりあえずの暫定的な結論をだす機能があればフレームレートに影響を与えないかもしれない。将棋囲碁ソフトなんかは自然にやってのけてると思う。
例えば、税金の使い方みたいにあらかじめ予算を組んで、その予算内で仕事してください、と各部署に頼むみたいに。末端の人間のやることが決まっているのでこの方法は上手く働くと思う。でも、「予算足りないのでこっちにまわしてください＞＜」みたいな自体には対応できない。だから予算の配分が何よりも重要になる。これは実際に計ってみるしか無いし、お役所が前例主義なのはシステム的に仕方ない。でも、ある程度大まかに分けたら、あとは分割しすぎないほうが資源は自然に効率的に分配される。
あと、どうやって大きな処理を分割するかという問題になる。分け方には縦割りと横割りがある。縦割りは省庁ごとの分割、描画とか衝突とかAIとか。横割りは、AIが「考えること」を時間数で分割して、前のフレームと今のフレームと次のフレームが連携して１つの問題に取り組む。

そもそも横割りが必要なほどの巨大な処理をするべきかという問題もある。処理が充分に小さければこんなことは考える必要が無いのだ。でも、100体でも1000体でも問題なく動くゲームにはこの仕組みが必要になるかもしれない。まぁ、実際には1000体になったらどうするか、という問題を末端に丸投げしているだけなのだが。仕事増えたけど、予算変わらないけど、優秀なキミタチならなんとかしてくれるよね、と頼む。そして、頼まれた側は可能な限り手抜きする。精度を落としたり、AIを単純にしたり、描画をシャギらせたり。でも、待って欲しい。はじめから手抜きが許されるなら、いままで100体でやっていたリッチな処理は無駄だったんじゃないだろうか。そう考えると初めから1000体で最適化しておけば効率的だったのではないだろうか。

これは部分最適と全体最適の問題である。1000体で最適化しておけば良かったというのは、部分最適の経験が蓄積したから全体最適の結論として言えるわけで、処理の前にはそんなことは分からなかったのである。全体最適されたシステムは効率的だが、汎用性が低い。だから問題の本質は、「そのシステムはあらゆる事態に対処すべきか否か」である。

あらゆる事態とはどんな事態だろうか。ゲームにおける事態の幅は、動くオブジェクトの数が多いか少ないかしかない。これは事前に分かることだ。PCゲームにおいては処理環境の性能不足という不測の事態もあるが、これも事前に分かることだ。

しかし、事前に分かるといってもその調整は誰かがやらなくてはいけない。手作業でやると、機能の追加のたびに調整員が死ぬ。なんという労働集約型ビジネス。こんな環境は人類のためにさっさと駆逐しなくてはいけない。

汎用性の高い横割りシステムを作って、それを少し動かした後、勝手に全体最適化してくれるシステムが文句なしに最強だ。多分既に誰かが作ってて名前があるはずだけど、知らないので調べてみよう。

あぁ、結局まだ何もしていない。