A星寻路算法(六):平滑权重

Number of views 79

A星寻路算法(五):权重与并发中我们介绍了如何为多个角色的多个目标点开启寻路的并发逻辑,并为不同的地形选择最优的线路。但是有一个问题是,寻路的过程如马路,角色会沿着马路边沿进行,这有悖常理。针对该问题,我们需要平滑权重。

image1747357541630.png

平滑权重并没有想象的难,我们只需要对移动成本做“模糊”处理即可完成。

image1747357985526.png

image1747358006875.png

通过对马路的“模糊”处理,间接对移动成本(这里指的地形成本,即移动惩罚)进行了平滑操作。我们得到了在马路中间寻路的自然效果。

image1747358134998.png

我们来看一下它的具体实现。对于模糊操作,我们使用模糊算法"Box Blur",假设地形成本如下右图所示:

image1747359080084.png

对于“Box Blur”我们需要找到“Kernel”即卷积核,我们会把每一个网格单元作为核心,并通过计算该核心周边局部区域内(半径)的平均值来实现模糊效果,卷积核的Size通常为奇数,因为目的是对卷积核的核心做均值运算。

先以左上角第一个节点为核心说明:

image1747359984823.png

我们使用了3x3的卷积核,卷积核大小半径可以扩大。当我们选择左上角第一个节点时,由于核心在边缘位置,所以会导致卷积核的网格中有部分为空值。为了解决这个问题,我们可以简单重复边缘的值来填充这些空值。

image1747363288098.png

这时候就可以把卷积核中的值进行相加,得到了10。接着除以卷积核网格的块数,这里为9,来获取平均值。然后把平均值写入新的网格中,即是10/9向下取整。接着移动到下一个节点,就这样循环往复。

image1747363653871.png

直到所有节点都计算完成。新网格即是计算后的新的地形成本。

image1747363832370.png

这种方式还是有优化空间。因为我们设定的卷积核是3x3的网格,实际上我们可以在单方向上 (先横向后纵向)以固定数量的网格做卷积 (我们采用3个网格举例)。这样可以大大减少计算量。算法如下。

image1747364922498.png

先横向遍历,我们还是以左上角的节点作为遍历过程的第一个节点。得到结果为3

image1747377332115.png

接着第二个节点,现在节点的运算就比较特殊了。它的结果是通过前一个节点的运算结果 3,减去现有卷积核最左侧节点的前一个节点的值 1,加上新框选进的最右侧节点 2。得到4。

image1747377900389.png

image1747378032630.png

以此类推,直至结束:image1747378163597.png

接着纵向遍历,这时候我们会把横向遍历的结果作为纵向遍历的数据源进行纵向遍历,在横向遍历中我们使用的是1x3 (1行3列)网格遍历,而纵向我们使用的是3x1 (3行1列)网格遍历。

image1747378679075.pngimage1747378779594.png

以此类推,最后会把每个网格的结果除以9进行平均。

image1747378878853.png

虽然纵向遍历与横向遍历所花费的时间一致。但是该计算方式的整体效率还是比用最开始时介绍的方法效率更高。

我们在Grid类中新增了BlurPenaltyMap函数用于实现上述平滑权重的逻辑,并在CreateGrid函数中调用:

void CreateGrid() {
    // 初始化网格数组,大小为 gridSizeX × gridSizeY
    grid = new Node[gridSizeX, gridSizeY];

    // 计算网格的左下角世界坐标(相对于物体中心)
    Vector3 worldBottomLeft = transform.position 
        - Vector3.right * gridWorldSize.x / 2 
        - Vector3.forward * gridWorldSize.y / 2;

    // 遍历网格的每个节点
    for (int x = 0; x < gridSizeX; x++) {
        for (int y = 0; y < gridSizeY; y++) {
            // 计算当前节点的中心世界坐标
            Vector3 worldPoint = worldBottomLeft 
                + Vector3.right * (x * nodeDiameter + nodeRadius) 
                + Vector3.forward * (y * nodeDiameter + nodeRadius);

            // 检查该节点是否可行走(无碰撞体阻挡)
            bool walkable = !(Physics.CheckSphere(worldPoint, nodeRadius, unwalkableMask));

            int movementPenalty = 0;

            // 向下发射射线,检测该节点所在的地形类型(如草地、岩石等)
            Ray ray = new Ray(worldPoint + Vector3.up * 50, Vector3.down);
            RaycastHit hit;
            if (Physics.Raycast(ray, out hit, 100, walkableMask)) {
                // 根据地形类型从字典中获取对应的移动惩罚值
                walkableRegionsDictionary.TryGetValue(hit.collider.gameObject.layer, out movementPenalty);
            }

            // 如果节点不可行走,增加额外的障碍物接近惩罚
            if (!walkable) {
                movementPenalty += obstacleProximityPenalty;
            }

            // 创建节点并存储到网格中
            grid[x, y] = new Node(walkable, worldPoint, x, y, movementPenalty);
        }
    }

    // 对移动惩罚值进行模糊处理(平滑惩罚分布)
    BlurPenaltyMap(3);
}

BlurPenaltyMap() 方法

void BlurPenaltyMap(int blurSize) {
    // 计算模糊核的尺寸(例如 blurSize=3 时,核大小为 7×7)
    int kernelSize = blurSize * 2 + 1;
    int kernelExtents = (kernelSize - 1) / 2; // 核的半径

    // 初始化两个惩罚值数组:水平和垂直方向的中间结果
    int[,] penaltiesHorizontalPass = new int[gridSizeX, gridSizeY];
    int[,] penaltiesVerticalPass = new int[gridSizeX, gridSizeY];

    // 水平方向模糊处理
    for (int y = 0; y < gridSizeY; y++) {
        // 初始化第一列的水平惩罚值(滑动窗口初始范围)
        for (int x = -kernelExtents; x <= kernelExtents; x++) {
            int sampleX = Mathf.Clamp(x, 0, kernelExtents); // 限制采样范围
            penaltiesHorizontalPass[0, y] += grid[sampleX, y].movementPenalty;
        }

        // 遍历后续列,通过滑动窗口更新水平惩罚值
        for (int x = 1; x < gridSizeX; x++) {
            int removeIndex = Mathf.Clamp(x - kernelExtents - 1, 0, gridSizeX); // 移除左侧旧值
            int addIndex = Mathf.Clamp(x + kernelExtents, 0, gridSizeX - 1);   // 添加右侧新值
            penaltiesHorizontalPass[x, y] = penaltiesHorizontalPass[x - 1, y] 
                - grid[removeIndex, y].movementPenalty 
                + grid[addIndex, y].movementPenalty;
        }
    }

    // 垂直方向模糊处理
    for (int x = 0; x < gridSizeX; x++) {
        // 初始化第一行的垂直惩罚值(滑动窗口初始范围)
        for (int y = -kernelExtents; y <= kernelExtents; y++) {
            int sampleY = Mathf.Clamp(y, 0, kernelExtents); // 限制采样范围
            penaltiesVerticalPass[x, 0] += penaltiesHorizontalPass[x, sampleY];
        }

        // 计算第一行的模糊惩罚值
        int blurredPenalty = Mathf.RoundToInt((float)penaltiesVerticalPass[x, 0] / (kernelSize * kernelSize));
        grid[x, 0].movementPenalty = blurredPenalty;

        // 遍历后续行,通过滑动窗口更新垂直惩罚值
        for (int y = 1; y < gridSizeY; y++) {
            int removeIndex = Mathf.Clamp(y - kernelExtents - 1, 0, gridSizeY); // 移除上侧旧值
            int addIndex = Mathf.Clamp(y + kernelExtents, 0, gridSizeY - 1);   // 添加下侧新值
            penaltiesVerticalPass[x, y] = penaltiesVerticalPass[x, y - 1] 
                - penaltiesHorizontalPass[x, removeIndex] 
                + penaltiesHorizontalPass[x, addIndex];
            blurredPenalty = Mathf.RoundToInt((float)penaltiesVerticalPass[x, y] / (kernelSize * kernelSize));
            grid[x, y].movementPenalty = blurredPenalty;

            // 更新全局最大/最小惩罚值
            if (blurredPenalty > penaltyMax) {
                penaltyMax = blurredPenalty;
            }
            if (blurredPenalty < penaltyMin) {
                penaltyMin = blurredPenalty;
            }
        }
    }
}
0 Answers