A* 用于寻找最短路径并避开障碍物
我必须获得二维两点之间的（最短）/（最佳）距离。我必须避免可能连接在一起的线条形状。关于如何表示我可以行驶的节点有什么建议吗？我曾想过制作一个网格，但这听起来不太准确或优雅。如果一条线的任何点位于正方形内（该节点是正方形的中心），我会认为该节点不可行走。
一个示例是从 A 点到 B 点
。网格是解决此问题的推荐方法吗？提前非常感谢！
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).
An example would be going from point A to B.
Is the grid the recommended way to solve this? Thanks A LOT in advance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为您可以通过对定义为以下的图进行 A* 搜索来解决此问题：
即，没有必要将平面离散化为网格，但如果没有它，后继函数将变得难以定义。
I think you can solve this by an A* search on a graph defined as:
I.e., it's not necessary to discretize the plane into a grid, but without it, the successor function becomes difficult to define.
一个网格，A*贯穿其中就是正确的方法。我所知道的所有游戏都使用 A* 或其针对全球路线的改编，并通过转向行为对其进行补充以实现本地准确性。也许您没有意识到使用转向行为可以解决您对准确性的所有担忧（搜索引擎）。
编辑：我只记得一个使用流场的策略游戏。但它不是主流。
顺便说一句：要了解转向行为对您的对象的作用，请查看许多有关它的 YouTube 视频。其中一些在更一般的意义上使用术语“寻路”：包括全局算法（A*）以及转向行为中涉及的碰撞避免、路径平滑和物体惯性。
A grid, and A* running through it is the way to go. All games i am aware of use A* or an adaptation of it for the global route and complement it with steering behaviour for local accuracy. Maybe you were not aware that using steering behaviour will resolve all your concerns about accuracy (search-engine it).
EDIT: i just remember a strategy game that uses flow-field. But it is not main-stream.
BTW: to get a feel for what steering behavior does for your objects take a look at the many youtube-videos about it. Some of them use the term path-finding in a more general sense: including the global algorithm (A*) as well as collision-avoidance, path-smoothing and object-inertia involved in steering-behavior.
我认为这本质上是拉斯曼斯的答案，更加算法化：
图的节点是障碍顶点。每个内部顶点实际上代表两个节点：凹侧和凸侧。
如果障碍物中存在诸如“T”形交叉点之类的东西，您必须做额外的预处理工作，并且我不会惊讶地发现它在许多情况下会破裂。通过仅考虑位于当前节点和目标之间的连接组件的顶点，您也许能够使事情变得更快。
因此，在您的示例中，在第一次尝试 A,B 后，您将推送 A,8、A,5、A、 1、A,11 和 A,2。第一个考虑的节点是 A,8、A,1 和 A,5，但它们无法退出，并且他们可以到达的节点已经被推送到累积距离较短的队列中。 A,2 和 A,11 将被考虑，事情将从那里开始。
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.
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.
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.