寻求适用于带地形权重的无限加权网格的高效任意角度寻路算法

开发者阿泽

2026-6-22

带地形权重的无限网格任意角度寻路优化方案

我正在开发一款涉及地形寻路的游戏，不同地表（如雪地、泥地等）对应不同移动成本。需要一种能高效运行在带地形权重的无限加权网格上的任意角度寻路算法，目标是找到考虑各类地形权重的最短路径。

之前尝试给Theta*实现了一个成本函数，通过计算路径点连线下方节点的权重来累计成本，但效果很差：算法效率极低，找不到最优路径，还经常往反方向搜索。

原成本函数代码：

function cost(node1, node2)
    initialize totalCost to 0

    points = supercover(node1, node2)

    for each point in points except the last one do
        node = getNode(point.x, point.y)
        nextPoint = next point in points
        nextNode = getNode(nextPoint.x, nextPoint.y)
        
        if nextNode is not found then
            exit loop
        end

        distance = euclidean_distance(node, nextNode)

        if nextNode.material exists in costs then
            multiplier = costs[nextNode.material]
        else
            multiplier = 1
        end

        totalCost = totalCost + (distance * multiplier)
    end

    return totalCost
end function

问题分析

你的成本函数存在几个核心问题：

冗余计算拖慢效率：每次计算两点成本都遍历Supercover覆盖的所有节点，无限网格下这种遍历会带来巨大性能开销，路径越长问题越明显。
成本逻辑偏差：仅给nextNode的权重乘距离，实际上路径段是由覆盖的所有单元格共同影响成本，当前逻辑会漏掉部分节点权重，导致成本计算不准，进而让Theta*的启发式判断出错，出现反向搜索。
边界处理不当：nextNode不存在就直接退出循环，会导致成本计算不完整，算法无法准确评估路径代价。

优化方案

1. 简化地形成本采样逻辑

不需要遍历Supercover的所有点，改用线段步长采样，只统计路径穿过的单元格权重，避免重复计算同一单元格：

function cost(node1, node2)
    initialize totalCost to 0
    currentPos = node1.position
    direction = normalize(node2.position - node1.position)
    remainingDistance = euclidean_distance(node1, node2)
    // 步长设为网格单元格大小，保证每次采样都能覆盖到新单元格
    stepSize = min(gridCellSize, remainingDistance)

    while remainingDistance > 0:
        currentCell = getCell(currentPos.x, currentPos.y)
        // 无限网格下默认用基础权重，而非直接退出
        multiplier = costs[currentCell.material] if currentCell?.material in costs else 1
        
        costStep = stepSize * multiplier
        totalCost += costStep

        currentPos = currentPos + direction * stepSize
        remainingDistance -= stepSize

    return totalCost
end function

2. 修正Theta*启发式函数

Theta*的启发式必须满足可采纳性（启发值不超过实际最小成本），针对加权网格，用欧几里得距离乘以最小地形权重，避免启发值过高导致算法偏离最优路径：

function heuristic(node, goal)
    minMultiplier = min(costs.values())
    return euclidean_distance(node, goal) * minMultiplier
end function

3. 无限网格剪枝策略

因为是无限网格，必须限制搜索范围：

设定最大搜索距离，超出范围则放弃当前分支
用哈希表记录已访问的单元格坐标，避免重复处理同一单元格

4. 替代算法推荐

如果Theta*优化后仍不满足需求，可以考虑：

任意角度网格寻路（AAPG）：专门针对网格的任意角度寻路，原生支持加权地形
LPA（终身规划A）**：适合动态变化的无限网格，能复用之前的搜索结果，提升效率

内容的提问来源于stack exchange，提问作者josima