STM32学习笔记十四：WS2812制作像素游戏屏-飞行射击游戏（4）探索碰撞检测

今天又是游戏开发的一大主题。

一般成熟的游戏引擎，如unity/cocos等等，都有自己的碰撞系统。坏消息是我们什么也没有，必须从底层打造。好消息是，有机会可以从原理开始考虑从底层开始尝试。

做碰撞，需要考虑两方面事情：

1、碰撞算法本身的复杂度。

2、减少碰撞检测次数。

我们先看第一个：碰撞算法。

通常游戏引擎中的碰撞，需要设置碰撞钢体，这本质上就是把复杂的图形简化为简单的几何形状。以2D为例，比较常见的如 AABB / OBB / 凸多面体 / 圆形等等。

AABB 比较简单，就是把图形简化为端端正正长方形，对应（x1,y1,x2,y2）坐标。

然后再做判断：

min(x1,x2) > max( x3,x4)

max(x1,x2) < min( x3,x4)

min(y1,y2) > max(y3,y4)

max(y1,y2) < min( y3,y4)

这四个条件只要有一个成立，则图形不相交。很显然，这样端正的方形，很难精确匹配实际物体的边缘，如果要求不高，也够用了。谁叫他最简单呢。

圆形也比较简单。只要比较圆心距离就行了。

?TIPS：不用开平方，只要(x1-x2)*(x1-x2) +?(y1-y2)*(y1-y2) < (r1+r2) *?(r1+r2) 即可。

?这两者之外的其他图形，就需要一定的数学能力了。比如突多边形相交实际可简化为一堆三角形的边线相交；还有射线相交法等等很多方法，都要看实际情况，这里不再过多赘述。

所以说，算法的基础都是数学。否则，就是个CTRL+C / CTRL+V 的伪开发者。

?回归主题。

我们设置了三种敌机：

因为都是像素，所以最直观的方法，就是逐个像素点进行判断。加之子弹只有一个像素点，所以只要遍历一遍飞机所有像素点即可。那么，判断次数分别是 9/ 25 / 45。

如果用点到圆检测法呢？

比像素点判断计算量少多了。

TIPS：BOSS的机翼有点长，我们可以多弄两个圆进行判断。同样道理，对于复杂的图形，我们可以简化为多个简单图形进行判断。只要物体形状固定或者变形有规律，都可以直接得到各个子图形的位置。

如果用点到AABB检测法呢？?

两者都可以用。严格比较的话，可能圆形会更快一点。毕竟圆只需要做一次判断，而AABB需要四次。x1<x<x2, y1<y<y2.

?一切皆是速度与精度的平衡。

?我们再来看第二个事情。

由于我们是不知道谁与谁可能会产生碰撞，所以第一直觉就是用双重循环全都遍历一遍。但双重遍历的时间复杂度可是很高的。你要做个台球游戏还可以接受，要是有几百上千个碰撞体就麻烦了。我们必须设法减少碰撞检测数量。

常用的方法也有，如分治法，或者过滤附件的碰撞体。看具体情况具体分析。

本次项目中，我们采用分类法。玩家的子弹与敌机做检测，而敌人的子弹和玩家飞机做检测。

?TIPS：由于有PlaneXYScale的关系，所以计算乘法时，有可能会越界！

?碰撞检测我们采用点圆距离判断。机翼那点点伸出来的地方，由于处于一条直线上，采用点和线碰撞。

uint8_t EnemyT1::hitDetect(int x, int y) {
	int a = (x - baseInfo.x) / 100;
	int b = (y - baseInfo.y) / 100;
	int c = 180; // 1.5 * 10000 / 100 // 碰撞圈子略大一点，

	return (a * a + b * b < c * c) ? 1 : 0;
}

uint8_t EnemyT2::hitDetect(int x, int y) {
	int a = (x - baseInfo.x) / 100;
	int b = (y - baseInfo.y) / 100;
	int c = 280; // 3 * 10000 / 100 // 碰撞圈子略大一点，

	return (a * a + b * b < c * c) ? 1 : 0;
}

uint8_t EnemyT3::hitDetect(int x, int y) {
	int a = (x - baseInfo.x) / 100;
	int b = (y - baseInfo.y) / 100;
	int c = 280; // 2.5 * 10000 / 100 // 碰撞圈子略大一点，

	if (a * a + b * b < c * c)
		return 1;

	if (y / PlaneXYScale == baseInfo.y / PlaneXYScale && x - baseInfo.x < 50000
			&& baseInfo.x - x < 50000)
		return 1;
	return 0;
}

TIPS：这里由于子弹很小，只是一个点，但屏幕上是一个像素，等价于覆盖了10000*10000这么大的范围，所以，做碰撞检测的时候，我们把刚体适当放大一点点。

void Plane::checkCollision() {
	for (ListNode *enemy = enemyManager.enemyList->next;
			enemy != enemyManager.enemyList; enemy = enemy->next) {
		EnemyBase *ene = (EnemyBase*) enemy->data;

		for (ListNode *bullet = bulletManager.player1BulletList->next;
				bullet != bulletManager.player1BulletList; bullet =
						bullet->next) {
			BulletObject_t *bul = (BulletObject_t*) bullet->data;
			if (ene->hitDetect(bul->x, bul->y)) {
				bul->visiable = 0;
				ene->HP -= 40;
				if (ene->HP < 0)
					ene->baseInfo.visiable = 0;
			}

		}

		for (ListNode *bullet = bulletManager.player2BulletList->next;
				bullet != bulletManager.player2BulletList; bullet =
						bullet->next) {
			BulletObject_t *bul = (BulletObject_t*) bullet->data;
			if (ene->hitDetect(bul->x, bul->y)) {
				bul->visiable = 0;
				ene->HP -= 40;
				if (ene->HP < 0)
					ene->baseInfo.visiable = 0;
			}

		}
	}
}

注意：这里把被伤害目标放在外循环，是为了在里面可以加多种伤害它的方式。?

好了，看看现阶段效果：

STM32学习笔记十五：WS2812制作像素游戏屏-飞行射击游戏（5）探索动画之帧动画