One Bump or Two: An Investigation Into Collision Detection in Agent-Based Modeling
(Excerpts from final conference paper)
I. Introduction
Our day to day lives are shaped by our interactions with other people. More often than not, we find ourselves navigating through crowds, whether in a vast metropolis, or in a Costco. Though the movements of average crowds are generally placid and of walking speed, our instinct for a fight-or-flight response is trigger in situations of emergency; it follows that simulations of crowds generally focus on changes in directionality and speed. However, historically speaking, the dangers presented in a mass flight response lies not in the attacker or hostile event, but in injuries and fatalities resulting from being stampeded or from collision with other solid bodies. While initially, the simulation of The Running of the Bulls aimed to model multi-agent behavior when faced with attackers, it eventually led to a more nuanced examination of how to detect collision efficiently in changing environments.
III. Collision as Vectors
In creating collision models, the agent itself does not contain any inherent attributes that allow it to collide or interact with the environment. Cellular Automata models circumvent this issue entirely by coding cell to cell interactions as a series of on-off switches in the form of Boolean if-then statements. This allows for a rules to be abstracted into a simple checklists; if the conditions are met, then the appropriate switches are flipped. The agent-based model used in our simulation in some sense has the same boolean components — certain states such as “injury”, “alive”, “dead”, are turned “on” or “off” depending on preset parameters. In the case of collision, however, a boolean variable of “did the object experience collision” (isCollided) is checked, but the outputs are not so much switches as they are a change in direction and speed, coded as vectors.
This explanation begs the question of how the boolean (isCollided) can be detected. Without any coding, agents are reduced to pixels on a screen. The movements are optical illusions created by moving points along an xy cartesian plane. One way of coding simple collision is to use x y coordinates as switches.
“If x position of point A is 1, then x position of A becomes -1”
However, because collision models are fundamentally fluid, it becomes very taxing very quickly when faced with a complex spatial configuration of the environment. Furthermore, if the goal is to examine a variety of spatial forms simultaneously, it becomes also impossible for humans to detail every coordinate on a grand scale.
One challenge of the simulation is to describe a way of creating collision for non static spaces.
V. Time Driven Simulation
The initial method used for collision detection is a “Time Driven Simulation” where time is coded as a discrete quanta. Quanta is the smallest unit of time. After setting a quanta size of dt, we can update the position of each agent after every dt units of time to check if any positions of agents intersect; if an overlap of positions is detected, the program reverts back to the time when the “collision” was detected, while updating the velocities of the colliding agents. In essence, “Time Drive Simulation” utilizes the positional markers of x-position and y-position of each agent but adjusts the agents based not only on their spatial position but also spatial-temporal position. It is a four-dimensional method of approaching collision.
IFthe x position of agent A is -1 at time T and the velocity of A is VANDthe x position of agent B is at -1 at time T and the velocity of B is V2THENthe x position of A is the x position of A at time (T-dt) and the velocity of A is -VANDThe x position of B is the x position of B at time (T-dt) and the velocity of B is -V2
Here, the “Velocity” is changed and updated becomes velocity is a vector, which contains direction. This approach still utilizes the same same principles of using constant positional checks on agents, but also allows for a freer range of interactions between various agent types. The drawback to this approach is twofold: checking overlap checks for each time quantum is tasking on computer memory, and in simulations with large population sizes, the simulation will begin to experience lag. In more extreme cases involving many anticipated collisions, the simulation checks performed on each agent and continuous spatial-temporal updating of agent’s relative positions could cause the simulation to crash.
Moreover, this approach is not always accurate; the collision detection relies on the value set for dt; if the intervals in which the checks happen are too far apart, and the agents “collide” during an interval in which the check does not occur, then the “collision” will be missed, and the agents will have seemingly phased through one another. In other words, if dt is too large relative to the speed at which the agents are traveling, then colliding agents will not be detected. On the other hand, if dt is too small, too many checks are performed per time quantum, slowing down the simulation. If the population size of colliding agents is large enough, the simulation will inevitably result in instances when agents collide in between checks, and therefore slip past one another.
This phenomenon was visibly present in our initial simulation, when the people agents as well as bull agents would sometimes slip through the city block boundaries. Due to our desired population sample of > 50, a smaller value in dt would have resulted in the simulation lagging severely. An alternative method of dealing with this issue in this particular instance is to adjust the running speeds of both the people and the bulls to be slower, so that they are less likely to experience an overlap event prior to the next check occuring. This approach, however, cannot be readily utilized in simulations with a rigid speed parameter, and is therefore not a universal solution.
We can see in the figure above that the Time-Driven collision model works until there is an increase in the velocity of the agents. Once we place a bull down, and the agents began to “run”, the continuous checks failed to capture instances of collision, allowing the agents to phase past the boundary. Even though the dt set for the simulation was already small — in other words, the time interval between “checks”, most of the agents managed to move past the boundary undetected.
VI. Event-Driven Simulation
We can aim to avoid the majority of the computational headaches of the time-driven approach by looking at a different model for particle collision systems — event-driven simulation. Instead of using a quantized time approach to performing on the order of N² collision checks for each time step (each particle must check against every other particle/wall), event-driven simulation presents a much more computationally feasible approach. By noting that the majority of the timesteps will not involve a collision between particles, an event, we can drastically simplify each iteration by only predicting when such an event will occur. Assuming that all particles travel in straight line trajectories at constant velocities between collisions, we will avoid performing any collision checks until after such an event has occurred. This allows us to skip a vast proportion of the previously necessary collision checks at each time step, and rapidly advance the simulation until the next event occurs. Thus, this problem is transformed from a time-driven simulation into an event-driven simulation.
The crux of this event-driven simulation lies with how we can determine what the next particle collision is. We address this by using a priority queue of future events, ordered by time. A priority queue is a data structure that ensures that the first element in the priority queue is always the “smallest” element in the queue. In this case, usage of the priority queue will help us ensure that the next event to be considered in the simulation will always be at the front of the queue. At any point in time, the PQ contains all future collisions that will occur, assuming that again, all particles continue to move in a straight line trajectory forever. If a particle collides and changes direction, any event that was inserted into the priority queue prior to this event is rendered invalid, and will not be processed when it is popped from the head of the PQ.
Figure 1
First, upon initializing all of our particles, we determine all future collisions that could possibly occur given our initial particle state, and insert them one by one into the PQ. These predictions can be easily calculated with some basic manipulation of physical formulas for displacement and velocity. Collision resolution is equally easy to handle in this framework, as we do not need to be concerned with checks at each timestep to ensure that particles do not “clip” past one another. Here in this model, we simply calculate the times at which the collisions will occur, and upon removal of such events from the head of the PQ, we resolve the collisions and ensure that any overlaps are appropriately handled at this time. Upon processing an event, we move all particles to the time t using their current velocities. recalculate all possible collisions with any affected particles and re-insert them into the PQ. If the next event processed corresponds to an invalidated collision (either particle moved/collided since the event was inserted onto the PQ, or either particle is removed/dead), we discard the event and do not process it.
Event-driven simulation does serve to address a great deal of the issues that might arise from the computational complexity and inaccuracy of collisions of time-driven simulation, but this comes at a cost. With time-driven simulations, we are able to make modifications to the velocities of all objects at each step, thus providing us with mechanism that can allow for particles to “chase” one another, as their new velocity can be updated to point towards another position or particle. However, one of the base assumptions of the event-driven simulation is that particles will continue to travel with constant velocity between collisions, an assumption that will break under any adjustment of the particle’s velocity upon “chasing” another particle. As a result, after each modification of a particle’s velocity, all future collisions with said particle are immediately invalidated. While this is not an issue in an of itself, the recomputation of possible collisions with this new particle increases the computational complexity of this simulation, as well as consuming space on the PQ with many additions of new potential events that are constantly being invalidated. With enough particles, the introduction of the “chasing” mechanism could potentially make this simulation method as slow as the time-driven approach.
We can see in the case of the Event-Driven collision model, the agents are much more well contained within the boundaries even in the case of high starting velocities. This illustration shows its more suited applicability to chemistry or physics models for Brownian motion in particles or electron movement.
VII. Addressing Collision in Crowd Simulation
To address the issues of collision clipping in the case of particles accidentally making it through walls, we had considered the event-driven simulation. However, in order to maintain our desired behavior of particle chasing, this approach proved to be a less-than-ideal approach towards modeling our people and bull model. The strengths of the event-driven simulation are much more apparent in the modeling of Brownian motion as in particle physics simulations, as each particle travels in a straight line with little to no velocity changes aside from the elastic collisions with other particles. In such a case, the prediction of all possible future collisions are easy solutions to a closed-form expression. However, with the necessary inclusion of particle-particle interactions at a distance, the nature of the particle collision dynamics shifts. While still deterministic, the prediction of any future collisions can only rely on the current velocities in the time step immediately before the velocities change again in response to altered positions of nearby bulls/people. In this sense, we can describe the benefits of event-driven simulation as being maximized in first-order particle simulation systems, where the deltas in position, or velocity, remain constant through time prior to collisions, and can thus be used to mitigate the recalculations of timesteps that do not result in any collisions.
However, once we introduce heteroskedasticity, or instances under which variability of a variable contains variance across a range of values of another distinct predictor variable, in in the higher moments of the particle system, the time-driven simulations prove to be vastly superior in terms of computational complexity and simplicity of the simulation system itself. This is a result of the ability to customize how the change in each moment of the particle’s motion is very easy to model from each timestep to the next, in a sort of differential equation formulation of the next state of the model as a function of the previous state. While potentially taxing to simulate very large scale systems, by decreasing the time-step one is able to recover much of the precision lost at the expense of longer simulation times.
Earlier we had noticed some clipping of the particles past walls. To address these issues, there was in fact some parameterizations and simulation mechanics that needed to be adjusted. Generally, speaking, this clipping happens when the particle moves in a manner that updates the current position of the particle to past the boundary as delineated by the wall. To combat this, we made several changes to our initial approach. First, we shifted the collision check with the wall to happen after all the other collision checks of each particle against one another, as well as the subsequent re-orientation of all the bulls / people to chase after / run away from their nearest neighbor. This allowed us to have a sanity check after all the previous redirection of the particle’s path were finalized, and to allow us to bounce the particle off of the wall. We also played around with the exact setting of a parameter that controlled the distance that a particle had to be close to a wall in order for us to consider it a collision. Initially, we had set this value to be somewhat high, in order to capture corner cases in which a fast moving particle would clip past the wall simply because there was no frame in which it was close to the wall before it jumped past it. However, this led to some vast inaccuracies, in addition to particle bouncing off of a wall before it even got close to it.
Finally, the most subtle change that we had made was to combat the observed phenomenon that because a particle was either chasing or running from one another, this additional factor was of strong enough magnitude that it caused the particle to overcome the natural normal force of the wall and clip past the wall. To address this issue, we made the wall normal force strong enough to compensate for any chase forces, and also limited the impact the reflection force would have on the velocity of the original object. This causes some particles to bounce against a wall continuously, as the same chase target is on the other side of the wall, but the wall normal force allows the particle to resist clipping through the wall. For good measure, we also decreased the timestep of the model to account for such increased need for granularity with these collisions.
In comparing this formulation to previous forms of this simulation study, we find that the crucial difference between our work and other previous studies is in how we handle the collision issues. Other formulations avoid the problem altogether by programming their agents to move away from walls in some sort of guided reaction to the environment about them. While this approach does allow one to avoid some of the tricky issues around collision artifices, we believe that allowing particles to collide with one another lends itself to the most realistic simulation. Instead of allowing particles to turn away from the wall, we force an interaction with the wall by calculating the incident angle of collision and reflecting it along the normal vector of the wall. After all, not every agent has the ability to avoid collisions.
VIII. Space as an Agent
One question to consider in agent-based models is whether or not collision is even necessary in order to simulate larger crowd movement. Would eliminating the issue of collision altogether allow for a more fluid model of crowd movement? For our purposes, the simulation was focused on the anticipated results of agent-to-agent collision during movement instances. Moreover, the agent-to-agent interaction was largely a consequence of how agents interacted in specific configurations of space. Hence, without agent-to-environment collision, the concept of “space” and differential orientations of space does not exist without collision to define it.
The simulation leveraged simple mechanical behavior rules for the attacking agent (bulls) for a more complex agent behavior for people. Whereas bulls generally only have a [chase] state, the people agents can have multiple quantitative traits such as “isInjured”, “isDead”, and “isChased”, the latter affecting its speed and directionality. “isDead” also physically removes the agent as an agent and replaces it with a static object “body”. The “body” is then integrated into the environment as part of the spatial fabric. Here, we can see agent-based simulation not only as a model for agent-to-agent interactive but as a agents physically alter the spatial parameters.
We have thus far been describing the environment as static objects, but that is actually a misclassification. The spatial environment under with the people operate should actually be seen as part of the multi-agent based model, where environment has temporal fluidity rather than spatial.
Temporal fluidity in this context is achieved by the addition of “bodies” resulting from the collisions. Much like the neighborhoods of cellular automata, the environment of agent-based models can be developed incrementally and shifted through the progression of time. Therefore, to discount the effects of space as an agent in free-movement agent models is to overlook a very key component in agent behavior.
In our simulation, the spatial change is both deliberate and incremental; we can shift through various preset maps, altering the possible paths for agents to take, or we can add mass to maps through placement of obstructions.
IX. Scalability and Applicability
One of the more interesting applications of collision models is the ability to simulate crowd movement without subject actual crowds in danger. There are several ideas on how to circumvent the lag and processing speed drop when applying a Time-Driven Model approach to a crowd simulation with collision. We can effectively increase starting population size to 1000 or 10,000 or infinite given enough computing power and powerful enough graphics card. Even on slower technological infrastructures, we can take time-lapse photos of the simulation to allow for mega scale populations operating on a significantly reduced framerate. If we find alternative methods of screen capturing running simulations that are painstakingly slow, then theoretically it is possible to decrease dt in a Time Driven model to such small intervals that the program will be essentially checking at every perceivable time interval. This however, is still extremely inefficient in terms of energy consumed in simply running and loading each framerate of the program.
Finding an efficient solution to collision is the key to high accuracy predictive model agent based simulations. While many python libraries created for gaming already have pre-built functions for collision, these often run on separate physics engines. The simulation field is tasked with finding its own solution to allow for seamless integration of environmental collision, especially as the looming threat of climate change and predictable disasters heightens to urgency for accurate agent-based spatial-temporal models. This scalability must allow for varied analysis of the effects of certain spaces in crowd movement and collision frequency, so that more complex parameters may be applied to simulate the complexities of true urban conditions.
Time-Driven Collision Model Code
#Time Driven Collision Modelimport random
import math
xMax = 1000
yMax = 1000class People:
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 update(self):
if self.isDead:
return
self.position.add(PVector.mult(self.velocity, 1))
if self.injuryCount > 30:
self.isDead = True
def display(self):
noStroke()
if self.isDead:
fill(255, 0, 0)
elif self.injuryCount > 0:
fill(0, 255, 255)
else:
fill(0)
ellipse(self.position.x, self.position.y, self.radius*2, self.radius*2)
noFill()
if self.startSim:
self.update()
def beginSim(self):
self.startSim = True
def stopSim(self):
self.startSim = False
def collision(self, other):
if not self.startSim:
return
#Get distance between people
distanceVect = PVector.sub(other.position, self.position)
#Calculate magnitude of the vector separating the balls
distanceVectMag = distanceVect.mag()
#minimum distance before they are touching
minDistance = float(self.radius + other.radius)
if (distanceVectMag < minDistance):
distanceCorrection = (minDistance-distanceVectMag)/2.0
d = distanceVect.copy()
correctionVector = d.normalize().mult(distanceCorrection)
other.position.add(correctionVector)
self.position.sub(correctionVector)
#get angle of distance vector
theta = distanceVect.heading()
#precalculate trig values
sine = sin(theta)
cosine = cos(theta)
bTemp= [
PVector(),
PVector()
]
bTemp[1].x = cosine * distanceVect.x + sine*distanceVect.y
bTemp[1].y = cosine * distanceVect.y - sine * distanceVect.x
#rotate temp velocity
vTemp = [
PVector(),
PVector()
]
vTemp[0].x = cosine * self.velocity.x + sine*self.velocity.y
vTemp[0].y = cosine * self.velocity.y - sine*self.velocity.x
vTemp[1].x = cosine * other.velocity.x + sine*other.velocity.y
vTemp[1].y = cosine * other.velocity.y + sine*other.velocity.x
vFinal = [
PVector(),
PVector()
]
# final rotated velocity for 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;
# final rotated velocity for 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;
# hack to avoid clumping
bTemp[0].x += vFinal[0].x;
bTemp[1].x += vFinal[1].x;
bFinal = [
PVector(),
PVector()
]
bFinal[0].x = cosine * bTemp[0].x - sine * bTemp[0].y
bFinal[0].y = cosine * bTemp[0].y + sine * bTemp[0].x
bFinal[1].x = cosine * bTemp[1].x - sine * bTemp[1].y
bFinal[1].y = cosine * bTemp[1].y + sine * bTemp[1].x
#update balls to screen position
self.velocity.x = cosine * vFinal[0].x - sine * vFinal[0].y
self.velocity.y = cosine * vFinal[0].y + sine * vFinal[0].x
if other.__class__.__name__ == 'People':
other.velocity.x = cosine * vFinal[1].x - sine * vFinal[1].y
other.velocity.y = cosine * vFinal[1].y + sine * vFinal[1].x
other.position.x = self.position.x + bFinal[1].x
other.position.y = self.position.y + bFinal[1].y
if self.running:
self.injuryCount += 1
else:
self.injuryCount += 10
self.position.add(bFinal[0])class Bull:
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.1def update(self):
self.position.add(PVector.mult(self.velocity, 0.1))
if (self.position.x > width-self.radius):
self.position.x = width-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 = height-self.radius
self.velocity.y *= -0.9
elif (self.position.y < self.radius):
self.position.y = self.radius
self.velocity.y *= -0.9
def display(self):
noStroke()
fill(60)if self.startSim:
self.update()
ellipse(self.position.x, self.position.y, self.radius*2, self.radius*2)
noFill()
def beginSim(self):
self.startSim = True
def stopSim(self):
self.startSim = FalsepeopleList = []
bullList = []
wallList = []class Wall:
delta = 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 display(self):
stroke(0)
line(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.y2)/2 + self.normVector.y)
def collision(self, other):
d1 = dist(other.position.x, other.position.y, self.x1, self.y1)
d2 = dist(other.position.x, other.position.y, self.x2, self.y2)
if ( ((d1+d2) >= (self.wallLength - Wall.delta)) and ((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():
size(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():
global peopleList
global bullList
global wallList
if key == 'p':
new_person = People(mouseX, mouseY)
peopleList.append(new_person)
for p in peopleList:
p.stopSim()
for b in bullList:
b.stopSim()
elif key == 'b':
new_bull = Bull(mouseX, mouseY)
bullList.append(new_bull)
for p in peopleList:
p.stopSim()
for b in bullList:
b.stopSim()
elif key == ' ':
for p in peopleList:
p.beginSim()
for bull in bullList:
bull.beginSim()def draw():
global peopleList
global bullList
global wallList
to_remove = set()
background(255)
stroke(0)
rect(300,300,300,300)
for p_i in range(len(peopleList)):
peopleList[p_i].display()
for p_j in range(p_i + 1, len(peopleList)):
peopleList[p_i].collision(peopleList[p_j])
for b_i in range(len(bullList)):
peopleList[p_i].collision(bullList[b_i])
for b_i in range(len(bullList)):
bullList[b_i].display()
for w_i in range(len(wallList)):
wallList[w_i].display()
for p_i in range(len(peopleList)):
wallList[w_i].collision(peopleList[p_i])
for b_i in range(len(bullList)):
wallList[w_i].collision(bullList[b_i])
for p_i in range(len(peopleList)):
min_dist = 1e6
closest_bull = -1
for b_i in range(len(bullList)):
bull_dist = PVector.dist(peopleList[p_i].position, bullList[b_i].position)
if bull_dist < min_dist:
min_dist = bull_dist
closest_bull = b_i
if closest_bull != -1 and 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
else:
peopleList[p_i].running = False
for b_i in range(len(bullList)):
min_dist = 1e6
closest_people = -1
for p_i in range(len(peopleList)):
if peopleList[p_i].isDead:
continue
people_dist = PVector.dist(peopleList[p_i].position, bullList[b_i].position)
if people_dist < min_dist:
min_dist = people_dist
closest_people = p_i
if closest_people != -1 and min_dist < 500:
bullList[b_i].velocity.add(PVector.sub(peopleList[closest_people].position, bullList[b_i].position).normalize()).limit(5)
Event-Driven Collision Model Code
#Event-Driven Collision Modelimport heapq
import random
import math
xMax = 1000.0
yMax = 1000.0
xBoxMax = 300.0
yBoxMax = 300.0class People:
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):
if self.isDead:
return
self.position.add(PVector.mult(self.velocity, dt))
if self.injuryCount > 30:
self.isDead = True
def display(self):
noStroke()
if self.isDead:
fill(255, 0, 0)
elif self.injuryCount > 0:
fill(0, 255, 255)
else:
fill(0)
ellipse(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):
self.startSim = False
def count(self):
return self.collisionCount
def timeToHit(self, other):
if self == other:
return 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
if dvdp > 0:
return 1e20
dvdv = dvx * dvx + dvy * dvy
if dvdv == 0:
return 1e20
dpdp = dx * dx + dy * dy
sigma = self.radius + other.radius
d = dvdp * dvdp - dvdv * (dpdp - sigma*sigma)
if d < 0:
return 1e20
return -(dvdp + sqrt(d)) / dvdv
def timeToHitVerticalWall(self):
if self.velocity.x > 0:
return (1.0 - self.position.x - self.radius) / self.velocity.x
elif self.velocity.x < 0:
return (self.radius - self.position.x) / self.velocity.x
else:
return 1e20
def timeToHitHorizontalWall(self):
if self.velocity.y > 0:
return (1.0 - self.position.y - self.radius) / self.velocity.y
elif self.velocity.y < 0:
return (self.radius - self.position.y) / self.velocity.y
else:
return 1e20
def bounceOff(self, other):
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 bounceOffHorizontalWall(self):
self.velocity = PVector(self.velocity.x, -self.velocity.y)
self.collisionCount += 1class Bull:
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 display(self):
noStroke()
fill(0)
ellipse(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):
self.startSim = False
def count(self):
return self.collisionCount
def timeToHit(self, other):
if self == other:
return 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
if dvdp > 0:
return 1e20
dvdv = dvx * dvx + dvy * dvy
if dvdv == 0:
return 1e20
dpdp = dx * dx + dy * dy
sigma = self.radius + other.radius
d = dvdp * dvdp - dvdv * (dpdp - sigma*sigma)
if d < 0:
return 1e20
return -(dvdp + sqrt(d)) / dvdv
def timeToHitVerticalWall(self):
if self.velocity.x > 0:
return (1.0 - self.position.x - self.radius) / self.velocity.x
elif self.velocity.x < 0:
return (self.radius - self.position.x) / self.velocity.x
else:
return 1e20
def timeToHitHorizontalWall(self):
if self.velocity.y > 0:
return (1.0 - self.position.y - self.radius) / self.velocity.y
elif self.velocity.y < 0:
return (self.radius - self.position.y) / self.velocity.y
else:
return 1e20
def bounceOff(self, other):
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 bounceOffHorizontalWall(self):
self.velocity = PVector(self.velocity.x, -self.velocity.y)
self.collisionCount += 1
class Event:
def __init__(self, t, a, b):
self.t = t
self.a = a
self.b = b
self.countA = -1 if a is None else a.count()
self.countB = -1 if b is None else b.count()
def isValid(self):
if self.a is None:
if (self.b is not None) and (self.b.count() != self.countB):
return False
if self.b is None:
if (self.a is not None) and (self.a.count() != self.countA):
return False
if (self.a is not None) and (self.a.count() != self.countA):
return False
if (self.b is not None) and (self.b.count() != self.countB):
return False
return TruepeopleList = []
bullList = []
events = []
t = 0.0
running = False
freq = 2def setup():
global events
size(int(xMax), int(yMax))
heapq.heappush(events, (0.0, Event(0.0, None, None)))
def predict(a):
global peopleList
global bullList
global t
if a is None:
return
for b in peopleList + bullList:
if a == b:
continue
dt = a.timeToHit(b)
if dt == 1e20:
continue
heapq.heappush(events, (t + dt, Event(t + dt, a, b)))
dtX = a.timeToHitVerticalWall()
dtY = a.timeToHitHorizontalWall()
if dtX != 1e20:
heapq.heappush(events, (t + dtX, Event(t + dtX, a, None)))
if dtY != 1e20:
heapq.heappush(events, (t + dtY, Event(t + dtY, None, a)))def keyPressed():
global peopleList
global bullList
global running
if key == 'p':
if mouseX > xBoxMax and mouseY > yBoxMax and mouseX < 2*xBoxMax and mouseY < 2*yBoxMax:
new_person = People((mouseX - xBoxMax)/ xBoxMax, (mouseY - yBoxMax) / yBoxMax)
peopleList.append(new_person)
running = False
elif key == 'b':
if mouseX > xBoxMax and mouseY > yBoxMax and mouseX < 2*xBoxMax and mouseY < 2*yBoxMax:
new_bull = Bull((mouseX - xBoxMax)/ xBoxMax, (mouseY - yBoxMax) / yBoxMax)
bullList.append(new_bull)
running = False
elif key == ' ':
running = True
for a in peopleList + bullList:
predict(a)def draw():
global peopleList
global bullList
global running
global events
global t
background(255)
stroke(0)
rect(xBoxMax, yBoxMax, xBoxMax, yBoxMax)
for a in peopleList + bullList:
a.display()
if running:
event = heapq.heappop(events)[1]
if event.isValid():
a = event.a
b = event.b
for p in peopleList + bullList:
p.update(event.t - t)
t = event.t
if (a is not None and b is not None):
a.bounceOff(b)
predict(a)
predict(b)
elif (a is not None and b is None):
a.bounceOffVerticalWall()
predict(a)
predict(b)
elif (a is None and b is not None):
b.bounceOffHorizontalWall()
predict(a)
predict(b)
elif (a is None and b is None):
heapq.heappush(events, (t + 1.0 / freq, Event(t + 1.0 / freq, None, None)))
events = [event for event in events if event[1].isValid()]
print events
