- 2Dゲーム物理における剛体衝突の解決とは、すでに接触または重なっている物体が次のフレームで互いを貫通しないように、速度変化を計算する問題である
- ゲームループは毎フレーム速度とΔtで位置を更新するため、新しい位置でジオメトリが重なると、別途処理がない限り物体は互いをすり抜ける
- 衝突は単なる接触の有無ではなく、接触した物体が現在の速度のまま引き続き互いに向かって動いているかまで含めて見る必要がある
- 表面から遠ざかっているかどうかは、法線(normal) と速度の内積の符号で判断でき、正なら同方向成分、負なら反対方向成分を持つ
- 2つの物体の場合は個別の速度よりも相対速度と衝突法線が重要であり、接触状態で相対法線速度が負のとき衝突とみなせる
剛体物理と衝突解決の範囲
- 対象は剛体物理(rigid body physics) であり、力を受けても変形しない物体を扱う
- 現実ではすべての物体が分子レベルで変形するため、完全な剛体は存在しない
- ほとんどの物理シミュレーションでは、こうした細かな変形まで計算するのは非常に難しいかコストが高い
- 物体が十分に現実的に見えるなら、剛体として単純化する方法が実用的である
- ゲームエンジンの衝突処理は通常2段階に分かれる
- 衝突検出(collision detection): シーン内でどの物体が衝突中かを判定する
- 衝突解決(collision resolution): 衝突中の物体の移動方向、速度、材質などをもとに、その後の状態を決定する
- ここで扱う焦点は、幾何学的な交差の有無を見つける段階ではなく、衝突後の動きを決める衝突解決である
ゲームループで衝突が発生する仕組み
- ほとんどのゲームは、大きなループの中でシーン内の物体の位置を繰り返し再計算する
- 各反復で物体の位置は現在の速度(velocity) をもとに更新される
- 速度は大きさと方向の両方を持つベクトル量である
- 矢印の長さは速さ、矢印が指す方向は移動方向を表す
- 一定時間間隔Δtのあいだの位置変化は変位(displacement) で表される
- 変位も大きさと方向を持つベクトル量である
- ゲームループが毎秒60回実行されるなら、Δtは1/60秒になる
- 新しい位置は、現在の速度から計算した変位を既存の位置に足して得られる
- 2つの物体の新しい位置が互いのジオメトリを重ねてしまうと、別途処理がない限り物体は貫通して通り抜けてしまう
衝突解決が求める値
- 衝突解決の目的は、シミュレーションが進行する際に物体同士がこれ以上互いを貫通しないよう、各物体の速度変化を決めることである
- 衝突前後の速度は次の記号で表される
v_a,i, v_b,i: 物体a、bの衝突前速度v_a,f, v_b,f: 物体a、bの衝突後速度Δv_a, Δv_b: 衝突によって生じた各物体の速度変化
- 結局のところ、衝突解決はΔv_aとΔv_bの値を求める問題である
- 現実的に見える衝突を作るには、選ばれた速度変化が関連する物理法則を満たしていなければならない
接触だけでは衝突はわからない
- 2つの物体が接しているからといって、常に衝突しているとは限らない
- 衝突とは、現在の速度のまま動き続けたときに物体同士が互いを貫通してしまう状況である
- 同じ接触シーンでも、2つの物体の速度方向によって衝突である場合も、そうでない場合もある
- したがって衝突条件には次の2つが必要である
- 物体同士のジオメトリが接しているか重なっていること
- 物体がなお衝突する方向へ動いていること
表面法線と遠ざかる方向
- 物体がある表面から遠ざかっているかどうかは、その表面に対する法線方向(normal direction) で判断できる
- 法線方向は表面に垂直で、表面から直接離れる方向を指す
- 平坦な表面では、すべての点で法線方向は同じである
- 曲面では、法線方向は点ごとに異なる
- 円周では、中心からその円周上の点へ向かう方向が法線方向である
- 法線方向は長さ1の正規化ベクトルとして表される
- 長さ1のベクトルは単位ベクトル(unit vector)とも呼ばれる
- 正規化されたベクトルであることを示すため、変数の上に
^記号を付けることがある
- ある点での法線方向は、その点における表面の接線(tangent) に垂直である
内積で方向成分を判断する
- あるベクトルが別のベクトルとどの程度同じ方向を向いているかを計算するとき、内積(dot product) を使える
- 2次元ベクトルでの内積は、対応する成分同士の積を足し合わせた値であり、結果はベクトルではなくスカラーである
- 幾何学的には、内積は一方のベクトルを他方のベクトル方向に投影したスカラー投影長に、投影先ベクトルの長さを掛けた値とみなせる
- 内積の符号は2つのベクトルの方向関係を示す
- 2つのベクトルのなす角が90°未満なら、内積は正で、おおむね同じ方向を向いている
- 角度が90°を超えるなら、内積は負で、おおむね反対方向を向いている
- 角度がちょうど90°なら、内積は0である
- 物体の速度ベクトルと表面法線の内積が正であれば、物体はその表面から遠ざかっている
2物体の衝突に適用する
- 2つの箱のように物体が2つある場合、速度ベクトルも各物体に1つずつ存在する
- このときは個別の速度より、2物体の相対速度(relative velocity) を使う
- 相対速度は2物体の速度差である
- 幾何学的には、
v_bの終点からv_aの終点へ向かうベクトルである
- たとえば2台の車がそれぞれ50km/hで正面衝突する状況は、条件が同じなら、1台の車が停止中の車に100km/hで突っ込むのと同じである
- 表面に相当する方向は衝突法線(collision normal) で表す
- 衝突法線の計算方法は、衝突する物体の形状やジオメトリによって異なる
- ここでの例は、ある物体の点または頂点が別の物体の辺と衝突するvertex-edge collisionである
- vertex-edge collisionでは、衝突法線はその辺に垂直である
- 慣例として物体を
a、bと表すと、衝突法線は物体aの方向を向く
- どちらの物体を
aまたはbと呼ぶかは、計算全体で一貫していればよい
相対法線速度で定義する衝突
- 相対速度
v_abと衝突法線n^の内積を計算すると、2物体が衝突する方向へ動いているかを判断できる
- この値は相対法線速度(relative normal velocity) と呼ばれる
- 相対速度のうち、衝突法線方向の成分である
- ここでは符号が重要だが、後で衝突中に作用する力を計算するときにも重要な役割を果たす
- 相対法線速度の符号は衝突状態を区別する
- 値が正なら、2物体はすでに互いに離れつつある
- 値が負なら、2物体はまだ互いにぶつかり続けている
- 最終的には、一方の物体の点がもう一方の物体に接していて、相対法線速度が負のときに衝突が発生する
1件のコメント
Hacker News のコメント
この記事は、私のようにゲーム開発者ではなく、数学のバックグラウンドも強くない人を対象にしています。そのため、この分野の経験者にはほとんど自明に見える概念も、かなり時間をかけて説明しました。質問があれば喜んで答えます
ゲーム開発の入門者は、衝突処理をするには剛体衝突計算や Box2D のような 2D 物理エンジンが必要だと誤解しがちです。ビリヤードゲームや Angry Birds のように箱が崩れるゲームを作りたいならその通りですが、2D プラットフォーマーなら、軸にそろった矩形同士を比較して衝突を検出し、重なりを戻すようにキャラクターの X/Y 座標を変えたり、ジャンプ・着地後の Y 速度を設定したりする程度で十分です。こうするとキャラクターの操作感もより細かく調整しやすく、慣性も含まれますが、通常は物理的にリアルな慣性ではありません。初心者がリアルな物理を使おうとすると、動きがふわふわして満足のいかないものになりがちです
このシンプルな、物理エンジンなしのアプローチから始められるチュートリアル例: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
点や線のような構成要素を繰り返し積み上げ、小さなステップと視覚的なデバッグ線をたくさん入れた結果、かなりぎくしゃくして遅いものになりましたが、とにかくある程度は動きました
今後 XPBD（Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf）も読んで説明する予定はありますか？この概念はだんだん注目を集めているようで、私は Bevy で https://github.com/Jondolf/bevy_xpbd を通じてかなりうまく使えました。一般的なアプローチより安定しているように見えます
追いかけ続けられるように RSS フィードを追加してくれると本当にうれしいです
好奇心からですが、そのページを作るのにどんなツールを使いましたか？
正直、最初にドメイン名を見てトップレベルドメインが「.ski」だと分かったとき、Mechanical Watch [1] や他の素晴らしい記事を書いた人のサイトだと思いました。実際にはまったく別の人でしたが、品質は同じくらいですね。この 「.ski」トップレベルドメインには、どんな秘密のソースがあるのでしょう :)
私たちがここで好んでいる https://ciechanow.ski の筆者も、Apple で働くポーランド人プログラマーです
このゲームの重要な要素は、宇宙デブリをアリーナ内で動かせて、それを創造的に使って相手を閉じ込めたり、目標達成を妨げたりする点です。プロジェクトの一環として、ゲームエンジンはあえて使わないつもりでした。息子にアプリケーション構造をもう少し教えたかったですし、後で既製のゲームエンジンを使うとしても、少なくとも一度はすべて実装する過程を経験したいと思っていました。衝突検出と処理に取りかかるまでは順調でした。そこから状況は急速に悪化しました。理論数学のバックグラウンドがあるにもかかわらず、膨大な量の境界ケースにすぐ圧倒され、結局諦めて Box2D を使うことにしました。プロのゲーム開発者ではありませんが、開発経験は20年以上あり、数学のバックグラウンドもあります。それでもこの問題を過小評価するというミスをしました。言葉にすると簡単そうですが、細部に入るほど複雑さが幾何級数的に増える問題のようです
とても単純な矩形比較でシューティングゲームを作る一般的な方法はこちらにあります: https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
ただし、宇宙デブリのオブジェクト同士が現実的に衝突してまとまる必要があり、プレイヤーの宇宙船が重い物体の群れを押しのけるのを難しくしたいなら、物理ライブラリを使うのは妥当です
[1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...
[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...
Flash がどこにでもあった時代ですね
コード: https://github.com/vandrieu/canvas-bouncing-ball
衝突ロジックは src/collision.ts にあります
結果/デモ: https://vandrieu.github.io/canvas-bouncing-ball/
可能ならライセンスを追加してもらえますか？
しかしゲームでは、物理更新がしばしば 30Hz まで下がり、任意の Euler-Cromer 方式を使うため、かなり異なるアプローチが必要になります
数カ月かけましたが、広く知られている基本を少し超える程度で、ようやく表面をなぞっただけでした。物体が互いにめり込んだり震えたりしない安定したエンジンを作るのは底なしのウサギ穴で、私が見つけられた数学-heavy な記事でもほとんど扱われていませんでした。私は Chris Hecker の古い記事シリーズで数学を理解しました
http://www.chrishecker.com/Rigid_Body_Dynamics
難しい部分は投射体の衝突です。弾丸の現在位置と次の時間ステップでの位置を取り、敵のヒットボックスも同じ方法で見て交差するか確認する必要がありましたが、私は現在の時間ステップだけを検査していました。そのため弾丸が魔法のように敵をすり抜けることがあります！ 間抜けな話です。いつか戻って直すかもしれません