我有一个应用程序，需要在屏幕上以随机方式移动许多对象，并且它们不能相互碰撞。我正在寻找一种算法，允许我生成不会产生碰撞的路径，并可以无限期地继续移动（即：对象继续在程序中移动，直到用户驱动的事件将其从程序中删除）。
我不是游戏程序员，但我认为这似乎是一个AI问题，你们可能闭着眼睛就能解决。根据我所读的，A *似乎是推荐的“基本思路”，但如果没有得到确认，我真的不想在它上面投入太多时间。
有人能提供一些方法吗？也许是反重力运动？
A*是一种算法，用于找到起点和目标配置之间的最短路径（根据您定义的任何短距离，例如欧几里得距离、成本或时间、角度距离等）。你的昆虫似乎没有特定的目标，甚至不需要最短路径。我肯定不会选择A*。（顺便说一句，由于您拥有动态环境，D*可能是个好主意——它仍旧要寻找从A到B的路径）。
我将如下解决问题：
对于随机路径，我看到两种方法。第一种方法是简单的随机游走（点击此处查看带有解释的漂亮2D动画），但容易产生抖动效果，不太美观。第二种方法需要更详细的解释。
为每个昆虫生成四个随机点，可以从正弦曲线开始。使用样条插值在这些点之间生成平滑的曲线。注意具有C1（在2D中）或C2（在3D中）连续性。（建议使用埃尔米特样条）。使用Catmull-Rom样条，您可以沿着曲线移动，找到您的配置。
类似方法的应用可以在这篇关于过程赛道生成的博客文章中找到，同时在一门计算机动画课程的这份旧幻灯片(PDF)中也可以找到更加技术化但仍易懂的解释。
昆虫开始移动时，它可以不断地在第二个点和第三个点之间移动，当昆虫到达第三个点时，始终删除第一个点并追加一个新的点，使其成为第二个点。
If third point is reached
Remove first
Append new point
Recalculate spline
End if
为了使曲线更加平滑，总点数要增加，并将其移动到中间位置，但原则依然不变。（个人只在固定环境中使用过，尽管在动态环境中也应该能起作用。）
如果您的随机点生成良好（也许可以使用类似于上面链接博客文章中提供的方法，或查看PCG Wiki上的算法），则可以在屏幕上获得平滑路径。
有三种不同的方法可以避免其他昆虫。
对于潜在领域，我建议阅读这篇关于动态运动规划的论文（pdf）。虽然这是来自机器人技术领域的内容，但很容易适用于您的问题。您可以将机器人的下一个样条点设置为目标，并将其速度设置为0以应用此方法。但是，这可能对您的简单游戏来说有点太过复杂。
关于Braitenberg车辆的讨论可以在此处（pdf）找到。最初的想法更多地是一种技术方法（根据马达与光受体的耦合情况向光源驱动或远离光源），通常用于展示我们如何将恐惧和吸引等情感概念应用于其他物体。避障中使用了“恐惧”行为，也被用于机器人技术中的障碍物避开。
第三种，也可能是最简单的方法是使用虫算法 (pdf)。我总是会遇到边界跟随的问题，这有点棘手。但为了避免与其他障碍物发生碰撞，无论你使用哪种算法 (我建议 Bug 1 或 Tangent Bug)，都应该行得通。它们非常简单：朝着目标移动（在这个应用中是 Catmull-Rom 样条曲线），直到你面前有一个障碍物。如果障碍物很近，将虫的状态更改为“避障”并运行虫算法。如果给两只“碰撞”的昆虫相同的转向方向，它们将自动绕过彼此并沿着原来的路径走。
作为变化，你可以让它们转向并从那个点开始重新计算样条曲线。
寻路和随机路径生成是不同的事情。你必须尝试一下看哪个方法对你的昆虫看起来最好。A* 明显是用于查找最短路径，而不是创建随机路径并跟随它们。
尽可能快地到达屏幕的右侧边缘。避免受伤。"对于无限期的轨迹规划是不可行的！
我建议采用一种更简单的方法，即只预测下一次碰撞（知道物体的位置和速度可以告诉你它们是否会碰撞以及何时碰撞），并通过改变其中一个对象的速度或方向来解决它（在物体接触之前弹跳）。
确保重新检查碰撞，以防您创建了更早的碰撞！
在您的情况下，真正的挑战是有效地预测众多物体之间的碰撞，这是 O(N²) 任务。通过在游戏区域上叠加粗略网格，并仅查看相邻单元格中的对象，可以加快速度。
还可能有可能维护一组“在某个未来可能干扰”的对象对列表（即考虑其距离和相对速度），并保持其更新。检查一对可能离开列表相对容易；高效地检查需要进入列表的新对则不然。
此外，对于额外的奖励分数，哈密顿路径往往会“摆动”，因为它是一个循环，您可以预测（并预先计算）未来的路径。
您始终可以将网格的节点用作样条线的结点以平滑运动，甚至可以随机将所有点从其严格的2d网格位置移开，直到获得所需的运动。
来自Wikimedia的示例哈密顿回路：
