可见性路径规划
July 30, 2021Less than 1 minute
可见性路径规划
我不知道翻译是不是对的,英文是：Visibility Graph Path Planning，简称：VGAPH。
是什么
我们从实际问题出发，如下图，当我们在游戏中需要使一个角色自动从start点移动到goal点并且绕开障碍物，蓝色为障碍物。
我们第一个想到的使用的方法就是寻路，那么我们说的VGAPH就是一种寻路的策略。
为什么
我们常见的寻路方案中，需要在角色移动或者是在规划路线时检测物理碰撞，从而找到顺畅通过的路线。检测碰撞也是一个比较耗时的工作，如果使用不当的话。 VGAPH这个寻路的方案是直接跳过碰撞检测。
怎么用
实现
参考
https://lis.csail.mit.edu/pubs/tlp/collision-free-planning-cacm.pdf
http://ntur.lib.ntu.edu.tw/bitstream/246246/200704191001565/1/01389835.pdf
https://github.com/christopher-boustros/Unity-Visibility-Graph-Path-Planning-Simulation