２DのRPGにおける衝突判定について

放浪中 · #1

　初めての投稿です。DXライブラリで２DのRPGを制作しようと思い勉強を始めたのですが、衝突判定でつまづいてしましました。矩形同士の衝突判定はできたのですが、点と線分の衝突判定が中々うまくいかなくて悩んでます。
　いろいろ検索して以下のアルゴリズムにたどり着きました。

・点と線分の衝突判定
線分の長さ L1 = sqrt( (x1-x0)^2 + (y1-y0)^2 )
線分の始点から点までの長さ L2 = sqrt( (x2-x0)^2 + (y2-y0)^2 )
(x1-x0)*(x2-x0) + (y1-y0)*(y2-y0) が L1*L2 に等しく、かつL1≧L2の時衝突している

　上記のアルゴリズムをDXライブラリで再現しようと思ってプログラムを組んだのですがうまくいきません。具体的には、線分上での衝突判定が行われる所と行われない所があります。
　以下のようにプログラムを組みました。

コード:

 
#include	<stdio.h>
#include	<math.h>
#include	"DxLib.h"

int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2);

int	WINAPI	WinMain(HINSTANCE, HINSTANCE, LPSTR, int){
	ChangeWindowMode(TRUE), DxLib_Init(), SetDrawScreen(DX_SCREEN_BACK); //ウィンドウモード変更と初期化と裏画面設定

	int	x_0=320, y_0=240, x_1=100, y_1=190, x_2=280, y_2=60;
	int	Cr1=GetColor(0,255,0), Cr2=GetColor(0,255,0);

	// while( 裏画面を表画面に反映, メッセージ処理, 画面クリア )
	while (ScreenFlip() == 0 && ProcessMessage() == 0 && ClearDrawScreen() == 0){

		if (CheckHitKey(KEY_INPUT_UP)){
			y_0--;
		}
		if (CheckHitKey(KEY_INPUT_DOWN)){
			y_0++;
		}
		if (CheckHitKey(KEY_INPUT_LEFT)){
			x_0--;
		}
		if (CheckHitKey(KEY_INPUT_RIGHT)){
			x_0++;
		}

		Line_cd(x_0, y_0, x_1, y_1, x_2, y_2, &Cr2);

		DrawPixel(x_0, y_0,Cr1);
		DrawLine(x_1,y_1,x_2,y_2,Cr2);
	}

	DxLib_End(); // DXライブラリ終了処理
	return 0;
}

//点と線分の衝突判定
int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2){
	int	L1, L2;
	L1 = sqrt(pow((x_2 - x_1), 2.0) + pow((y_2 - y_1), 2.0));	//線分の長さ
	L2 = sqrt(pow((x_0-x_1),2.0)+pow((y_0-y_1),2.0));	//線分の始点から点までの長さ 
	DrawFormatString(100, 300, *Cr2, "%d　%d",L1,L2);

	if (((x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1)) == L1*L2 ) {
		if (L1 >= L2){
			*Cr2 = GetColor(255, 0, 0);
			return	1;	//衝突したら1を返す
		}
		
	}
	*Cr2 = GetColor(0, 255, 0);
	return	0;	//衝突しなければ0を返す
}

　上記のプログラムは間違っているかもしれないので、もしよろしければ点と線分のアルゴリズムについてお教えいただければありがたいです。
　また、話は変わりますが矩形と線分の衝突判定というのはどのようなものなのでしょうか。

#2

とりあえず現状のLine_cd関数の問題点を書きます。
・sqrtの戻り値をint型の変数に代入しているため、値の丸めが発生し、大きな誤差が生じる
・浮動小数点型の比較を通常の演算子で行っているため、演算誤差による誤判定のリスクが生じる

この2点を修正してみました。また、誤差のリスクがある気がするsqrt関数の仕様をやめ、2乗した値で判定するようにしてみました。
テストはしていません。
地の文とパラメータの意味が違うようですが、実装の方を尊重しました。

コード:

// (x_1,y_1) : 線分の始点  (x_2,y_2) : 線分の終点 (x_0,y_0) : 点
int Line_cd(double  x_0, double y_0, double x_1, double y_1, double x_2, double y_2, int    *Cr2){
	static const double EPS = 1e-7;
	double L1, L2, naiseki;
	L1 = (x_2 - x_1) * (x_2 - x_1) + (y_2 - y_1) * (y_2 - y_1);   //線分の長さの2乗
	L2 = (x_0-x_1)*(x_0-x_1)+(y_0-y_1)*(y_0-y_1);   //線分の始点から点までの長さの2乗
	DrawFormatString(100, 300, *Cr2, "%d　%d",L1,L2);

	naiseki = (x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1);
	//if (naiseki >= 0 && naiseki*naiseki == L1*L2 ) {
	if (naiseki + EPS > 0 && fabs(naiseki*naiseki - L1*L2) < EPS) {
		//if (L1 >= L2){
		if (L1 + EPS > L2){
			*Cr2 = GetColor(255, 0, 0);
			return  1;  //衝突したら1を返す
		}

	}
	*Cr2 = GetColor(0, 255, 0);
	return  0;  //衝突しなければ0を返す
}

【追記】
テストしたところ、何かがおかしいようです。
例えば、x_0=190, y_0=125で当たっていないと判定されます。
デバッグ中です。

► スポイラーを表示

コード:

#include	<stdio.h>
#include	<math.h>
#include	"DxLib.h"

int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2);
int	Line_cd_mod(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2);

int	WINAPI	WinMain(HINSTANCE, HINSTANCE, LPSTR, int){
	ChangeWindowMode(TRUE), DxLib_Init(), SetDrawScreen(DX_SCREEN_BACK); //ウィンドウモード変更と初期化と裏画面設定

	int	x_0=320, y_0=240, x_1=100, y_1=190, x_2=280, y_2=60;
	int	Cr1=GetColor(0,255,0), Cr2=GetColor(0,255,0);

	bool komaFlag = false;

	// while( 裏画面を表画面に反映, メッセージ処理, 画面クリア )
	while (ScreenFlip() == 0 && ProcessMessage() == 0 && ClearDrawScreen() == 0){
		bool nextKomaFlag = false;

		if (!CheckHitKey(KEY_INPUT_LSHIFT)){
			// 左Shiftキーが押されているときは1ドットずつ移動する
			komaFlag = false;
		}
		if (CheckHitKey(KEY_INPUT_UP)){
			if (!komaFlag) y_0--;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_DOWN)){
			if (!komaFlag) y_0++;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_LEFT)){
			if (!komaFlag) x_0--;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_RIGHT)){
			if (!komaFlag) x_0++;
			nextKomaFlag = true;
		}
		komaFlag = nextKomaFlag;

		Line_cd(x_0, y_0, x_1, y_1, x_2, y_2, &Cr2);
		Line_cd_mod(x_0, y_0, x_1, y_1, x_2, y_2, &Cr2);

		DrawPixel(x_0, y_0,Cr1);
		DrawLine(x_1,y_1,x_2,y_2,Cr2);
		DrawFormatString(10, 10, Cr1, "Line: x_1 = %d, y_1 = %d, x_2 = %d, y_2 = %d", x_1, y_1, x_2, y_2);
		DrawFormatString(10, 50, Cr1, "Dot : x_0 = %d, y_0 = %d", x_0, y_0);
	}

	DxLib_End(); // DXライブラリ終了処理
	return 0;
}

//点と線分の衝突判定
int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2){
	int	L1, L2;
	L1 = sqrt(pow((x_2 - x_1), 2.0) + pow((y_2 - y_1), 2.0));	//線分の長さ
	L2 = sqrt(pow((x_0-x_1),2.0)+pow((y_0-y_1),2.0));	//線分の始点から点までの長さ 
	DrawFormatString(100, 300, *Cr2, "%d　%d",L1,L2);

	if (((x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1)) == L1*L2 ) {
		if (L1 >= L2){
			*Cr2 = GetColor(255, 0, 0);
			return	1;	//衝突したら1を返す
		}
		
	}
	*Cr2 = GetColor(0, 255, 0);
	return	0;	//衝突しなければ0を返す
}

// (x_1,y_1) : 線分の始点  (x_2,y_2) : 線分の終点 (x_0,y_0) : 点
int Line_cd_mod(double  x_0, double y_0, double x_1, double y_1, double x_2, double y_2, int    *Cr2){
	static const double EPS = 1e-7;
	double L1, L2, naiseki;
	L1 = (x_2 - x_1) * (x_2 - x_1) + (y_2 - y_1) * (y_2 - y_1);   //線分の長さの2乗
	L2 = (x_0-x_1)*(x_0-x_1)+(y_0-y_1)*(y_0-y_1);   //線分の始点から点までの長さの2乗
	DrawFormatString(100, 350, *Cr2, "%f　%f",L1,L2);

	naiseki = (x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1);
	//if (naiseki >= 0 && naiseki*naiseki == L1*L2 ) {
	if (naiseki + EPS > 0 && fabs(naiseki*naiseki - L1*L2) < EPS) {
		//if (L1 >= L2){
		if (L1 + EPS > L2){
			*Cr2 = GetColor(255, 0, 0);
			return  1;  //衝突したら1を返す
		}

	}
	*Cr2 = GetColor(0, 255, 0);
	return  0;  //衝突しなければ0を返す
}

【さらに追記】
テストの方法が間違っていただけのようです。
x_0=190, y_0=125のとき、元の関数では当たっていないと判定されますが、改良した関数では当たっていると判定されます。

コード:

#include	<stdio.h>
#include	<math.h>
#include	"DxLib.h"

int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2);
int	Line_cd_mod(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2);

int	WINAPI	WinMain(HINSTANCE, HINSTANCE, LPSTR, int){
	ChangeWindowMode(TRUE), DxLib_Init(), SetDrawScreen(DX_SCREEN_BACK); //ウィンドウモード変更と初期化と裏画面設定

	int	x_0=320, y_0=240, x_1=100, y_1=190, x_2=280, y_2=60;
	int	Cr1=GetColor(0,255,0), Cr2=GetColor(0,255,0), Cr2_mod=GetColor(0,255,0);

	bool komaFlag = false;

	// while( 裏画面を表画面に反映, メッセージ処理, 画面クリア )
	while (ScreenFlip() == 0 && ProcessMessage() == 0 && ClearDrawScreen() == 0){
		bool nextKomaFlag = false;

		if (!CheckHitKey(KEY_INPUT_LSHIFT)){
			// 左Shiftキーが押されているときは1ドットずつ移動する
			komaFlag = false;
		}
		if (CheckHitKey(KEY_INPUT_UP)){
			if (!komaFlag) y_0--;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_DOWN)){
			if (!komaFlag) y_0++;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_LEFT)){
			if (!komaFlag) x_0--;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_RIGHT)){
			if (!komaFlag) x_0++;
			nextKomaFlag = true;
		}
		komaFlag = nextKomaFlag;

		Line_cd(x_0, y_0, x_1, y_1, x_2, y_2, &Cr2);
		Line_cd_mod(x_0, y_0, x_1, y_1, x_2, y_2, &Cr2_mod);

		DrawPixel(x_0, y_0,Cr1);
		DrawLine(x_1,y_1,x_2,y_2,Cr2);
		DrawFormatString(10, 10, Cr1, "Line: x_1 = %d, y_1 = %d, x_2 = %d, y_2 = %d", x_1, y_1, x_2, y_2);
		DrawFormatString(10, 50, Cr1, "Dot : x_0 = %d, y_0 = %d", x_0, y_0);
	}

	DxLib_End(); // DXライブラリ終了処理
	return 0;
}

//点と線分の衝突判定
int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2){
	int	L1, L2;
	L1 = sqrt(pow((x_2 - x_1), 2.0) + pow((y_2 - y_1), 2.0));	//線分の長さ
	L2 = sqrt(pow((x_0-x_1),2.0)+pow((y_0-y_1),2.0));	//線分の始点から点までの長さ 
	DrawFormatString(100, 300, *Cr2, "%d　%d",L1,L2);

	if (((x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1)) == L1*L2 ) {
		if (L1 >= L2){
			*Cr2 = GetColor(255, 0, 0);
			return	1;	//衝突したら1を返す
		}
		
	}
	*Cr2 = GetColor(0, 255, 0);
	return	0;	//衝突しなければ0を返す
}

// (x_1,y_1) : 線分の始点  (x_2,y_2) : 線分の終点 (x_0,y_0) : 点
int Line_cd_mod(double  x_0, double y_0, double x_1, double y_1, double x_2, double y_2, int    *Cr2){
	static const double EPS = 1e-7;
	double L1, L2, naiseki;
	L1 = (x_2 - x_1) * (x_2 - x_1) + (y_2 - y_1) * (y_2 - y_1);   //線分の長さの2乗
	L2 = (x_0-x_1)*(x_0-x_1)+(y_0-y_1)*(y_0-y_1);   //線分の始点から点までの長さの2乗
	DrawFormatString(100, 350, *Cr2, "%f　%f",L1,L2);

	naiseki = (x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1);
	//if (naiseki >= 0 && naiseki*naiseki == L1*L2 ) {
	if (naiseki + EPS > 0 && fabs(naiseki*naiseki - L1*L2) < EPS) {
		//if (L1 >= L2){
		if (L1 + EPS > L2){
			*Cr2 = GetColor(255, 0, 0);
			return  1;  //衝突したら1を返す
		}

	}
	*Cr2 = GetColor(0, 255, 0);
	return  0;  //衝突しなければ0を返す
}

#3

修正です。
DXライブラリの環境だと精度が足りないらしく、このEPSの値では>=の判定がうまくいかないようです。
そのため、EPSの値と条件式を微調整しました。

コード:

// (x_1,y_1) : 線分の始点  (x_2,y_2) : 線分の終点 (x_0,y_0) : 点
int Line_cd(double  x_0, double y_0, double x_1, double y_1, double x_2, double y_2, int    *Cr2){
	static const double EPS = 1e-4;
	double L1, L2, naiseki;
	L1 = (x_2 - x_1) * (x_2 - x_1) + (y_2 - y_1) * (y_2 - y_1);   //線分の長さの2乗
	L2 = (x_0-x_1)*(x_0-x_1)+(y_0-y_1)*(y_0-y_1);   //線分の始点から点までの長さの2乗
	DrawFormatString(100, 300, *Cr2, "%f　%f",L1,L2);

	naiseki = (x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1);
	//if (naiseki >= 0 && naiseki*naiseki == L1*L2 ) {
	if (naiseki + EPS >= 0 && fabs(naiseki*naiseki - L1*L2) <= EPS) {
		//if (L1 >= L2){
		if (L1 + EPS >= L2){
			*Cr2 = GetColor(255, 0, 0);
			return  1;  //衝突したら1を返す
		}

	}
	*Cr2 = GetColor(0, 255, 0);
	return  0;  //衝突しなければ0を返す
}

テストコード

► スポイラーを表示

コード:

#include	<stdio.h>
#include	<math.h>
#include	"DxLib.h"

int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2);
int	Line_cd_mod(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2);

int	WINAPI	WinMain(HINSTANCE, HINSTANCE, LPSTR, int){
	ChangeWindowMode(TRUE), DxLib_Init(), SetDrawScreen(DX_SCREEN_BACK); //ウィンドウモード変更と初期化と裏画面設定

	int	x_0=320, y_0=240, x_1=100, y_1=190, x_2=280, y_2=60;
	int	Cr1=GetColor(0,255,0), Cr2=GetColor(0,255,0), Cr2_mod=GetColor(0,255,0);

	bool komaFlag = false;

	// while( 裏画面を表画面に反映, メッセージ処理, 画面クリア )
	while (ScreenFlip() == 0 && ProcessMessage() == 0 && ClearDrawScreen() == 0){
		bool nextKomaFlag = false;

		if (!CheckHitKey(KEY_INPUT_LSHIFT)){
			// 左Shiftキーが押されているときは1ドットずつ移動する
			komaFlag = false;
		}
		if (CheckHitKey(KEY_INPUT_UP)){
			if (!komaFlag) y_0--;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_DOWN)){
			if (!komaFlag) y_0++;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_LEFT)){
			if (!komaFlag) x_0--;
			nextKomaFlag = true;
		}
		if (CheckHitKey(KEY_INPUT_RIGHT)){
			if (!komaFlag) x_0++;
			nextKomaFlag = true;
		}
		komaFlag = nextKomaFlag;

		Line_cd(x_0, y_0, x_1, y_1, x_2, y_2, &Cr2);
		Line_cd_mod(x_0, y_0, x_1, y_1, x_2, y_2, &Cr2_mod);

		DrawPixel(x_0, y_0,Cr1);
		DrawLine(x_1,y_1,x_2,y_2,Cr2);
		DrawFormatString(10, 10, Cr1, "Line: x_1 = %d, y_1 = %d, x_2 = %d, y_2 = %d", x_1, y_1, x_2, y_2);
		DrawFormatString(10, 50, Cr1, "Dot : x_0 = %d, y_0 = %d", x_0, y_0);
	}

	DxLib_End(); // DXライブラリ終了処理
	return 0;
}

//点と線分の衝突判定
int	Line_cd(double	x_0, double	y_0, double	x_1, double	y_1, double	x_2, double	y_2, int	*Cr2){
	int	L1, L2;
	L1 = sqrt(pow((x_2 - x_1), 2.0) + pow((y_2 - y_1), 2.0));	//線分の長さ
	L2 = sqrt(pow((x_0-x_1),2.0)+pow((y_0-y_1),2.0));	//線分の始点から点までの長さ 
	DrawFormatString(100, 300, *Cr2, "%d　%d",L1,L2);

	if (((x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1)) == L1*L2 ) {
		if (L1 >= L2){
			*Cr2 = GetColor(255, 0, 0);
			return	1;	//衝突したら1を返す
		}
		
	}
	*Cr2 = GetColor(0, 255, 0);
	return	0;	//衝突しなければ0を返す
}

// (x_1,y_1) : 線分の始点  (x_2,y_2) : 線分の終点 (x_0,y_0) : 点
int Line_cd_mod(double  x_0, double y_0, double x_1, double y_1, double x_2, double y_2, int    *Cr2){
	static const double EPS = 1e-4;
	double L1, L2, naiseki;
	L1 = (x_2 - x_1) * (x_2 - x_1) + (y_2 - y_1) * (y_2 - y_1);   //線分の長さの2乗
	L2 = (x_0-x_1)*(x_0-x_1)+(y_0-y_1)*(y_0-y_1);   //線分の始点から点までの長さの2乗
	DrawFormatString(100, 350, *Cr2, "%f　%f",L1,L2);

	naiseki = (x_2 - x_1)*(x_0 - x_1) + (y_2 - y_1)*(y_0 - y_1);
	//if (naiseki >= 0 && naiseki*naiseki == L1*L2 ) {
	if (naiseki + EPS >= 0 && fabs(naiseki*naiseki - L1*L2) <= EPS) {
		//if (L1 >= L2){
		if (L1 + EPS >= L2){
			*Cr2 = GetColor(255, 0, 0);
			return  1;  //衝突したら1を返す
		}

	}
	*Cr2 = GetColor(0, 255, 0);
	return  0;  //衝突しなければ0を返す
}

放浪中 · #4

みけCATさん、わざわざありがとうございます！早速実装し勉強してみます。
自分で理解してみたら改めて報告します。

放浪中 · #5

自分なりの解釈ですが、
EPS=10^-4
L1は線分の長さ^2
L2は線分の始点から点までの長さ^2として、

コード:

if (naiseki + EPS >= 0 && fabs(naiseki*naiseki - L1*L2) <= EPS)

内積＋EPSを足した値が０以上かつ|内積^2－L1*L2|がEPS以下、

コード:

if (L1 + EPS >= L2)

L1+EPSがL2以上の時に衝突、ということでよろしいでしょうか？

また、判定が行われない所はDXライブラリ環境の精度が足りないということですね。
私はマップ上での衝突判定をキャラクター同士は矩形同士の衝突判定、キャラクターと壁は点と線分、矩形と円の衝突判定の組み合わせで行おうと思っていたのですがこの場合、点と線分を矩形と線分に変えたほうがよいでしょうか？
重ね重ね質問してしまいましたが、お教えくださればありがたいです。

#6

放浪中さんが書きました:自分なりの解釈ですが、
EPS=10^-4
L1は線分の長さ^2
L2は線分の始点から点までの長さ^2として、
コード:
if (naiseki + EPS >= 0 && fabs(naiseki*naiseki - L1*L2) <= EPS)
内積＋EPSを足した値が０以上かつ|内積^2－L1*L2|がEPS以下、
コード:
if (L1 + EPS >= L2)
L1+EPSがL2以上の時に衝突、ということでよろしいでしょうか？

コードそのまんまですが、間違ってはいないと思います。

放浪中さんが書きました:また、判定が行われない所はDXライブラリ環境の精度が足りないということですね。

いいえ、sqrtの戻り値を無駄に丸めている影響の方が大きいと思います。

放浪中さんが書きました:私はマップ上での衝突判定をキャラクター同士は矩形同士の衝突判定、キャラクターと壁は点と線分、矩形と円の衝突判定の組み合わせで行おうと思っていたのですがこの場合、点と線分を矩形と線分に変えたほうがよいでしょうか？

移動方法などの設計によると思います。線分と線分、という選択肢もあります。
ただし、キャラクターの当たり判定の表現をまっすぐな壁の時だけ(?)矩形ではなく点にするのは不自然である気がします。

放浪中 · #7

sqrtの戻り値ですか。お教えいただきありがとうございます！
衝突判定は線分と線分、について自分で調べてみたいと思います。
みけCATさん、ありがとうございました！

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

２DのRPGにおける衝突判定について

２DのRPGにおける衝突判定について

Re: ２DのRPGにおける衝突判定について

Re: ２DのRPGにおける衝突判定について

Re: ２DのRPGにおける衝突判定について

Re: ２DのRPGにおける衝突判定について

Re: ２DのRPGにおける衝突判定について

Re: ２DのRPGにおける衝突判定について