💾 Archived View for lufte.net › en › post › game-of-life-shenzhen-io captured on 2023-09-28 at 15:43:40. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
Published on 2020-04-24
In this post I'm going to (show off) explain my implementation of Conway's Game of Life inside SHENZHEN I/O[1]. This[2] video shows it in action with an "oscillator"[3].
I implemented the game in a 29x34 matrix following the next approach taken from Wikipedia[4].
If it is desired to save memory, the storage can be reduced to one array plus two line buffers. One line buffer is used to calculate the successor state for a line, then the second line buffer is used to calculate the successor state for the next line. The first buffer is then written to its line and freed to hold the successor state for the third line.
[4] Algorithms to implement the game of life
Given that I will need to store the state of two whole rows of 29 cells each, I am using two 100P-33 RAM modules. The 200P-33 ROM module is used to know how to calculate the number of alive neighbours for each cell, but more on that later. The rest of the board is the screen, a button, and 8 MC6000 modules. I don't think I would've been able to put a single more item in this board, and I have a total of 8 free lines of code left, so this is basically on the limit. I had to work some serious magic to wire the damn thing too. But moving on...
First of all, let's see how the circuit is designed and what role each piece has in the whole thing.
This is the easy part. Before you press the button on top, this MC6000 is the only controller executing code (the others are sleeping), and its only responsibility is to turn on/off the pixels in the screen according to what the user taps. It's not really complex so I'll skip this part.
Once you press the button, the control is transferred to the MC6000 in #2. If this was a program written in your every-day high level language, then this would be the outer loop.
This controller performs one iteration per row of the screen matrix. For each row it will ask #3 to calculate the state of such row in the next generation. Then it will ask #4 to draw the previous row. Finally, it will add 29 (the length of each row) to its offset and repeat the loop. When it reaches the last row (offset 986) it starts over.
There is a special case for the first row where it skips the drawing of the previous row, because there is none. Also, every time it transfers control to other modules, it waits for a response to avoid any concurrency-related issues.
The first module in #3, #3.1, receives the row to work on from #2. It will loop through each cell in the row and ask #3.2 to calculate the state of them in the future generation. When it completes the row, it answers back to #2 to let it know it's finished. It will also skip the loop if offset is 986, because that means it will try to work on a non existent row.
The module at #3.2 takes care of calculating the state of a cell for the future generation based on the number of alive neighbours, and #3.3 does the actual counting. #3.3 makes use of the weird-looking ROM module. That module has 2 purposes:
1. To keep the distance from the current cell to its first (top-left) neighbour, and the distances from each neighbour the the next.
2. To know which special cells don't have neighbours. For example, we should remember that a cell on the left border doesn't have the 3 neighbours to its left.
So, for each cell, #3.3 needs to check the state of its 8 neighbours, and skip the neighbours that don't exist. Let's review how the loop goes for a particular cell:
1. We first read the special cell index from the ROM. The first special cell is 1.
1.1. If we are on cell 1, we should skip the following offset because it's meant to get the state of the top-left neighbour. Cell 1 doesn't have neighbours on its left.
1.2. If we are not on cell 1, then we should move -30 cells to go the the top-left neighbour.
2. If we didn't skip the offset, we check the state of such pixel on the screen and communicate back to #3.2.
The loop then repeats for the top neighbour, the top-right neighbour, the left neighbour, and so on. If the special index is 0 it means that particular neighbour always exists and we don't need to skip.
In the meantime, #3.2 it's counting all the alive neighbours in acc. Well, actually we are counting the neighbours and the current cell, it's easier that way. When #3.3 returns -999 it means it has finished and we can write the next state of this cell on the RAM. If the count is 3 we write 1 (becomes alive), if it's 4 we write -1 (stays the same), and otherwise we write 0 (dies). You'll notice that we don't write directly to the RAM but instead use #5.1. More on that in section 5: The RAM controller.
The last part consists of reading the future state of a given row and render it to the screen. The state, as we saved it in the RAM, it's not "absolute", meaning that we cannot simply take it as it is and write it to the screen. We need to consider the special value -1 which means "leave the pixel in its current state". #4.1 takes care of looping through the row and passing the cell index to #4.2 along with its current state. #4.2 accepts the index and current state, reads the future state of the cell from the RAM (again, not directly but through the RAM controller, and applies the necessary transformations to get the final state and write it to the screen.
The RAM modules are not written or read directly, but I instead put two MC6000 to act as RAM controllers. If you pay attention to the quote from Wikipedia, we need to save the future state of row n to our RAM module 1, then row n+1 to RAM 2, then row n+2 to RAM 1 again, and so on... Similarly, when reading the future states to write them to the screen, we read from RAM 1, then RAM 2, then RAM 1...
The module at #5.1 takes care of that alternation when writing to the RAM modules. It makes sure that we write exactly 29 values to one module and then we switch to the other other. #5.2 does the same thing but for reading. Since we can't sleep until a value is being read on a port, #5.2 asks #4.2 to write something to x1 to wake it up. Besides that, the code for the two modules is quite similar.
This little trick works flawlessly. We don't even need to reset the memory addresses since the pointers automatically cycle when they reach the end.
The Game of Life can be written with a modern language in a matter of minutes. Now, with a bit of imagination and willpower, you can make that task take days if you do it in the proper (or least proper?) environment.
I hope this inspires you to also find extremely complicated ways of writing otherwise pretty simple pieces of software. It's sounds silly, but (now in all seriousness) it's a great and fun way of learning or practicing the fundamentals of computer architecture. The complete source code is here[5] in its original format so you can dump it in your save folder and go crazy. You will also need the image for the touchscreen[6].
Also, if you find the size of the board too limiting, try gtw123's ShenzhenMod[7].
![[6] Touchscreen image](/kennedy.gemi.dev/archive/cached?url=gemini%3a%2f%2flufte.net%2fen%2fpost%2fgame-of-life-shenzhen-io%2f29x34-matrix.png&t=638315126200000000&raw=False){kind=link}