2D游戏中的碰撞检测：圆形与矩形碰撞检测（Javascript&C++版）

浏览数：22 / 时间：2015年06月08日

这几天放寒假了，时间也多了起来，当然又有时间搞搞程序了。哈哈~

昨天在开发我的塔防游戏时突然发现人物实际攻击范围比规定的范围小，按理说应该是一样大的，但偏偏不是，我被这个问题搞得糊里糊涂的，一直没想出问题所在。最后询问了一个程序高手——我哥哥。他虽然是搞C++的，但听了我代码解释中有检测圆形碰撞时，他立刻就发现了问题，他告诉我，敌人可以看作是方块，而攻击范围是圆的，如果把敌人弄成圆形进行碰撞检测那必然不准，应该检测矩形和圆形碰撞才行。我听了之后恍然大悟，但是lufylegend中没有这个功能，怎么办呢？我第一想法是对lufy说说，让他老人家实现吧。当我点开Google Talk准备发起对话时，突然又想到一来要是lufy老人家去实现，那要等到猴年马月去了，况且lufy前辈琐事缠身，要是我总是给他提意见不帮忙解决，他老人家是不是想打我啊……最后我还是决定自己来实现吧。但是我没搞过这方面的，没有经验，所以一开始有点懵，于是就去Google了一下，发现还真有人讲过，于是就点开看了，不知道是我理解能力不好还是文章写得差（估计都是我理解能力不好……）我看了半晌没看懂，呜呼，无法可想，我当时就失望了。但是文章下面有段C代码，于是我把它移植到js上来，运行了一下，感觉效果还不错，于是就马上跑到github上把代码上传给lufy了，并做了一个demo，并在Google Talk上提醒了lufy叫他老人家测试，结果lufy拿到代码一测试就发现了bug。我X，不愧是大神啊……没有办法，只有另谋出路了。

今早起来，哎呀，天气不错啊，成都好久没有这么爽的天气了。只见空气清新，阳光和煦，真是外出骑车的好机会啊！于是我便和家人一块儿跑到外面溜达了一圈。边走边想矩形和圆形碰撞的事。半天想不明白，呜呼，我只好在路上问了问哥哥。哥哥果然是高手，他想了一会儿便说出了重点，给了我启发。于是回到家，我便马上打开电脑，进行了实验，结果还成功了。当然，按照以往我的习惯，这次小小“发明”也当然也要分享给大家啦~

（以上事情均发生在1月11日和1月12日，所以lufy看到文章开头不要以为走错家门了……）

上面说到了我的塔防游戏，现在已经完工得差不多了~大家可以看看它的一些介绍：http://www.cnblogs.com/yorhom/p/sanguotd.html ，顺便发几张截图，给大伙提提兴趣。

废话写了一大堆，接下来还是来看看矩形和圆形碰撞实现过程吧。

一，原理介绍

这回有点复杂，不过看懂了还是很好理解的。当然，我不敢保证这种算法在任何情况下都会起效果，如果有同学测试时，发现出现错误，请及时联系我。

我们首先来建立一个以圆心为原点的坐标系：

然后要检测碰撞就只有两种情况了。

情况一，矩形全部都在一个象限内，如图：

当然，图中只是举个例子，不一定是只在第二象限，任何一个象限都行，只要是矩形全在该象限。

这种情况比较好解决，首先，我们计算出矩形每个角的坐标，然后用勾股定律依次算出这个角到圆心的距离是否小于或者等于半径。设这个角与圆心横坐标之差为d1，纵坐标之差为d2，半径为r，公式表达如下：

如果有一个角满足要求说明产生碰撞，返回true。

但是有朋友懵了，怎么判断矩形是不是在一个象限内呢？很简单，只要判断这个矩形左上角和右下角是否在同一个象限内就可以了。于是我们得写个函数来实现判断某两个角是否在同一象限。

函数代码如下：

function isSameQuadrant(cood,objA,objB){
	var coodX = cood.x;
	var coodY = cood.y;
	var xoA = objA.x
	,yoA = objA.y
	,xoB = objB.x
	,yoB = objB.y;
	
	if(xoA-coodX>0 && xoB-coodX>0){
		if((yoA-coodY>0 && yoB-coodY>0) || (yoA-coodY<0 && yoB-coodY<0)){
			return true;
		}
		return false;
	}else if(xoA-coodX<0 && xoB-coodX<0){
		if((yoA-coodY>0 && yoB-coodY>0) || (yoA-coodY<0 && yoB-coodY<0)){
			return true;
		}
		return false;
	}else{
		return false;
	}
}

这个函数原本是准备写到lufylegend中LMath静态类中的，参数原本是LPoint对象，但是这里可以用json，因为LPoint里的x，y属性可以写到json里，函数也就同样取得出值了。函数参数介绍：[cood创建的坐标系原点坐标, objA第一个点坐标, objB第二个点坐标] 这几个参数均为json对象，格式为：

{x:点的x坐标, y:点的y坐标}

函数中的代码还是很好理解的，就是判断一下两个点的x坐标都分别减去原点x坐标，看得出的数正负符号是否相同，然后又用同样的办法算出y轴上的符号是否相同，如果都相同就在同一象限。

有了这个函数，剩下得就好办了，直接代入开头给出的公式进行计算即可。

情况二，矩形跨度两个象限或者两个象限以上

这种情况更好办，我们就可以直接把圆看作一个边长为2r正方形，然后用矩形碰撞算法检测正方形和矩形的碰撞，如下图所示：

矩形碰撞的算法是什么呢？很easy，如图：

如果要横向判断碰撞的话，判断(x1-x2)的绝对值是否小于w1/2+w2/2，如果是则横向则有碰撞。纵向判断是一样的，判断(y1-y2)的绝对值是否小于h1/2+h2/2即可。

有了这些算法，我们就可以实现情况2了。

二，Javascript版算法&测试代码

先上代码吧：

function hitTestRectArc(rectObj,arcObj,rectVec,arcR){
	var rw = rectObj.getWidth()
	,rh = rectObj.getHeight()
	,ar = arcObj.getWidth()*0.5
	,rx = rectObj.x
	,ry = rectObj.y
	,ax = arcObj.x
	,ay = arcObj.y;
	
	if(typeof rectVec != UNDEFINED){
		rx += (rw - rectVec[0])*0.5;
		ry += (rh - rectVec[1])*0.5;
		rw = rectVec[0];
		rh = rectVec[1];
	}
	if(typeof arcR != UNDEFINED){
		ax += (ar - arcR);
		ay += (ar - arcR);
		ar = arcR;
	}
	
	var rcx = rx+rw*0.5,rcy = ry+rh*0.5;
	var rltx = rx
	,rlty = ry
	,rlbx = rx
	,rlby = ry+rh
	,rrtx = rx+rw
	,rrty = ry
	,rrbx = rx+rw
	,rrby = ry+rh;
	
	if(
		isSameQuadrant(
			{x:ax,y:ay},
			{x:rltx,y:rlty},
			{x:rrbx,y:rrby}
		)
	){
		var dX1 = Math.abs(ax-rltx),dY1 = Math.abs(ay-rlty);
		var dX2 = Math.abs(ax-rlbx),dY2 = Math.abs(ay-rlby);
		var dX3 = Math.abs(ax-rrtx),dY3 = Math.abs(ay-rrty);
		var dX4 = Math.abs(ax-rrbx),dY4 = Math.abs(ay-rrby);
		
		if(
			(((dX1*dX1) + (dY1*dY1)) <= (ar*ar))
			||(((dX2*dX2) + (dY2*dY2)) <= (ar*ar))
			||(((dX3*dX3) + (dY3*dY3)) <= (ar*ar))
			||(((dX4*dX4) + (dY4*dY4)) <= (ar*ar))
		){
			return true;
		}
		return false;
	}else{
		var result = false;
		var squareX = ax
		,squareY = ay
		,squareW = ar*2
		,squareH = squareW;
		if(
			(Math.abs(squareX-rcx) <= (squareW+rw)*0.5)
			&&(Math.abs(squareY-rcy) <= (squareH+rh)*0.5)
		){
			result = true;
		}
		return result;
	}
}

由于是为lufylegend设计的函数，所以参数为[rectObj矩形对象（LSprite或者LShape对象）, arcObj圆形对象（LSprite或者LShape对象）, rectVec矩形规定大小（可不填）, arcR圆形半径（可不填）] 当然，或许些朋友不懂这几行代码：

var rw = rectObj.getWidth()
,rh = rectObj.getHeight()
,ar = arcObj.getWidth()*0.5
,rx = rectObj.x
,ry = rectObj.y
,ax = arcObj.x
,ay = arcObj.y;

好吧，我告诉你，这里用到的是lufylegend中LSprite和LShape，这两个类有x、y属性，还有获取宽度和高度的getWidth()和getHeight()，这里看不懂没关系，你知道是取高度和宽度还有x，y坐标的就行了。当然你要深究，那就看看lufylegend.js的API文档吧：http://lufylegend.com/lufylegend/api ，以下测试代码也用到了lufylegend.js，据说这个引擎是个不错的引擎，想了解的同学，去官方网站看看吧：http://lufylegend.com/lufylegend/ 或者看看我的文章，大多数是讲解有关lufylegend开发的。

示例代码：

init(50,"mylegend",500,250,main);

function main(){
	LGlobal.setDebug(true);
				
	var back = new LSprite();
	back.graphics.drawRect(5,"green",[0,0,LStage.width,LStage.height],true,"lightblue");
	addChild(back);
	
	var cObj = new LSprite();
	cObj.x = 200;
	cObj.y = 120;
	cObj.graphics.drawArc(0,"",[0,0,50,0,2*Math.PI],true,"red");
	back.addChild(cObj);
	
	var rObj = new LSprite();
	rObj.x = 250;
	rObj.y = 70;
	rObj.alpha = 0.8;
	rObj.graphics.drawRect(0,"",[0,0,100,100],true,"green");
	back.addChild(rObj);

	trace(hitTestRectArc(rObj,cObj));
	
	back.addEventListener(LMouseEvent.MOUSE_DOWN,function(e){
		rObj.x = e.offsetX-rObj.getWidth()*0.5;
		rObj.y = e.offsetY-rObj.getHeight()*0.5;
		trace(hitTestRectArc(rObj,cObj));
	});
}

测试链接：http://www.cnblogs.com/yorhom/articles/hitTestRectArc.html

三，C++版

C++版我用的是Qt，所以大家运行要在Qt creator里编译运行。

HitTestAlg.h里的代码：

#ifndef HITTESTALG_H
#define HITTESTALG_H

#include <math.h>
#include <QPoint>
#include <QRect>

class CMath
{

public:

	static int pow(int base, int powerOf)
	{
		return (int)::pow((double)base, (double)powerOf);
	}

	static int sqrt(int n)
	{
		return (int)::sqrt((double)n);
	}

	static int abs(int n)
	{
		n = n < 0 ? -n : n;
		return n;
	}

	static int distance(const QPoint& pt1, const QPoint& pt2)
	{
		return CMath::sqrt(CMath::pow(CMath::abs(pt1.x() - pt2.x()), 2) + CMath::pow(CMath::abs(pt1.y() - pt2.y()), 2));
	}

};

class CArc
{

protected:

	int	m_nRadius;
	QPoint	m_ptCenter;

public:

	CArc() : m_nRadius(0), m_ptCenter(0, 0){}
	CArc(const CArc& arc) : m_nRadius(arc.radius()), m_ptCenter(arc.center()){}
	CArc(int radius, QPoint center) : m_nRadius(radius), m_ptCenter(center){}
	CArc(int radius, int centerX, int centerY) : m_nRadius(radius), m_ptCenter(centerX, centerY){}
	~CArc(){}

	void setRadius(int radius){m_nRadius = radius;}
	int radius() const {return m_nRadius;}
	void setCenter(const QPoint& center){m_ptCenter = center;}
	void setCenter(int centerX, int centerY){m_ptCenter = QPoint(centerX, centerY);}
	QPoint center() const {return m_ptCenter;}
	QRect rect() const {return QRect(center().x() - radius(), center().y() - radius(), 2 * radius(), 2 * radius());}

};

class CHitTestAlg
{

protected:

	QRect	m_rtRect;
	CArc	m_arArc;

protected:

	bool locatedSameQuadrant() const
	{
		bool bRes = false;
		int nRectLeft = m_rtRect.left(), nRectTop = m_rtRect.top(), nRectRight = m_rtRect.right(), nRectBottom = m_rtRect.bottom();
		int nArcCenterX = m_arArc.center().x(), nArcCenterY = m_arArc.center().y();
		if((nRectLeft - nArcCenterX >= 0 && nRectRight - nArcCenterX >= 0 && nRectTop - nArcCenterY <= 0 && nRectBottom - nArcCenterY <= 0)
			|| (nRectLeft - nArcCenterX <= 0 && nRectRight - nArcCenterX <= 0 && nRectTop - nArcCenterY <= 0 && nRectBottom - nArcCenterY <= 0)
			|| (nRectLeft - nArcCenterX <= 0 && nRectRight - nArcCenterX <= 0 && nRectTop - nArcCenterY >= 0 && nRectBottom - nArcCenterY >= 0)
			|| (nRectLeft - nArcCenterX >= 0 && nRectRight - nArcCenterX >= 0 && nRectTop - nArcCenterY >= 0 && nRectBottom - nArcCenterY >= 0)
		){
			bRes = true;
		}
		return bRes;
	}

	bool hitTestRect() const
	{
		QRect rtArc = m_arArc.rect();
		bool bRes = false;
		if(CMath::abs(m_rtRect.center().x() - rtArc.center().x()) <= CMath::abs((m_rtRect.width() + rtArc.width()) / 2)
			&& CMath::abs(m_rtRect.center().y() - rtArc.center().y()) <= CMath::abs((m_rtRect.height() + rtArc.height()) / 2)
		){
			bRes = true;
		}
		return bRes;
	}

	bool hitTestAngleArc() const
	{
		bool bRes = false;
		QPoint ptRectTopLeft = m_rtRect.topLeft(), ptRectTopRight = m_rtRect.topRight()
		, ptRectBottomLeft = m_rtRect.bottomLeft(), ptRectBottomRight = m_rtRect.bottomRight()
		, ptArcCenter = m_arArc.center();
		int nArcRadius = m_arArc.radius();

		if(CMath::distance(ptRectTopLeft, ptArcCenter) <= nArcRadius
			|| CMath::distance(ptRectTopRight, ptArcCenter) <= nArcRadius
			|| CMath::distance(ptRectBottomLeft, ptArcCenter) <= nArcRadius
			|| CMath::distance(ptRectBottomRight, ptArcCenter) <= nArcRadius
		){
			bRes = true;
		}
		return bRes;
	}

public:

	CHitTestAlg(const QRect& rect, const CArc& arc) : m_rtRect(rect), m_arArc(arc){}
	~CHitTestAlg(){}

	bool hitTest() const
	{
		bool bRes = false;
		if(locatedSameQuadrant()){
			bRes = hitTestAngleArc();
		}else{
			bRes = hitTestRect();
		}
		return bRes;
	}

};

#endif // HITTESTALG_H

mainwindow.h里的代码：

#ifndef MAINWINDOW_H
#define MAINWINDOW_H

#include <QWidget>
#include "HitTestAlg.h"

class MainWindow : public QWidget
{
	Q_OBJECT

protected:

	QRect		m_rtRect;
	CArc		m_arArc;
	bool		m_bHit;

protected:

	virtual void mouseReleaseEvent(QMouseEvent *mouseEvent);
	virtual void paintEvent(QPaintEvent *paintEvent);

public:

	MainWindow(QWidget *parent = 0);
	~MainWindow();

};

#endif // MAINWINDOW_H

mainwindow.cpp里的代码：

#include <QDebug>
#include <QMouseEvent>
#include <QBrush>
#include <QPainter>
#include "mainwindow.h"

MainWindow::MainWindow(QWidget *parent)
	: QWidget(parent)
	, m_rtRect(0, 0, 100, 50)
	, m_arArc(50, 200, 200)
	, m_bHit(false)
{
	QWidget::showMaximized();
}

MainWindow::~MainWindow()
{
	
}

void MainWindow::mouseReleaseEvent(QMouseEvent *mouseEvent)
{
	if(mouseEvent){
		QPoint ptPos = mouseEvent->pos();
		QRect rtRect;
		rtRect.setX(ptPos.x() - m_rtRect.width() / 2);
		rtRect.setY(ptPos.y() - m_rtRect.height() / 2);
		rtRect.setWidth(m_rtRect.width());
		rtRect.setHeight(m_rtRect.height());
		m_rtRect = rtRect;
		m_bHit = CHitTestAlg(m_rtRect, m_arArc).hitTest();
		QWidget::update();
	}
}

void MainWindow::paintEvent(QPaintEvent *paintEvent)
{
	Q_UNUSED(paintEvent)

	QPainter xPainter(this);
	{
	xPainter.save();
	QBrush xBrush; xBrush.setColor(Qt::red); xBrush.setStyle(Qt::SolidPattern);
	QPen xPen; xPen.setColor(Qt::black); xPen.setStyle(Qt::SolidLine);
	xPainter.setBrush(xBrush);
	xPainter.setPen(xPen);
	xPainter.drawEllipse(m_arArc.center(), m_arArc.radius(), m_arArc.radius());
	xPainter.restore();
	}
	{
	xPainter.save();
	QBrush xBrush; xBrush.setColor(Qt::darkGreen); xBrush.setStyle(Qt::SolidPattern);
	QPen xPen; xPen.setColor(Qt::black); xPen.setStyle(Qt::SolidLine);
	xPainter.setBrush(xBrush);
	xPainter.setPen(xPen);
	xPainter.drawRect(m_rtRect);
	xPainter.restore();
	}
	{
	xPainter.save();
	QString sContent = QString("Hit Test: %1").arg(m_bHit ? "true" : "false");
	QFont ftFont("Tahoma", 12, QFont::DemiBold, true);
	xPainter.setFont(ftFont);
	xPainter.drawText(20, m_arArc.rect().bottom() + 30, sContent);
	xPainter.restore();
	}
}

main.cpp里的代码：

#include <QApplication>
#include "mainwindow.h"

int main(int argc, char *argv[])
{
	QApplication a(argc, argv);
	MainWindow w;
	w.show();
	
	return a.exec();
}

原理和js版是一样的，就不多解释了，在下面我会放出所有代码。C++版运行demo如下：

Qt做的界面感觉还是不错的，哈哈~~