到目前为止，我们有了时间，可以输入，还可以对「物件」进行位移，看来可以开始让「小铁(LittleIron)」开始跑跑跳跳了，就像那名传奇的水管工一样，但在这之前我想先让小铁「脚踏实地」，这个就会需要一些基本的碰撞知识了。

今日目标

• 初步了解几个常见的碰撞演算法
• AABB碰撞侦测演算法

碰撞侦测与解析与这款游戏

物理引擎与游戏中，所说到的碰撞，整个流程应该拆成两种，侦测与碰撞。

侦测就是回答两个物体有没有接触或撞在一起的方法；解析则是碰撞之後，对於这些「碰撞到的点要做甚麽」的处理方法。由於目标是2D游戏，一定比3D处理简单N倍，而且事实上也不会套入真正的物理处理(各式各样的「力」)，又更加简单了。

注意: 简单不代表容易 (Simple does not mean easy to do...)

最重要的还有一点，我们游戏物件的碰撞「框」，预测大部分都会是都会是矩形，而且是不会旋转的，这又大大减少难度，原因是有这麽多碰撞侦测的演算法，都是考虑这些图形或模型是不规则(凸体(Convex))，且可能会进行位移旋转之类操作的。

所以接下来，做个实验看看，来看看就简单的碰撞侦测演算法 - AABB。

实验: AABB

AABB是Axis-Aligned Bounding Box的简称，从名字就可以看出来Bounding Box，会是把我们要检测的物件用一个Box装起来，不论是否旋转或是是不规则的形状，然後互相比对各轴的最大与最小的边界，然後就可以决定是不是碰撞了，简单标示一下，其实就可以看得懂了:

//         x1 min       x1 max
//    y1 max +------------+
//           |            |
//           |        +---|--------+ y2 max
//           |        |   |        |
//           |        |   |        |
//    y1 min +--------|---+        |
//                    |            |
//                    +------------+ y2 min
//                   x2 min      x2 max

if (x2 min > x1 max && x1 min < x2 max
   && y1 min < y2 max %&& y2 min < y1 max) 
   {
       // Collision!!
   }

其实核心就是这样子，如上面所说的比较各轴可以知道答案了。下面直接贴上我测试的code，可以参考看看

// struct for our game object
    typedef struct {
        V2f pos;
        V2f speed;
        V2f size;
        Color c;
    } Entity;


// in `Game Loop`
       float dt = GetDeltaTime();
        if (IsKeyDown(KEY_RIGHT)) {
            p.pos.x += p.speed.x * dt;
        } else if (IsKeyDown(KEY_LEFT)) {
            p.pos.x -= p.speed.x * dt;
        }

        if (IsKeyDown(KEY_DOWN)) {
            p.pos.y += p.speed.y * dt;
        } else if (IsKeyDown(KEY_UP)) {
            p.pos.y -= p.speed.y * dt;
        }

        // AABB
        float box_x_min = box.pos.x - box.size.x / 2.0f;
        float box_x_max = box.pos.x + box.size.x / 2.0f;
        float box_y_min = box.pos.y - box.size.y / 2.0f;
        float box_y_max = box.pos.y + box.size.y / 2.0f;

        float p_x_min = p.pos.x - p.size.x / 2.0f;
        float p_x_max = p.pos.x + p.size.x / 2.0f;
        float p_y_min = p.pos.y - p.size.y / 2.0f;
        float p_y_max = p.pos.y + p.size.y / 2.0f;

        if (p_x_max >= box_x_min && p_x_min <= box_x_max
            && p_y_max >= box_y_min && p_y_min <= box_y_max) {
            p.c = COLOR_PURPLE;
            box.c = COLOR_ORANGE;
        } else {
            p.c = COLOR_WHITE;
            box.c = COLOR_WHITE;
        }

功能是，如果碰撞就变换颜色，但以我们游戏来讲，应该是要阻挡两个物件可以重叠才对。

其他我还「听过」的演算法

其实之前就听过一些碰撞侦测的演算法了，但也都是听过。因为数学的关系，让我却步，於是趁这机会多接触一下，以下是我对这些演算法的初步了解(胡言乱语)。

• SAT: 分离轴碰撞检测(Separating Axis Theorem)，印象中这个做法是利用凸体顶点在某个轴(这个轴怎麽来的)的投影，利用投影检测是否重叠表示碰撞。
• GJK: 完全不知道，只知道这是以三的人的名字命名的(Gilbert–Johnson–Keerthi) (ˊ_>ˋ)
• EPA: 完全不知道这是甚麽，好像是要搭配GJK完成的演算法 (ˊ_>ˋ)

参考

• 游戏中的碰撞检测Collision Detection
• Learn OpenGL
• YT - Convex Polygon Collisions #1

这是今天成果，只是简单的测试，没有切到别的文件进行封装。明天会尝试实作SAT的方法。