Circular Obstacle Pathfinding (2017)
3 hours ago
- #pathfinding
- #graph theory
- #A* algorithm
- A*算法可在任意图上找到最优路径，不仅限于网格。
- 它使用基于预估长度的优先队列：实际长度 + 启发式低估值。
- 通过使用冲浪边（双切线）和贴边来将圆形障碍物转换为图。
- 切线可见性图：内部和外部双切线连接圆形障碍物。
- 通过对障碍物进行点到线距离检查来剔除被阻挡的边。
- 处理相切或重叠的圆形障碍物需要对反余弦进行定义域检查。
- 贴边也可能被阻挡；交点决定其可用性。
- 通过应用闵可夫斯基加法进行简化：将移动的圆形视为点，同时扩大障碍物。
- 在A*过程中惰性地生成图以节省时间，使用邻居函数。
- 过滤有尖点的贴边，以保持最优路径旋转的一致性。