首页 >
> 详细

Data structure and algorithm analysis project

2021

N-Body dynamics simulation under gravitational force and

collision

1. Introduction

In this project, you are going to build a simulation system of rigid spherical objects. You should write a

program to simulate some rigid balls in a vacuum space so that they can move and collide with each

other.

The basic aspects of the problem are as follows:

• All of the objects are rigid body. When they collide with each other, they will not change shape.

They will not break into pieces either.

• Each object has its own size, mass, position and color. You can add as many attributes to the

objects as you wish. The size, mass and color of an object do NOT change. But the position can

change with time.

• Since the objects move their position, they can collide with each other and bounce off with each

other. When this happens, the energy and momentum are preserved.

• There are gravitational forces between objects. This affects the movement of the objects.

• You need to write programs to simulate this process.

The difficulty of this problem can vary a lot with different requirement of the program. In order to simplify

this job, we add the following simplification:

• All of the objects that move in space are spherical balls with uniform density, which means the

centroid of mass of a ball is the the geometry center of the same ball.

• Ignore relativistic effect, quantum effect, air resistence (as the space is vacuum), friction.

• The gravitational force between two objects is denoted as: , where is the gravitational

constant, approximatly . You can use that number in this project. and

are the mass of the two object, respectively. is the distance between the centroid of the two

object.

• The objects are smooth. And they do NOT rotate at the initial state of the simulation. So they will

not rotate at any time.

• The objects are in a two dimensional space. There are four walls around the space. The walls are

also rigid. When the objects collide with the wall, they can bounce off the wall. The mass of the

walls are very small, so the gravitational force between the walls and the objects are ignored. The

walls do not move, so that you can simulate a finite size of a square space where x,y [0, length]

instead of from negative infinity to positive infinity.

R2

Gm m1 2 G

6.67 × 10 Nm /kg −11 2 2 m1

m2 R

∈

• The objects cannot intersect with each other. The objects cannot intersect with the wall.

• All collisions happens instantly.

Your program should display the result using a graphic window. The window should display how the balls

move as time goes.

You should also write some test code to test the correctness of your program as well as the performance.

Note that in real world project, this could be equally important as writing a good algorithm.

2. Project Requirement

The actural work of the project contains many parts:

• Write the system described above. (50 Points)

• Test the accuracy and performance of your system. (10 points)

• Write your report. (10 points)

Write the system described above. First of all, you should make such a system.

• (10 points) Can customize all collision balls.(This means that the program should be able to read

from standard input the initial state of all the balls.)

• (20 points) The program should be able to run and show the movement of the objects with GUI.

• (10 points) To collide and bounce according to the energy and momentum.

• (10 points) Consider the influence of gravity.

Test the accuracy and performance of your system.

• (5 points) Show that your program can produce the correct result.

• (5 points) Show the performance of your program.

Programming mistakes can happen anywhere in such a project. Some mistakes will make your program

produce the wrong result but still be able to run. Try to prove that your program can produce the right

result.

You could also find ways to show that your program runs fast, especially when you have some

performance improvement in your project. Try to run your program with large number of objects instead

of just 10 objects. Maybe you can test the frame rate of your program. You may also find hints in the

reference material at the end of this document.

Write your report.

Include everything you want us to know about your project. Such as the basic structure of your project,

the data structures you have used in the project, the way you optimize the performance, and anything

that makes your project different from others.

Clearly state how to run your program in your report. It's necessary when we test your program.

You may also include some statistics of your program, such as those mentioned in the reference links.

However, we have no requirement on the length of the report. Do NOT try to make it unnecessarily long.

Remember to include group members and student numbers. Also remember to upload your report in

"pdf" format.

Extra test

You may noticed that the above parts add up to 70 points. In the last we will run some test we have

prepared on your program. That is the last 30 points of your project. This can only be down after your

code is submitted. We'll test your program by some cases. By specifying the number of objects and each

object's size, mass, position and color, your program's result should be the same with the standard

answer. The difficulty of each test cases is different. Some examples contains only a few objects, e.g. only

3 or 4 balls in the space. However, some cases contains much more objects than that. Brute force

algorithms may not pass all of them, and you can try to minimize the time complexity of your algorithm.

Each test case has some score, and your score depends on the number of test cases you pass. Your

algorithm has to be able to show us the process through the GUI.

There are restrictions on what you can use and cannot use in this project.

You could use various tools to advance your project, but third party physics engines, game engines are

not allowed. For instance, you could use OpenGL, and OpenCL, but Unity and Unreal are not allowed to

use in the project.

You are allowed to use algs4 library. If you want to use some library and you are not sure about it, you

can ask.

3. Input & Output Standard

Here's a template input file in the block shown as below.

terminal

100

3

0.5 0.5 0 0 0.1 1000000 150 30 10

0.1 0.5 0 0.01 0.03 1 50 50 50

0.8 0.5 0 0.01 0.01 0.1 50 50 50

3

4 2

10 0

14 4

There are 2 choices of line 1st: terminal and gui. terminal means you should not show a window.

Instead, you should print the required information in the terminal. gui means you should show a window.

The number of line 2nd indicates the side length of the square space, all the objects are supposed be in

the square space. For example, the second line contains 100, then the x and y coordinate of everything in

your space is in [0, 100].

The number of line 3rd num is the number of objects.

For each of the next num lines, there are 9 numbers represent the initial state of one object. The 9

numbers are:

• x-coordinate x

• y-coordinate y

• initial velocity in the x direction vx

• initial velocity in the y direction vy

• radius of the square radius

• mass of the square weight

• color of the square r g b.

The unit of x, y and radius is meter. The unit of vx and vy is meter/second. The unit of weight is

kilogram.

The objects are indexed. The first object is the 0th and the second object is the 1st,..., the last object is

num-1.

The number in the next line query indicates the number of querys. For each of the next query lines, there

are 2 numbers. The first is the time t in seconds and the second is index of the object. You should print a

line containing the x, y, vx, vy of the object at the time t seconds after the begining of the simulation.

Sample Input:

terminal

100

1

3 5 1 0 1 100 150 150 150

3

4 0

5 0

6 0

Sample Output:

7 5 1 0

8 5 1 0

9 5 1 0

In the above example, the object's initial location is (3, 5), the velocity is (1, 0). So after 4 seconds, the

location is (7, 5). The speed remains the same in the above example.

Please follows strictly the above requirement. When we test your program (as mentioned in the last

section, 30 points), we will run your program with our input data and compare your result with the

standard output data. If your program does not follow the above restriction and prints something else,

the comparison will fail and it will not be good.

It you have any question about the input output format, you can ask.

Reference

N-Body Simulation:

https://introcs.cs.princeton.edu/java/assignments/nbody.html

N-Body Simulation, with Barnes-Hut tree:

https://introcs.cs.princeton.edu/java/assignments/barnes-hut.html

Molecular Dynamics Simulation of Hard Sphere:

https://algs4.cs.princeton.edu/61event

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23