Go&Ebitengineで衝突判定を作る
はじめに
Ebitengineには衝突判定が無い。触り始めたときにebitengine-graphicsを使うことも検討したが、Rectが回転できないことと、Spriteは回転可能なくせに衝突判定がAABBだったことで、自前で作り始めたという経緯がある。前の記事で作ったやつでも簡素なOBBの衝突判定は作ってあったが、今回は真面目に作りこんでみた。ちなみに前の記事というのはこれ。
Githubに置く
こんな感じのものが動く。
実行はこちらで。
コードはこちら。
これは何か
前までは四角しか判定できなかったが、回転する四角は分離軸判定でOBBを処理すればよかったので簡単だった(簡単とは言っていない)。これを作り直して円や多角形を判定できるようにした。毎度コードは置いてあるので興味がある人は見てくれればいいが、これをどのように作ったのか、というのが今回のお話。
内容
衝突判定の設計について
collision.goに全部まとめてある。計算が大変だったのでebitengine-graphicsの人のgmathをお借りしている。
Zennではそこそこ長いコードは途中までしか表示してくれないようだ。コードの上の部分にリンクがあるようなのでそれで見てもらえれば良い。
さて、衝突判定には構造体を3つ用意して、それぞれの形状に対応している。凸型多角形のPolygonと、円のCircleと、複合形状のCompositである。Compositeじゃないのは書いてて今気づいたのでどうか見なかったことにしておいてほしい。
複合形状というのは星型みたいな凸型じゃない多角形を表現するために、PolygonやCircleを複数まとめて管理するための構造体である。これはOr/Andの条件を指定できて、星型の場合は三角形のOr、半円は円と長方形のAnd条件で衝突判定をしている。collision.goの最後のほうの関数群でやっているのがその処理だ。こんなやつ。
GoにはUnionが無いのでこのバラバラの形をした3つの構造体はTestメソッドを用意してcollosion.Testerインターフェースでまとめている。
個々の判定方式について
円と円は省略。多角形と多角形は素朴な分離軸判定であり、知らない人は適当に検索したりこのあたりを見てもらえれば少しわかるようになるかもしれない。 んで、今回追加したもので厄介なのは円と多角形の判定である。実装した方式はSAT.jsを参考にしていて、キーになるのは以下のコメントだった。これのおかげで理解できた。 エッジの始点と終点に対してエッジと垂直な線を引いたとき、円の中心がこれより外側にいる場合、エッジの中で始点/終点が最も近いと言えるので、始点/終点と円の距離で判定すれば、点と円の判定ができる。例えば1つ前のエッジより後ろ側で、今のエッジよりも前側であれば、このエッジの始点が円に最も近いので、これが当たっていなければ全体として衝突していないと言える。エッジと円の判定は外積を求めればすぐであり、あとはこれをエッジの数だけ繰り返せば良い。
Base構造体
いままでRectとして作っていたものを一新して、Baseという構造体に置き換えた。
Rectは四角専用だったが、Baseはあらゆる形状の描画と判定、タッチによる移動に対応する。描画は衝突判定の形状から頂点情報を作成していて、このサンプルでは見た目と判定が一致するようになっている。
なお、各種形状はutil.goのほうで作っており、半円だけはそのまま描画ができない特殊形状になるのでHarfCircle構造体としてBaseを埋め込む形で作っている。
基本的に形状は中心が重心になって回転原点になるようにしていたが、半円だけは中心がズレている。これは衝突範囲のCircle構造体に回転原点を持っていないためで、円は回転する意味無いし回転原点とか無くていいよね？って先見の明の無い俺がささやいた痛恨のミスである。今から追加するのもちょっと面倒なのでそのままにしておいた。
作られていない機能
Baseと衝突判定用のPolygon/CircleそれぞれにPosなどの情報を持っていて、これは重複しているのでちょっとイケてない。複合形状に至っては内部に持つPolygon/Circle全部に持っているし、毎フレーム更新しないといけない。単純に無駄である。1つにまとめたい。
あと、現在の作りでは素朴に1対1の判定しかできないが、これだとAABBなどでの枝刈りができず、複雑な形状で大量に判定する場合に負荷が高くなる。枝刈り用の形状は計算したらキャッシュして、フレームの最後に削除するみたいな仕組みがあればマシになるだろう。collision.Testerのスライス同士の衝突判定関数を作るとかでもよさそうだ。
変形した形状の判定も無い。多角形の変形は座標を計算するだけだし、楕円と多角形の判定であれば、楕円を真円になるように逆変形して、多角形も同様に変形してやれば今の判定でそのままいける。問題は回転した楕円同士の判定で、これは魔の領域に踏み込む。具体的には近似計算でごまかすしかない。
おしまい
などなど考えてはみるものの、そもそもこれは突貫工事のサンプルであって、ライブラリとしてきちんと作って公開する予定も無いので、よっぽど気が向かない限りこれ以上の進展はなさそうに思える。
このようなコードを書いたらこのように動くものが作れるのだ、と目に見える形で提供するのが目的であり、見せるものの目標ラインは既に達成しているからだ。
Discussion