台球类html5游戏的AI设计与核心算法的实现

03月

420 0 0

　　本文想讲述下台球游戏中核心算法的实现, 以及游戏AI的设计技巧。当然自己也有个小愿望, 希望能实现一个html5版的台球游戏。

　　基础物理知识：

　　1、摩擦阻力

　　其满足牛顿第二定律：

　　f = m * a

　　速度与加速度关系公式：

　　vt = v0 + a * t

　　地面摩擦力与运动物体的方向相反, 阻碍物体的向前运动。

　　2、动量守恒

　　假设物体A质量为m1, 速度为v1, 物体B质量为m2, 速度为v2, 碰撞后速度分别为v1, v2。

　　则满足动量守恒定律：

　　m1 * v1 + m2 * v2 = m1 * v1 + m2 * v2

　　碰撞类型和能量守恒定律

　　1)完全弹性碰撞

　　动能没有损失, 则满足如下公式：

　　1/2 * m1 * v1^2 + 1/2 * m2 * v2^2 = 1/2 * m1 * v1^2 + 1/2 * m2 * v2^2

　　注: 前后物体的动能保持均衡, 没有其他能量的转化。

　　结合之前的动量守恒定律, 我们可以进一步得到：

　　v1 = [(m1-m2) * v1 + 2 * m2 * v2] / (m1 + m2)

　　v2 = [(m2-m1) * v2 + 2 * m1 * v1] / (m1 + m2)

　　2)完全非弹性碰撞

　　则存在其他能量的转化, 动能不守恒。

　　且此时两物体粘连, 速度一致, 即v1=v2, 此时动能损失最大。

　　3)弹性碰撞

　　介于完全弹性碰撞和完全非弹性碰撞两者之间。动能有损失的。

　　物理模型：

　　台球游戏中, 最核心的就是其物理模型的抽象及其碰撞算法的执行过程了。

　　鉴于是2D版的台球游戏, 因此我们对物理模型做下简化, 球运动的方向必然穿越球的中心。

　　把每个台球抽象为圆(x, y, radius), 而台球桌边框抽象为线段((x1, y1), (x2, y2))。

　　1、碰撞检测

　　1)检测球与球碰撞

　　我们假定球A(x1, y1, r), 球B(x2, y2, r)。则满足条件：

　　(x1 - x2) ^ 2 + (y1 - y2) ^ 2 <= (2*r) ^ 2

　　则发生碰撞, 否则没有发生碰撞

　　2) 检测球与球台边框碰撞

　　相对比较简单。求球心到边框的垂直距离即可, 若小于等于则发生碰撞, 若大于则没有。

　　2、碰撞反应

　　1)球与球的碰撞反应

　　动量是向量, 其在正交的两个方向上, 互相守恒。我们选取两球圆心的直线为x轴, 垂直于圆心直线的为y轴。如上图所述。

　　x轴上满足动量守恒：

　　m1 * Vx + m2 * Ux = m1 * Vx + m2 * Ux；

　　并假定两球碰撞是完全弹性碰撞, 两球质量相等m1=m2, 依据基础物理知识篇的结论。

　　Vx = [(m1-m2) * Vx + 2 * m2 * Ux] / (m1 + m2) = Ux；

　　Ux = [(m2-m1) * Ux + 2 * m1 * Vx] / (m1 + m2) = Vx；

　　在X轴方向, 两球交换速度, 而在Y轴方向, 两球分速度不变。

　　Vy = Vy；

　　Uy = Uy；

　　最终碰撞后的速度公式为：

　　V = Vx + Vy = Ux + Vy；

　　U = Ux + Uy = Vx + Uy；

　　2)球与边框的碰撞反应

　　把台球边框视为质量无穷大, 则简单把运动的球, 其在垂直边框的分方向反向即可。

　　假定碰撞碰撞平面为x轴

　　Vx = Vx；

　　Vy = -Vy；

　　最终速度公式为：

　　V = Vx + Vy = Vx - Vy；

　　碰撞执行算法：

　　游戏的主循环往往遵循如下代码结构：

while ( true ) {
game.update(time_interval);
game.render();
}

　　紫色球在t2时刻, 和蓝球检测到碰撞, 但实际上, 在紫球在t1~t2之间的某时刻和蓝球发生了碰撞。

　　为了解决该问题, 在具体的算法中, 需要引入更细的时间分片slice, 该过程在具体的update中进行模拟。

　　整个台球场景的更新函数：

void update(time_interval) {
- while time_interval > 0:
  - // 碰撞检测
    - if detectionCollide(time_interval, least_time, ball_pairs):
      - // 游戏更新least_time
        billiards.update(least_time)
        // 对碰撞的两球进行碰撞反应
        collideReaction(ball_pairs=>(ball, other))
        // time_interval 减少 least_time
        time_interval -= least_time
        else：
        // 游戏更新least_time
        billiards.update(time_interval)
        time_interval = 0
        
        }

复制代码
　　注: 碰撞反应, 按物理模型篇讲述的来。

　　而具体的碰撞检测算法为：

/*
- @brief
  - 在time_interval 时间内, 返回最先碰撞的球或台球边, 以及时间点
    - */
      - bool detectionCollide(time_interval, least_time, ball_pairs) {
        
        res = false;
        least_time = time_interval;
        
        foreach ball in billiards:
        foreach otherBall in billiards:
        // 求出两球的距离
        S = distance(ball, otherBall)
        // 以某一球作为参考坐标系, 则令一球速度向量变为 U’=U-V
        // 在圆心的直线作为x轴
        Ux(relative) = Ux(other ball) - Vx(ball)
        //若该方向使得两球远离, 则直接忽略
        if Ux(relative) < 0：
        continue
        //某该方向使得两球接近, 则可求其碰撞的预期时间点
        A = 2 * A; // 加速度为原来的两倍
        
        // 取两者最小的时间点
        delta_time = min(time_interval, Ux(relative) / Ax’)
        // 预期距离小于两球距离，则在time_interval中不会发生碰撞
        if 1/2 * Ax’ * delta_time ^ 2 + Ux(relative) * delta_time < S - 2*r:
        continue
        
        // 解一元二次方程, 使用二分搜索逼近求解
        res_time <= slove(1/2 * Ax’ * x ^ 2 + Ux(relative) * x = S - 2 * r)
        
        if res_time < least_time:
        ball_pairs <= (ball, otherBall)
        least_time = res_time
        res = true
        
        foreach wall in billiards:
        S = distance(ball, wall)
        // 设垂直于平面的方向为x轴
        if Vx < 0:
        continue
        
        // 取两者最小的时间点
        delta_time = min(time_interval, Vx / Ax)
        // 预期距离小于两球距离，则在time_interval中不会发生碰撞
        if 1/2 * Ax * delta_time ^ 2 + Vx * delta_time < S - r:
        continue
        
        // 解一元二次方程, 使用二分搜索逼近求解
        res_time <= slove(1/2 * A * x ^ 2 + Vx * x = S - r)
        
        if res_time < least_time:
        ball_pairs <= (ball, walll)
        least_time = res_time
        res = true
        
        return res
        
        }

复制代码
　　注: 对于一元二次方程, 也可以借助分1000个细粒度时间片, 然后计算逼近求解。

　　台球模拟碰撞算法过程, 大致就是如上所述。

　　计算最复杂的时刻, 其实就是开球, 打散一堆球的时候。

　　总结：

　　本文参考了NEHE的OPENGL中文教程第30课碰撞检测与模型运动。当然实现台球游戏, 未必真的需要该算法, 很多开发者直接使用box2d就能完美并轻松的实现。参考使用 cocos2d-x Box2d 的实现。后续的文章, 想讲述下台球游戏的AI如何设计和实现。望一同努力。

　　相关阅读：对弈类游戏的人工智能设计（1）：评估函数+博弈树算法

标签：魔兽开发经验爬坑游戏开发者开发技术游戏开发论坛

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！