代写CSE 6010、代做C++语言编程

日期：2023-11-07 09:13

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𝑅𝑅).