The goal of this project was to simulate a world of critters with the capability to move, eat, reproduce, evolve, and die. To that end, we had several goal milestones for this project:
- Recursive descent parser and interpreter for a simple critter language (context-free grammar with 16 production rules)
- Model and controller for critter world simulation
- Graphic user interface to visually represent the model
We split up the major components into different packages, and team members worked individually on them in order to modularize our program and ensure loose coupling. Additionally, we created a rigorous test suite of parameterized, random, blackbox, and glassbox testing to check the validity of all modules. In total, this project took around 12,000 lines of code in Java and was completed over the span of a month and a half.
For more detailed information about the project specifications, see this document.
Note: in accordance with Cornell University's Academic Integrity Policy, we cannot show any of our code (upon request, source code can be shared with individual recruiters, however). Still, we would like to provide a demonstration of our graphic user interface and highlight some features that we are especially proud of.
Our GUI was implemented in JavaFX and was designed with user experience as the utmost priority behind functionality.
Going into more detail regarding the world view, critters are represented as colored circles with an arrow indicating the direction they are facing. Critters of different species are visualized with different colors (determined through a hash table, mapping species name to RGB color). 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 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, however, so at high speeds (i.e. >100) there is potential for the calculation of updated world objects to take longer than the 1/30 of a second, causing issues with the GUI. One such problem would be lag if the simulation controller became backlogged with world state updates, and drawing was only done after all the updates had been completed. Another potential issue would be invalid world renderings if the simulator tried to calculate steps from a no-longer valid world state and then tried to draw it.
Ultimately, we didn't have to deal with these issues as we solved them during design, using multithreading and synchronization techniques. First, we split up the drawing and simulation onto different threads (a rendering thread and background worker threads) to improve efficiency. Second, we made the simulator only do calculations on a clone of the current world state and pass back a read-only version to the view controller at specified turns (predetermined through the speed). In this way, even as a user navigated the world (through scrolling or zooming) at high simulation speed, the GUI stayed clean and smooth.
ASCII Art vs GUI
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 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.
___________
Example Critters
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, on an infinite rock-less world, this critter would eventually reach every possible spot. Below is our program for the critter, affectionally named "Spiral Sam", and a demonstration of it 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 was 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 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 an 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.