可见性路径规划

July 30, 2021About 2 min

我不知道翻译是不是对的,英文是：Visibility Graph Path Planning，简称：VGAPH。

是什么

我们从实际问题出发，如下图，当我们在游戏中需要使一个角色自动从start点移动到goal点并且绕开障碍物，蓝色为障碍物。

我们第一个想到的使用的方法就是寻路，那么我们说的VGAPH就是一种寻路的策略。

我们常见的寻路方案中，需要在角色移动或者是在规划路线时检测物理碰撞，从而找到顺畅通过的路线。检测碰撞也是一个比较耗时的工作，如果使用不当的话。 VGAPH这个寻路的方案是直接跳过碰撞检测。

可见性图（Visibility Graph）将导航问题转化为图搜索问题：

由于两点间最短路必然沿障碍物顶点折行（直线段不会无故绕弧），因此可见性图上的最优路径就是环境中的全局最短无碰撞路径。路径会紧贴障碍物的角，这也是其最显著的视觉特征。

构建步骤：

收集所有障碍物多边形的顶点，加入起点与终点，共 $n$ 个节点。
对每对节点做可见性检测（线段与所有障碍物边求交），可见则加边。暴力检测的复杂度为 $O (n^{2} \cdot m)$ （ $m$ 为障碍物边数总量），优化算法（如旋转扫描线）可降至 $O (n^{2} \log n)$ 。
在图上运行 A*（以欧氏距离为启发值）或 Dijkstra，输出最短路径点列。

复杂度与局限：