Implementing Conway's Game of Life on the NES
2020-03-27 - [49] 1:7
To the sadness of myself and many other professionals and hobbyists in STEM fields, Mathematician John Horton Conway passed away on April 11th, 2020. One of the concepts he was most known for creating was Conway's Game of Life.
What is Conway's Game of Life?
Before I Explain What Conway's Game of Life Is...
John Conway was a brilliant Mathematician who has worked in quite a few areas of Mathematics other than just being the "guy who created Conway's Game of Life." In numerous interviews, John Conway described his relationship with Conway's Game of Life by saying "I hate the Game of Life." Why did I decide to implement Conway's Game of Life on the NES then? The easy answer is because Conway's Game of Life is computationally simple to program and is something I have been meaning to implement on the NES for a few years now.
Rules of Conway's Game of Life
If you are reading this blog post, I would assume you are likely familiar with Conway's Game of Life. With that said, I will explain the rules anyways.
Initial Game State
First, you will need a grid. It can be any size you want. Here is a 10x10 grid as an example to show what I mean.
___________________
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|Each cell in the grid can be either dead or alive. Any combination of dead and alive cells are allowed on this grid. The grid above happens to be filled with only dead cells, but a grid with only alive cells, deliberately picked cells, or a random distribution of dead and alive cells are also perfectly valid initial game states. Below is one such possible initial game state, which is just a random assortment of dead and alive cells.
___________________
|#|#|_|_|_|_|#|_|_|_|
|#|#|#|_|#|#|#|#|_|#|
|#|#|#|_|_|_|_|#|#|_|
|_|#|_|_|#|#|#|#|#|#|
|#|_|#|_|_|_|_|#|_|#|
|#|_|_|_|#|#|_|#|#|_|
|#|#|_|#|#|_|_|_|_|_|
|_|#|_|#|_|_|#|#|_|#|
|_|_|#|#|_|_|#|_|#|#|
|_|#|#|#|_|#|_|_|#|_|To determine what the next turn of Conway's Game of Life will be, you will need to check every cell on the grid and figure out how many neighbors it has that are currently alive.
Detecting Neighbors
Each cell in the game grid has neighbors. Those neighbors are the 8 cells surrounding the cell you are looking at. The cell you are looking at can be either dead or alive and each neighbor can also individually be dead or alive.
Here is a 3x3 grid showing all of the neighbors of an alive cell
_____
|1|2|3|
|8|#|4|
|7|6|5|And here is a 3x3 grid showing all of the neighbors of a dead cell
_____
|1|2|3|
|8|_|4|
|7|6|5|Cell Is Currently Alive
To determine if a cell that is currently alive will be alive in the next turn, figure out if it has EXACTLY 2 or 3 living neighbors.
If a cell is currently alive and has EXACTLY 2 living neighbors, it will stay alive
_____
|#|#|_|
|_|#|_| -> Middle cell will stay alive
|_|_|_|If a cell is currently alive and has EXACTLY 3 living neighbors, it will stay alive
_____
|#|#|#|
|_|#|_| -> Middle cell will stay alive
|_|_|_|FEWER THAN 2 living neighbors will result in the cell being dead next turn due to isolation.
If a cell is currently alive and has FEWER THAN 2 living neighbors, it will die of isolation
_____
|#|_|_|
|_|#|_| -> Middle cell will die
|_|_|_|MORE THAN 3 living neighbors will result in the cell being dead next turn due to overcrowding.
If a cell is currently alive and has MORE THAN 3 living neighbors, it will die of overcrowding
_____
|#|_|#|
|#|#|_| -> Middle cell will die
|#|#|_|Cell Is Currently Dead
A cell that is currently dead will become alive next turn if there are EXACTLY 3 living neighbors. Think of this as the cell being "born."
If a cell is currently dead and has EXACTLY 3 living neighbors, it will become alive (born)
_____
|#|#|_|
|_|_|_| -> Middle cell will become alive
|_|#|_|FEWER THAN 3 living neighbors will result in a dead cell remaining dead next turn.
If a cell is currently dead and has FEWER THAN 3 living neighbors, it will stay dead
_____
|#|#|_|
|_|_|_| -> Middle cell will stay dead
|_|_|_|MORE THAN 3 living neighbors will result in a dead cell remaining dead next turn.
If a cell is currently dead and has MORE THAN 3 living neighbors, it will stay dead
_____
|#|#|_|
|_|_|#| -> Middle cell will stay dead
|#|_|#|Conway's Game of Life Rules in a Nutshell
On each turn:
- 1. If a cell is alive, it will only stay alive next turn if it has EXACTLY 2 or 3 living neighbors.
- 2. If a cell is dead, it will only become alive next turn if it currently has EXACTLY 3 living neighbors.
- 3. Any other situation results in the cell being dead next turn.
- 4. Repeat these steps for every single cell in the grid.
It is easily possible to tweak these rules, but a cell being alive if and only if EXACTLY 2 or 3 living neighbors when the cell is alive or EXACTLY 3 living neighbors when the cell is dead are the rules John Conway set, likely because of some fun mathematical properties, so that's what I'm using.
Conway's Game of Life on the NES
[HTTPS] Game of Life on NES - 6502 Assembly - Youtube Video
So this video shows my implementation of Conway's Game of Life running on an NES emulator.
Looks pretty slow...
So you noticed... Yeah, this is running at 100% speed of an NTSC (North American or Japanese) NES/Famicom. This is the fastest it will go on hardware. There is actually a reason for that...
Earlier in this post, I mentioned that you have to figure out how many living neighbors a cell has FOR EACH CELL. In this case, there are 40x40 cells, or 1600 cells altogether. The bigger the grid, the more cells you have to analyze before you know the next turn.
The NES has a CPU clock rate of about 1.79MHz (1789773Hz), or about 1.79 million CPU clock ticks per second. Because of that, I only have about 1100 CPU clock ticks per second to analyze each individual cell of the 1600 grid cells. Many NES CPU instructions take 3-6 CPU clock ticks on their own to execute, and that's just for a single machine code instruction. With an average of 4-ish CPU clock ticks per instruction, and having to analyze 8 neighbors for all 1600 grid cells each turn, there are only about 34-ish CPU instructions per second that can be used to analyze each neighbor per cell. That's unfortunately just not enough CPU clock ticks, so it takes over a second to calculate each turn...
There are certainly ways I can shave off a few CPU clock ticks per cell analysis. I'm not currently sure if I'm planning on making this ROM more efficient in the future. We'll see though.
A Few Technical Details
(Warning: Math ahead. Only a little bit though. Arithmetic and exponents are discussed below, so fair warning.)
So an annoying couple of quirks about the NES... The way the graphics chip (PPU, or Picture Processing Unit) is set up, you can't just draw single pixels onto the screen wherever I want. You actually need to define a set of 8x8 pixel "background tiles." There is a hard limit to how many background tiles you can use as well... 64. Okay, so I have 64 8x8 pixel tiles to work with. Why did I decide to stick with a 40x40 grid? Why didn't I decide to go with more grid cells?
Well, the way I set up the grid cells in the background tiles of this ROM is to have 3 pixel by 3 pixel cells seperated by a 1 pixel wide border/separator. That means I have a 2x2 grid per 8x8 pixel background tile. Why 2x2? Turns out I only need 16 background tiles to handle every 2x2 grid situation. (0=Dead, 1=Alive) 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. The next biggest grid size per 8x8 pixel background tile I "might" be able to do is a 3x3 grid, which would allow for a 60x60 grid, but would also require 512 background tiles, which is over the 64 tile limit, rather than 16 background tiles to represent every possibility for 2x2 (I get 16 possibilities for the 2x2 based cell background tiles because 2x2=4, so there are 4 Yes/No possibilities, which is 2 to the power of 4, which is 16. The same rule applies for 3x3 cell background tiles. 3x3=9 and 9 Yes/No possibilities is 2 to the power of 9, which is 512).
The NES only has 2048 bytes (16384 bits) of memory available by default to games (we're going to ignore cartridge RAM, like what was used in The Legend of Zelda to store save data). 256 bytes of that are used for sprite positions and attributes and another 256 bytes are used for what is called "the stack", so I now have 512 bytes fewer to work with, lowering what I can use to 1536 bytes of memory. The current turn of the grid and the next turn of the grid need to be stored somewhere in that 1536 bytes...
As I stated earlier, a cell can be either dead or alive. 1 or 0. Binary. That means I only need a single bit to say whether a particular cell is dead or alive. Great! With 1600 grid cells, I need 1600 bits to store the current turn. 1600 bits / 8 bits per byte = 200 bytes, so I need 200 bytes to store the current turn and 200 more bytes to store the next turn. Thankfully, that leaves me with 1136 bytes left, so RAM is not an extra bottle neck like CPU speed turned out to be.
This project has lead to me hitting some walls in NES development that I really haven't had to deal with before, specifically CPU speed. The NES really is a slow computer compared to anything even remotely modern. I welcome and encourage other NES homebrew developers to develop their own implementation of Conway's Game of Life on the NES or other retro graming systems. Make a more efficient implementation! Make an implementation that has a grid size of larger than 40x40! Be sure to let me know when you have an implementation of Conway's Game of Life publicly available or other work John Conway has produced. Let us celebrate the life of a brilliant human being.
You will be missed, Professor John Horton Conway. Rest in peace, and may your work continue to spark the creativity of passionate Mathematicians, whether amature, professional, hobbyists who only occasionally dabble in mathematics, or anything in between or beyond.
Extra Bits
(My apologies for stealing the phrase Extra Bits from Computerphile. As the sister channel of Numberphile, I feel the phrase was specifically appropriate for this blog post.)
It was actually a few days ago, as I started writing this blog post, when I first learned that John Conway was the inventor of the "Doomsday" algorithm my calendar calculating library datecalc used to calculate the day of the week of positive years (on or after 1 AD) in the Gregorian Calendar.
[HTTPS] Doomsday algorithm Wikipedia page
[HTTPS] datecalc GitHub Repository
If you have not seen John Conway talk about things he has worked on or found interest in, linked below is a Youtube Playlist by Numberphile.
[HTTPS] John Conway on Numberphile Youtube Playlist
Interested in playing around with this implementation of Conway's Game of Life?
This NES ROM will work on an actual NES or Famicom console if you burn this game properly to an NROM-256 board, the same exact board type Super Mario Bros used (the isolated copy of Super Mario Bros, not the one with Track & Field and/or Duck Hunt included). It should also run on essentially any NES emulator Super Mario Bros can run on.