CPSC312-2024-GameOfLife

Authors: Shibo Ai, Kevin Huang

What is the problem?

The Game of Life is a simulation of evolution created by a mathematician in 1970. It is an world of infinite size composed of cells that can either be dead or alive. Each cell interacts with its neighbours.

The rules of how the world changes over time are simple:
1. Any live cell with fewer than two live neighbors dies
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies
4. Any dead cell with exactly three live neighbors becomes a live cell. (source)

Functional programming would be good for this task because it allows us to use lazy evaluation (can make world that is infinitely large), do calculations, has immutability (since states of cells and their transitions matter a lot) and concurrency.

What is the something extra?

The world is infinitely large. Achieved by leveraging Haskell's infinite list lazy evaluation.

Variations of life: What music will game of life produce if the world map becomes a piano keyboard, and each world is a variation? The music follows the following rules:

The y-axis from 0 to 14 represents all the white keys in the fifth and sixth octaves on the piano.
In the interval 0-d where d is a fixed positive value, each x=k where 0 <= k <= d represents a note.
The program traverses the x interval 0-d (positive integer mentioned above). At each x=k where 0 <= k <= d, find the coordinates of all living cells on the axis x=k. Then filter those with y values between 0 and 14 (including 0 and 14). These live cells represent the chord consisting of that single note. if there are no live cells, they represent empty beats (but empty beats before and after the variation will be removed). In this way, all the chords in the interval 0-d form a variation. When the world advances, next variation will be produced, and user can choose to play the next variation.

Gloss GUI: To address the issue of entering coordinates line by line into the terminal, we developed a solution that will help in user experience. This allows for easier interaction with the simulation. The following features were included:

The ability to evolve the world one step at a time, pausing at the next step
Automatically evolve the world by a specified amount of frames per second
Randomly populate the world of alive cells by specified diameter
Ability to increase and decrease the diameter to be able to generate more or less cells
Ability to zoom in and out to view the entire process of evolution
Click an alive cell to unalive and vice versa to facilitate precise cell placement
Paint mode to paint your favorite picture using a mouse (placing cells one at a time was too tedious)
Ability to play music of the current grid
Ability to restart the grid in case of a mistake
A detailed help menu that displays relevant key binds to the user

What did we learn from doing this?

GUI Development:

We first coded the GUI using the regular Gloss play function but later down the line, the music player introduced IO operations which were incompatible with our first approach. We learned that Haskell's pure functions cannot combine with IO's directly and must adapt our existing code to use monads to use the System Random functions. Surprisingly, Gloss had an interface for games in IO, which led to us using playIO.
Each pixel is 1x1 in width and height of the screen. It was a challenge at first where the canvas was empty since size wasn't taken into account. It is important to scale your picture components so they are of desired scale. To integrate the backend code, which had coordinates in single pixels, we had to keep track of the size in the GUI to enlarge and shrink pixels. The coordinates designed in the backend were perfect fit for the GUI since in both ends, the origin was dead center and so no extra calculations were needed.
Given a backend with clear documentation, the GUI was compartmentalized into several parts that the world state needed in order to function properly. Mostly Booleans were used (e.g. Paint, Auto) to indicate when an event should happen when the user initiates an action.

Game Development:

Uses Haskell's lazy evaluation. implements an infinite world using an infinite list.
The simulation's logic is purely functional. Thanks to the "zero player" nature of the Game of Life, after getting the world's initial status from the user, we were able to implement all the following computations in a purely functional way with zero side effects.

Music Part:

We learnt how the music notes and chords could be manipulated in a functional way elegantly. The MIDI music library we use, called Euterpea, has implemented its special operator to manipulate its representation of Music, the Music class. Thanks to this design, we were able to treat music as any other common data type, and use functions like folder to combine a list of notes into a chord, just like adding all the elements in a list. This really expanded our view on what the functional programming could do.

What did not quite work:

The program is known to freeze when music is played, as Euterpea, the music library we used, plays music and stalls until it is done playing to continue its execution. This resulted in our GUI not responding and returning to normal after a few seconds. This indicates that our program is single threaded and this is one of the downsides of implementing a simulation that updates every frame and can't stall.
The program also lags when the world is too large. With a large list of alive cells, it must be traversed to update itself for the next world. We put a hard cap of a diameter of 100, which is around 40000 cells and also stalls for a few seconds. This performance may be limited by the specific computer but also shows that Haskell's immutable lists may be expensive to update every frame.

Some final analysis, and thoughts,

I would like to start from why we do the project Game of Life. We initially choose this project because Game of Life (later referred as game) is very “functional”. For any game input, there is only one possible after some fixed number of iterations, which is just like Haskell function with no side effects. In our original plan, the only non-functional part is to generate the original world (either from user input or random). After this, we could harvest performance benefit from the game’s functional nature (like Haskell could automatically leverage the concurrency). To verify our hypothesis, I benchmarked the game: 2000 alive cells in a 100*100 world, it took over 13 seconds to compute only 10 iterations and it used over 1635 MB of memory (yes, over 1G!) on my reference machine (6-core Intel Xeon E5 1650v2, 32G 1866 MHz DDR3 ECC memory, MacOS 12). This totally deviates from our expectations. Although we don’t have enough time and skills to determine the root cause of this performance issue, we made some educated guesses.

The scaring memory usage might be caused by repetitive list operations. Because lists are immutable in Haskell, each modification will generate an entire new list. In our implementation, we largely used large lists to represent the state of the world, and they are often processed in a list decomposition recursion.
There might be no concurrency leveraged. This idea was immerged from our experience with Haskell graphics framework gloss. We noticed that when the program plays music (a function does not return until the music finishes), the whole GUI freezes. This indicate that the whole GUI runs on the same thread with the rest of the program. For such a wildly used Haskell GUI not implementing multi-threading, this could indicate leveraging concurrency is much harder than we originally anticipated.

Instead of gaining the performance benefit, one big advantage I found using Haskell is, the program is less bug prone. Haskell’s syntax forced me to breakdown the problem, and instead of thinking how to solve it, I could focus more on the definition of the problem. There are many times, after I define a problem in Haskell, I found that problem has already been solved.

Work division

Shibo: Implemented game without GUI, music

Kevin: GUI

Links to code etc.

https://github.com/AiShibo/GameOfLife