進捗状況(2012/12) - FPSを作ってみる@wiki

(2012/12/31)

とりあえず動画

年内デモは厳しそうなので動画で誤魔化す方針。
http://www.youtube.com/watch?v=ARMti2JIi_M

速度の問題

前回から凸形状の重なってる部分を求めるアルゴリズムに対して
安易に動的リストやnewしていた所を固定配列やデータ構造を工夫することで高速化を図った。
これによりデバッグ時1ペア10msかかっていた箇所が4.5msに改善。
リリースビルドでは1ペア0.5ms程度。
まだ最適化してない部分が半分あるのでもうちょっと改善できそうだ。

力の発散

皆無ではないものの、箱が凄い勢いで吹っ飛ぶ現象（発散）はほとんど解決。
もちろん仕様上どんな物体でも大丈夫という訳にはいかない。

例えば小箱のはるか上空から数倍以上あるデッカイ箱が落ちてきて下敷きになった場合、小箱の逃げ場がないので力が発散する。そっと置くだけなら大丈夫だが。

1cmの薄い板で密度が発泡スチロール並みといった非現実的な設定にすると
現実では力が加えられれば単に折れるだけだが、シミュレーター上では
「絶対に変形しない剛体」という制約を守るために物凄い加速度が加えられ、これも吹っ飛ぶ。

あとは高速で小さい物体が衝突するなど、場面場面じゃどの方向に物体を逃がしていいのかわからないなど更新レートに起因するケース。
これは更新レートを上げれば解決できるがゲームという性質上難しいか。
そもそもそういう状態を作らないのが一番である。

パラメータの調整の仕方とかコツがちょびっとだけわかってきた。
来年初週にはデモ上げたい。

(2012/12/28)

途中経過

年明けまでにはデモ上げたいんだけどねー
シャドウマッピングと物理演算の。

こんな感じで資料を片手に延々と作業している。静止画じゃわからんが。
流れとしてはVerocityVerletで積分計算、GJKで衝突判定してMullerのアルゴリズムで凸物体の共通部分を割りだし、
その体積に応じて抗力と摩擦力を加えるという物。いわゆるペナルティ法。
昔からある点接触で全部扱う方式と違い重なった体積に応じて力をかけるから
よく問題として挙げられる「箱を積み上げると振動が収まらない」等の現象は少なくとも今の所ない。

まーこんな事やってるとやれ「quickHullライブラリ使えよ」だの「Bulletでいいじゃん」だのと茶々が入るんだとは思うが
主に目的が数年前に挫折したリベンジということもあるし
修正を繰り返した甲斐もあって現時点で割と動いてるから気にしない方針で。
もちろん最初は例の如く箱がめり込んだりあらぬ方向に吹っ飛んだりで散々だったけど。
3度目(4度目？)の正直で今度は絶対完成させる。

課題

残る課題は動作速度とスプリング & ダンパ係数の調整、それと
これは何か計算間違えてるんだと思うが摩擦力が異様にかかる時がある。
箱が床の上を右に滑って行ってるとしたら突如床が物凄い速度で左にスライドしたかの様に箱が横転したり。
スプリング係数の調整はまぁ、ゲームだから適当にそれっぽく取り繕えばいいだろう。

一番の問題はとにかく遅いという事。
デバッグビルドにて普段は影描画を入れて45fps程度出ている所が
箱の衝突計算1ペアにつき10msもかかっている。これではテストにならない。
箱を10個くらい出して最低限ゲームとして成立するレベル(20fps)を保って貰わないと。
その為には1ペアで2ms以下に抑える必要がある。

という訳でまずはちょっと部分部分のパフォーマンス計測を行ってみた。
全体を10.34msとすると
0.02ms: 接触凸形状の中点の算出
0.32ms: 接触平面の算出
5.08ms: 接触凸形状の算出
5.00ms: 接触凸形状を3角形ポリゴンに分割 & それぞれ抗力計算

こんな感じだった。接触凸形状の算出が重そうなのは薄々感じてたけど3角形ポリゴンの云々が重いのはちょっと意外。
もう少し詳しく調べる必要がありそうだ。

まず思いつくのは手抜きで動的リスト使ってる所を固定配列にして、
3角形を平面で分割するルーチンを多角形クラスのメソッドで代用してる所を3角形専用で書き直す。
あと色んな箇所で重いアサート処理かましてるのを外す。
そんなとこかね。

(2012/12/20)

続 コリジョン

ゲームの要であるあたり判定について本腰を入れるので暫くはそれ関係の話が続く。

前々回にOcTreeを使うと書いた気もするが
そこそこ複雑なマップのポリゴンと何か物体をあたり判定したいとなった場合、
マップ専用のOcTreeに全てのポリゴンを登録しておくという手も悪くはないんだが
終始動かないとわかっている物に
いわば「多少の判定効率を犠牲に更新の手軽さを手に入れた」OcTreeもどうだかなぁという気がしたので
今日はBounding Volume Hierarchyについて調べていた。

ググって出てきた資料の中で図をふんだんに使用していて特に分り易かったのがコレ
http://www.gris.uni-tuebingen.de/people/staff/jmezger/papers/bvh.pdf
プレゼン資料なので英語はさして問題じゃなかろう。

言ってみれば境界ボリュームを木構造にしましょうねというだけの話ではあるが、
これが中々奥が深い。
Discrete oriented polytopesなんて前に何かの図で見かけたっきり名前を知らなかったけど更新早そうだし便利かも。
Swept Sphere Volumeは全くのノーマーク。これどうなの。速いんだろうか？

あたり判定は描画とかと同様、凝り出すとキリがない世界だねぇ・・

結論

変形や移動など、動的なオブジェクトはOcTreeで。
静的な地形はAABBを使ったBVHで行こうかと思っている。
というのも
http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.100/institut/Papers/QBVH.pdf
QuadTreeによるAABBのBVHではSSE命令で倍近く高速化を図れるようなので。

そんな訳で最低動作環境にSSEが必須になる予定。PenIII以降なら載ってるしいいよね？

(2012/12/20)

BSPの分割基準(sourceの場合)

前回「DoomIIIエンジンだとポータルが手動設置で～」などと書いたがじゃあ他のエンジンは？と思い
sourceエンジンのゲームでワイヤーフレーム表示にしたりnoclipで飛び回ってざっと挙動を確認。
ポータルを可視化するチートコードが無いのか、又は調査不足なのかわからなかったので
表示の切り替わりを見ての憶測だが結構細かくセルが作られている。
また、本来は分割する必要のないところでポリゴンが分割されている（多分BSPの過程でスライスした）箇所も見受けられた。
少なくとも手動ではなさそうだ。

四角い部屋なら最初に四角く基本形状を作って、柱とか瓦礫の細かい装飾物は通常のモデルとして置く感じかねぇ。

マップエディタはある程度の幅のグリッドにスナップさせる物が多いようだけど
あぁあれは微量ずつ横に位置がズレてる壁を何枚も作るとポリゴン分割が起きまくる関係で
そうなってんのか！等と勝手に合点したり。

つーか憶測で書くくらいなら実際に何かマップ作ればいいじゃんと言われそうだが。
本当に思いつきだったので。
―――ま、それはともかく・・

コリジョン

衝突判定ってまだゲームができてない段階でテキトーに総当たりしてる分には簡単だけど
本気でやるとすれば洞窟物語（ふとタイトル名が出てきただけ。他意は無い）みたいに
「ボスも主人公も弾丸も全部矩形でやる」とか割り切らないと厄介だね。
同人2.5Dシューティングなんかでも「球とカプセルオンリー」だったりして。

何が言いたいかといえば不用意に衝突形状を増やすと簡単に組み合わせ爆発するという事。
自分が正にこの状態で今組み込んである形状を列挙してみると
<球、カプセル、円柱、円錐、線分、レイ(半直線)、直線、視錘台、凸物体、3角ポリゴン、OBB、AABB>
他に2D形状もいくつか。

計画もなしに思いつくまま追加してった結果がこれである。
視錘台て要するに四角錘だろ！円錐も四角錘で代用しろよ！AABBなんて何時使うんだ？など突っ込んでも突っ込み足りないくらい。
次回のエンジン組み直しで一掃する予定。
(1つ言い訳するとAABBは sweep and prune というあたり判定カリングアルゴリズムの名残)

そして現状

前回からの進捗。

• 凸物体同士のあたり判定を行うGJKアルゴリズム
• 凸物体がどれくらいめり込んでいるかを調べるEPSアルゴリズム
• 凸物体が重なっている領域を求めるMullerのアルゴリズム
• 複数の点座標が与えられた時にそれらを含む最少の凸形状を求めるQuickHull
• Velocity Verlet法により速度と回転を数値積分するクラス
• 球、ボックス、凸形状のサポート写像ルーチン

これらを実装。

もう何を意味するか分かった人も多いのではないか？
続きはまた今度。

そして久々に専門書が欲しくなった。
Collision Detection in Interactive 3D Environments (Series in Interactive 3d Technology)
という本。
ちょっとしたあたり判定くらい出来るプログラマになりたい。

(2012/12/13)

本格的に衝突判定をする

衝突判定関連をやっているので今回はスクリーンショット無し。残念。

今まで「どうせそんな規模作れないだろ」と微妙なネガティブ思考で総当たりしていた
衝突判定だが、いよいよゲームとして動かすにあたって本格的に取り組む必要性を感じた。
といっても衝突判定なんてそれこそゲームのジャンルに依存する。
例えば2Dのターン制シミュレーションやパズルゲームとかだったら普通に総当たりで構わないと思うし
アクションでも今どきのCPUだったら力任せに行けそうである。

で、自分が作ろうとしてるのはFPSと2.5Dシューティングな訳だが
シューティングなら100や200の弾幕は当たり前だしFPSは敵の数こそ数十体と少ないものの何分、3Dなので
たとえ判定用の簡易モデルを使うにしても無駄な判定は極力避けたいのである。
従って何らかの機構で衝突の可能性が無い物体はバッサバッサと刈って行きたい。

3Dの空間分割？

とりあえずメインはFPSなので用途をFPSに絞って考える。
自分の場合、FPSといえばまず浮かぶのはBSP(Binary Space Partition)である。
こいつは空間を任意の平面（quakeとかだと部屋の壁で区切る）で2つに分けていって木構造にしたもの。
そしてBSPの木から作られるのがPVS(Potentially Visible Sets)という、凸空間(セル)とそれらを繋ぐ出入り口のような平面の凸ポリゴン(ポータル)がやはり木構造で繋がった代物。
一応4年前の動画でやってたりもするがそれはさておき。

PVSは通常、視点の位置からどのセルが見えるかを判定するのに用いられるが
よくよく考えればPVSの各空間はそれを構成する平面リストを持っている訳で
ある座標や線分がそれらのすべて表側に位置すればその空間にあるという事がわかり
更にポータルによりどの空間からどのくらい見えているか（射線が通るかなど）判定できる。
実際、quakeなど昔のFPSはこれで効率的に処理していたようだ。
しかし・・

BSPを作る時に部屋の壁で区切ると書いたが部屋の壁が複雑すぎると細かいセルとポータルが大量生成され
結果として描画・衝突判定両方のパフォーマンスが落ちる。
多分壁の選定でそれなりの工夫はしてたんだろうけど。

自分はどうしたかといえばマップ全体を大まかにに包むBSP用ポリゴンを別途定義してそれに沿って
表示用ポリゴンを分割して・・とやっていた。
ただこれだと上記の「セル内にあるかを平面リストで判定」という手は使えず結局セル内の
ポリゴン全部と総当たりという。効果なしとは言わんけど非常に微妙。
ちなみにDoomIIIではvisportalというbrushを手動で設置するようだ・・・モロだねぇ

御託はともかく

作ろうとしているFPSはローグライク、すなわちランダムマップと決めている以上
人手でポータルを設置するのは無理。
いや、マップパーツの組み合わせオンリー & 断面は垂直などと決めていれば別だが
別のマップ生成法も試したい関係上。

表示については前述した別途BSPポリゴンを定義する方式(PVS)で行くと思う。
どうやって大まかに包むかはまたちょっと考えなきゃイカンけど後で悩む事にする。

で、衝突判定は単純に8分木(OcTree)とする。
「8分木を使います」と言いたいが為にこんな長々と書いてしまって遺憾。

(2012/12/06)

SixSpotlights

本当は昨日できてるハズだったんだが。色々あって今日になった。
まぁ、フツーの全方位ライトっすな。線形なので綺麗に影が出ている。
今回はキューブマップでもなくバーチャルキューブでもなく、SixSpotlightsという手法。

キューブと何が違うかといえば使用する深度テクスチャは2Dで一枚のみ。
深度描画して、(Deferred Lightingなので)ライトバッファにステンシルで範囲を限定して書き込む。
これを6方向分繰り返す。勿論視界に入ってない方向は無視。
1方向で「深度、ステンシル、ライティング」と3回描画コールがかかるので回数自体キューブと比べ増えてしまうが
各々の処理は軽いものばかりなので全体としてはそうでもないだろう。多分。
少なくとも無理にDualParaboloidとかポリゴン数増やすよりマシかと。

それに、キューブでは各サーフェス同じ解像度だがSixSpotlightsでは好きなように設定可能。
遠い場所なら解像度低くする事でいくらか高速化できるし
サーフェスも一枚しか要らないのでメモリ節約にもなっている。
そんな感じ。

もしかして今どきのゲームってみんなコレだったりするんだろうか？

(2012/12/03)

umm....

ついでにvariance shadowにしてみた。微量のライト漏れや影が丸くなってるのは仕様。
それはいいが・・

分割平面の方向と壁の角度によって相変わらずWTF!?な状況は存在する

もう無理。更にポリゴン数を増やせば改善するが描画コール削減の為だけに
これしきの部屋で1万ポリゴンとか使う位なら素直にキューブマップした方がもう少し効率的なカリングも出来るからマシ。
何が一番我慢ならんかって「安定しない所」だ。
光源の位置によって影が綺麗な時と酷い時があるのなら安定してそこそこの品質が良いに決まってる。

やはり諦めが悪いのと努力の才能は別だと実感。早々に切り上げていれば時間も節約できたろうに。
デモの為に一応残しておくが本番では捨てる予定。環境マップになら使えるのかねぇ？

とすれば前にやったVirtual Cubemapか？いやいや。それも何か芸が無いだろう。
じゃあいつぞやのSix Spotlightsか？

...
影の為にと色々やった挙句、全て裏目に出てる