任意目标点集场景下双向A*最短路径寻路方案咨询

完全可以基于标准双向A*框架改造实现多目标（抵达目标集合中任意节点即终止）的最短路径搜索，适配你提到的不可达目标逆可达集小的场景特性，核心规则如下：

基础搜索框架定义 #

首先明确两个搜索方向的运行逻辑：

• 正向搜索：在原始有向图上从给定起点s向外扩展，维护g_f[u]为起点到节点u的已探索最短路径长度
• 反向搜索：在边方向全翻转的反向图上扩展，初始化时直接将所有目标点加入反向开放队列，所有目标点的初始g_b[t] = 0（t属于目标集合T），维护g_b[v]为反向图上任意目标点到v的已探索最短路径长度，等价于原图上v到任意目标点的已探索最短路径长度

这个初始化逻辑刚好适配你提到的不可达目标特性：不可达目标在反向图中可扩展的节点规模很小，反向搜索会快速遍历完这类目标的所有可达节点，一旦反向开放队列提前清空，可直接判定所有目标均不可达，无需等正向搜索遍历大范围节点。

启发函数设定 #

两个方向的启发函数只要满足标准双向A*的可采纳/一致性要求即可，不需要特殊设计：

• 正向启发h_f[u]：和普通单源多目标A*完全一致，取节点u到所有目标点的最短距离下界即可，比如游戏场景常用的曼哈顿距离、欧氏距离，计算时取u到所有目标点的距离最小值，天然满足h_f[u] ≤ min_{t∈T} d(u,t)的可采纳要求
• 反向启发h_b[v]：反向搜索的目标是找到到起点s的路径，因此直接取节点v到起点s的距离下界即可，同样用空间距离计算，满足h_b[v] ≤ d(s,v)的可采纳要求
  只要两个方向的启发函数各自满足一致性（三角不等式），就完全符合双向A*的启发约束条件，不会损失正确性。

终止条件 #

和单目标双向A*的终止逻辑完全对齐，不需要为多目标特殊修改：

1. 维护一个全局变量μ存储当前已知的最短路径长度上界，初始值设为无穷大
2. 每次从正向或反向开放队列取出节点扩展时，检查该节点是否已经被另一个方向访问过：如果是，计算候选路径长度g_f[u] + g_b[u]，若该值小于当前μ则更新μ为该值
3. 当正向队列下一个待扩展节点的优先级f_f = g_f[u] + h_f[u]，加上反向队列下一个待扩展节点的优先级f_b = g_b[v] + h_b[v]，二者之和大于等于当前μ时，搜索终止，此时μ对应的路径就是全局最短路径

场景适配优化 #

针对游戏AI场景可以做几个针对性的性能优化：

• 如果不需要严格最短路径，可以给两个方向的启发值加1.1~1.5倍的权重做加权A*，搜索速度会提升30%以上，路径偏差在游戏场景里几乎不可感知
• 动态更新目标集合时，不需要重置全部搜索状态，只需要把新增的目标点加入反向开放队列、把移除的目标点对应的反向g值标记为无效即可，适合帧间复用搜索状态的场景
• 扩展节点时优先选正向/反向队列顶f值更小的方向取节点扩展，可以进一步减少无效节点遍历量

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