没有跨越无限平面的图形的运动规划
一个对象位于A并且想要移动到B。 我想计算一个移动向量，该向量不会在数组 C 中要避免的点的距离 D 内移动。
因此，如果移动矢量 (BA) 归一化并与物体速度相乘，使其位于 C 中任意点的 D 范围内，则矢量会旋转，这样就不会出现这种情况。
这是二维的。 另外，如果此操作有名称，请发表评论或自行编辑此问题，因为我不知道该怎么称呼它。
另外，我的第一直觉是将活动区域划分为节点并运行 A*，但我想在这个上尝试数学方法，一些植绒实验给我的印象是它可以完成。
更新（来自评论）：此图像非常接近我想要的解决方案：
假设我们从左边的点开始，我们开始向右转向目标（另一个点），我们检测到右侧有墙，所以我们停下来转身并前进。 墙消失了，所以我们可以再次开始转向目标，等等。 我知道这可能会导致对象根本无法到达那里，但我想定义一个行为，而不一定是一个解决方案，如果你明白我的意思的话。
更新2：将活动区域转换为一组节点可能效率低下。 A* 和其他启发式图遍历算法非常适合低维问题。 但我想要穿越的区域是无限大的，并且只有少数障碍物散布在其中。 节点本身，或者更确切地说，潜在的位置，是无限小的。 这当然可以使用某种四叉树来优化，但我感觉简单的运动向量以某种方式旋转和插值也可以解决这个问题。
An object is positioned at A and wants to move to B. I want to calculate a movement vector there that doesn't move within the distance D of the to-be-avoided points in array C.
So if the move vector (B-A) normalized and multiplied with the objects speed would bring it within D of any point in C the vector is rotated so that it doesn't.
This is in two dimensions. Also, if this operation has a name, please make a comment or edit this question yourself as I had no idea of what to call it.
Also, my first instinct was to divide the active area into nodes and run a A* but I want to try the mathematical approach on this one, a few experiments with flocking gives me the impression that it can be done.
Update (from comments): This image is very close to the solution I want:
Assuming we start at the point to the left, we start turning right towards the goal (the other point), we detect a wall on the right so we stop turning and move forward. The wall is gone so we are allowed to start turning towards the goal again, and so on. I know this may cause the object to not get there at all, but I want to define a behavior, not necessarily a solution, if you know what I mean.
Update2: Translating the active area into a set of nodes might prove inefficient. A* and other heuristic graph traversal algorithms are great for low dimensional problems. But the area I want to move across is infinite in size and only has a handful of obstacles scattered across it. The nodes themselves, or rather the potential positions, are infinitely small. This could of course be optimized with a quad tree of some sort but I have a feeling simple movement vectors that are in some way rotated and interpolated can solve this as well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我听说这叫做运动规划，以及寻路（如上所述）
有一个很多算法，但根据您的描述，可见性图可能是一个不错的选择开始。 您有一个图形，其中包含点 A、B，以及 C 中每个点周围的多边形（我相信，您也可以通过计算每个点的切线来使用圆来实现）。 您可以将边计算为点之间的潜在路径。 这是一个幻灯片，它更好地解释了这一点。
然后，在可见性图之上，应用 A*（启发式搜索）等搜索算法来找到穿过该图的最佳路径。
但是，您应该考虑您正在寻找什么。 上述方法将通过非常接近所有角来找到最短路径，但其他算法可能更适合您的最优想法。
I hear this called motion planning, and pathfinding (as mentioned above)
There are a lot of algorithms, but from your description, a visibility graph might be a good start. You have a graph with points A, B, and polygons around each point in C (you could also do it with circles by calculating tangent lines from each point, I believe). You calculate edges as potential paths between the points. Here's a slide show which explains it better.
Then, on top of the visibilty graph, apply a search algorithm like A* (a heuristic search) to find the most optimal path through the graph.
However, you should consider what you are looking for. The above approach will find a shortest path by sticking extremely close to all corners, but other algorithms might better fit your idea of optimality.
另外，在您在答案中链接到的页面上，对转向行为进行了很好的讨论一般的。
特别是，请查看他的页面，了解 containment 和 路径跟踪 是很好的例子。
自主角色的转向行为
Also on the page you linked to in your answer is a pretty good discussion of steering behaviours in general.
In particular, look at his pages for containment and path following for good examples.
Steering Behaviors for Autonomous Characters
您可以考虑使用潜在字段。 这提供了一种避免“拥抱障碍物边缘”的方法。
但请注意，与 A* 算法一样，这需要您量化状态空间，因此计算量可能相当大，具体取决于您需要多少精度。
You could consider using potential fields. This offers a way to avoid "hugging the edges" of the obstacles.
But note that, like the A* algorithm, this requires that you quantize the state space, and may therefore be quite computationally intensive depending on how much accuracy you need.
我在此页面上发现了关于集群例程的相当详细的描述。
对所有障碍物使用分离规则，仅向目标位置对齐（因为我们没有群体伙伴）并且（出于同样的原因）忽略凝聚力规则。
我担心这是否会产生预期的效果。
I found a quite verbose description of a flocking routine on this page.
Use the separation rule for all obstacles, and alignment only towards the goal position (since we have no flock mates) and (for the same reason) ignoring the cohesion rule.
I wounder if that would yield the desired effect.