2Dゲームの衝突判定と座標軸別移動衝突法(仮称)について
近年ではゲームエンジンの普及により、いたく立派な物理エンジンが気軽に使われるようになって久しい。しかし主人公が着地したとか壁にぶつかっただとかの判定は、長い間それぞれのゲーム開発者が自分の手でちょちょいと実装してきたもののはずではなかったか。
そのような自作は今も有力な選択肢であることは間違いない。また、プログラミングの入門としても恰好の題材であるように思われる。
一方で実際のところ、その実装についてネットで調べてみると悩みの声も多く目につく。思うに、実装にどんなバリエーションがあってどこさえ外さなければいいのかとか、そういうところが整理されていないのである。
この記事では最もシンプルで実装が楽な方法を紹介する。誰も名前を付けている人が居ないので、仮に「座標軸別移動衝突法」と呼ぶことにした。
目次
注意点: 以降では説明のためC++とSiv3Dによるコードを使用する。だが、描画以外でC++およびSiv3D特有の命令などは使っていないし、他の言語に書き直しても使えるはずだ。自分の好きな言語とライブラリで実装してよい。
マップデータの用意
今回はこのようなマップデータを用意する。1がブロックあり、0がブロックなし。
int tiles[12][16] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, },
{1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, },
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, },
};
描画処理。ブロックの一辺の長さは仮に40とする。
const int block_sz = 40;
for(int yi = 0; yi < 12; yi++) {
for(int xi = 0; xi < 16; xi++) {
if (tiles[yi][xi] == 1) {
// ブロックを描画
RectF(block_size * xi, block_size * yi, block_size, block_size).draw(Palette::White);
}
}
}
こんな感じ。
主人公の用意
主人公の判定は長方形とする。これが一番計算が楽。
// 主人公のサイズの定義(横幅、高さ)
const int wm = 30, hm = 40;
// 主人公の位置(左上基準)
int px = 100, py = 100;
// 主人公を描画
RectF(px, py, wm, hm).draw(Palette::Red);
座標は整数で管理する方が簡単ではある。浮動小数点でももちろん書けるのだが、境界まわりの挙動をちゃんと考察する必要がある。
移動の実装
後々を考えると、「X/Y速度」を変数として管理しておいた方がいい。
// 主人公のX, Y速度
int vx = 0, vy = 0;
// X, Y速度を毎フレーム反映
px += vx; // X速度による移動
py += vy; // Y速度による移動
ジャンプの仕組みにはこれを使うし、この記事では扱わないが、例えば「滑る地面」とか「慣性」とかを実現するにも入り用だ。
左右移動
if (KeyLeft.pressed()) { // 左が押されていたら
vx = -5; // 左方向の速度
} else if (KeyRight.pressed()) { // 右が押されていたら
vx = +5; // 右方向の速度
} else {
vx = 0; // どちらも押されていなければ停止
}
px += vx; // X速度による移動
重力
毎フレームY速度を上げていく。いわゆる重力加速度である。これが大きいと物体はストンと落ちるし、小さいとふわっとする。
vy += 1; // 重力加速度
vy = Clamp(vy, -20, +20); // 最大速度制限
py += vy; // Y速度による移動
この時点では衝突処理などなにもしていないので、画面外へ真っ逆さまに落ちていく。
速度制限をかけているのは、際限なく速度を増やしていくと判定のすり抜けが発生するからである。 また実際に遊んでいても速すぎる動作は混乱する。
タイルとの交差判定
ではいよいよ判定を付けてみよう。
主人公とタイルが共に長方形/正方形なので、角の点さえ確認すればよい。
左上が(px, py)とすると、右下は(px+wm-1, py+hm-1)である。この-1を忘れるだけで挙動が変わるので注意。
※浮動小数点で座標を管理する場合、適当に-0.001といった小さい数にするか、仕組みを考えた上で判定時に> <と>= <=の使い分けなどで解決することになる。これを考えるのが面倒だから整数座標の方が初心者にはおすすめだ。
点とタイルの交差判定
座標をタイルのサイズで割って切り捨てればその位置のタイルを取得できる。 ある点(x,y)がタイルと重なるかどうかをチェックするにはこれだけでよい。
if(tiles[int(y / block_sz)][int(x / block_sz)] == 1) {
// 点(x,y)がタイルと重なっている
}
補足: 「取得するため」か「判定のため」か
上のように、切り捨て除算でタイル配列の添え字を求める処理は広く使われる。 これの本質は「ブロックに当たっているかを求める」ことではなく、「マス目状の区切りにおいてある点がどこに入るかを求める」ことだ。
何が言いたいかというと、マス目と判定形状が一致している前提なら上のようなプログラムでよい。しかしそうでないなら追加で何か判定が要る。坂道などを作るならそれが必要だ。
if(tiles[int(y / block_sz)][int(x / block_sz)] == 2 && is_triangle_crossed(x, y)) {
// ...
}
衝突時の処理
発想はシンプルだ。
- まず移動させる。
- もしめり込んでいたら、
- めり込んでいないところまで押し戻す。
この原則を念頭に衝突処理のプログラムを書く。
が、その前に大変重要な注意点がある。
座標軸別移動衝突法
さてここで、この記事で最も重要なことを書く。
今回紹介する実装方法では、
具体的に言うとこうだ。
- 「X軸移動→Y軸移動 → 壁・天井・床判定」これはダメ！
- 「X軸移動→壁判定 → Y軸移動→天井・床判定」これはOK！
- 「Y軸移動→天井・床判定 → X軸移動→壁判定」これもOK！
この切り分けにより、シンプルかつバグりにくい実装ができる。なぜかというと、衝突後の「押し戻し」の前に例えばX軸での移動しかしていないならば、X軸の移動だけでめり込みが解消することが明らかだからである。Y軸についても同様である。
広く使われているテクニックのようなのだが、誰も名前を付けていないので「座標軸別移動衝突法」と名付けることにした。
床判定
- 下の辺が地形にめり込んでいたら上に押し戻す
// 床判定
if (tiles[(py + hm - 1) / block_size][px / block_size] ||
tiles[(py + hm - 1) / block_size][(px + wm - 1) / block_size])
{
py = ((py + hm - 1) / block_size) * block_size - hm;
vy = 0;
}
天井判定
- 上の辺が地形にめり込んでいたら下に押し戻す
// 天井判定
if (tiles[py / block_size][px / block_size] ||
tiles[py / block_size][(px + wm - 1) / block_size])
{
py = (py / block_size) * block_size + block_size;
vy = 0;
}
左右壁判定
- 左の辺が地形にめり込んでいたら右に押し戻す
- 右の辺が地形にめり込んでいたら左に押し戻す
// 左壁判定
if (tiles[py / block_size][px / block_size] ||
tiles[(py + hm - 1) / block_size][px / block_size])
{
px = (px / block_size) * block_size + block_size;
vx = 0;
}
// 右壁判定
if (tiles[py / block_size][(px + wm - 1) / block_size] ||
tiles[(py + hm - 1) / block_size][(px + wm - 1) / block_size])
{
px = ((px + wm - 1) / block_size) * block_size - wm;
vx = 0;
}
これで壁・天井・床判定が揃った。
注意点に気を付けて移動処理と衝突判定処理を並べれば、床に着地し壁に触れるようになるはずだ。
px += vx; // X速度による移動
if(...) { /* ... */ } // 左壁判定
if(...) { /* ... */ } // 右壁判定
py += vy; // Y速度による移動
if(...) { /* ... */ } // 床判定
if(...) { /* ... */ } // 天井判定
(おまけ)座標軸別移動衝突法を行わなかった場合
とりあえず「X・Y軸移動」→「衝突判定」の順にしただけでバグるようになるはずだ。
各衝突判定の順序にもよるが、床をまともに歩けなくなったり、壁に当たっただけですり抜けが起きるはずである。これはブロックに当たったとき「X軸移動の結果として」当たったのか「Y軸移動の結果として」当たったのかを考慮しない結果になってしまったことによる。
まともな物理エンジンであれば、速度の向きや当たった物体の面の向きなどを考慮して、正しい「押し戻し」の方向を算出する。これをちゃんと実装するのはそれなりに面倒くさい。このようなことを考えずとも良い感じに動いてくれる座標軸別移動衝突法は優れたアルゴリズムに思われる。
(おまけ)衝突判定の別実装
上の方で「右下をとるときに-1を忘れるとバグる」という話をした。
しかし-1を入れずに(x+w, y+h)で右下の座標を取っていても、主人公の矩形とブロックの矩形の判定を追加で入れれば正常に動く。
// 矩形同士の交差判定関数
bool rectCollision(
int x1, int y1, int w1, int h1,
int x2, int y2, int w2, int h2
) {
// <= ではなく < になっていることに注意
return
x1 < x2 + w2 && x2 < x1 + w1 && // X軸の判定
y1 < y2 + h2 && y2 < y1 + h1; // Y軸の判定
}
// タイルの添え字
int i = int((px + wm) / block_sz), j = int((py + hm) / block_sz);
// タイルが地面である かつ 主人公とタイルが交差している
if(tiles[j][i] == 1 &&
rectCollision(
px, py, wm, hm,
i * block_sz, j * block_sz,
block_sz, block_sz)) {
// ...
}
この判定法はいささか冗長にも見えるが、浮動小数点の場合はこちらの方が自然かもしれない。割り算&切り捨てによる格子判定の場合、ブロックの判定は基本的に半開区間になる。整数であれば-1とかで補正できるが、浮動小数点の場合は> <と>= <=の使い分けで正す方が真っ当な方法だろう。格子判定はあくまで「衝突する可能性のある」タイルの取得に留めておき、追加判定で両側開区間の判定にすればよい。
区間の重なり判定の実装については以下の記事を参考にした。
参考:
ジャンプの実装
せっかくアクションっぽくなっているのでジャンプも実装してみる。
ボタンを押すと上方向の速度が付くようにしてみよう。
if (KeySpace.down()) {
vy = -15;
}
これだけでジャンプはできるようになる。ただし空中でもジャンプできてしまうので、接地判定が必要だ。
接地判定
適当にフラグ変数を追加する。
bool onground = false; // 接地フラグ、フレームの最初に初期化
床判定で接地フラグをオンにする。
// 床判定
if (tiles[(py + hm - 1) / block_size][px / block_size] ||
tiles[(py + hm - 1) / block_size][(px + hm - 1) / block_size])
{
py = (py / block_size) * block_size;
vy = 0;
onground = true; // 追加
}
接地していなければ跳べないようにすれば完成だ。
if (KeySpace.down() && onground) { // 条件を追加
vy = -15;
}
接地判定だけならboolで良いと思うが、例えば2段ジャンプだったり壁キックだったりでもっと複雑な状態管理が必要な場合は、ステートマシン図などを書いてみることをおすすめする。
参考:
実装全体
#include <Siv3D.hpp>
// 0は空白、1はブロックあり
int tiles[12][16] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, },
{1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, },
{1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, },
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, },
};
const int block_size = 40; // ブロックの一辺の大きさの定義
const int wm = 30, hm = 40; // 主人公のサイズの定義
void Main()
{
// 主人公の位置(左上基準)
int px = 100, py = 100;
// 主人公のX, Y速度
int vx = 0, vy = 0;
while (System::Update())
{
bool onground = false; // 接地フラグ
if (KeyLeft.pressed()) {
vx = -5;
}
else if (KeyRight.pressed()) {
vx = +5;
}
else {
vx = 0;
}
vy += 1;
vy = Clamp(vy, -20, +20); // 最大速度制限
px += vx;
py += vy;
// 床判定
if (tiles[(py + hm - 1) / block_size][px / block_size] ||
tiles[(py + hm - 1) / block_size][(px + wm - 1) / block_size])
{
py = ((py + hm - 1) / block_size) * block_size - hm;
vy = 0;
onground = true;
}
// 天井判定
if (tiles[py / block_size][px / block_size] ||
tiles[py / block_size][(px + wm - 1) / block_size])
{
py = (py / block_size) * block_size + block_size;
vy = 0;
}
if (KeySpace.down() && onground) {
vy = -15;
}
// 左壁判定
if (tiles[py / block_size][px / block_size] ||
tiles[(py + hm - 1) / block_size][px / block_size])
{
px = (px / block_size) * block_size + block_size;
vx = 0;
}
// 右壁判定
if (tiles[py / block_size][(px + wm - 1) / block_size] ||
tiles[(py + hm - 1) / block_size][(px + wm - 1) / block_size])
{
px = ((px + wm - 1) / block_size) * block_size - wm;
vx = 0;
}
RectF(px, py, wm, hm).draw(Palette::Red);
for (int yi = 0; yi < 12; yi++) {
for (int xi = 0; xi < 16; xi++) {
if (tiles[yi][xi] == 1) {
// ブロックを描画
RectF(block_size * xi, block_size * yi, block_size, block_size).draw(Palette::White);
}
}
}
}
}
その他の注意点など
- 座標が整数だと速度の微調整が効かず困る、ということもあるかもしれない。その場合は、長さ256を画面上の1ドットに対応させるなどすればよい。いわゆる固定小数点である。
- この実装の場合、主人公をブロックよりも大きくするとバグる。4隅の点しか判定していないためである。ブロックより大きい主人公を作りたい場合は、重なるタイル全体について判定するのが確実かもしれない。
- この記事では主人公の左上隅を位置の基準としている。これは別に本質ではないので、ちゃんと実装すれば中心や足元を位置の基準にとっても構わない。
- 坂道の実装は少し難しい。なぜなら、坂道は横の速度を縦の速度に変換しなければならないので、XY軸を分離することで実装をシンプルにしている座標軸別移動衝突法とは根本的に相性が良くないのである。多少は泥臭い実装が要る。
参考にした記事について
この記事は以下のブログ記事を大いに参考にしている。というよりその記事を参考にして別言語で実装したらバグらせまくったのでその時の知見をまとめたのがこの記事である。
２Ｄアクションゲームの簡易衝突判定入門 - 土屋つかさの技術ブログは今か無しか
また、他の実装例についても調べた。細かい部分や言語の違いはあるが、本質的には大体みんな同じ実装をしている。
- アクションゲームにおけるマップとの当たり判定基本 - ＤＸライブラリ置き場
- 【Rust】アクションゲームの挙動を実装する - k-yaina60
- 2Dアクションゲームでキャラと地形との当たり判定を取った後の処理についてのまとめ - AiNI Bellwood
- 2D矩形マップとの当たり判定 - 2dgames.jp
- マップとの衝突判定について - ジュニアプログラミングスクール コード
- アクションゲームにおける壁の当たり判定など with OpenSiv3D - 空飛ぶサトイモの書
- 2Dアクションゲームの当たり判定と当たらない判定 - div1に上がりたいkeitanxkeitanの日記
- アクションゲームの当たり判定について - C言語何でも質問掲示板
- アクションゲームのブロックとの衝突判定について - HSPTV!掲示板