腾讯游戏开发精粹
上QQ阅读APP看本书，新人免费读10天
设备和账号都新为新人
上一章目录下一章

1.10 动态地图

使用预计算得到的SDF地图较难实现动态更新，因为重新计算SDF比较耗时。那么如何能实现动态地图的需求呢？对于特殊游戏类型，如地牢游戏（Rouge-like）中的地图，本身就是由均匀网格所组成的，我们可以为其输入数据，将每一个网格都看作一个矩形，可以用上文中提到的矩形SDF公式来表示单个矩形。

在均匀网格地图上，当角色在一帧内行走的距离不会超过单个网格的大小时，可以通过检测每一帧与玩家所在网格相邻的8个网格的碰撞来实现规避障碍物的功能。如图1.16所示，当玩家行走之后位于网格4时，图中最右边的圆圈代表玩家，此时我们只需要检测网格6、0、5与玩家的最近距离来进行碰撞规避。

图1.16 角色在均匀网格地图上移动的例子

整个过程的伪代码如下：

    float EvalSDF(Vector2 p) {
        int x = posToGridX(p);      // 坐标离散成网格
        int y = posToGridY(p);
        float dist = cellSize;
        int center = grid[y ＊ width + x];
        if (center == WALL)         // WALL格子不可行走
          dist = min(dist, sdBox(centerPos - vecTopLeft, cellExtents));
        int topleft = grid[(y -1) ＊ width + (x -1)];
        if (topleft == WALL)
          dist = min(dist, sdBox(centerPos - vecTop, cellExtents));
        int top = grid[(y -1) ＊ width + x];
        // ...
        return dist;
    }

    Vector2 EvalGradient(Vector2 p) { /＊... ＊/ }

    void Update() {
        // 新目标位置
        Vector2 nextPlayerPos = playerPos + moveDir ＊ moveSpeed;
        // 目标位置的最近距离
        float d = EvalSDF(nextPlayerPos);
        // 距离小于玩家半径，有穿插
        if (d ＜ playerRadius) {
          // 计算最近表面的法线
          Vector2 n = EvalGradient(nextPlayerPos);
          // 将玩家推出障碍区域
          nextPlayerPos = nextPlayerPos + n ＊ (playerRadius - d);
        }
        playerPos = nextPlayerPos;
    }

SDF数据是通过读取网格地图中的可通过标记来决定这个网格是否参与计算的，因此就可以实现动态修改均匀网格地图，可以在运行时标记某个网格的通过性。

可以通过取距离场的梯度得到朝向向量，对于简单的几何图形，可以通过几何方法求出，比如圆形：

    Vector2 GradSphere(Vector2 p) {
        return p.Normalized();
    }

对于矩形，假设坐标系原点在矩形中心，矩形的四个象限是相互镜像的，则可将此问题退化为在一个象限内求解：

    Vector2 GradBox(Vector2 p) {
        // 退化为在+x, +y象限内求解
        Vector2 d = Vector2.Abs(p) - halfSize;
        // 记录符号，用来还原原始象限
        Vector2 sign = Sign(p);
        // 假设以halfSize为中心，p落在右上区域中，p-halfSize即为所求
        if (d.x ＞ 0 && d.y ＞ 0)
          return (d ＊ sign).Normalized();

        // 以halfSize为中心，检测距离x轴和y轴哪个更近
        float max = Max(d.x, d.y);
        // 距离x轴近，法线为y轴；反之，相反
        Vector2 grad = new Vector2(max == d.x ? 1 : 0, max == d.y ? 1 : 0 );
        return (grad ＊ sign).Normalized();
    }

刚才的方法是不考虑地图中会出现如图1.17所示的障碍物卡住玩家的情况的。

图1.17 障碍物卡住玩家的情况

要解决此问题，只需进行多次迭代求出最终修正的位置即可。而当玩家移动步幅较大时，如闪现等，需要进行连续碰撞检测。与基于预计算的离散SDF数据有所不同的是，均匀网格的SDF数据都是以函数计算的高精度连续的值，因此计算方法与前文稍有不同。

    bool DiskCast(Vector2 origin, Vector2 dir, float r, float maxDist, out float t)
    {
        t = 0;
        while (true) {
          // 根据当前t求出当前采样点p
          Vector2 p = origin + dir ＊ t;
          // 采样出最近距离
            float d = EvalSDF(p);
            // 若距离＜0，则p点在障碍区域中，结束迭代
            if (d ＜ 0)
                return false;

            // 当距离与角色半径的差距大于阈值时，继续迭代
            if (d ＞ radius + 0.001f)
                t += d - radius;
            else // 当距离与角色半径的差距小于阈值时，结束迭代
                return false;

            // 当t大于最大迭代距离时，结束迭代
            if (t ＞= maxDist) {
                t = maxDist;
                return true;
            }
        }
      }

而场景中的其他障碍物，如较大的汽车、其他玩家等，则可通过矩形、圆形的SDF函数来表示，并将结果与网格地图取出的SDF做交集操作。

上一章目录下一章