RGBY Cell Life is a simulation project that models the interactions and dynamics of cells with different colors, sizes, and movement directions on a 2D plane, focusing on the classic problem of collision detection. The project demonstrates the superiority of the Quadtree algorithm over a brute force approach in terms of performance.
Simulation of cell movement and collision on a 2D plane Color transformation of cells based on the surrounding cells within their perception range Implementation of a Quadtree data structure for optimized performance
Cells can move within a boundary and collide with other cells. The hitWall and hitCell functions determine the movement and collision responses of the cells.
After each round of movement, cells scan for neighbors within their perception range and change color based on specific rules.
The project improves upon the Quadtree algorithm for adding nodes and regional searches, significantly reducing the number of cells to be traversed during a search.
To ensure the accuracy and reliability of the RGBY Cell Life simulation, we implement rigorous testing methods. These visualizations help us to quickly identify and address any unexpected behaviors or collisions that may occur.
Visualization of searching algorithm
Visualization of adding algorithm
The images shows the process of adding cells. When the number of cells in one area reaches the capacity, it will be divided into four subareas.
In our practical experiments, we found that the size of the canvas significantly affects the speed of drawing. To control the variables and explore the effects of optimization, we mainly discuss two cases:
- Without using GUI, pure computation.
- Using a specific canvas resolution, here uniformly adopting an equivalent of 600*400, which is 240,000 pixels in resolution.
As for the frame rate, we define it as: (\frac{15}{\text{the time required to complete 15 rounds of computation}}).
We analyzed the relationship between the number of cells and the frame rate. Since drawing also consumes time, the scenario where the code is run without drawing is as follows:
The scenario when drawing is also performed is as follows:
The analysis above shows that the use of the Quadtree algorithm has clearly optimized the program. Additionally, drawing significantly slows down the program's execution. If the time consumed by drawing is on the same order of magnitude as moving and changing colors, theoretically, with 10,000 cells, it would also be possible to achieve the standard of 15 movements per second, that is, 15 frames.
- Open the
Projectfolder in the command line. - Since the real-time frame rate is output in the command line, switch to UTF-8 encoding. Enter in cmd:
CHCP 65001 - Compile all the java files in the
srcfolder:javac -cp lib\algs4.jar -encoding utf-8 src\*.java -d bin - Run
main-QuadTree, specify the mode, and redirect input:- GUI mode: Just redirect input, no extra arguments needed:
java -cp bin;lib\algs4.jar main_QuadTree < sample3.txt - Terminal mode:
java -cp bin;lib\algs4.jar main_QuadTree --terminal < sample3.txt
- GUI mode: Just redirect input, no extra arguments needed:
Demonstration Effects:
GUI Mode:
Terminal Mode:
