Boids算法--涌现行为和杂音

2020-05-03 05:03:56

1986年,我制作了一个协调动物运动的计算机模型,比如鸟群和鱼群。它基于计算机动画或计算机辅助设计中通常使用的那种三维计算几何。我称之为一般的模拟群体生物体。基本的群体模型由三个简单的转向行为组成,它们描述了个体群体是如何根据它附近的群体伙伴的位置和速度进行机动的:

每个物体都可以直接接触到整个场景的几何描述,但是植绒要求它只对自己周围某一小块邻域内的鸟群成员做出反应。邻里关系的特点是距离(从车身中心测量)和角度,从车身的飞行方向测量。这个社区以外的鸟群成员会被忽略。这个社区可以被认为是一种有限的感知模式(就像浑浊的水中的鱼),但它可能更直截了当…。

在早期的实验中使用了一个稍微精细一些的行为模型,它包括预测性的避障和寻找目标。障碍物避免允许机器人在模拟环境中飞行,同时躲避静态物体。对于计算机动画中的应用程序,低优先级的目标寻找行为导致蜂群遵循脚本路径。

在符号图形事业部和惠特尼/演示制作公司的许多同事的合作下,我们制作了一部动画短片,以身体模型斯坦利(Stanley)和斯特拉(Stella)为主角,拍摄了“破冰记”(The Break The Ice)。这部电影首先在SIGGRAPH&87的电子剧院放映。在同一次会议上发表了一篇关于人体的技术论文。在SIGGRAPH#88的课程笔记中,有一篇关于避障的非正式论文。

自1987年以来,体模型在行为动画领域已经有了许多其他的应用。1992年蒂姆伯顿执导的电影“蝙蝠侠归来”就是第一部。它包含了计算机模拟的蝙蝠群和企鹅群,它们是用Symbolics开发的原始Boid软件的修改版本创建的。安迪·科普拉(当时在VIFX工作)制作了蝙蝠群的现实主义图像。安德里亚·洛施(当时在Boss Films工作)和PaulAshdown创作了企鹅军队行进通过……的动画。

幸运的是,在1987年Boids论文发表几个月后,克里斯·朗顿(Chris Langton)组织了最初的开创性人工生命研讨会。一位乐于助人的中间人得到了克里斯的消息,他让我在研讨会上做一个关于物体的非正式演示。物体模型已经成为人工生命原理的一个经常被引用的例子。群集是涌现的一个特别令人联想到的例子:复杂的全局行为可以由简单的局部规则的相互作用而产生。

在体模型中,个体的简单行为之间的相互作用会产生复杂而有组织的群体行为,而组成行为本身就是非线性的,因此将它们混合在一起会给新兴的群体动力学带来混沌的一面。同时,行为控制器提供的负反馈使群体动力学趋于有序。结果就是栩栩如生的群体行为。

拟真人行为的一个重要特征是不可预测性,时间尺度过于适中。例如,在某个时刻,上面小程序中的天体可能主要是从左向右飞行。但是要预测(比如说)五分钟后他们会朝哪个方向移动是完全有可能的。在很短的时间尺度内,运动是相当可预测的:从现在开始,一个物体将沿着大致相同的方向运动。这一特性是复杂系统所特有的,与这两者形成鲜明对比的是…。

Boids模型是基于个人的模型的一个例子,这是一类用于捕获大量交互自治Agent的全局行为的仿真。基于个体的模型被广泛应用于生物学、生态学、经济学等研究领域。

请注意,Boids算法的直接实现具有O(N)的渐近复杂度。每个身体都需要考虑彼此的身体,即使只是为了确定它是否不是近亲。然而,有可能通过使用适当的空间数据结构将这一成本降低到早期的O(N),该空间数据结构允许按其位置对物体进行分类。然后,要找到附近的Agivenboid群体伙伴,只需要检查群体中在一般范围内的那部分。..。

在ACM SIGGRAPH教育委员会的HyperGraph项目中关于计算机动画中的人工生活的报告中对羊群、牛群和学校的总结。

描述物体活着的书籍和文章,科学家们在他们自己创造的二元宇宙中扮演上帝的角色&(1998),柯特·苏普利(Curt Suplee)。

布拉姆·贝克(Bram Bakker)的“心理学的适应行为方法”(2000)为认知心理学的读者描述了包括躯体在内的适应行为。(PDF)。

肖恩·卡尔森(Shawn Carlson)的“人工生活:羽毛的身体聚集在一起”(2000)。这是一项科学研究