algorithm - 无限期地随机移动物体而不会发生碰撞

Question

我有一个应用程序，我需要以随机方式在屏幕上移动多个对象，并且它们不能相互碰撞。我正在寻找一种算法，它允许我生成不会产生碰撞并且可以无限期持续的路径(即:对象不断移动，直到用户驱动的事件将它们从程序中删除)。

我不是游戏程序员，但我认为这看起来像是一个人工智能问题，你们可能闭着眼睛解决它。从我所读到的 A* 似乎是推荐的“基本想法”，但我真的不想在没有得到确认的情况下投入大量时间。

任何人都可以阐明一种方法吗？可能是反重力运动？

如果这很重要，这将在 iOS 上实现

每条路径末尾需要生成新路径

没有可见的“网格”。运动在二维空间中完全自由

对象是在屏幕上走来走去直到被杀死的昆虫

Answer 1

A*是一种找到起点和目标配置之间最短路径的算法(就您定义的任何短路径而言:常见的是例如欧几里德距离、成本或时间、角距离......)。你的昆虫似乎没有特定的目标，它们甚至不需要最短路径。我当然不会去 A* . (顺便说一下，由于您有一个动态环境，D* 本来是一个想法 - 它仍然是为了找到从 A 到 B 的路径)。

我将解决这个问题如下:

随机路径并跟随它们

对于随机路径，我看到了两种方法。第一个是简单的随机游走( click here to see a nice 2D animation with explanations )，它可能会受到抖动的影响并且看起来不太好。第二个需要更详细的解释。

对于每只昆虫，在它们周围生成四个随机点，可能从正弦曲线开始。带 spline interpolation在这些点之间生成一条平滑的曲线。照顾好 C1(2D)或 C2(3D)continuity . (建议:Hermite splines)
与 Catmull-Rom splines您可以在沿着曲线移动时找到您的配置。

可以找到类似方法的应用 in this blog post about procedural racetracks ，也可以在 these old slides (pdf) 中找到更具技术性(但仍然不是太技术性)的解释。来自计算机动画类(class)。

当一只昆虫开始移动时，它可以不断地在第二个和第三个点之间移动，当你总是移除第一个点并在昆虫到达第三个点时添加一个新点，从而成为第二个点。

If third point is reached
    Remove first
    Append new point
    Recalculate spline
End if

对于更平滑的曲线，总共添加更多点并在中间的某个位置移动，原理保持不变。 (我个人只在固定环境中使用它，但它也应该适用于动态环境。)

这可以，如果您的随机点生成良好(也许您可以使用类似于上面链接的博客文章中提供的方法，或者查看 PCG Wiki 上的算法)，可以在整个屏幕上生成平滑的路径.

避免其他昆虫

为了避免其他昆虫，我想到了三种不同的方法。

错误算法

Braitenberg 车辆

潜在领域的应用

对于潜在领域，我建议阅读 this paper about dynamic motion planning (pdf) .它来自机器人技术，但也很容易应用于您的问题。您可以仅使用机器人的下一个样条点作为目标并将其速度设置为 0 来应用此方法。但是，对于您的简单游戏来说，这可能有点太多了。

可以找到关于 Braitenberg 车辆的讨论 here (pdf) .最初的想法更多是一种技术方法(根据您的电机与光接收器的耦合方式，朝向或远离光源行驶)，并且通常用于展示我们如何将恐惧和吸引力等情感概念应用于其他物体。 “恐惧”行为也是机器人技术中用于避障的一种方法。

第三种也是最简单的方法是 bug algorithms (pdf) .我总是遇到边界跟随问题，这有点棘手。但是为了避免另一种昆虫，这些算法 - 无论您使用哪种算法(我建议使用 Bug 1 或 Tangent Bug) - 都可以解决问题。它们非常简单:朝着你的目标前进(在这个应用程序中使用 catmull-rom 样条)，直到你前面有障碍物。如果障碍物很近，请将昆虫的状态更改为“避障”并运行您的错误算法。如果你给两个“碰撞”的昆虫指定相同的转弯方向，它们会自动绕过彼此并遵循它们原来的路径。
作为一种变体，您可以让它们转动并从该点开始重新计算新的样条。

结论

路径查找和随机路径生成是不同的事情。你必须尝试什么最适合你的昆虫。 A* 绝对是用于寻找最短路径，而不是用于创建随机路径并跟随它们。