代写CSE 6010、代做C++语言编程
Assignment 4
Collisions
Last updated November 1: output positions at simulation end time
Initial Submission Due Date: 11:59pm on Thursday, October 26
Final Submission Due Date: 11:59pm on Thursday, November 2
Peer review and code reflections assignments due November 9 will be posted separately
Submit codes as described herein to Gradescope through Canvas
48-hour grace period applies to all deadlines
In this assignment, you will simulate collisions of particles in a two-dimensional box. Particles can
collide with the walls and with each other. Here, you will use an event-driven approach by
calculating the times of all possible interactions and allowing the earliest collision to occur.
Compared to the alternative approach of updating all particles’ positions over short time intervals
and checking for collisions, the event-driven approach can offer more accuracy by computing exact
collision times as well as more efficiency by waiting until a collision happens to update a particle’s
position.
Your task is to write a program in C to simulate particle collisions. Specifically, you will calculate the
times of all possible collisions. Then, for as long as the time is less than some user-specified end
time, you will sort the possible collisions according to the collision time, allow the earliest collision
to happen, and update the times of possible collisions involving the particle(s) that just collided. At
the end, you will update all particle positions to the specified end time.
Note that you may test your code against the autograder for the final submission; you may submit
as many times as you like. Please note that you still must submit your initial submission on time.
Specifications:
• Your code should read in the initial particle information from a file along with other key
values. The first line of the file will specify the number of particles (N); you should assume
the particles are represented as integers from 0 to N-1. The second line will list the radius of
the particles. The third line will specify the length of the box in the 𝑥𝑥-direction followed by
the 𝑦𝑦-direction. Each following line of the file will specify the following information for
particles 0 to N-1, one per line, in order: 𝑥𝑥-position, 𝑦𝑦-position, 𝑥𝑥-velocity, and 𝑦𝑦-velocity,
which should all be stored as doubles. A small test file will be provided; other files will be
used to test your final submission, but you should also generate some test cases (e.g., to test
for collisions with each wall as well as for particle-particle collisions). You may assume that
the values and file format are valid.
• The name of the file containing the initial particle information should be read as the first
command-line argument. You do not need to perform any validation and may assume that
the user will specify a valid filename.
• The second command-line argument should be a double specifying the simulation end
time. Assume the simulation begins at time 0. You may also assume that the input time will
be a positive value; validation is not required. Collisions should be processed until the
current collision time would be greater than the end time. At the end, the positions of all
particles will be updated to the end time, as detailed below.
Page 2 of 7
• Your code should define two structures: one to represent a particle and one to represent a
potential collision. Each particle will need to store its position and velocity and the time
these values were last updated. In addition, to aid in debugging, each particle should keep
track of the number of collisions it has with walls (lump together collisions with all four
walls) and the number of collisions it has with other particles. Each potential particleparticle collision should include the two particles involved and the potential collision time;
each potential particle-wall collision should include the particle involved and a
representation for each wall (for example, you could use various negative integers to
represent walls).
• You should define an array of particles to represent the N particles and an array of potential
collisions. Assume that all particles have non-zero 𝑥𝑥- and 𝑦𝑦-velocity components. Thus, each
particle will have 2 potential wall collisions (one with the left or right wall and one with the
upper or lower wall), one of which will be earlier than the other, and you can just store the
earlier. In addition, every particle potentially could collide with every other particle, for a
total of N*(N-1)/2 potential particle-particle collisions. Thus, there will be a total of
N+N*(N-1)/2 = N*(N+1)/2 potential collisions. Memory for these arrays should be
allocated dynamically.
• You will initially calculate all potential collision times. The information at the end of this
document specifies how to do so for both particle-wall collisions and particle-particle
collisions. Some collisions will not be possible. You should set the potential collision time in
that case to a large value that will ensure the collision will not occur in the program.
• Once all potential collisions times have been calculated, you should sort the array of
potential collisions. (Note that you could in principle use a priority queue; however, for
this assignment you are asked to use sorting instead.) You may use any sorting method you
like; we recommend insertion sort because it is easy to implement and because the array
will be “somewhat” sorted after the first sort, so that insertion sort should be efficient.
• “Process” the earliest potential collision: update the current time to the collision time and
update the position, velocity, last update time, and the count of the relevant collision type
for each particle involved. The information at the end of this document specifies how to
update the particle position and velocity values for both particle-wall collisions and
particle-particle collisions.
• After processing the collision, scan through the array of potential collisions and update the
times for all potential collisions involving the particle(s) that participated in the most
recent collision that was just “processed.”
• After the last collision has been processed, advance all particle positions to the userspecified simulation end time (so all particle positions are at the same time), then output
the final position and the counts of wall and particle collisions (in that order) for each
particle to the screen. Use a format statement like the following for each particle (adjust for
your variable names, of course—the point is to use the precision listed, commas and spaces
as indicated, and one particle per line).
printf("%.6f, %.6f, %d, %d\n", particles[i].xpos,
particles[i].ypos, particles[i].cwall, particles[i].cpart);
• All dynamically allocated memory should be freed (consider using valgrind to test for
memory leaks or, if you use MacOS, you may wish to try leaks).
Page 3 of 7
To receive full credit, your code must be well structured and documented so that it is easy to
understand. Be sure to include comments that explain your code statements and structure.
Test files of initial particle positions/velocities are provided for you; we will check results for other
sets of initial particle positions/velocities. In particular, we are including test cases with only
particle-wall collisions and with only particle-particle collisions so that you can test these
capabilities separately.
Final submission: You should submit to Gradescope through Canvas the following files:
(1) your code (all .c and .h files); no specific filenames are required for your code but note the
specification for your executable file below.
(2) the Makefile you use to compile your program such that your executable file that will run your
program is named ‘particles’. You may use the Makefile provided for previous assignments as a
starting place.
(3) a series of 2-3 slides saved as a PDF and named slides.pdf, structured as follows:
• Slide 1: your name and a brief explanation of how you developed/structured your program.
This should not be a recitation of material included in this assignment document but should
focus on the main structural and functional elements of your program (e.g., the purpose of
any loops you used, the purpose of any if statements you used to change the flow of the
program, the purpose of any functions you created, etc.). The goal is to help us understand
how you developed your code and your intentions. You are limited to one slide.
• Slides 2-3: a discussion of why you believe your program functions properly, with reference
to at least one test case for a particle-wall collision and at least one for a particle-particle
collision.
Initial submission: Your initial submission does not need to include the slides or Makefile. It will
not be graded for correctness or even tested but rather will be graded based on the appearance of a
good-faith effort to complete the majority of the assignment.
Some hints:
• Start early!
• Identify a logical sequence for implementing the desired functionality. Then implement one
piece at a time and verify each piece works properly before proceeding to implement the
next.
• Consider implementing just particle-wall collisions first and then adding in particle-particle
collisions later.
• Or, consider implementing both particle-wall collisions and particle-particle collisions for
just the initial time, then add in the loop and collision time updates later.
Updating potential collision times and colliding particle positions and velocities
The remainder of this document details how to calculate the times for potential collisions as well as
how to update the positions and velocities of particles involved in collisions. Don’t be alarmed by
Page 4 of 7
the length! The exposition is intended to be comprehensive, but what you actually need to
implement is fairly small and straightforward. Look for boldface red text that specifies the actual
update equations to be solved.
For the exposition below, the following notation is used. (The choices here are a mathematical
convenience; you do not need to use the same notation.)
(𝑥𝑥𝑖𝑖, 𝑦𝑦𝑖𝑖): position of particle 𝑖𝑖 (if distinguishing particles is not needed, subscripts will be dropped)
(𝑢𝑢𝑖𝑖, 𝑣𝑣𝑖𝑖): velocity of particle 𝑖𝑖 (if distinguishing particles is not needed, subscripts will be dropped)
When needed, we will introduce a functional notation: e.g., 𝑥𝑥(𝑡𝑡) represents the 𝑥𝑥-position of a
particle at time 𝑡𝑡.
𝑅𝑅: radius of each particle
𝐿𝐿𝑥𝑥: position of right edge (length in the 𝑥𝑥-direction)
𝐿𝐿𝑦𝑦: position of right edge (length in the 𝑦𝑦-direction)
You may assume that each particle has non-zero velocity components in both directions: e.g., 𝑢𝑢 ≠ 0
and 𝑣𝑣 ≠ 0. Also, the origin is assumed to be located at the lower left corner (e.g., 𝑦𝑦 = 0 at the lower
boundary). Thus, the walls of the box are at 𝑥𝑥 = 0, 𝑥𝑥 = 𝐿𝐿𝑥𝑥, 𝑦𝑦 = 0, and 𝑦𝑦 = 𝐿𝐿𝑦𝑦.
Calculation of particle-wall collisions:
In the absence of any other interactions, a particle will travel using the speed and direction given by
its velocity until it encounters a wall. We will consider collisions with the left and right walls first.
Collisions with the left and right walls are governed by 𝑢𝑢: if 𝑢𝑢 > 0, the particle is moving to the right
and the collision would occur with the right wall; if 𝑢𝑢 < 0, the particle is moving to the left and the
collision would occur with the left wall.
Collisions occur when a particle comes within 𝑅𝑅 of either wall. Thus, a collision with the left wall
would take place when 𝑥𝑥 = 𝑅𝑅 and a collision with the right wall would take place when 𝑥𝑥 = 𝐿𝐿𝑥𝑥 − 𝑅𝑅.
We can express a particle’s path over time when we know its position at time 𝑡𝑡1 using the following
(parametric) description:
𝑥𝑥(𝑡𝑡) = 𝑥𝑥(𝑡𝑡1) + 𝑢𝑢 ∗ (𝑡𝑡 − 𝑡𝑡1); 𝑦𝑦(𝑡𝑡) = 𝑦𝑦(𝑡𝑡1) + 𝑣𝑣 ∗ (𝑡𝑡 − 𝑡𝑡1).
We will first consider the case of potential collisions with the left and right walls. We wish to solve
for the time that results in the particle having 𝑥𝑥-position of either 𝑅𝑅 (in the case that the particle is
moving to the left) or 𝐿𝐿𝑥𝑥 − 𝑅𝑅 (in the case that the particle is moving to the left). Therefore, the
collision time at the left edge, 𝑡𝑡𝐿𝐿, for a particle moving left would be given by
𝑡𝑡𝐿𝐿 = 𝑡𝑡1 +
𝑅𝑅 − 𝑥𝑥(𝑡𝑡1)
𝑢𝑢 .
Similarly, the collision time at the right edge, 𝑡𝑡𝑅𝑅, for a particle moving to the right would be given
by
Page 5 of 7
𝑡𝑡𝑅𝑅 = 𝑡𝑡1 + (𝐿𝐿𝑥𝑥 − 𝑅𝑅) − 𝑥𝑥(𝑡𝑡1)
𝑢𝑢 .
Note that 𝑅𝑅 ≤ 𝑥𝑥(𝑡𝑡) ≤ 𝐿𝐿𝑥𝑥 − 𝑅𝑅 for all 𝑡𝑡 (that is, the particle cannot get closer to either wall than a
distance of 𝑅𝑅 from it), so 𝑡𝑡𝐿𝐿 is in the future only for 𝑢𝑢 < 0 and 𝑡𝑡𝑅𝑅 is in the future only for 𝑢𝑢 > 0.
When calculating potential collisions, you will only need to record the time of the potential collision,
because the collision actually may not occur, so it is more efficient to wait to update positions and
velocities. You may choose to have logic that calculates only the appropriate collision time based on
the sign of 𝑢𝑢 or you may calculate both options and keep only the collision information for the
future collision.
If a particle actually collides with the right or left wall (i.e., it is the earliest collision of those
considered), the particle’s position will be set to the position it would have at that time (e.g., the 𝑥𝑥-
position should be 𝑅𝑅 or 𝐿𝐿𝑥𝑥 − 𝑅𝑅 depending on the sign of 𝑢𝑢), and its velocity will be updated by
reversing the sign of 𝑢𝑢 (the 𝑥𝑥-component of the velocity).
For collisions involving the top and bottom walls, everything is the same after replacing 𝑥𝑥 with 𝑦𝑦
and 𝑢𝑢 with 𝑣𝑣.
Calculation of particle-particle collisions:
Below, we build on the explanation of particle-wall interactions.
We will define two particles as colliding when they just touch—that is, the distance between the
centers of the two particles is twice their radius, 2𝑅𝑅. To find the time of such an event, we begin
geometrically by defining the circle with radius 𝑅𝑅 (diameter 2𝑅𝑅) that represents when the two
particles just touch, as we will want to find the time that this event occurs. We find the center of this
circle using the average of the 𝑥𝑥 positions of the two particles and the average of their 𝑦𝑦 positions,
so that the center is given by
1
2 𝑥𝑥1(𝑡𝑡𝑐𝑐) + 𝑥𝑥2(𝑡𝑡𝑐𝑐) ,
1
2 𝑦𝑦1(𝑡𝑡𝑐𝑐) + 𝑦𝑦2(𝑡𝑡𝑐𝑐) , at some collision time 𝑡𝑡𝑐𝑐 that
we seek. Note that the general equation for a circle with radius 𝑅𝑅 and center (𝑥𝑥𝑐𝑐𝑐𝑐𝑐𝑐, 𝑦𝑦𝑐𝑐𝑐𝑐𝑐𝑐) is given by
(𝑥𝑥 − 𝑥𝑥𝑐𝑐𝑐𝑐𝑐𝑐)2 + (𝑦𝑦 − 𝑦𝑦𝑐𝑐𝑐𝑐𝑐𝑐)2 = 𝑅𝑅2.
The particles thus are on the circle representing when they are just touching when the following
condition is satisfied:
𝑥𝑥1(𝑡𝑡𝑐𝑐) − 1
2 𝑥𝑥1(𝑡𝑡𝑐𝑐) + 𝑥𝑥2(𝑡𝑡𝑐𝑐) 2
+ 𝑦𝑦1(𝑡𝑡𝑐𝑐) − 1
2 𝑦𝑦1(𝑡𝑡𝑐𝑐) + 𝑦𝑦2(𝑡𝑡𝑐𝑐) 2
= 𝑅𝑅2.
Simplifying gives
1
2 𝑥𝑥1(𝑡𝑡𝑐𝑐) − 𝑥𝑥2(𝑡𝑡𝑐𝑐) 2
+
1
2 𝑦𝑦1(𝑡𝑡𝑐𝑐) − 𝑦𝑦2(𝑡𝑡𝑐𝑐) 2
= 𝑅𝑅2
or
𝑥𝑥1(𝑡𝑡𝑐𝑐) − 𝑥𝑥2(𝑡𝑡𝑐𝑐)
2
+ 𝑦𝑦1(𝑡𝑡𝑐𝑐) − 𝑦𝑦2(𝑡𝑡𝑐𝑐)
2 = 4𝑅𝑅2.
Page 6 of 7
We can express the position of a particle at an arbitrary time if we know its velocity and its position
at some known reference time 𝑡𝑡𝑟𝑟. We will use the current time (the time of the most recent
previous collision) as the reference time. Thus, we will need to update the positions of the two
particles to the current time to perform the calculation. We will denote the updated positions as
𝑥𝑥𝑢𝑢𝑢𝑢1, 𝑦𝑦𝑢𝑢𝑢𝑢1 and 𝑥𝑥𝑢𝑢𝑢𝑢2, 𝑦𝑦𝑢𝑢𝑢𝑢2 . Note that each particle’s position can be updated using the
expressions above; in this case, we update from the last updated time to the current time as 𝑥𝑥(𝑡𝑡𝑟𝑟) =
𝑥𝑥(𝑡𝑡𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙) + 𝑢𝑢 ∗ (𝑡𝑡𝑟𝑟 − 𝑡𝑡𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙); 𝑦𝑦(𝑡𝑡𝑟𝑟) = 𝑦𝑦(𝑡𝑡𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙) + 𝑣𝑣 ∗ (𝑡𝑡𝑟𝑟 − 𝑡𝑡𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙).
Thus, continuing the calculation of the potential collision time, we have:
𝑥𝑥1(𝑡𝑡𝑐𝑐) = 𝑥𝑥1(𝑡𝑡𝑟𝑟) + 𝑢𝑢1 (𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟), 𝑦𝑦1(𝑡𝑡𝑐𝑐) = 𝑦𝑦1(𝑡𝑡𝑟𝑟) + 𝑣𝑣1(𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟),
𝑥𝑥2(𝑡𝑡𝑐𝑐) = 𝑥𝑥2(𝑡𝑡𝑟𝑟) + 𝑢𝑢2 (𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟), 𝑦𝑦2(𝑡𝑡𝑐𝑐) = 𝑦𝑦2(𝑡𝑡𝑟𝑟) + 𝑣𝑣2 (𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟).
Substituting these expressions into the above gives
𝑥𝑥1(𝑡𝑡𝑟𝑟) + 𝑢𝑢1(𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟) − 𝑥𝑥2(𝑡𝑡𝑟𝑟) − 𝑢𝑢2(𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟)
2
+ 𝑦𝑦1(𝑡𝑡𝑟𝑟) + 𝑣𝑣1(𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟) − 𝑦𝑦2(𝑡𝑡𝑟𝑟) − 𝑣𝑣2(𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟)
2
= 4𝑅𝑅2,
which is just a quadratic equation in 𝒕𝒕𝒄𝒄 that can be solved using the quadratic formula. (You may
find it simpler to solve for 𝑡𝑡𝑐𝑐 − 𝑡𝑡𝑟𝑟 and add 𝑡𝑡𝑟𝑟 to the result to obtain 𝑡𝑡𝑐𝑐.) If the discriminant (the value
under the square root) is negative, no interaction is possible between the particles. (For example,
the particles may be moving away from each other and not intersect at some future time.) If the
discriminant is nonnegative, use the earlier time that will occur by choosing the smaller of the two
roots. (The two roots would occur at the early point of tangency—the time we desire—and as a
second point of tangency post-collision, if the collision did not affect the trajectories of the
particles.)
In the event that a collision is not possible, choose a value that will ensure it is never selected as the
next collision.
If a particle-particle collision actually happens, their positions will be updated by setting them to
the values given by (𝑥𝑥1(𝑡𝑡𝑐𝑐), 𝑦𝑦1(𝑡𝑡𝑐𝑐) and 𝑥𝑥2(𝑡𝑡𝑐𝑐), 𝑦𝑦2(𝑡𝑡𝑐𝑐) —that is, let them continue along their
current trajectories as specified by their current velocities until the collision time.
To update the velocity, we assume a perfectly elastic collision, where the kinetic energy remains the
same, and also assume the particles have the same mass. Essentially, we will have the two colliding
particles switch velocities. Thus, after the collision,
𝑢𝑢1(𝑡𝑡𝑐𝑐) = 𝑢𝑢2(𝑡𝑡𝑟𝑟), 𝑣𝑣1(𝑡𝑡𝑐𝑐) = 𝑣𝑣2(𝑡𝑡𝑟𝑟)
and
𝑢𝑢2(𝑡𝑡𝑐𝑐) = 𝑢𝑢1(𝑡𝑡𝑟𝑟), 𝑣𝑣2(𝑡𝑡𝑐𝑐) = 𝑣𝑣1(𝑡𝑡𝑟𝑟).
(Here we assume that no collisions have occurred since 𝑡𝑡𝑟𝑟, which will be the case if you set 𝑡𝑡𝑟𝑟 to be
the time of the most recent previous collision, since the current collision being “processed” will the
next.)
Page 7 of 7
Some verification hints: Note that you can check that the time you predict for a collision is correct.
• For a particle-wall collision with the left or right wall, calculate the new 𝑥𝑥-position of the
particle by adding the product of the elapsed time from the particle’s last update to the
predicted collision time with the particle’s 𝑥𝑥-velocity. The result should have the position
located one particle radius 𝑅𝑅 away from the left or right wall. The same goes for collisions
with the upper and lower walls, just use the 𝑦𝑦-position and 𝑦𝑦-velocity.
• For a particle-particle collision, calculate the new 𝑥𝑥- and 𝑦𝑦-positions of both particles by
evolving them to the collision time as described above for a particle-wall collision
(essentially, let them follow their current trajectory to the collision time). Then use the new
positions of the particles at the time of collision to calculate the distance between the
particles at the time of collision. The distance should be twice the particle radius (2𝑅𝑅).