一撞二:基于Agent的建模中的碰撞检测研究

(摘录自最后的会议论文)

一,引言

我们与他人的互动影响着我们的日常生活。 无论是在广阔的大都市还是在Costco,我们常常会在人群中漫游。 尽管一般人群的活动通常较为平稳且步行速度很快,但在紧急情况下会触发我们对战斗或飞行做出反应的本能。 因此,人群的模拟通常集中在方向性和速度的变化上。 但是,从历史上讲,大规模逃避反应所带来的危险不在于攻击者或敌对事件,而在于被踩踏或与其他固体碰撞而造成的伤害和死亡。 最初,《奔跑的公牛》的模拟旨在对攻击者面对的多主体行为进行建模,但最终导致人们对如何在变化的环境中有效检测碰撞进行了更为细致的研究

三, 碰撞为向量

在创建碰撞模型时,主体本身不包含任何使其与环境发生碰撞或与环境交互的固有属性。 元胞自动机模型通过以布尔if-then语句的形式将一系列的开-关开关编码为单元到单元的交互,从而完全避免了此问题。 这样可以将规则抽象为简单的清单。 如果满足条件,则翻转相应的开关。 在某种程度上,我们的模拟中使用的基于代理的模型具有相同的布尔成分-某些状态(例如“伤害”,“活动”,“死亡”)取决于预设参数而被“打开”或“关闭”。 但是,在发生碰撞的情况下,将检查布尔变量“对象是否经历了碰撞”(isCollided),但是输出不是很多开关,因为它们是方向和速度的变化,被编码为矢量。

该解释引出了如何检测布尔值(isCollided)的问题。 无需任何编码,座席将缩小为屏幕上的像素。 这些运动是沿xy笛卡尔平面移动点所产生的错觉。 编码简单碰撞的一种方法是使用xy坐标作为开关。

“如果点A的x位置为1,则点A的x位置变为-1”

但是,由于碰撞模型从根本上来说是不稳定的,因此当面对复杂的环境空间配置时,碰撞模型将变得非常繁琐。 此外,如果目标是同时检查各种空间形式,那么人类就不可能大规模地详述每个坐标。

模拟的一个挑战是描述一种为非静态空间创建碰撞的方法。

五,时间驱动仿真

用于碰撞检测的初始方法是“时间驱动模拟”,其中时间被编码为离散的量子。 Quanta是最小的时间单位。 设置dt的量子大小后,我们可以在每个dt时间单位后更新每个代理的位置,以检查代理的任何位置是否相交。 如果检测到位置重叠,程序将更新到检测到“碰撞”的时间,同时更新碰撞代理的速度。 本质上,“时间驱动模拟”利用每个代理的x位置和y位置标记,但不仅根据其空间位置而且还根据时空位置调整代理。 它是接近碰撞的一种四维方法。

 如果在时间T代理A的x位置为-1并且A的速度为V并且在时间T 代理B的x位置为-1且B的速度为V2 则A的x位置为x A在时间(T-dt)的位置,并且A的速度是-V AND B的x位置是B在时间(T-dt)的x位置,并且B的速度是-V2 

在此,“速度”被改变并且更新成为速度是包含方向的向量。 这种方法仍然利用在代理上进行恒定位置检查的相同原理,但是还允许各种代理类型之间的交互作用的范围更宽。 这种方法的缺点是双重的:每次在计算机内存上分配量子任务时都要检查重叠检查,并且在人口众多的模拟中,模拟将开始出现滞后。 在涉及许多预期碰撞的更极端情况下,对每个代理执行的模拟检查以及对代理相对位置的连续时空更新可能会导致模拟崩溃。

而且,这种方法并不总是准确的。 碰撞检测取决于为dt设置的值; 如果进行检查的时间间隔相距太远,并且代理在没有进行检查的时间间隔内发生“碰撞”,则将错过“冲突”,并且各代理之间似乎已经逐步过渡。 换句话说,如果dt相对于代理商行进的速度而言过大,则不会检测到碰撞的代理商。 另一方面,如果dt太小,则每个时间段执行的检查太多,从而降低了仿真速度。 如果碰撞代理的种群数量足够大,则模拟将不可避免地导致代理之间在支票之间碰撞,从而相互滑过的情况。

这种现象在我们最初的模拟中很明显地出现了,当时人口经纪人和公牛经纪人有时会越过城市边界。 由于我们希望的人口样本> 50,因此dt较小的值将导致模拟严重滞后。 在此特定情况下,解决此问题的另一种方法是将人和多头的运行速度调整为较慢,以便在下一次检查发生之前,他们不太可能经历重叠事件。 但是,这种方法在具有刚性速度参数的仿真中不易使用,因此不是通用解决方案。

我们可以在上图中看到,时间驱动碰撞模型可以起作用,直到代理速度增加为止。 一旦我们放下公牛,特工开始“奔跑”,连续检查就无法捕获冲突实例,从而使特工可以越过边界。 即使模拟的dt设置已经很小(换句话说,两次“检查”之间的时间间隔),大多数代理仍设法移动到未检测到的边界。

VI。 事件驱动的仿真

通过研究粒子碰撞系统的另一种模型-事件驱动的模拟,我们可以避免大多数时间驱动方法的麻烦。 事件驱动的仿真提供了一种在计算上更可行的方法,而不是使用量化的时间方法来对每个时间步长执行N²碰撞检查的顺序(每个粒子必须相对于其他粒子/壁进行检查)。 通过注意大多数时间步长不会涉及粒子之间的碰撞,即事件,我们可以通过仅预测此类事件何时发生来大大简化每次迭代。 假设所有粒子在碰撞之间以恒定速度沿直线轨迹移动,我们将避免执行任何碰撞检查,直到发生此类事件为止。 这使我们可以在每个时间步跳过大部分先前必要的碰撞检查,并快速进行仿真,直到发生下一个事件。 因此,该问题从时间驱动的仿真转换为事件驱动的仿真。

事件驱动模拟的关键在于我们如何确定下一次粒子碰撞是什么。 我们通过使用按时间顺序排列的未来事件优先级队列来解决此问题。 优先级队列是一种数据结构,可确保优先级队列中的第一个元素始终是队列中“最小”的元素。 在这种情况下,使用优先级队列将有助于我们确保模拟中要考虑的下一个事件始终位于队列的最前面。 在任何时间点,PQ都将包含所有将来会发生的碰撞,前提是再次假设所有粒子永远永远沿直线轨迹运动。 如果粒子碰撞并改变方向,则在此事件之前插入优先级队列的任何事件都将变为无效,并且从PQ头部弹出该事件时将不会对其进行处理。

图1

首先,在初始化所有粒子之后,我们确定在给定初始粒子状态的情况下可能发生的所有未来碰撞,并将它们逐一插入到PQ中。 通过对位移和速度的物理公式进行一些基本的操作,可以轻松计算出这些预测。 在此框架中,冲突解决同样容易处理,因为我们不需要在每个时间步上都进行检查,以确保粒子不会“夹住”彼此。 在此模型中,我们仅计算冲突发生的时间,并从PQ的开头删除此类事件后,我们将解决冲突并确保此时适当地处理了任何重叠。 处理事件后,我们使用它们的当前速度将所有粒子移动到时间t。 重新计算与任何受影响的粒子的所有可能的碰撞,然后将其重新插入PQ。 如果处理的下一个事件对应于无效的碰撞(自从将事件插入PQ以来粒子已移动/碰撞,或者粒子已被删除/死亡),我们将丢弃该事件,而不对其进行处理。

事件驱动的仿真确实解决了很多问题,这些问题可能是由时间驱动的仿真的计算复杂性和碰撞的不准确性引起的,但这是有代价的。 通过时间驱动的仿真,我们能够在每一步上修改所有对象的速度,从而为我们提供一种机制,可以使粒子彼此“追逐”,因为它们的新速度可以更新为指向另一个位置或粒子。 但是,事件驱动模拟的基本假设之一是粒子将在碰撞之间以恒定速度继续行进,该假设会在“追赶”另一个粒子时在粒子速度的任何调整下破裂。 结果,在每次改变粒子的速度之后,与该粒子的所有将来的碰撞都立即失效。 尽管这本身不是问题,但重新计算与该新粒子的可能碰撞会增加此模拟的计算复杂性,并会消耗PQ上的空间,并且还会添加许多不断被无效的新潜在事件。 如果有足够的粒子,“追赶”机制的引入可能会使这种仿真方法与时间驱动方法一样慢。

我们可以看到,在事件驱动碰撞模型的情况下,即使在高起始速度的情况下,代理也可以更好地包含在边界内。 此图显示了其更适合用于粒子或电子运动中的布朗运动的化学或物理模型。

七。 解决人群模拟中的冲突

为了解决在粒子意外穿过墙的情况下发生碰撞剪切的问题,我们考虑了事件驱动的模拟。 但是,为了维持我们期望的粒子追赶行为,这种方法被证明是对人类和公牛模型进行建模的不理想方法。 事件驱动模拟的优势在布朗运动建模中比在粒子物理模拟中更为明显,因为除了与其他粒子的弹性碰撞外,每个粒子都沿直线传播,速度几乎没有变化。 在这种情况下,对所有可能的未来碰撞的预测都是对闭式表达式的简单解决方案。 但是,在一定距离内必须包含粒子间相互作用的情况下,粒子碰撞动力学的性质发生了变化。 尽管仍是确定性的,但对任何未来碰撞的预测只能依赖于速度在响应附近多头/人的位置改变而再次改变之前的时间步长中的当前速度。 从这个意义上讲,我们可以将事件驱动模拟的好处描述为在一阶粒子模拟系统中得到最大化,其中位置或速度的变化量在碰撞之前随时间保持恒定,因此可用于缓解碰撞重新计算不会导致任何冲突的时间步长。

但是,一旦引入了异方差性,或者在变量系统的更高时刻,变量的可变性包含另一个不同的预测变量的值范围内的方差的实例,那么时间驱动的模拟就表现出极大的优越性。仿真系统本身的计算复杂性和简单性。 这是由于能够根据模型的下一状态,通过自定义模型的下一状态的微分方程式,可以自定义如何轻松地模拟从每个时间步到下一时间步的粒子运动的每个矩的变化。以前的状态。 尽管可能要模拟非常大型的系统,但是通过减少时间步,可以以较长的模拟时间为代价来恢复很多精度损失。

早些时候,我们注意到一些颗粒从墙壁上被剪掉了。 为了解决这些问题,实际上需要调整一些参数设置和仿真机制。 一般而言,当粒子以某种方式移动时会发生这种截断,该方式将粒子的当前位置更新为越过由壁划定的边界。 为了解决这个问题,我们对初始方法进行了一些更改。 首先,我们将与壁的碰撞检查移动到每个粒子的所有其他碰撞检查彼此抵触之后,以及随后所有公牛/人员重新定位以追赶/逃离最近的邻居。 这样,在完成之前所有对粒子路径的重定向之后,我们就可以进行完整性检查,并允许我们将粒子弹回墙壁。 我们还精确地设置了一个参数,该参数控制粒子必须靠近壁的距离,以便我们将其视为碰撞。 最初,我们将这个值设置为较高,以便捕获快速移动的粒子会夹过墙壁的角部情况,这仅仅是因为在它跳越之前没有靠近墙壁的框架。 但是,这导致了一些巨大的误差,除了粒子甚至在靠近壁之前从壁上反弹之外。

最后,我们所做的最微妙的变化是与观察到的现象作斗争,即由于一个粒子正在相互追逐或相互奔跑,这一额外因素的强度足以使粒子克服粒子的自然法向力。墙并夹过墙。 为了解决这个问题,我们使墙法向力足够强以补偿任何追逐力,并且还限制了反射力对原始对象速度的影响。 由于相同的追逐目标位于墙的另一侧,这会导致一些粒子连续弹回墙,但是墙的法向力使粒子能够抵抗穿过墙的剪切。 从好的方面来说,我们还减少了模型的时间步,以解决此类冲突对粒度的日益增长的需求。

通过将此公式与该模拟研究的先前形式进行比较,我们发现我们的工作与其他先前研究之间的关键区别在于我们如何处理碰撞问题。 其他配方通过对它们的代理进行编程以对它们周围的环境进行某种引导反应,从而完全避免了该问题。 尽管这种方法确实可以避免碰撞技巧周围的一些棘手问题,但我们认为允许粒子相互碰撞有助于进行最真实的模拟。 我们通过计算碰撞的入射角并沿着壁的法线矢量反射入射角,来强制与壁发生交互作用,而不是使粒子离开壁。 毕竟,并非每个代理都有避免冲突的能力。

八。 太空代理

在基于代理的模型中要考虑的一个问题是,为了模拟更大的人群移动,是否甚至需要碰撞。 完全消除碰撞问题是否可以使人群运动的模型更加流畅? 就我们的目的而言,模拟着重于运动实例期间智能体与智能体碰撞的预期结果。 而且,主体之间的相互作用很大程度上是由于主体在特定的空间配置中相互作用的结果。 因此,在没有主体与环境的碰撞的情况下,如果没有碰撞来定义它,就不会存在“空间”的概念和空间的不同方向。

该模拟利用了攻击者(bulls)的简单机械行为规则,从而使人员的行为更为复杂。 公牛通常只具有[追逐]状态,而人员则可以具有多个定量特征,例如“已受伤”,“已死”和“已追赶”,后者会影响其速度和方向性。 “ isDead”还将物理上删除该代理作为代理,并将其替换为静态对象“ body”。 然后将“身体”作为空间结构的一部分整合到环境中。 在这里,我们不仅可以将基于代理的仿真视为代理与代理交互的模型,还可以将代理视为物理地改变空间参数。

到目前为止,我们一直将环境描述为静态对象,但这实际上是错误的分类。 人们实际操作下的空间环境实际上应该被视为基于多主体的模型的一部分,其中环境具有时间流动性而不是空间流动。

在这种情况下,时间上的流动性是通过增加碰撞产生的“主体”来实现的。 就像细胞自动机的邻域一样,基于代理的模型的环境可以逐步发展并随着时间的推移而变化。 因此,要在自由移动代理模型中减少作为代理的空间的影响,就是要忽略代理行为中的一个非常关键的组成部分。

在我们的模拟中,空间变化既有意又有增量。 我们可以在各种预设地图之间移动,从而改变特工采取的可能路径,也可以通过放置障碍物来增加地图质量。

九。 可扩展性和适用性

碰撞模型最有趣的应用之一是能够模拟人群移动而无需使实际人群处于危险之中的能力。 在将时间驱动模型方法应用于具有碰撞的人群模拟时,有一些关于如何避免滞后和处理速度下降的想法。 只要有足够的计算能力和强大的图形卡,我们就可以有效地将初始人口数量增加到1000或10,000或无限。 即使在较慢的技术基础架构上,我们也可以拍摄仿真的延时照片,以允许以显着降低的帧速率运行的大规模人口。 如果我们发现非常慢的屏幕捕获运行模拟的替代方法,那么从理论上讲,可以将“时间驱动”模型中的dt减小到如此小的间隔,以使该程序实际上将在每个可感知的时间间隔进行检查。 然而,就简单地运行和加载程序的每个帧速率而言,这在能量消耗方面仍然极其低效。

寻找有效的碰撞解决方案是基于高精度预测模型代理的仿真的关键。 尽管为游戏创建的许多python库已经具有针对碰撞的预建功能,但这些函数通常在单独的物理引擎上运行。 模拟领域的任务是找到自己的解决方案,以实现环境碰撞的无缝集成,尤其是在气候变化迫在眉睫的威胁和可预见的灾难加剧了基于代理的准确时空模型的紧迫性时。 这种可伸缩性必须允许对某些空间在人群移动和碰撞频率中的影响进行各种分析,以便可以应用更复杂的参数来模拟真实城市条件的复杂性。

时间驱动碰撞模型代码

 #时间驱动碰撞模型导入随机 
导入数学
xMax = 1000
yMax = 1000
班级人员:

def __init __(self,x,y,startSim = False,isDead = False):
self.startSim = startSim
self.injuryCount = 0
self.isDead = isDead
self.position = PVector(x,y)
self.velocity = PVector.random2D()。mult(1)
self.radius = 3
self.m = self.radius * 0.1
self.running = False

def更新(自己):
如果self.isDead:
返回
self.position.add(PVector.mult(self.velocity,1))
如果self.injuryCount> 30:
self.isDead = True

def显示(自己):
noStroke()
如果self.isDead:
填充(255,0,0)
elif self.injuryCount> 0:
填充(0,255,255)
其他:
填充(0)
椭圆(self.position.x,self.position.y,self.radius * 2,self.radius * 2)
noFill()
如果self.startSim:
self.update()

def beginSim(self):
self.startSim = True

def stopSim():
self.startSim =假

def碰撞(自身,其他):
如果不是self.startSim:
返回

#人与人之间保持距离
distanceVect = PVector.sub(other.position,self.position)

#计算分离球的向量的大小
distanceVectMag = distanceVect.mag()

#他们接触之前的最小距离
minDistance = float(self.radius + other.radius)

如果(distanceVectMag <minDistance):
distanceCorrection =(minDistance-distanceVectMag)/2.0
d = distanceVect.copy()
CorrectionVector = d.normalize()。mult(distanceCorrection)
other.position.add(correctionVector)
self.position.sub(correctionVector)

#获取距离矢量的角度
theta = distanceVect.heading()
#预先计算触发值
正弦= sin(θ)
余弦= cos(theta)

bTemp = [
PVector(),
PVector()
]

bTemp [1] .x =余弦* distanceVect.x +正弦* distanceVect.y
bTemp [1] .y =余弦* distanceVect.y-正弦* distanceVect.x

#旋转温度速度
vTemp = [
PVector(),
PVector()
]
vTemp [0] .x =余弦* self.velocity.x +正弦* self.velocity.y
vTemp [0] .y =余弦* self.velocity.y-正弦* self.velocity.x
vTemp [1] .x =余弦* other.velocity.x +正弦* other.velocity.y
vTemp [1] .y =余弦* other.velocity.y +正弦* other.velocity.x

vFinal = [
PVector(),
PVector()
]

#b [0]的最终旋转速度
vFinal [0] .x =((self.m-other.m)* vTemp [0] .x + 2 * other.m * vTemp [1] .x)/(self.m + other.m);
vFinal [0] .y = vTemp [0] .y;

#b [0]的最终旋转速度
vFinal [1] .x =((other.m-self.m)* vTemp [1] .x + 2 * self.m * vTemp [0] .x)/(self.m + other.m);
vFinal [1] .y = vTemp [1] .y;

#破解以避免结块
bTemp [0] .x + = vFinal [0] .x;
bTemp [1] .x + = vFinal [1] .x;


bFinal = [
PVector(),
PVector()
]
bFinal [0] .x =余弦* bTemp [0] .x-正弦* bTemp [0] .y
bFinal [0] .y =余弦* bTemp [0] .y +正弦* bTemp [0] .x
bFinal [1] .x =余弦* bTemp [1] .x-正弦* bTemp [1] .y
bFinal [1] .y =余弦* bTemp [1] .y +正弦* bTemp [1] .x

#将球更新到屏幕位置
self.velocity.x =余弦* vFinal [0] .x-正弦* vFinal [0] .y
self.velocity.y =余弦* vFinal [0] .y +正弦* vFinal [0] .x
如果其他。__class __.__ name__ =='People':
other.velocity.x =余弦* vFinal [1] .x-正弦* vFinal [1] .y
other.velocity.y =余弦* vFinal [1] .y +正弦* vFinal [1] .x

other.position.x = self.position.x + bFinal [1] .x
other.position.y = self.position.y + bFinal [1] .y

如果自运行:
self.injuryCount + = 1
其他:
self.injuryCount + = 10
self.position.add(bFinal [0])
公牛类:

def __init __(self,x,y,startSim = False):
self.startSim = startSim
self.position = PVector(x,y)
self.velocity = PVector.random2D()。mult(3)
self.radius = 5
self.m = self.radius * 0.1
def更新(自己):
self.position.add(PVector.mult(self.velocity,0.1))
如果(self.position.x> width-self.radius):
self.position.x =宽度-self.radius
self.velocity.x * = -0.9
elif(self.position.x <self.radius):
self.position.x = self.radius
self.velocity.x * = -0.9
elif(self.position.y> height-self.radius):
self.position.y =高度-self.radius
self.velocity.y * = -0.9
elif(self.position.y <self.radius):
self.position.y = self.radius
self.velocity.y * = -0.9

def显示(自己):
noStroke()
填充(60)
如果self.startSim:
self.update()
椭圆(self.position.x,self.position.y,self.radius * 2,self.radius * 2)
noFill()

def beginSim(self):
self.startSim = True

def stopSim():
self.startSim =假
peopleList = []
bullList = []
wallList = []
类墙:

增量= 1

def __init __(self,x1,y1,x2,y2):
self.x1 = x1
self.y1 = y1
self.x2 = x2
self.y2 = y2
self.wallLength = dist(x1,y1,x2,y2)
self.normVector = PVector(-(y2-y1),x2-x1).normalize()

def显示(自己):
行程(0)
行(self.x1,self.y1,self.x2,self.y2)
line((self.x1 + self.x2)/ 2,(self.y1 + self.y2)/ 2,(self.x1 + self.x2)/ 2 + self.normVector.x,(self.y1 + self.x2) .y2)/ 2 + self.normVector.y)

def碰撞(自身,其他):
d1 = dist(other.position.x,other.position.y,self.x1,self.y1)
d2 = dist(other.position.x,other.position.y,self.x2,self.y2)
如果((((d1 + d2)> =(self.wallLength-Wall.delta))和(((d1 + d2)<=(self.wallLength + Wall.delta)))):
other.velocity = PVector.sub(other.velocity,PVector.mult(self.normVector,2 * PVector.dot(other.velocity,self.normVector)))

def setup():
大小(xMax,yMax)
wallList.append(Wall(300,300,600,300))
wallList.append(Wall(600,300,600,600))
wallList.append(Wall(600,600,300,600))
wallList.append(Wall(300,600,300,300))
def keyPressed():
全球人榜
全球公牛清单
全球墙列表
如果键=='p':
new_person =人物(mouseX,mouseY)
peopleList.append(new_person)
对于人中的p
p.stopSim()
对于BullList中的b:
b.stopSim()
elif键=='b':
new_bull =公牛(mouseX,mouseY)
bullList.append(new_bull)
对于人中的p
p.stopSim()
对于BullList中的b:
b.stopSim()
elif键=='':
对于人中的p
p.beginSim()
对于BullList中的bull:
bull.beginSim()
def draw():
全球人榜
全球公牛清单
全球墙列表
to_remove = set()
背景(255)
行程(0)
直肠(300,300,300,300)
对于范围内的p_i(len(peopleList)):
peopleList [p_i] .display()
对于范围内的p_j(p_i + 1,len(peopleList)):
peopleList [p_i] .collision(peopleList [p_j])
对于范围内的b_i(len(bullList)):
peopleList [p_i] .collision(bullList [b_i])
对于范围内的b_i(len(bullList)):
bullList [b_i] .display()
对于范围内的w_i(len(wallList)):
wallList [w_i] .display()
对于范围内的p_i(len(peopleList)):
wallList [w_i] .collision(peopleList [p_i])
对于范围内的b_i(len(bullList)):
wallList [w_i] .collision(bullList [b_i])
对于范围内的p_i(len(peopleList)):
min_dist = 1e6
最近的牛= -1
对于范围内的b_i(len(bullList)):
bull_dist = PVector.dist(peopleList [p_i] .position,bullList [b_i] .position)
如果bull_dist <min_dist:
min_dist = bull_dist
最近的牛= b_i
如果closet_bull!= -1且min_dist <100:
peopleList [p_i] .velocity.add(PVector.sub(peopleList [p_i] .position,bullList [closest_bull] .position).normalize())。limit(3)
peopleList [p_i] .running = True
其他:
peopleList [p_i] .running = False
对于范围内的b_i(len(bullList)):
min_dist = 1e6
最近的人= -1
对于范围内的p_i(len(peopleList)):
如果peopleList [p_i] .isDead:
继续
people_dist = PVector.dist(peopleList [p_i] .position,bullList [b_i] .position)
如果people_dist <min_dist:
min_dist = people_dist
最近的人= p_i
如果最接近的人!= -1并且min_dist <500:
bullList [b_i] .velocity.add(PVector.sub(peopleList [closest_people] .position,bullList [b_i] .position).normalize())。limit(5)

事件驱动的碰撞模型代码

  #Event-Driven Collision Modelimport heapq 
随机导入
导入数学
xMax = 1000.0
yMax = 1000.0
xBoxMax = 300.0
yBoxMax = 300.0
班级人员:

def __init __(self,x,y,startSim = False,isDead = False):
self.startSim = startSim
self.injuryCount = 0
self.collisionCount = 0
self.isDead = isDead
self.position = PVector(x,y)
self.velocity = PVector.random2D()。mult(xBoxMax / 10000)
self.radius = 5 / xBoxMax
self.m = 10

def update(self,dt):
如果self.isDead:
返回
self.position.add(PVector.mult(self.velocity,dt))
如果self.injuryCount> 30:
self.isDead = True

def显示(自己):
noStroke()
如果self.isDead:
填充(255,0,0)
elif self.injuryCount> 0:
填充(0,255,255)
其他:
填充(0)
椭圆(self.position.x * xBoxMax + xBoxMax,self.position.y * yBoxMax + yBoxMax,self.radius * xBoxMax,self.radius * yBoxMax)
noFill()

def beginSim(self):
self.startSim = True

def stopSim():
self.startSim =假

def计数(自己):
返回self.collisionCount

def timeToHit(self,other):
如果self ==其他:
返回1e20
dp = PVector.sub(other.position,self.position)
dx = dp.x
dy = dp.y
dv = PVector.sub(other.velocity,self.velocity)
dvx = dv.x
dvy = dv.y
dvdp = dx * dvx + dy * dvy
如果dvdp> 0:
返回1e20
dvdv = dvx * dvx + dvy * dvy
如果dvdv == 0:
返回1e20
dpdp = dx * dx + dy * dy
sigma = self.radius + other.radius
d = dvdp * dvdp-dvdv *(dpdp-sigma * sigma)
如果d <0:
返回1e20
返回-(dvdp + sqrt(d))/ dvdv

def timeToHitVerticalWall(self):
如果self.velocity.x> 0:
return(1.0-self.position.x-self.radius)/ self.velocity.x
elif self.velocity.x <0:
返回(self.radius-self.position.x)/ self.velocity.x
其他:
返回1e20

def timeToHitHorizo​​ntalWall(self):
如果self.velocity.y> 0:
返回(1.0-self.position.y-self.radius)/ self.velocity.y
elif self.velocity.y <0:
返回(self.radius-self.position.y)/ self.velocity.y
其他:
返回1e20

def bounceOff(自身,其他):
dp = PVector.sub(other.position,self.position)
dx = dp.x
dy = dp.y
dv = PVector.sub(other.velocity,self.velocity)
dvx = dv.x
dvy = dv.y
dvdp = dx * dvx + dy * dvy
sigma = self.radius + other.radius

magn = 2 * self.m * other.m * dvdp /((self.m + other.m)* sigma)

f = PVector(magn * dx / sigma,magn * dy / sigma)

self.velocity.add(f.mult(1.0 / self.m))
other.velocity.add(f.mult(1.0 / other.m))

self.collisionCount + = 1
other.collisionCount + = 1

def bounceOffVerticalWall(self):
self.velocity = PVector(-self.velocity.x,self.velocity.y)
self.collisionCount + = 1

def bounceOffHorizo​​ntalWall(self):
self.velocity = PVector(self.velocity.x,-self.velocity.y)
self.collisionCount + = 1
公牛类:


def __init __(self,x,y,startSim = False,isDead = False):
self.startSim = startSim
self.collisionCount = 0
self.position = PVector(x,y)
self.velocity = PVector.random2D()。mult(xBoxMax / 10000)
self.radius = 10 / xBoxMax
self.m = 30

def update(self,dt):
self.position.add(PVector.mult(self.velocity,dt))

def显示(自己):
noStroke()
填充(0)
椭圆(self.position.x * xBoxMax + xBoxMax,self.position.y * yBoxMax + yBoxMax,self.radius * xBoxMax,self.radius * yBoxMax)
noFill()

def beginSim(self):
self.startSim = True

def stopSim():
self.startSim =假

def计数(自己):
返回self.collisionCount

def timeToHit(其他):
如果self ==其他:
返回1e20
dp = PVector.sub(other.position,self.position)
dx = dp.x
dy = dp.y
dv = PVector.sub(other.velocity,self.velocity)
dvx = dv.x
dvy = dv.y
dvdp = dx * dvx + dy * dvy
如果dvdp> 0:
返回1e20
dvdv = dvx * dvx + dvy * dvy
如果dvdv == 0:
返回1e20
dpdp = dx * dx + dy * dy
sigma = self.radius + other.radius
d = dvdp * dvdp-dvdv *(dpdp-sigma * sigma)
如果d <0:
返回1e20
返回-(dvdp + sqrt(d))/ dvdv

def timeToHitVerticalWall(self):
如果self.velocity.x> 0:
return(1.0-self.position.x-self.radius)/ self.velocity.x
elif self.velocity.x <0:
返回(self.radius-self.position.x)/ self.velocity.x
其他:
返回1e20

def timeToHitHorizo​​ntalWall(self):
如果self.velocity.y> 0:
返回(1.0-self.position.y-self.radius)/ self.velocity.y
elif self.velocity.y <0:
返回(self.radius-self.position.y)/ self.velocity.y
其他:
返回1e20

def bounceOff(自身,其他):
dp = PVector.sub(other.position,self.position)
dx = dp.x
dy = dp.y
dv = PVector.sub(other.velocity,self.velocity)
dvx = dv.x
dvy = dv.y
dvdp = dx * dvx + dy * dvy
sigma = self.radius + other.radius

magn = 2 * self.m * other.m * dvdp /((self.m + other.m)* sigma)

f = PVector(magn * dx / sigma,magn * dy / sigma)

self.velocity.add(f.mult(1.0 / self.m))
other.velocity.sub(f.mult(1.0 / other.m))

self.collisionCount + = 1
other.collisionCount + = 1

def bounceOffVerticalWall(self):
self.velocity = PVector(-self.velocity.x,self.velocity.y)
self.collisionCount + = 1

def bounceOffHorizo​​ntalWall(self):
self.velocity = PVector(self.velocity.x,-self.velocity.y)
self.collisionCount + = 1

课堂活动:
def __init __(self,t,a,b):
自我t = t
self.a = a
self.b = b
如果a为None,则self.countA = -1 a.count()
如果b为None,则self.countB = -1 b.count()

def isValid(self):
如果self.a为None:
如果(self.b不是None)和(self.b.count()!= self.countB):
返回False
如果self.b为None:
如果(self.a不为None)和(self.a.count()!= self.countA):
返回False
如果(self.a不为None)和(self.a.count()!= self.countA):
返回False
如果(self.b不是None)和(self.b.count()!= self.countB):
返回False
返回True
peopleList = []
bullList = []
事件= []
t = 0.0
运行=错误
频率= 2
def setup():
全球事件
大小(int(xMax),int(yMax))
heapq.heappush(事件,(0.0,事件(0.0,无,无)))

def预测(a):
全球人榜
全球公牛清单
全球t
如果a为None:
返回
对于peopleList + bullList中的b:
如果a == b:
继续
dt = a.timeToHit(b)
如果dt == 1e20:
继续
heapq.heappush(事件,(t + dt,Event(t + dt,a,b)))
dtX = a.timeToHitVerticalWall()
dtY = a.timeToHitHorizo​​ntalWall()
如果dtX!= 1e20:
heapq.heappush(事件,(t + dtX,Event(t + dtX,a,无)))
如果dtY!= 1e20:
heapq.heappush(events,(t + dtY,Event(t + dtY,None,a)))
def keyPressed():
全球人榜
全球公牛清单
全球运行
如果键=='p':
如果mouseX> xBoxMax和mouseY> yBoxMax和mouseX <2 * xBoxMax和mouseY <2 * yBoxMax:
new_person =人物((mouseX-xBoxMax)/ xBoxMax,(mouseY-yBoxMax)/ yBoxMax)
peopleList.append(new_person)
运行=错误
elif键=='b':
如果mouseX> xBoxMax和mouseY> yBoxMax和mouseX <2 * xBoxMax和mouseY <2 * yBoxMax:
new_bull = Bull((鼠标X-xBoxMax)/ xBoxMax,(鼠标Y-yBoxMax)/ yBoxMax)
bullList.append(new_bull)
运行=错误
elif键=='':
运行=真
对于peopleList + bullList:
预测
def draw():
全球人榜
全球公牛清单
全球运行
全球事件
全球t
背景(255)
行程(0)
rect(xBoxMax,yBoxMax,xBoxMax,yBoxMax)

对于peopleList + bullList:
a.display()

如果正在运行:
事件= heapq.heappop(事件)[1]
如果event.isValid():
a =事件
b = event.b
对于peopleList + bullList中的p:
p.update(event.t-t)
t = event.t

如果(a不为无,b不为无):
a.bounceOff(b)
预测
预测(b)
elif(a不为None,b为None):
a.bounceOffVerticalWall()
预测
预测(b)
省略号(a为None且b为None):
b.bounceOffHorizo​​ntalWall()
预测
预测(b)
elif(a为None,b为None):
heapq.heappush(事件,(t + 1.0 /频率,Event(t + 1.0 /频率,无,无)))
events = [如果事件[1] .isValid(),则事件中事件的事件
打印事件