3. 算法加速策略：A*变体、双向搜索、分层规划与增量式搜索

说到航线规划的性能优化，绕不开一个核心问题：搜索效率。经典的 A* 算法在网格地图上表现不错，但一旦地图变大、维度变高，它的搜索空间会膨胀得很快。我这些年踩过的坑，十有八九都跟搜索空间失控有关。

这一章，我们聊聊四种主流的加速策略。它们不是互相替代的关系，而是针对不同场景的「手术刀」。我个人习惯把它们分成两类：一类是改搜索逻辑（Theta*、JPS、双向搜索），另一类是改搜索结构（分层规划、增量式搜索）。

3.1 A* 变体：Theta* 与 JPS

经典 A* 有个隐含假设：路径只能沿网格的 8 个方向走。这导致路径看起来「锯齿状」，不够自然。Theta* 就是为了解决这个问题。

3.1.1 Theta*：让路径「直」起来

Theta* 的核心改动很小：在扩展节点时，检查当前节点的父节点与待扩展节点之间是否有视线（Line of Sight）。如果有，就直接把父节点设为祖父节点，跳过中间节点。说白了，就是允许「跳级」。

// Theta* 核心逻辑（伪代码）
function ThetaStar(start, goal):
    openSet = {start}
    cameFrom = {}
    gScore = map with default INF
    gScore[start] = 0
    
    while openSet is not empty:
        current = node in openSet with lowest fScore
        
        if current == goal:
            return reconstructPath(cameFrom, current)
        
        openSet.remove(current)
        for neighbor in neighbors(current):
            // 关键区别：检查视线
            if hasLineOfSight(cameFrom[current], neighbor):
                tentativeG = gScore[cameFrom[current]] + 
                            dist(cameFrom[current], neighbor)
                if tentativeG < gScore[neighbor]:
                    cameFrom[neighbor] = cameFrom[current]
                    gScore[neighbor] = tentativeG
            else:
                tentativeG = gScore[current] + dist(current, neighbor)
                if tentativeG < gScore[neighbor]:
                    cameFrom[neighbor] = current
                    gScore[neighbor] = tentativeG
            
            if neighbor not in openSet:
                openSet.add(neighbor)
    
    return failure

3.1.2 JPS：剪枝的艺术

JPS（Jump Point Search）是另一种思路。它不改变路径质量，而是大幅减少需要扩展的节点数。怎么做到的？利用网格的对称性。

你想想看，在一个空旷的网格区域里，A* 会把周围一圈节点都塞进 open set。但 JPS 会沿着一个方向「跳」过去，直到遇到障碍物或「强制邻居」才停下来。这一跳，可能跳过几十个节点。

3.2 双向搜索：两头并进

双向搜索的思路很朴素：从起点和终点同时开始搜索，让它们在中间相遇。为什么能加速？因为搜索空间的增长是平方级的，两个半球的搜索空间加起来，通常远小于一个完整球。

但这里有个坑：如何判断相遇？ 我见过不少实现，简单地检查两个方向的 open set 是否有交集。这其实不够。更可靠的做法是：当某个节点同时被两个方向的搜索「关闭」时，才认为相遇。

// 双向 A* 相遇判断（推荐做法）
function isMeetingPoint(node, forwardClosed, backwardClosed):
    // 节点必须同时出现在两个方向的 closed set 中
    return node in forwardClosed and node in backwardClosed

// 路径拼接
function combinePath(forwardCameFrom, backwardCameFrom, meetingPoint):
    forwardPath = reconstructPath(forwardCameFrom, meetingPoint)
    backwardPath = reconstructPath(backwardCameFrom, meetingPoint)
    backwardPath.reverse()
    return forwardPath + backwardPath[1:]  // 去掉重复的 meetingPoint

3.3 分层规划：HPA*

HPA*（Hierarchical Pathfinding A*）的思路是「先粗后细」。它把地图分成若干块（cluster），先在块级别规划一条粗路径，再在每个块内部细化。

我最早接触 HPA* 是在一个 RTS 游戏项目里。地图 2000x2000，单位数量上百。如果用 A*，每帧光寻路就能把 CPU 吃满。HPA* 把搜索时间从几十毫秒降到了 1-2 毫秒。

3.3.1 核心步骤

1. 分块：将地图划分为 k×k 的块（通常 k=8 或 16）。
2. 提取入口点：在块与块之间的边界上，找到可通行的「门」。
3. 构建抽象图：以块为节点，以入口点之间的路径为边，构建一个稀疏图。
4. 两层搜索：先在抽象图上搜索，再在每个块内部做局部 A*。

3.4 增量式搜索：D* Lite

前面几种策略都是针对静态地图的。如果地图会动态变化（比如障碍物移动、新障碍物出现），每次重新搜索就太浪费了。D* Lite 就是干这个的——它复用上一次的搜索结果，只更新受影响的部分。

D* Lite 的核心思想是：反向搜索。它从目标点向起点搜索，并维护每个节点的 rhs 值（一步可达的最小代价）。当地图变化时，它只更新 rhs 值发生变化的节点，然后重新规划。

// D* Lite 核心更新逻辑（简化版）
function updateVertex(u):
    if u != goal:
        rhs[u] = min_{v in succ(u)} (cost(u, v) + g[v])
    if u in openSet:
        openSet.remove(u)
    if g[u] != rhs[u]:
        openSet.add(u, calculateKey(u))

function computeShortestPath():
    while openSet.topKey() < calculateKey(start) or rhs[start] != g[start]:
        u = openSet.pop()
        if g[u] > rhs[u]:
            g[u] = rhs[u]
            for v in pred(u):
                updateVertex(v)
        else:
            g[u] = INF
            for v in pred(u) ∪ {u}:
                updateVertex(v)

3.5 选型指南：什么时候用什么？

说了这么多，到底怎么选？我列了一个决策表，你可以根据场景对号入座。