我有一个应用程序,我需要在屏幕上随机移动一些对象,他们不能互相撞击.我正在寻找一种算法,它允许我生成不会产生冲突的路径并且可以无限期地继续(即:对象一直移动直到用户驱动的事件将它们从程序中移除).
我不是游戏程序员,但我认为这看起来像AI问题,你们可能会闭着眼睛解决它.从我读过的内容来看,A*似乎是推荐的'基本理念',但我真的不想在没有确认的情况下投入大量时间.
任何人都可以对方法有所了解吗？反重力运动可能吗？
如果这很重要,这将在iOS上实现
需要在每个路径的末尾生成新路径
没有可见的'网格'.2D空间中的运动完全免费
物体是在屏幕上走动直到它们被杀死的昆虫
Sebastian Hö.. 27
A*是一种算法,用于查找开始和目标配置之间的最短路径(就您定义的短路而言:常见的是例如欧几里德距离,成本或时间,角距......).你的昆虫似乎没有特定的目标,甚至不需要最短的路径.我肯定不会去A*.(顺便说一下,既然你有一个动态的环境,那D*本来就是一个想法 - 它仍然意味着找到从A到B的路径).
我会解决这个问题如下:
对于随机路径,我看到两种方法.第一个是简单的随机游走(点击这里查看带有解释的精美2D动画),这可能会受到抖动的影响并且看起来不太好.第二个需要更详细的解释.
对于每只昆虫,在它们周围产生四个随机点,可能从正弦曲线开始.使用样条插值在这些点之间生成平滑曲线.注意C1(2D)或C2(3D)连续性.(建议:Hermite splines)使用Catmull-Rom样条曲线,您可以在沿曲线移动时找到您的配置.
在这篇关于程序性赛道的博客文章中可以找到类似方法的应用,在计算机动画课程的这些旧幻灯片(pdf)中也可以找到更技术性(但仍然不太技术性)的解释.
当昆虫开始移动时,它可以在第二点和第三点之间不断移动,当你总是移除第一点并在昆虫到达第三点时附加一个新点,从而使其成为第二点.
If third point is reached
Remove first
Append new point
Recalculate spline
End if
对于更平滑的曲线,总共添加更多的点并在中间的某处移动,原则保持不变.(我个人在固定环境中只使用它,但它也应该在动态环境中工作.)
如果您的随机点生成良好(也许您可以使用类似于上述链接博客文章中提供的方法,或者查看PCG Wiki上的算法),这可以导致整个屏幕上的平滑路径.
为了避免其他昆虫,我想到了三种不同的方法.
Bug算法
Braitenberg车辆
潜在领域的应用
对于潜在的领域,我建议阅读本文关于动态运动规划(pdf).它来自机器人技术,但也很容易应用于你的问题.您可以使用机器人下一个样条点作为目标,并将其速度设置为0以应用此方法.但是,对于简单的游戏来说,这可能有点太多了.
有关Braitenberg车辆的讨论可以在这里找到(pdf).最初的想法更多的是一种技术方法(取决于你的电机如何与光接收器耦合,朝向或远离光源),并且经常用于展示我们如何将恐惧和吸引等情感概念应用于其他物体."恐惧"行为也是用于机器人技术中避障的一种方法.
第三种也许是最简单的方法是bug算法(pdf).我总是遇到边界跟随问题,这有点棘手.但是为了避免另一种昆虫,这些算法 - 无论你使用哪种算法(我建议使用Bug 1或Tangent Bug) - 都应该做到这一点.它们非常简单:朝着你的目标前进(在这个带有catmull-rom样条的应用程序中)直到你前面有一个障碍物.如果障碍物接近,将昆虫的状态更改为"避障障碍"并运行您的错误算法.如果你给两个"碰撞"的昆虫提供相同的转弯方向,它们会自动绕过彼此并沿着它们的原始路径前进.
作为变体,您可以让它们转动并从该点重新计算新的样条线.
路径查找和随机路径生成是不同的事情.你必须尝试最适合你的昆虫的东西.A*绝对用于查找最短路径,而不是用于创建随机路径并跟随它们.
A*是一种算法,用于查找开始和目标配置之间的最短路径(就您定义的短路而言:常见的是例如欧几里德距离,成本或时间,角距......).你的昆虫似乎没有特定的目标,甚至不需要最短的路径.我肯定不会去A*.(顺便说一下,既然你有一个动态的环境,那D*本来就是一个想法 - 它仍然意味着找到从A到B的路径).
我会解决这个问题如下:
对于随机路径,我看到两种方法.第一个是简单的随机游走(点击这里查看带有解释的精美2D动画),这可能会受到抖动的影响并且看起来不太好.第二个需要更详细的解释.
对于每只昆虫,在它们周围产生四个随机点,可能从正弦曲线开始.使用样条插值在这些点之间生成平滑曲线.注意C1(2D)或C2(3D)连续性.(建议:Hermite splines)使用Catmull-Rom样条曲线,您可以在沿曲线移动时找到您的配置.
在这篇关于程序性赛道的博客文章中可以找到类似方法的应用,在计算机动画课程的这些旧幻灯片(pdf)中也可以找到更技术性(但仍然不太技术性)的解释.
当昆虫开始移动时,它可以在第二点和第三点之间不断移动,当你总是移除第一点并在昆虫到达第三点时附加一个新点,从而使其成为第二点.
If third point is reached
Remove first
Append new point
Recalculate spline
End if
对于更平滑的曲线,总共添加更多的点并在中间的某处移动,原则保持不变.(我个人在固定环境中只使用它,但它也应该在动态环境中工作.)
如果您的随机点生成良好(也许您可以使用类似于上述链接博客文章中提供的方法,或者查看PCG Wiki上的算法),这可以导致整个屏幕上的平滑路径.
为了避免其他昆虫,我想到了三种不同的方法.
Bug算法
Braitenberg车辆
潜在领域的应用
对于潜在的领域,我建议阅读本文关于动态运动规划(pdf).它来自机器人技术,但也很容易应用于你的问题.您可以使用机器人下一个样条点作为目标,并将其速度设置为0以应用此方法.但是,对于简单的游戏来说,这可能有点太多了.
有关Braitenberg车辆的讨论可以在这里找到(pdf).最初的想法更多的是一种技术方法(取决于你的电机如何与光接收器耦合,朝向或远离光源),并且经常用于展示我们如何将恐惧和吸引等情感概念应用于其他物体."恐惧"行为也是用于机器人技术中避障的一种方法.
第三种也许是最简单的方法是bug算法(pdf).我总是遇到边界跟随问题,这有点棘手.但是为了避免另一种昆虫,这些算法 - 无论你使用哪种算法(我建议使用Bug 1或Tangent Bug) - 都应该做到这一点.它们非常简单:朝着你的目标前进(在这个带有catmull-rom样条的应用程序中)直到你前面有一个障碍物.如果障碍物接近,将昆虫的状态更改为"避障障碍"并运行您的错误算法.如果你给两个"碰撞"的昆虫提供相同的转弯方向,它们会自动绕过彼此并沿着它们的原始路径前进.
作为变体,您可以让它们转动并从该点重新计算新的样条线.
路径查找和随机路径生成是不同的事情.你必须尝试最适合你的昆虫的东西.A*绝对用于查找最短路径,而不是用于创建随机路径并跟随它们.
看看这个和这个描述了一个自动播放马里奥游戏的AI程序.
所以在这个链接中,作者所做的是使用A*star算法来指导Mario Get to the right border of the screen as fast as possible. Avoid being hurt.
所以这个想法是针对每个时间框架,他将有一个描述场景中其他对象的当前位置的环境以及每个动作(向上,向左,向右,什么都不做),他计算其成本函数并做出决定基于此的下一个运动.
来源:http://www.quora.com/What-are-the-coolest-algorithms
您无法提前计划无限期的轨迹!
我建议使用一种更简单的方法来预测下一次碰撞(知道物体的位置和速度可以让你判断它们是否会发生碰撞以及何时碰撞),并通过改变任一物体的速度或方向来解决它(在物体接触之前反弹) ).
如果您创建了更早的碰撞,请务必重新检查碰撞!
在您的情况下,真正的挑战是有效地预测众多对象之间的冲突,先验的O(N²)任务.您将通过在游戏区域上叠加粗网格并仅查看相邻单元格中的对象来加速它.
还可以维护"可能在某些未来干扰"的对象列表(即考虑它们的距离和相对速度)并保持更新.检查一对可能离开列表相对容易; 有效地检查需要输入列表的新对不是.
京公网安备 11010802040832号 | 京ICP备19059560号-6 