2D游戏中常见的碰撞检测处理（仅碰撞体）【持续更新】

写在前面

嗯...打算开始每天写点啥了，不知道能坚持多久。

准备以一周为单位来进行更新，周一~周三写一些图形方面的内容，四~六是和图形没有什么太大关联的内容（意会就好），周日作为一个更新重点试着写一些乱七八糟的东西。

那么就这样开始更新了w~

在现今的游戏中，碰撞检测可以说是一个基础的不能再基础的技术。它关乎能否正确判断玩家的攻击有没有击中目标，判断玩家有没有踩在地板上，判断某两个物体有没有碰撞在一起，进而衍生出其它的各种行为。

而碰撞检测是建立在碰撞体上的。碰撞体是对一个物体“边界”的确切描述，它描述了每个需要进行碰撞检测的物体的边界，并依靠数学方法判断这些边界是否相交，进而产生碰撞检测的结果。

（“老鹰用爪子抓到了兔子”）

如上图所示，代表老鹰爪子的两个蓝色圆和代表兔子的淡黄色圆“相交”了，由此我们判定鹰抓到了兔子，进行一系列的后续操作。在这个过程中，我们不在意鹰的爪子具体是什么样子的，而只在意它的边界在哪里。在这个例子中，边界就是一个单纯的圆形。

在电子游戏发展早期，碰撞体和实际的轮廓之间还存在着巨大的差异，只是能够概括其大概的边界而已。尽管现在我们有许多丰富的手段来让我们的碰撞体尽可能的接近真实的外形，但多数情况下并不会这么做——归根结底，这么做没给游戏的真实程度带来什么太大的提升，反而还糟蹋了游戏的运行速度。

那让我们从一个最基本的开始吧。

1）圆形碰撞体

圆形碰撞体可以说是最简单的一种碰撞体，其计算速度也是最快的，算法也非常容易理解。

回想一下初中数学中关于两圆“相交”的定义：两圆圆心的距离大于半径和，我们就可以按照它来判断两圆是否相交。

1 bool IsHit(double x1, double y1, double x2, double y2, double r1, double r2)
2 {
3     //勾股定理
4     return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) < (r1+r2)*(r1+r2);
5 }

它也可以非常方便的扩展到三维球。这种碰撞体拥有最简单的计算过程，在运动速度够快（或形状够圆）的情况下也不会有太大的违和感；在弹幕游戏和射击游戏以及大量其它游戏中应用广泛。

2）"轴对齐"包围盒、Axis-Aligned Bounding Box （AABB）

这玩意好像也没什么统一的译名，所以在这里称为“轴对齐”包围盒，不过说AABB的话知道的人应该都知道是什么东西。除了用圆（球）来表示一个物体的边界，另外一种容易被人们想到的模型就是“盒子”——长方形（体）。但是会在空间中能随便转的盒子好像计算起来稍微有那么一点难算，也不好表示它到底怎么转了之类，于是人们就想到干脆别让它转，只能“立着”，就产生了AABB包围盒。

这么说好像有点越说越乱了...总之看图。

对于这种包围盒，我们可以很方便的通过min点和MAX点（见右上方蓝色方块）的位置来完全确定这样一个盒子，同时通过一些比较大小的操作就可以确定两个盒子是否相交。

（懒得贴代码了w）

3）逐像素碰撞检测

为了追求和形状最完美的贴合，人们展示了计算机可怕的计算力 —— 一种近乎于“暴力枚举”的方法。人们假设组成每个画面上的物体的是许许多多的像素点（虽然事实上这多半是真实情况），然后逐个像素的去比较它和其他的形状是否发生了碰撞。

从一个比较简单但是足够说清楚事的例子开始吧。假设有两个大小为3x3的物体a和b（这个大小在屏幕上就是一个点），组成它们的像素分别是a1~a9，b1~b9：

Pixel by pixel checking.

为了“逐像素”地判断a和b是否发生碰撞，我们需要每个像素每个像素的比较。来看看人们是怎么粗暴地解决这个问题的：

1）比较a1和b1位置是否相同

2）比较a1和b2位置是否相同

3）比较a1和b3位置是否相同

...

10）比较a2和b2位置是否相同（b1已经比过了）

11）比较a2和b3

...

45）比较a9和b9

就这样足足45次计算算出了两个3x3的物体是否碰撞。事实上这种方法有着巨大的开销，只有在非常必要的时候（其他方法都会误判）才有可能把它祭出来。不过它有着无可比拟的精细程度，在不追求实时渲染的情况下（比如一些工业生产、模拟、科研场景中），才稍微有点用它的必要性。

4）方向包围盒（Oriented Bounding Box, OBB）

方向包围盒OBB是一种被广泛使用的碰撞体。它也是一个长方形，但是它可以在空间中自由旋转。同时，我们只需要稍微复杂一点的方法就可以计算出两个OBB包围盒是否相交，加上它可以自由旋转带来的非常少的冗余部分（本不属于那个物体的 “碰撞面积” ），让它成为了最广泛使用的碰撞体。

明天会有啥？

碰撞体的复合 & 碰撞检测上的小技巧。

随记 - 2016 / 4 / 7 星期四

第一天更新，感觉那个图还是蛮费时间的...之后大部分图可能直接从网上找了。

===

Unity似乎用不了GLSL。可以试试NV的Cg，原因吗...只能说虽然身在ms但是对HLSL没有什么好感。

用Cg跟着教程随便写了个Show Screen Space Normal的shader，感觉还是挺平易近人的。

P.S. Unity添加shader的方法：

想要和场景中的灯光交互需要用Unity的SurfaceShader，还没有仔细研究，感觉unity自带的standardShader这个材质能干的事情够多了。

unity也提供了传统的shader接口，包括VS（顶点着色器）, FS（片断着色器）； GS（几何体“着色”器）/HS（外壳“着色”器）/TS（细分“着色”器）/DS（域“着色”器）是否支持还没细看。想使用的话需要使用Unlit（无光） Shader。

似乎也支持进行GPU的通用计算（CS, Computed Shader），没有看。

具体的添加方法： Assets > Create > Shader > Unlit Shader / Surface Shader.

详细的看官网： http://docs.unity3d.com/Manual/ShadersOverview.html

（附上那个蠢极了的ShowScreenSpaceNormal）

 1 Shader "Unlit/simpleShowNormals"
 2 {
 3     Properties
 4     {
 5         _MainTex ("Texture", 2D) = "white" {}
 6     }
 7     SubShader
 8     {
 9         Tags { "RenderType"="Opaque" }
10         LOD 100
11 
12         Pass
13         {
14             CGPROGRAM
15             #pragma vertex vert
16             #pragma fragment frag
17 
18             struct appdata
19             {
20                 float3 normal : NORMAL;
21                 float4 vertex : POSITION;
22                 float2 uv : TEXCOORD0;
23             };
24 
25             struct v2f
26             {
27                 fixed3 normal3 : COLOR0;
28                 float2 uv : TEXCOORD0;
29                 UNITY_FOG_COORDS(1)
30                 float4 vertex : SV_POSITION;
31             };
32 
33             sampler2D _MainTex;
34             float4 _MainTex_ST;
35             
36             v2f vert (appdata v)
37             {
38                 v2f o;
39                 o.vertex = mul(UNITY_MATRIX_MVP, v.vertex);
40                 o.uv = TRANSFORM_TEX(v.uv, _MainTex);
41                 o.normal3 = mul(UNITY_MATRIX_MVP, v.normal) * 0.5 + 0.5;
42                 return o;
43             }
44             
45             fixed4 frag (v2f i) : SV_Target
46             {
47                 return fixed4(i.normal3, 1);
48             }
49             ENDCG
50         }
51     }
52 }