围绕墙壁的二维寻路

Question

在最近发布的game中，角色导航（很差）围绕着执行任务的2D火星表面。我试图想出一个更好的算法（只是为了好玩）。如果你能够有效地构建“边缘”，你可以使用像A *搜索这样的算法。

问题：给定一组不相交的线和两个点，开始和结束，找到不与任何线相交的最短路线。

Answer 1

这个问题被称为 “任意角度路径规划”。简单的答案是有一些方法可以在O（n^2 log n）时间（也许更好）中生成可见性图，但由于可见性图可能具有多达n^2个边，所以使用生成VG的算法将始终具有最差案例表现比n^2慢。

VG算法：的Ch 13计算几何：算法和应用由德伯格

最先进的技术避免产生VG的，而是牺牲正确性渐近更快的结果。一些资源为动力：

• Lazy Theta *，一个A *变体：walkthrough | paper
• Sampling-Based Motion Planning，运动的第5章规划通过拉瓦列
• CS course with lecture notes.