A*用于寻找最短路径并避免线路作为障碍物

Question

我必须得到2D中两点之间的(最短)/(最佳)距离.我必须避免可能连接在一起的线条形状.关于如何表示我可以旅行的节点的任何建议？我曾想过制作一个网格,但这听起来不太准确或优雅.如果一条线的任何一点在一个正方形内(节点是正方形的中心),我会认为一个节点是不可行的.

一个例子是从A点到B点.

网格是推荐的解决方法吗？非常感谢!

Answer 1

我认为这实际上是Larsmans的回答做了更多的算法:

图的节点是障碍顶点.每个内部顶点实际上代表两个节点:凹面和凸面.

1. 将起始节点推入具有欧几里德启发距离的优先级队列.
2. 从优先级队列中弹出顶级节点.
3. 从节点到目标进行线交叉测试(可能使用光线跟踪数据结构技术进行加速).如果失败了,
4. 考虑从当前节点到每个其他顶点的光线.如果当前节点与正在考虑的顶点之间没有交叉点,并且顶点从当前节点的角度看是凸的,则将顶点添加到优先级队列,使用当前节点中的累积距离加上与当前节点的距离进行排序节点到顶点加上启发式距离.
5. 回到2.

如果在障碍物中有"T"交汇点之类的东西,你必须做额外的预处理工作,我不会惊讶地发现它在许多情况下会中断.您可以通过仅考虑位于当前节点和目标之间的连接组件的顶点来使事情变得更快.

所以在你的例子中,在第一次尝试A,B之后,你会推A,8,A,5,A,1,A,11和A,2.考虑的第一个节点是A,8,A,1,和A,5,但他们不能出去,他们可以到达的节点已经与较短的累积距离推队列. 将考虑A,2和A,11,事情将从那里开始.