矩形とマップチップの当たり

unity_chan_logo

概要

最終更新日:2020/02/24

矩形とマップチップの当たり判定について書いています。
この記事は以下の内容を知りたい方に向けて書いています。
  • 矩形とマップチップの当たり判定が知りたい

注意点

この記事内の座標軸はX軸「右が正、左が負」Y軸「下が正、上が負」で書いています。

サンプル

サンプルはここからダウンロードでき、環境については以下の内容となっています。

開発環境
VSのバージョン VisualStudio 2019
DirectXのバージョン DirectX9
説明 マップチップ上をキャラクターが移動出来て
ブロックの当たれば止まるようになっています。
キーボードの←と→でキャラクターを移動できます。


当たりの条件

判定は以下の条件を満たしている場合に当たっているとします。
  • 矩形がマップチップ配列の有効番号の位置にある
矩形をマップチップの配列にあてはめて、ブロックなどがあれば当たりで、
何もなかった場合は当たっていないとします。

collision_0058

上の図で「1」になっている部分はブロックが配置されていると考えてください。
その中に赤枠と青枠がありますが、赤枠は「1」の数字がある場所と被っており、
青枠は被っていません。
この場合、赤枠は矩形がマップチップの有効番号の位置にあるので当たっている、
青枠の位置には有効番号がないので当たっていないと判断します。

四頂点の座標で判定する

最も簡単な判定方法は矩形の四頂点の座標がマップチップのどの位置かを調べて
その位置の配列番号を調べる方法です。
この方法の手順は以下の通りです。
  1. 矩形の頂点の要素番号を調べる
  2. 要素の値を調べる
まず、矩形の四頂点をマップチップの要素番号のどこにあたるかを
計算は以下の式を使って調べます。
  • X軸要素番号 => 頂点のX座標 / チップの横幅
  • Y軸要素番号 => 頂点のY座標 / チップの縦幅
要素番号の割り出しが終了したら、要素が有効番号かを調べます。

// 当たりチェック
if (マップチップ配列[Y軸配列番号][X軸配列番号] != 0)
{
	// 当たってるので判定終了
}

四頂点の中でどれか一つでも有効番号の要素の位置にあれば、
そこで判定は終了します。

四頂点の座標の判定方法の実装

まず四頂点の座標を用意します。
矩形の場合、中心となる座標とサイズのみで構成されていることが
ほとんどなので、その情報から四頂点の座標を割り出します。

// 矩形の四頂点
Vec2 vertices[]
{
	{ Vec2(rect.Left, rect.Top) },
	{ Vec2(rect.Right, rect.Top) },
	{ Vec2(rect.Left, rect.Bottom) },
	{ Vec2(rect.Right, rect.Bottom) },
};

次は各頂点がマップ上のどこにあるのかを割り出します。

// 頂点座標のマップ位置割り出し
int x_id = vertices[i].X / CHIP_SIZE;
int y_id = vertices[i].Y / CHIP_SIZE;

最後に割り出した位置にブロックなどがあるかを調べます。

// 判定
if (Map[y_id][x_id] != 0)
{
	return true;
}

ブロックなどがあった場合は、当たっていると判定するので、
ここで判定を終了します。

問題点

単純な判定は効果的ではありますが、矩形のサイズが大きい場合に
すり抜けの問題が発生する可能性があります。
まず、次の動画を確認してください。



この動画ではマップチップを「32*32」、矩形を「108 * 108」で判定を行っています。
その結果、動画のように移動途中にあるブロックをすり抜けています。
これは矩形のサイズがチップよりも大きい際に起きるバグです。
次の図を確認してください。

collision_0059

この図では四頂点の判定が行われる要素番号は「F4 I4 F7 I7」、
すり抜けたブロックのある要素番号は「H6」なので、
「H6」は判定の対象にならずにスルーされます。
その結果、四頂点の要素は何もないと判断されるので、
当たっていないと判定され、今回のバグが発生しています。
このように四頂点のみで判定を行うと、矩形のサイズによって
調べていない要素番号が発生する可能性があります。

この問題を解決するために四頂点ではなく、矩形全体で判定するようにします。

矩形全体で判定を行う

四頂点で判定した場合、当たり抜けが発生します。
そのバグに対応するためには頂点ではなく、矩形全体で判定を行います。

collision_0060

上の図の緑の枠一つ一つが判定の対象です。

判定手順

判定の手順は以下のように行ないます。
  1. 開始と終了の要素番号を求める
  2. 範囲チェックをする
  3. 判定を行う

開始と終了の要素番号を求める

矩形全体の判定を行うために開始と終了の要素番号を求めて、
全て判定できるようにします。
今回は開始を矩形の左上、終了を右下として要素番号を求めます。
  • 左上:
    (x, y) => (矩形の左辺X座標 / チップの横幅, 矩形の上辺Y座標 / チップの縦幅)
  • 右下:
    (x, y) => (矩形の右辺X座標 / チップの横幅, 矩形の下辺Y座標 / チップの縦幅)

範囲チェックをする

要素番号が範囲内かを調べて範囲を超えているならば正常な値に変更します。
  • 最小値 => 0
  • 最大値 => マップチップの縦 or 横の最大数

判定を行う

範囲チェックが終了したら、あとは範囲内の全ての要素のチェックを行い、
当たっているかどうかを調べます。
判定に使う条件は頂点で判定した時と変わりません。

矩形全体判定の実装方法

まず、矩形範囲の開始と終了の要素番号を求めます。

// 矩形のX軸範囲
int width_range_ids[]
{
	rect.Left / CHIP_SIZE,
	rect.Right / CHIP_SIZE
};

// 矩形のY軸範囲
int height_range_ids[]
{
	rect.Top / CHIP_SIZE,
	rect.Bottom / CHIP_SIZE
};

次に求めた、要素番号の範囲チェックを行います。

// 範囲最大数
const int max_range_ids[]
{
	MAP_CHIP_HEIGHT_NUM - 1,
	MAP_CHIP_WIDTH_NUM - 1,
};

for (int i = 0; i < 2; i++)
{
	Clamp(&height_range_ids[i], 0, MAP_CHIP_HEIGHT_NUM - 1);
	Clamp(&width_range_ids[i], 0, MAP_CHIP_WIDTH_NUM - 1);
}

範囲チェックは判定時に行っても問題ありませんが、
全ての番号をチェックするのは無駄なので、判定前に範囲チェックをしています。
最後に範囲分だけ判定を行います。

// 範囲内の要素全てを判定する
const int start = 0;
const int end = 1;

for (int i = height_range_ids[start]; i <= height_range_ids[end]; i++)
{
	for (int j = width_range_ids[start]; j <= width_range_ids[end]; j++)
	{
		if (Map[i][j] == 1)
		{
			// 当たり
			return true;
		}
	}
}

これで、矩形範囲の判定は完了です。
もし、矩形のサイズが大き過ぎる時は、矩形のアウトラインだけを
判定する関数を用意して使い分けると高速化につながります。

注意点

矩形の要素番号の割り出しは「矩形サイズ - 1」で行うようにしてください。
そのままのサイズで計算を行うと一つの要素内で収まっているはずが、
隣接している要素にまたがっている結果になることがあります。
例えば、矩形サイズの縦、横とチップサイズの縦、横のサイズを「64」とします。
そして、矩形の左上頂点の座標を(0, 0)とした場合、四頂点の座標とマップ配列上の
要素番号は以下の内容になります。

位置 座標(x, y) 要素番号[y, x]
左上 (0, 0) [0, 0]
右上 (64, 0) [0, 1]
右下 (64, 64) [1, 1]
左下 (0, 64) [1, 0]
上の表から分かるように左上頂点以外は全て隣接する要素番号が含まれています。 これは座標(0, 0)から矩形のサイズ(64, 64)分を範囲として広げた場合に 範囲は矩形の開始座標を含むため「0~63」が矩形の範囲となります。 しかし、範囲を求める際にサイズをそのまま足し算すれば「0~64」が範囲となり、 表の結果へとつながっています。 この問題の対策として、最初に書いたように要素番号割り出しの際は 「矩形サイズ - 1」を行ってから計算をしてください。 // サイズ調整 rect.Right -= 1.0f; rect.Bottom -= 1.0f;