155 lines
25 KiB
Markdown
155 lines
25 KiB
Markdown
## Overview
|
||
|
||
I will be implementing Conway’s Game of Life, a cellular automaton and zero-player game with the following rules:
|
||
|
||
The game takes place on a two-dimensional orthogonal grid, extending infinitely in all four directions. On a given grid cell, there are two possible states - ‘alive’ and ‘dead’. The grid has a starting condition, the only interaction a human has with the system. The state of the grid on a given turn informs the state on the next turn like so:
|
||
|
||
* A live cell with fewer than two live neighbours (orthogonally or diagonally) becomes dead (starvation).
|
||
* A live cell with greater than three live neighbours becomes dead (overpopulation).
|
||
* A dead cell with exactly three live neighbours becomes alive (reproduction).
|
||
* Otherwise, the state of the cell remains unchanged.
|
||
* From these rules, more complex systems can be constructed. Game of Life is Turing-complete, meaning it is possible to construct a computer that can solve any computable problem (including simulating Game of Life) given enough time and memory.
|
||
|
||
While it is possible to carry out the rules by hand, this problem lends itself well to being calculated computationally due to its repetitive nature. It becomes very tedious and time-consuming for a human to simulate the game for more complex systems, and computers can calculate Life rules quickly and accurately.
|
||
|
||
I intend to write the program in Rust, due to its speed, advanced standard library, and object-oriented capabilities.
|
||
|
||
## Features
|
||
|
||
The application should have the following features
|
||
|
||
* The program should be able to display cells on a grid, providing UI buttons to step forwards, backwards, and run the game on a timestep. This is a necessary feature of interacting with Life.
|
||
* The program should allow the user to change cells at a given point, and clear the grid, which are necessary features to create custom patterns.
|
||
* The program should be able to open files from the internet. This allows users to open complex patterns without editing them in themself.
|
||
* The program should be able to save patterns into a standard file format compatible with other Life programs. This allows users to retain patterns without leaving the program open.
|
||
* The program should provide a set of example presets, allowing an easy onboarding process for users unfamiliar with Life.
|
||
* The program should be reasonably performant, which is necessary for a comfortable user experience.
|
||
|
||
I have chosen not to provide some features provided by more complex Life apps, such as variable timesteps, stepping multiple frames at once, and advanced board editing features, like those found in programs like Golly and LifeViewer. This not only saves program complexity but also allows for a simple UI consistent with other GNOME applications, which tend to sacrifice on advanced features in favour of a consistent and uncomplicated UI. Overall, this places the program inbetween the complexity of simple emulators like playgameoflife.com, and the aformentioned advanced emulators.
|
||
|
||
## Stakeholders
|
||
|
||
My first stakeholder is my uncle, who I will be asking for feedback with both the functionality and UX of the program. He is a competent programmer, and as a result will be able to compile it rather than be provided a package, and is able to use Linux, meaning I don't need to support other platforms, cutting down on complexity. He is not part of the Life hobbyist community and does not need advanced features used for very complex patterns.
|
||
|
||
My second stakeholder is a person seeking to implement their own application that implements the Life logic through my logic code, but does not need my UI. They will be able to compile the program, require good documentation for the logic code's functions, and require the logic code to be shipped seperately from the UI code. For example, the developer may want to develop an app with a different UI library, such as Qt, or may want to develop an alternative to my UI for Windows or macOS. For this reason, the logic code needs to be completely agnostic to both UI toolkit and operating system, including for interactions with the OS such as threading and file access. They may require more complex features, so the logic code should not be opinionated on things like timestep or editing features. Ideally I would ensure that it is ISA-independent and works on 32-bit machines, but I lack the hardware with which to test this.
|
||
|
||
My third stakeholder is a Linux user who uses the GNOME desktop environment and has limited technical skills. They will likely be uncomfortable installing the Rust toolchain and compiling from source, and will expect an easy-to-use package such as a Flatpak. They will expect the application to be consistent with the rest of their (GNOME) desktop, and as such I will have to use GNOME technologies and patterns (GTK4, libadwaita, Flatpak, HIG, etc). I should reference other GNOME applications and mimic their UI for consistency.
|
||
|
||
## Limitations
|
||
|
||
One of the main concerns with how this project will be implemented is the stepping backwards feature. It is not possible to determine the previous state of a grid from the current state - multiple states may result in the same state upon the next turn, so information is lost. I can see three possible solutions:
|
||
|
||
1. Store an entire history of the board (potentially as a linked list from end to beginning), which expands with each step. This would allow for fast retrieval of previous states (stepping back one turn having a time complexity of O(1)), but the program’s memory usage would grow with each step, until the program would eventually run out of memory.
|
||
2. Only store the state of the two most recent turns. This allows a user to step between the current and last state for comparison, but not further than that. This is very lightweight and as I already intended to store the state with a double-buffer, is very easy to implement, but is limited in use, as it can only go back one.
|
||
3. The program keeps track of the initial state of the game, and to return to a previous state, simply steps through the program again. This is space-efficient (only storing the first and current state), but will take longer to execute depending on how many turns the user has taken, a time complexity of O(n) where the state to be reverted to is the nth state since the initial state.
|
||
|
||
I ultimately opted for the third option. Not only is it simply to implement, but was not ultimately very slow except for very high iteration counts. A major limitation of this is that it is very wasteful for stepping back multiple turns - if the developer wanted to add a "step back by n turns" function to their own application, they may need to fork my library.
|
||
|
||
A second limitation is that my program does not optimise for stepping multiple turns at once. This makes sense for my UI, and a developer seeking a library that optimises for that should turn to significantly more complex libraries implementing algorithms such as HashLife, which is fast but considerably too complex to implement for an NEA.
|
||
|
||
Rust's safety features also made it difficult to implement some features that improve quality of life for developers interacting with the library. For example, it was functionally impossible to implement the `Index` trait for a game or board, due to Rust's strict ownership rules, meaning a developer cannot use easy indexing syntax (`board[2][1]`) to interact with a board. This is not a huge problem, but is inconvenient.
|
||
|
||
## Success Criteria
|
||
|
||
* The user should be able to open the program to an empty grid.
|
||
* The user should be able to edit the grid by clicking on cells to change state.
|
||
* The user should be able to clear the board through a UI button.
|
||
* The user should be able to step forwards, backwards, and "run", stepping the board forwards repeatedly on a fixed timestep. The step should not noticeably slow down as the program runs, and should match Life's rules.
|
||
* The program should be performant and run on low-spec computers, as well as not having any limit to grid size likely to be reached in a normal usecase.
|
||
* The program should be written in GTK4, run at least on Linux, and follow conventions for GNOME apps such as adding less frequently used actions to the menu in the top-right of the screen, have an about popup, and use client-side decorations (see the GNOME HIG).
|
||
* The program should be stable and not crash or leak memory. If an action fails, the user should be notified through the toasts standard on GNOME apps, rather than exit or fail silently.
|
||
* The program should be able to open files with at least one commonly used Life file format.
|
||
* The program should be able to save files with at least one commonly used Life file format that it can open.
|
||
* The UI and logic code should be cleanly separated, and the logic code should be downloadable as a separate package for use in Rust applications in the same way as it is used in my own application
|
||
* The logic code should be cross-platform
|
||
* The logic code should be well-documented and handle errors gracefully in a way idiomatic to Rust
|
||
* The application should be packaged as a Flatpak.
|
||
|
||
## Implementation
|
||
|
||
The program will have a `Game` class to represent the grid’s state and handle methods to change it. The grid will be implemented as a hashset using a tuple of two integers as keys. This means that the only information stored is the indices of live cells. For other cells, there is no value. This allows for two things - a sparse matrix - with no space taken up for dead cells - and an infinite matrix, allowing the game to stretch on in any dimension.
|
||
|
||
To find out the next value of a cell, the neighbouring indices are checked for whether they exist in the hashset, and the entry for the cell’s indices is created, removed, or left accordingly. To avoid checking over large areas of empty space, only hashset entries and their neighbours are checked. The program will step through one at a time, which leaves out some more optimised algorithms but is appropriate for the program's UI, which will not have multiple-step functionality.
|
||
|
||
The `Game` class will hold a second grid, advancing the game with a double buffer - the second grid’s next state is based on the state of the current grid, and then they are swapped. This allows going to the previous state by loading the second grid, but another strategy is needed to go further back than that (see limitations). The class will implement methods for advancing, reverting, and indexing. This is separated from UI logic, which I will implement in GTK. The UI could retrieve all of the elements it needs through requesting a slice of the overall matrix, from a top-left coordinate to a bottom-right coordinate.
|
||
|
||
## Beginning
|
||
|
||
My initial problem was the issue of storing a grid of infinite size in a program. While the size is infinite, the game will only ever have a finite number of live cells, making a hashset an ideal data structure for representing this. A hashset is a hashmap that does not store any value associated with each key, only whether an entry for a given key exists. I can use a tuple of integers as the hashset, giving it a grid size with 2^128 cells. My user will not be reaching the end of this, I think. (Rust has a bigint library, but I wasn't convinced that coordinates of this size were necessary, as no user would realistically reach the edge).
|
||
|
||
The `Game` struct contains a few fields. `primary_board` contains a `HashSet` representing the current state of the board. `secondary_board` contains a `HashSet` representing the prior state. They are swapped out for one another in a double buffer. `initial_state` is another `HashSet` representing the earliest tracked change to the board. This is done to implement reverting the board state.
|
||
|
||
When advancing to the next turn, each eligable cell has its neighbours counted up and applied to the game's rules. It doesn't make sense to check every cell (which is impossible on an infinite board), but thankfully only live cells and their neighbours have the capacity to change state. A "check set" is created, containing each live cell on the board and its neighbours. The set is then collected into a Vector and is split into chunks, with one chunk per core on the machine. A thread is then spawned for each chunk, which is tasked with determining the next state of each cell in its chunk. Once all threads have been completed, the secondary board is cleared and is extended with the values of each thread's results. The primary and secondary boards are then swapped.
|
||
|
||
The board implements Rust's `Iterator` trait (interface), allowing for lazily evaluated iteration over the game at each turn. While this is not used in the UI code, it can be useful for anyone seeking to use the library in their own project.
|
||
|
||
## Reverting the board
|
||
|
||
For reverting the board, the game keeps track of its `initial_state` and a `count` - the nuber of turns since the initial state. To revert a turn, the board reverts to the initial state and advances `count - 1` times. This is not performant at high `count`s, and cannot track before the last manual change (like the player clicking on a tile to flip its state manually), but is relatively simple to implement.
|
||
|
||
## GUI
|
||
|
||
The game logic is implemented as a Rust library to be included in other projects. For this reason, it makes sense to implement the GUI in Rust as well. Writing the UI in GTK is important for the third stakeholder, and is make easier here as my application only has to work on Linux. Unfortunately, Rust's default GTK bindings are quite difficult for me to use, as Rust's OOP system is quite different from GObjects, the cross-langauge OOP system that GTK uses. For example, GObjects has both inheritence and polymorphism, whereas Rust does not, opting for extensive use of "traits" (which are analogous to Java interfaces). This makes the GTK bindings cumbersome and full of unintuitive macros. This had stumped me for a while before I discovered Relm4, a Rust library for creating UIs that used gtk-rs as a backend but provided a much more intuitive API.
|
||
|
||
## Relm4
|
||
|
||
Relm4 is based on "models", representations of application state, their representations in GTK, and the messages passed between them. The main model for the Game of Life GUI has several messages that it can receive from UI elements - advance the board, revert the board, flip at a coordinate, etc.
|
||
|
||
Although GTK is not web-based, it uses CSS to style itself. The GNOME project provides the libadwaita library and stylesheets to enforce a consistent and clean look across their apps, which I opted to use. The program opens onto a single window, containing a headerbar with controls for the grid and a grid in the center of the screen.
|
||
|
||
The grid uses another useful concept that Relm4 has - factories. A factory is a collection of elements that each contain the data for a UI element. Adding an item to the collection (in my case, an item being a struct containing a coordinate and whether a cell is live) is sufficient to add it to the grid.
|
||
|
||
Two buttons on the left and right of the top bar send advance and revert messages to the app model, while the middle "play" button is a component with its own model, which, upon being clicked, toggles the "running" boolean through the toggle message. When the play button model receives a message, it checks if it is running, and if it is, spawns a thread that sends the advance message to the main model, waits 1 second, then sends a "pass" message to its own model (think of it as a form of recursion). The pass message contains the id of the thread it is called from. The model also contains the ID of the currently running thread, which is compared and does not spawn a thread if the ID does not match. This is to avoid a scenario where the user presses the play button twice in half a second, which ends up spawning two instances of the threads recursing at once. Now, only the most recently spawned will be allowed to continue.
|
||
|
||
To add cells to the factory, the app model requests a "view" from the game of life library - a list of all live cells between a top-left and bottom-right coordinate. The model then iterates through all coordinates between these two, adds it with the live value set to false if it is not in the view, and to true if it is. The model performs this synchronisation every time it receives a message.
|
||
|
||
## File access
|
||
|
||
There are several file formats that board states in game of life can be encoded in. The most popular are "plaintext" and "RLE". RLE uses a form of run-length encoding, which I opted not to use to avoid unnecessary complexity. The other, plaintext, sees each line in the file represent a row on the board, with "." representing a dead cell and "O" representing a live cell. An older format, Life 1.05, uses "\*" as a live cell. My game of life library supports both, and can generate a new game from them. This allows me to load pretty much whatever pattern I want from the internet and test it, which is helpful.
|
||
|
||
Relm4 provides a widget to allow file selection using the OS's native UI, giving me a path to feed into my reader function. This file selection also works on Flatpaks' sandboxing. Rather than giving the program universal file access, it has to open a dialog controlled by the OS for the user to select a file that they consent to the program accessing.
|
||
|
||
## Performance and optimisation
|
||
|
||
Implementing file loading allowed me to conduct more thorough benchmarks. Particularly, I was interested in how the performance of my system would manage with patterns whose live cell counts dramatically increase over time. Space fillers are a type of pattern that expand to fill the grid as quickly as possible. I downloaded a plaintext file for a spacefiller and tried to benchmark how quickly it would slow down. Sadly, the slowdowns were quite quick, with performance dropping off after 60 turns or so. It didn't reach a speed lower than the UI advanced it either way, but I still found it unsatisfactory. Reaching 150 turns took about 5.8 seconds, and I wanted to lower this.
|
||
|
||
Looking at the `advance_board` function, there were a few places I could see room for improvement. Rather than use a double buffer, with secondary board being drained and filled with the new values, I simplified it by removing the secondary board and simply initialising a new board each update, which lowered memory requirements. I experimented with changing the form of each thread's results from a `HashSet` to a vector, but this had no major effect. The system finds out how many threads it should split itself into by calling the `available_parallelism` function, which queries the system for a core count. This was being done every advance in my current implementation, which the documentation for the function warns against. I moved the call into the board's new function and stored it in the game struct itself, which improved it by about 0.2 seconds. Removing unnecessary prints in my code vastly improved performance. Still, only around 5.2 seconds for 150 iterations on the spacefiller.
|
||
|
||
I looked for other, more efficient algorithms for life and one that stood out to me was HashLife. HashLife is notable firstly because it's much faster, but also because it does not calculate the board turn-by-turn. It is able to look ahead and calculate several turns at once, which allows for a variety of optimisations. Sadly, the ability to traverse multiple turns does not make sense for my program, and the algorithm is also notoriously complex to implement, and would require me to implement several data structures I'm unfamiliar with, as well as my own garbage collector.
|
||
|
||
I had also been reccomended using SIMD for further improvements, but I was very unfamiliar with SIMD concepts and wasn't confident in implementing it. I explored simplifying the boolean logic for the neighbour counts, but I found it to have no benefit for performance and decrease readability. I also tried a parallel iteration library called rayon, which allowed me to abstract away the process of chunking and mapping each hashset, which was faster, but I wanted to try to do the game logic with as few libraries as possible.
|
||
|
||
The Rust Performance Book's section of hashing details that the default hasher used in `HashMap`s and `HashSet`s is relatively safe, but slow. However, it is possible to provide a custom hasher. The book details the rustc-hash crate (a crate is a Rust library), which provides a custom hasher that is considerably faster at the cost of a higher collision rate. Applying this to my board gave a moderate speedup (about 0.6s) with no apparent logic errors. It also mentions the nohash_hasher crate, which is able to use integers as keys verbatim, without hashing. I wanted to see if I could do something similar with my key, a tuple of `isize`s (an isize is a signed integer with size dependent on the architecture). Sadly, no implementation I could provide was faster than rustc-hash, so I didn't pursue it further, but it did give me some useful knowledge of Rust's `Hash` and `Hasher` traits (interfaces).
|
||
|
||
## Testing
|
||
|
||
The library has a number of integration tests. These ensure that the rules of Life are followed in the program's simulation. These tests typically involve taking established patterns like the R-Pentomino, advancing them a couple turns, and checking them against a result I took from another simulator. The Linux UI automated testing scene is not well-established, and the application has no tests for ITs UI. Rust's extensive use of static analysis allows many things that would otherwise have been tested for to be caught as compile-time, such as type errors, memory unsafety, and race conditions (Rust is famously impossible to get memory unsafety without an explicit unsafe keyword).
|
||
|
||
## Packaging
|
||
|
||
So far, if a user wanted to install the application, they would have to install the Rust toolchain (compiler, package manager, etc), install the necessary GTK development libraries, and compile my program from source, a long and performance-intensive process. This may be acceptable for my first stakeholder, and is considerably easier for the Rust developer (they would already have the toolchain, do not require GTK dependencies, and can compile the library quicker than the full application), but it is not realistic for a casual Linux user with limited technical skills like my third stakeholder.
|
||
|
||
Fortunately, Relm4 provides a template for building applications into Flatpaks. After integrating the necessary build files and installing runtimes, it becomes possible to build a full Flatpak for my application. Not only does this make my application very easy to install (Flatpak installation is well-documented on almost all Linux systems), but it also provides users a degree of security assurance - for example, Flatpaks do not have file access by default outside of a file picker that the user controls and the application cannot tamper with. This was not a design goal, but is nice to have.
|
||
|
||
## Documentation
|
||
|
||
Rust has a built-in documentation system, in which code and appropriate comments are compiled into an HTML page containing documentation for any given type, module, or library. This allows me to document any given function by writing a comment directly above it. My code is well-commented and documentation extends across all types and functions that are exposed in the library's API.
|
||
|
||
## Software/hardware requirements
|
||
|
||
As this is a GTK app, it is only runnable on a Linux system, or through WSL2, which needs some technical knowledge to set up. This is acceptable, as my stakeholder is confident with using Linux. Installing from source requires Rust and several GTK development libraries, which are readily available through most Linux package managers, while Flatpaks make installation significantly easier. Flatpaks can also be installed through Crostini, making the application available on ChromeOS (with some elbow grease). The application is not available for macOS, Android, and iOS. It is untested for Linux phones but should run (though presently the user would not be able to scroll).
|
||
|
||
It is a lightweight app, with low hardware requirements. The speed at which the board advances is slow enough that the cost of computing the next term is negligable. It will struggle on very low-spec systems due to the requirements of GTK, but works well on my budget Chromebook.
|
||
|
||
## Success analysis
|
||
|
||
Overall, almost all of the success criteria have been met, with the exception of providing presets. This is relatively low-impact, as a user can easily find examples of patterns online and open them in the app.
|
||
|
||
The program's interface is idiomatic for GNOME apps, and any GNOME user should be able to navigate it without surprises. The application is available as a Flatpak, and the logic code is easy to compile and cross-platform. The logic library is both well-documented and idiomatic to a Rust library.
|
||
|
||
I have a few further goals with which I intend to extend the program after the NEA is complete:
|
||
* I will replace some of my own code with libraries, such as having rayon implement multithreading for me
|
||
* I will ensure that my program works well with standard Linux screen readers.
|
||
* I will ensure that the program works on mobile Linux devices
|
||
* I will modify the logic library to allow for custom rulesets.
|