CS 2112: Honors Object Oriented Design and Data Structures was taught in Java by Professor Andrew Myers in Fall 2021
The goal of this project was to simulate and display a world of self-controlling artificial life forms (critters) capable of interacting with each other and the environment.
The project was naturally split into three primary steps:
- create a recursive descent parser for the critter language to store the program in an abstract syntax tree
- simulate the critter world using a controller and interpreter for the abstract syntax tree
- build a graphical user interface in JavaFX to display the world and control simulation
In short, critters exist on a regular hexagonal grid. Critters require energy to perform any function, such as attacking, reproducing, and even eating. When critters run out of energy, they die and become food for other critters. If critters accumulate enough energy, they can reproduce. The genome of a critter consists of a program that determines what the critter does in each time step. Programs are written according to a context-free grammar with 16 different production rules. The program includes rules defining what critters should do under certain conditions. When critters reproduce, their genome can be copied and mutated, and over time, this will result in evolution. View the project specifications for more information about the critters, their rule language (grammar), the world, mutations that contribute to evolution, and the requirements for the GUI.
Note: in accordance with Cornell University's Academic Integrity Policy, we cannot show any of our code or explain our solutions to required tasks. Thus, this page will only provide a demonstration of our graphic user interface and highlight some features that we are especially proud of. The capabilities of our project imply we were successful in achieving our goals without revealing the manner in which we did so.
Our GUI was written using JavaFX and was designed with user experience as the utmost priority behind functionality.
As seen above, our GUI used a muted, pastel color scheme and was separated into three sections. The leftmost section contains the controls and details of the simulation, allowing a user to load in a new world, set the simulation speed, toggle features related to the world, view information about the current world state, and pop out a help menu. The middle section displays a view of the simulation as well as two buttons to zoom in and out. Further, the middle view supports scrolling, enabling a user to better navigate large worlds. Finally, the rightmost section has information about a highlighted critter, including its attributes, last rule/action executed, and program (a.k.a. its genome or brain). This section is collapsible and is only shown when a user clicks on a hexagon containing a critter.
In our application, we represent critters as colored circles with an arrow indicating the direction that they are facing. Critters of different species are drawn with different colors, while critters of species with the same name have the same color. Our use of species-specific colors allows the user to clearly see the evolution of the critter species over time, as the dominant colored species may change over time. Food is represented as a yellow-orange hexagon labeled by the amount of food at that location. Rocks and out-of-bound spaces are represented as gray hexagons. Finally, empty spaces in the world are represented as light green hexagons.
In action, a simulation of the critter world running continuously looks like this:
The application runs on a main thread—the JavaFX Application Thread. All updates to the screen and handling of user input had to be done on this thread. If we were not careful, we could ask this thread to do too much, resulting in the application lagging and being unresponsive. The simulation speed indicates how many turns are drawn per second, and it can be set anywhere from 0 all the way up to 1,000,000. Our rendering of the view is hard-capped at 30 frames per second to prevent the application from lagging when trying to draw too many frames. Thus, when the speed was greater than 30, we needed to ensure all the desired turns were run and only up to 30 frames were drawn while maintaining the smoothness of the simulation. An ineffective solution might result in a uneven amount of updates to the view per frame or might cause the screen to lag. Additionally, if the drawing action "fell behind" the real state of the world, the view may try to display an invalid world or one that no longer exists in memory.
We solved these issues with a careful design, using multithreading and synchronization techniques. First, we split up the drawing and simulation onto different threads; all simulation work was done on background threads. We used JavaFX's concurrent package to manage the additional threads, ensuring only one turn was simulated at a time. Second, the view was rendered from a read-only clone of the world so the simulation could be independent of the rendering. Finally, we encountered issues in which sometimes an excess of user inputs, such as dragging the screen or resizing the application, could still cause the rendering to fall behind. We solved this by keeping our view up to date with the simulation rather than drawing every frame. This allowed us to avoid interfering with the simulation and thus reach much higher speeds, which kept the GUI stayed clean and smooth.
We included a sidebar on the right to give more information about a selected critter. The sidebar provides a glimpse into the critter's brain and memory to to aid with writing and testing critter programs.
Due to the nature of the project assignment, we had to create our world simulation before the GUI. It would be nearly impossible to debug the simulation without some form of visual representation, so for that reason, we also created a basic ASCII art representation of the world that was displayed in the console. Because we implemented our code with a MVC (model-view-controller) design pattern in mind, doing this was very easy. Below is a side-by-side comparison of the same critter world, the left being the ASCII art version and the right being our final GUI representation.
Another aspect of the project was to write programs for specific critter behavior. These programs would be parsed into an AST when they were loaded in, and this AST would be interpreted at each time step, determining the action the critter should take at that given time.
One such program we wrote was for a critter that moved in a growing hexagon spiral. Theoretically, in an infinite rock-less world, this critter would eventually reach every possible spot. Below is a demonstration of our critter in action.
Here is another critter, named "Ruthless Ricky", that wanders around the world and attacks other critters of different species. Below is its program followed by a demo of it in a small world with other critters (Ricky is the purple critter).
And finally, we wrote a critter named "Bouncing Borat" that bounces back and forth. Its program is below, along with a demo of two Borats bouncing.
We tested the edge cases of the GUI by clicking all over the place in the GUI and trying actively to break it. Besides testing out the features and edge cases ourselves, we also conducted alpha and beta-testing with friends and family. Using their feedback, we made functionality more user-friendly and flattened the learning curve to use our system. In this way, testing the GUI was relatively straightforward.
Testing that parsing and interpreting were working, however, was significantly more challenging and time-consuming. This is where the bulk of our JUnit testing took place, as we created corner case unit tests programs and asserted that they maintained our abstract syntax tree invariant when parsed. We also used parameterized testing to create many thousand random programs and parse them, checking that each parsed program generated a valid AST.
Beyond manually creating parse trees, we also developed a visualizer to make the AST (abstract syntax tree) testing process easier. Below is the visualization of the AST of "Bouncing Borat" shown in the previous section.
Besides the visualizer, another way we tested the AST was using fault injection that was built into critter simulation logic. As context, when critters reproduce, there is a chance their genome, or program, will mutate. There are various kinds of mutation, but regardless, all of them are valid changes to an AST and should not break our AST invariant. Thus as extra reinforcement to our tests, we parsed in a known valid program, recursively called random mutations, and ensured that at each step of the way, we had a valid AST. Through this extensive testing, we became confident that all of our components were working and that our critter world simulation worked seamlessly.
Special thanks to Kevin Cui for helping to write this.