A* 用于寻找最短路径并避免作为障碍物的线 [英] A* for finding shortest path and avoiding lines as obstacles

问题描述

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

I have to get the (shortest)/(an optimal) distance between two points in 2D. I have to avoid shapes that are lines, that may be connected together. Any suggestion on how to represent the nodes I can travel on? I have thought of making a grid, but this doesn't sound very accurate or elegant. I would consider a node as unwalkable if any point of a line is inside a square (with the node being the center of the square).

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

An example would be going from point A to B.

网格是解决这个问题的推荐方法吗?提前致谢！

Is the grid the recommended way to solve this? Thanks A LOT in advance!

推荐答案

我认为这基本上是 Larsmans 的回答使算法更加复杂:

I think this is essentially Larsmans' answer made a bit more algorithmic:

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

Nodes of the graph are the obstacle vertices. Each internal vertex actually represents two nodes: the concave and the convex side.

1. 使用欧几里得启发式距离将起始节点推入优先级队列.
2. 从优先级队列中弹出顶部节点.
3. 进行从节点到目标的线相交测试(可能使用光线追踪数据结构技术来加速).如果失败，
4. 考虑从当前节点到每个其他顶点的射线.如果当前节点和考虑的顶点之间没有交点，并且该顶点从当前节点的角度来看是凸的，则将该顶点加入优先级队列，按照当前节点的累计距离加上与当前节点的距离进行排序节点到顶点加上启发式距离.
5. 返回 2.

如果障碍中有像T"形交叉点这样的东西，你必须做额外的预处理工作，我不会惊讶地发现它在很多情况下都会中断.您可以通过仅考虑位于当前节点和目标之间的连接组件的顶点来加快速度.

You have to do extra pre-processing work if there are things like 'T' junctions in the obstacles and I wouldn't be surprised to discover that it breaks in a number of cases. You might be able to make things faster by only considering the vertices of the connected component that lies between the current node and the goal.

因此，在您的示例中，在第一次尝试 A,B 后，您将按 A,8、A,5、A,1、A,11 和 A,2.考虑的第一个节点是 A,8、A,1 和 A,5，但它们无法退出并且他们可以到达的节点已经被推到队列中，累积距离更短.A,2 和 A,11 将被考虑，事情将从那里开始.

So in your example, after first attempting A,B, you'd push A,8, A,5, A,1, A,11, and A,2. The first nodes of consideration would be A,8, A,1, and A,5, but they can't get out and the nodes they can reach are already pushed on the queue with shorter accumulated distance. A,2 and A,11 will be considered and things will go from there.

这篇关于A* 用于寻找最短路径并避免作为障碍物的线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！