网格障碍物场景下两点间最短直线路径查找算法咨询

你描述的2D平面带障碍物、求航点间最短折线路径（无移动方向限制、仅连线不能穿障）的问题属于计算几何中的经典最短路径问题，有两个非常成熟的主流算法可以直接套用：

• 可见性图算法（Visibility Graph）
  这是该类问题的标准解法，完全匹配你的航班飞行模拟场景。你提到的不需要遵循类图遍历规则，应该是指不需要受网格8/4方向移动限制的网格图遍历，可见性图的图结构是根据实际可见性动态生成的，不受网格相邻关系约束，完全符合你的要求。核心逻辑是先为所有可通行航点（含起点）构建可见性关系：两个航点连线不穿过障碍物的情况下，为二者添加一条权重为欧氏距离的边。建图完成后直接运行Dijkstra算法即可得到起点到所有航点的最短路径，会自动选择你举例的S - 9 - 13这类最少中转的最短路径，不会产生冗余节点。如果需要优化可见性计算效率，可搭配旋转扫描法快速生成单个点的所有可见点集合，无需逐一遍历所有点对判断。
• 快速行进法（Fast Marching Method, FMM）
  如果你的障碍物是栅格化存储的，该算法更适合批量计算全图最短路径。它不需要显式构建可见性图，直接基于栅格平面求解从起点出发到任意点的最短距离，天然支持任意方向的移动规则。

你目前的设计思路和可见性图算法的核心逻辑是一致的，属于标准算法的简化实现方向。

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