# CS203B-DSAAb Project Report
## 团队成员
**顾晨宇 12011123**
**何心怡 11911234**
**许路珂 12011105**
## 总体框架结构
本项目通过模拟细胞运动以及变色，设计终端输入计算，图形化显示窗口，以及随机生成细胞三个模块，再加入优化算法，实现了对于大量细胞下在稳定15帧内的细胞运动，变换以及碰撞，并通过系统输出结果。
```
./src
├── Main.java
├── listener
│ ├── KeyHandler.java
│ └── MouseHandler.java
├── model
│ ├── Cell.java
│ ├── CellsTree.java
│ ├── Entity.java
│ ├── QuadTree.java
│ └── Query.java
├── test.java
└── view
├── Pannel.java
└── StartFrame.java
```
## 运行方式
配套的文件中分别有`run.bat`,`run.sh`两个文件可供运行
或者可以自定义运行以下命令：
其中
`MODE`为`--terminal`or`--GUI`or`--random`
`InputPath`为输入数据地址
`OutputPath`为输出数据地址
* Windows：
```bash=
javac -cp src;lib\algs4.jar src\*.java -d bin
java -cp bin;lib\algs4.jar Main ${MODE} < ${InputPath} > ${OutputPath}
```
* Linux：
```bash=
javac -cp src:lib/algs4.jar src/*.java -d bin
java -cp bin:lib/algs4.jar Main ${MODE} < ${InputPath} > ${OutputPath}
```
## 详细实现部分
* [GUI设计](#gui设计)
* [碰撞检测](#碰撞检测)
* [感知检测](#感知检测)
* [输入输出处理](#输入输出数据处理)
* [优化算法](#优化算法)
* [测试结果以及误差分析](#测试结果以及误差分析)
* [Bonus](#bonus)
## GUI设计
> 利用java自带的swing图形化界面工具实现对于细胞的绘画及刷新
在`Pannel.java`类中，创建新的线程用于处理数据，完成没帧刷新
### FPS控制
通过计算每帧所用的`nanotime`，加上`timer`以及`delta`的控制，动态控制刷新率
```java=
double drawInterval = 1E9 / FPS; // calculate draw interval
double delta = 0;
long lastTime = System.nanoTime();
long currentTime;
long timer = 0;
int drawCount = 0;
while (thread != null){
currentTime = System.nanoTime();
// accumulating nanotimes until up to 1/15s
delta += (currentTime -lastTime)/drawInterval;
timer += (currentTime - lastTime);
lastTime = currentTime;
if (delta >= 1){
// do the update and repaint
delta--;
//delta will be zero when repainted over
drawCount++;
}
if (timer >= 1E9){
realFPS = drawCount; // output realtime FPS
drawCount = 0;
timer = 0;
}
}
}
```
### 细胞绘制
在`CellsTree.java`中储存了所有需要刷新的cell，并通过传入`pannel`，调用每个cell的draw方法实现绘画
**需要注意的是对于每个细胞的更新重画，即repaint函数，是在这一帧所有的细胞`update`之后进行调用，重新显示所有细胞的颜色**
***所以之后所说的改变颜色，改变位置等变化都是对于cell自身变量的变化，不会实时显示，而会在所有细胞依次更新完后显示在GUI上（==每一帧重画一次==）***
```java=
public void draw(Graphics2D g2){
switch (color){
case RED:
g2.setColor(java.awt.Color.RED);
break;
case GREEN:
g2.setColor(java.awt.Color.GREEN);
break;
case BLUE:
g2.setColor(java.awt.Color.BLUE);
break;
case YELLOW:
g2.setColor(java.awt.Color.YELLOW);
break;
default:
System.out.println("Wrong color");
}
g2.fillOval((int) (x-radius), (int) (y-radius), (int) radius*2, (int) radius*2);
}
```
## 碰撞检测
### 细胞前进方向区域内细胞探测
>由于每个细胞在1/15s后可能完全穿过某些细胞，所以不能仅在1/15s后检测细胞是否与其他细胞相撞，所以对每个细胞进行碰撞检测时应当获得离它最近的细胞。这里我们的解决方式是检测所有与这个细胞前区域相交的细胞并返回一个包含这些细胞的List，遍历这个List计算与这些细胞相切时的需要对这个细胞做的修正距离并取最小的修正距离进行修正。
>
>如上图，位方便计算我们将探测区域分割为了蓝色矩形区域与红色圆形区域分别探测（若重叠区域检测到了重复cell不影响后续最小修正值的计算），问题简化为圆与矩形的相交判断和圆与圆的相交判断。
>圆与矩形相交检测参考[circle-rectangle-conflit](https://blog.csdn.net/weixin_45683908/article/details/111462799?spm=1001.2101.3001.6650.11&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-11-111462799-blog-107674368.pc_relevant_antiscanv2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-11-111462799-blog-107674368.pc_relevant_antiscanv2&utm_relevant_index=13)
前进区域探测具体实现代码
```java=
case RED:
newY=newY+speed;
for (int i = 0; i < returnObjects.size(); i++) {
if(ID!=returnObjects.get(i).ID){
if(Cell.RectangleCircleCol(this.x-this.radius,this.y,newX+this.radius,newY, returnObjects.get(i))){
CoID.add(returnObjects.get(i));
}
else{
double distance = Math.sqrt(Math.pow((newX- returnObjects.get(i).x), 2)+Math.pow((newY- returnObjects.get(i).y),2));
if (distance < (this.radius+ returnObjects.get(i).radius)){
CoID.add(returnObjects.get(i));
}
}
}
}
break;
```
### 碰撞检测细节
>若是细胞前进区域内没有其他细胞，则检测细胞是否撞墙，若撞墙，直接将细胞位置置于与墙相切位置，没有撞墙则按原定速度向前移动。若前进区域内存在细胞，遍历计算使其相切的最小修正值，修正值公式按照几何推导（两次勾股定理），并在前进方向上加上修正值。
修正部分具体代码实现
```java=
case RED:
distanceSquareInitial=Math.pow(this.x-CoidList.get(0).x,2)+Math.pow(this.y-CoidList.get(0).y,2);
AxisDistanceSquareInitial=Math.pow(Math.abs(this.x-CoidList.get(0).x),2);
Fixdistance=Math.sqrt(distanceSquareInitial-AxisDistanceSquareInitial)-Math.sqrt(Math.pow(this.radius+CoidList.get(0).radius,2)-AxisDistanceSquareInitial);
for (int i = 0; i < CoidList.size(); i++) {
double distanceSquare=Math.pow(this.x-CoidList.get(i).x,2)+Math.pow(this.y-CoidList.get(i).y,2);
double xDistanceSquare=Math.pow(Math.abs(this.x-CoidList.get(i).x),2);
double newFixdistance=Math.sqrt(distanceSquare-xDistanceSquare)-Math.sqrt(Math.pow(this.radius+CoidList.get(i).radius,2)-xDistanceSquare);
if(Fixdistance>newFixdistance){
Fixdistance=newFixdistance;
}
}
this.y=this.y+Fixdistance;
return;
```
## 感知检测
> 通过检测细胞的感知范围内所存在的细胞个数以及比例，动态改变细胞的颜色
### 感知范围存在的细胞计算
> 更具要求我们可以得知，一个细胞是否存在于另一个另一个细胞的感知范围实际上可以转换为以这个cell的大小的圆形是否与目标cell以感知范围为半边长的正方形是否重叠的问题，即圆形于正方形的碰撞问题
可参照[circle-rectangle-collision-detection-intersection](https://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection)
具体代码实现
```java=
static boolean intersects(Cell c, Cell percepRect) {
double circleDistance_x = abs(c.x - (percepRect.x));
double circleDistance_y = abs(c.y - (percepRect.y));
if (circleDistance_x > (percepRect.perceptionRange + c.radius)) { return false; }
if (circleDistance_y > (percepRect.perceptionRange + c.radius)) { return false; }
if (circleDistance_x <= percepRect.perceptionRange) { return true; }
if (circleDistance_y <= percepRect.perceptionRange) { return true; }
double cornerDistance_sq = pow(circleDistance_x - percepRect.x,2) +
pow(circleDistance_y - percepRect.y, 2);
return (cornerDistance_sq <= sqrt(2)*percepRect.perceptionRange+c.radius);
}
```
### 具体变色细节
> 在每一个cell对象中都有一个change的成员变量，记载的是在这一帧它是否需要变色（不需要则为null），在对于这个细胞运动完后会调用它自身的change函数，修改这个细胞的颜色，并且刷新change变量
具体代码如下
```java=
public void change(){
if (change != null){
this.color = change;
change = null;
}
}
```
## 输入输出数据处理
* 数据读入和数据输出
>对于GUI和terminal两个模式，均需要从终端读取输入文件：
由main方法的传参 `args[0]` 判断为GUI或者terminal模式后，由命令行"< 指定文件.txt"和 `Scanner input = new Scanner(System.in)` 重定向输入；之后，由命令行"> 指定文件.txt" 重定向输出。
random模式与以上两个模式会使用不同的`pannel`构造器和不同的`CellsTree`构造器；以上两个模式将继续用Scanner类作传参，以下为代码实现：
```java=
public CellsTree(Pannel pannel, Scanner input) {
this.pannel = pannel;
generateListCells(input, pannel);
generatePercpList();
cellTree = new QuadTree(0, new Rectangle(0, 0, pannel.screenWidth, pannel.screenHeight));
percpTree = new QuadTree(0, new Rectangle(0, 0, pannel.screenWidth, pannel.screenHeight));
insertAllCell();
insertAllPercep();
}
```
输出数据以读到的全部querylist为基础，换算后变成对应的帧数，输出totalcount帧数下对应的 `ArrayList<Query>` ，在run（）方法内每帧运算和显示的同时，输出chasingID的坐标值。
```java=
public ArrayList<Query> querylistofcurrentshow(int totalcount){
for (Query query : this.querylist) {
if (query.getStoptime()*15 >= (totalcount) && query.getStoptime()*15 < totalcount+1) {
this.currentquerylist.add(query);
}
}
return this.currentquerylist;
}
```
* 调整界面宽高
> 用以下方法保证屏幕显示宽高正常合适：
> 在输入宽大于高时，以宽为标准调整到800像素；
> 在输入高大于宽时，以高为标准调整到600像素；
两种模式下的Pannel构造起如下：
Pannel类的`scalingratio`变量由除法计算得到，并将同步用于调整Cell的速度、坐标和半径。
```java=
// instructor for not random mode (GUI+terminal)
public Pannel(int width, int height,boolean isdefault){
if(width >= height){
this.screenWidth = 800;
this.screenHeight = 800*height/width;
this.scalingratio = (double) 800/width;
}else{
this.screenHeight = 600;
this.screenWidth = 600*width/height;
this.scalingratio = (double)600/height;
}
this.setPreferredSize(new Dimension(screenWidth, screenHeight));
this.setBackground(Color.BLACK);
this.setDoubleBuffered(true);
this.addKeyListener(keyHandler);
this.setFocusable(true);
if(isdefault){
this.isDefaultMode = true;
}else this.isDefaultMode = false;
}
```
此为速度调整方法：
```java=
public void setSpeed(double scalingratio) {
this.speed *= scalingratio;
}
```
此为Cell的x,y,r和速度调整：
```java=
public void generateListCells(Scanner input, Pannel pannel) {
int n = input.nextInt();
pannel.setCellnum(n);
Double scalingratio = pannel.getScalingratio();
int i = 0;
while (i < n) {
double xi = input.nextDouble() * scalingratio;
double yi = input.nextDouble() * scalingratio;
double ri = input.nextDouble() * scalingratio;
double percept_range_i = input.nextDouble() * scalingratio;
String color_i = input.next();
Cell.Color colori = Cell.Color.getValue(color_i);
Cell singleCell = new Cell(pannel, ri, xi, yi, colori, percept_range_i);
singleCell.setSpeed(scalingratio);
cellArrayList.add(singleCell);
i++;
}
}
```
## 优化算法
在处理碰撞检测算法以及感知检测算法的时候，为了算出与每个细胞碰撞or感知的其他细胞，采用brutal的算法（如下），采用双重循环，可以计算并返回与之碰撞的其他细胞
```pseudocode
for each cell_A in all_cells{
for each cell_B in all_cells{
if (cell_A != cell_B)
perform colllision OR perception detection Algorithm;
}
}
```
但是，这种算法在数据量增大的同时会对于计算的时间消耗呈N^2^的指数级增长，导致刷新率非常低,采用brutal算法的sample3的结果如下，（可以看到实时FPS只有4）：
### 四叉树构建
> 参照[Use Quadtrees to Detect Likely Collisions in 2D Space](https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374)
通过构建四叉树，设定每个节点内的最大单位数，将所有细胞插入四叉树，倘若细胞数大于在这个节点的最大单位数，四叉树就会分裂，将2D界面平均分成4块，并将在父节点中的单位重新插入子节点，如果单位与边界线有交叠，则存在父节点中，以此类推。
四叉树中的`retrieve`方法，递归返回这个单位所在的子节点的所有单位，如果此单位于边界线交叠，则返回所有相交的子节点。
大致代码结构如下：
```java=
public class QuadTree {
/* MAX_OBJECTS = maximum child number
MAX_LEVELS = maximum depth of tree
Level = the current node(0 is the father node of 4 children)
bounds = corresponding 2D area of the current node
nodes = includes 4 nodes
*/
private final int MAX_OBJECTS = 100;
private final int MAX_LEVELS = 10;
private int level;
private ArrayList<Entity> objects;
private Rectangle bounds;
private QuadTree[] nodes;
/*
* Constructor
*/
public QuadTree(int pLevel, Rectangle pBounds)
/*
* Clears the quadtree
*/
public void clear()；
/*
* Splits the node into 4 subnodes
*/
private void split()；
/*
* Determine which node the object belongs to.
* -1 means object cannot completely fit
* within a child node and is part
* of the parent node
*/
private int getIndex(Entity entity)；
/*
* Insert the object into the quadtree. If the node
* exceeds the capacity, it will split and add all
* objects to their corresponding nodes.
*/
public void insert(Entity entity)；
/*
* Return all objects that could collide with the given object
*/
public ArrayList retrieve(ArrayList returnObjects, Entity entity)；
/*
* Return all objects in the Quadtree
*/
public ArrayList returnAllObj()；
/*
* Return the number of all objects in the Quadtree
*/
public int returnAllObjNum()；
}
```
### 四叉树应用
> 因此对于以上问题，我们采用了四叉树的数据结构，通过将细胞传入四叉树，四叉树会返回可能与之产生交集的部分细胞，可以大大的减少循环次数，思路如下：
```pseudocode
for each cell_A in all_cells{
returnCells=cell_A.retrieve();
//potential cells may intersect with CellA
for each cell_B in returnCells{
if (cell_A != cell_B)
perform colllision OR perception detection Algorithm;
}
}
```
经过优化后的Sample3输出（如下），可以轻松稳定15帧：
## 测试结果以及误差分析
* **Sample1\2\3在GUI模式下运行结果**
**Sample1:**
> 结果与sample1_output相同；FPS（每秒帧数）为稳定15帧
**Sample2：**
> 结果与sample2_output相同；FPS（每秒帧数）为稳定15帧
**Sample3：**
> 结果与sample3_output的差距在小数点后10位左右开始，几乎相同
* **误差分析**
数据上：
由于储存时间信息的数据类型使用的是double，在指向每个帧数的判断(FPS=15)：
```pseudocode
double drawInterval = 1E9 / FPS;
```
```pseudocode
(currentTime - lastTime) / drawInterval>=1`
```
上有计算误差，可以导致细小差别；
显示上：
>1.当一个Cell坐标行走为1/15时，每帧在GUI里对应行走（没有scale的情况下）也应为1/15，但1/15个pixel无法显示；只有15个1/15才可以看出Cell的pixel的移动；任何介于整数pixel之间的移动将无法被看到；
2.当Cell半径很小的时候去产生碰撞，计算相切的位置即使准确，由于pixel分辨率不是很高，在roundoff后可能在显示上依然看起来“不相切”。
以下为使用鼠标点击显示`Cell.toString()` 下的细胞x,y,color,radius值；前两行对应图中黄色细胞和它右下角红色细胞，此时为相切状态，但显示“不相切”；
输出后进行test.java中运算，发现误差很小，在小数点后13位左右；所以从计算角度，程序没有太大计算误差问题；
## Bonus
### KeyHandler 和 MouseHandler
在`listener`模块中，我们新加入了两个类，分别是`KeyHandler.java` 和 `MouseHandler.java`。
这两个类用于分别处理在程序运行过程中的键盘事件和鼠标事件。
**现有的用法罗列：**
* 在任意模式的程序运行状态下，只要按下键盘上的ESC键，程序会进入暂停状态，冻结所有细胞的状态，并将其停留在这一帧的画面上
* ==（仅在`random`模式中生效）==，鼠标点击屏幕上方的某一个细胞，系统会自动输出这个细胞的详细坐标以及颜色（格式与Query相一致）
### Random Mode
> 在原本的`GUImode`和`terminal`mode之外，我们新加了一个`random`mode
>
在这一个模式下，用户可以定义生成细胞的数量和所有细胞的感知范围（在此模式下，默认所有细胞的感知范围一致），系统会自动生成细胞，并进行更新。
在随机模式下，为了使生成时间不至于过长，我们特定规定了，最多生成的细胞数为10000个。输入的number如果多于10000个则只能生成10000个。
同时，在随机模式下，鼠标事件是被允许的，用户可以点击生成的细胞，系统会输出这个细胞的信息。
**随机生成细胞的参数**
* 屏幕的大小固定为800*600
* 细胞的位置为pannel中的均匀分布
* 细胞的半径大小为0-10之间的均匀分布
* 每个细胞在生成前会先判断是否会产生碰撞，并进行筛选
Sign in with Wallet
Connect another wallet