Saturday, September 14, 2013

Conway's Game Of Life on a Commodore 64.

I remember when I learned for the 1st time about Conway's Game Of Life – a Cellular Automata model in a Polish equivalent of Popular Mechanics for youth: “Mlody Technik” (Young Technician) in 1984. I have been at the time a technical high school freshman. I immediately recognized how great a simulation platform a computer would be for this model. Unfortunately I did not have a computer or even an access to one. I spent long hours simulating colonies on a piece of a graph paper.
In the early 2000-s when I was learning C#/.NET I did a C# implementation as an exercise. The GUI is a bit awkward, but simulation is fairly fast and can emulate quite big arrays of the cells. My son loves to play with this program even though I never had time to refine it or get rid of few bugs. It has edit/load/save abilities, user can set, unset cells with a mouse click, zoom in and out and enable grid lines. My 9-year old has no problem with that, so I guess everybody could get used to it.

Modern GUI C# implementation of Game of Life.
C# Game of Life - program setup.
C# Game of Life - with elevated zoom and grid lines enabled for easy editing.
In the meantime I made numerous console based ports in C language for DOS and Linux. It is always fun. Now, while this is quite easy with modern computers and programming languages, it is not the same on some old slow CPU and limited memory platform using low level machine language or slow interpreted language like BASIC for example.
Recently I realized that I have never did a C-64 port. Being a Commodore aficionado, I found this a great oversight, so I got to work.
My first tries using BASIC and Power-C for C-64 and C-128 were disappointing. My algorithm was very slow. I realize that with some clever coding I could do a fast simulation in higher level language. Perhaps one day I will try to invent some clever GOL simulation algorithm in C which will be fast enough for practical application. Even though I like to work directly on a retro hardware, (emulator does not emulate look and feel), this time I wanted to try the cross-platform IDE called C64 Studio (I love the demo helicopter game that comes with it). I installed it, made sure it points to my installation of Vice emulator and got to work. I researched some GOL implementations for CBM platform on the internet and have been impressed by this great piece of 6502/C64 code by 'Ruk':

Although Ruk's goal was minimum size and maximum speed, so the program is not really packed with features, it is still very impressive what you can do with this ancient by today's standard hardware. He does some pretty clever encoding of the colony so the calculating of the next generation is real fast and code is extremely compact. It fits in less than 256 bytes with full screen emulation/presentation and sound.
I did not match Ruk's implementation of GOL speed and tiny size, however these were not my goals (well, maybe the speed was, but I lack the skill at the moment). Instead my program is packed with practical features and makes up for slower speed and (much) bigger code size with numerous functions like: built-in demo colonies, random colony generator, colony full screen screen editor and disk I/O. Although program takes 16 blocks on a disk, the colony files are only one block in size (binary encoded, 40*25/8 = 125 bytes is all it takes to encode 1000-cell colony) and save and load pretty fast. The simulation speed is also satisfactory with about 2 ¼ generations per second.

Conway's Game Of Life – the rules.

The world of Game of Life (GOL) consists of a 2-dimensional array of cells, which can have a dot (live cell) or be empty. The next generation of dots is calculated by counting the live neighbors on adjacent cells. E.g: please refer to illustration below, where the central cell is live (has a dot) and has 8 adjacent cells, which contain a total of 3 live neighbors.

A cell with adjacent cells.
The rules of death and life are as follows:

- Death -
  • Each dot that has 1 or no live neighbors dies out of loneliness.
  • Each dot that has 4 or more live neighbors, dies out of the overcrowding.
- Life -
  • On each empty cell that has exactly 3 live neighbors, a new dot is born.
  • Each dot that has 2 or 3 live neighbors, remains in its live status.


Computer algorithm.

On today's fast hardware, the directly implemented algorithm causes no speed concerns. The cells can be encoded in bit fields or directly in a BOOLEAN or character array. The cells of the arrays are iterated sequentially and the neighbors number is calculated for each cell separately and the next generation of the colony can be generated to the separate memory buffer and then presented in whatever form to the user.
However working with the 1 MHz 8-bit CPU with limited RAM is different. There are memory and performance considerations. We want to avoid too much of the data copying operations (internal colony representation vs. screen presentation, copying data between buffers etc.) and really huge arrays. In my implementation I decided to compute the next generation directly in the text screen memory (the world is a 1000 cells array, 25 rows 40 columns each). To avoid artifacts on the screen while the next generation is calculated, double buffering technique could be used. However I chose a technique to encode the screen codes for dying and born cells of the next generation to be as closely represented on the screen to the live and empty cells of a current generation as possible. For example the dot (live cell) is presented with screen code $51, which is a big filled oval dot. The dying cell is represented with code $57, which is a very similar semi-graphical character to the one represented by code $51, except it just has a small not filled with color hole inside (donut like) while remaining the same size. Therefore when the next generation calculating algorithm is marking the cells for dying, their screen presentation do not change significantly. Just a little hole appears briefly in the middle of each dying cell, which has a nice side effect for the presentation function anyway. Even better screen code match was found for a new-born cell. Note that it is not desired to have new born dots appear on the screen before the whole array is calculated. The screen code $60 is represented on the screen as empty space, just as the empty cell is represented by code $20, also resulting with an empty space on the screen. For the computer algorithm these are 2 different codes (desirable feature). However for the user, there is no change on the screen when the algorithm marks cells where a new dot is born in the next generation. Thanks to that I avoided necessity of performing double buffering and switching screen memory banks. After next generation is calculated, quick routine converts the died and new born screen codes to the empty and dot codes (fully filled) and the next generation is again calculated in the endless loop. The end-user presentation in effect is quite pleasant and appears as a seamless generation after generation display.

Apparently the assembly routine calculating the next generation of the colony was the most challenging for me. The performance of the simulation depends on it the most. I used direct GOL rules implementation with few tricks and optimization techniques. The resulting binary image is under 4 kB in size. Considering the amount of features packed, I consider this a moderate achievement. Thanks to the speed of the machine language, I achieved satisfactory performance without affecting the readability of the code or necessity to use advanced colony encoding techniques. Although it is my desire in the future to do just that and make the code blazing fast, for now I will settle for 2 generations per second speed as I need some more 6502 assembly language practice to achieve better results in code.
Zero page indexing addressing mode and various counters are used by the algorithm to cycle through screen memory cells from left upper corner to right-lower corner of the screen (YIND – column counter is used to iterate through cells in a row and then ZPG vector is increased by 40 and YIND zeroed at the beginning of each next row).

Here is the routine which is the heart of the GOL simulation algorithm:

; calculate the next generation    
; Theory of operation:
; The screen memory is scanned from start to end.
; Each row is iterated with pointer ZPGA1 and index Y.
; Addressing mode (ZPGA1),Y is used. Register Y is
; reloaded with column counter yind, which is incremented
; accordingly at the end of the loop,
; then ZPGA1 is increased by 40 at the start of the next row.
; The number of neighbors is calculated for each cell.
; Depending on the # of neighbors, the cell is encoded
; to either die (DCELL), be born (BCELL) or remain unchanged.
; After this procedure, the 'disp' routine should be called
; to convert died cells to empty spaces and born cells (BCELL)
; to live cells (LCELL).
next
    ldx #0
    stx xind  ; initialize row index
    stx yind  ; initialize column index
    stx nbct  ; initialize neighbor cells counter
    lda #<MSCR  ; initialize ZPG address buffer
    sta ZPGA1   ; and current cell address counter
    sta smct
    lda #>MSCR
    sta ZPGA1+1
    sta smct+1
nl0 ; left neighbor check    
    ldy yind
    beq nl1         ; skip left neighbor check if column=0
    dey             ; decrement ZPGA1 pointer (left side neighbor)
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl000
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl00        ; jump to nl00
nl000    
    inc nbct        ; increment neighbors count
nl00    
    ldy yind
nl1 ; right neighbor check
    cpy #MAXCOL     ; if cell at the far right side
    beq nl2         ; then skip right neighbor check
    iny             ; increment ZPGA1 pointer (right side neighbor)
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl111
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl2        ; jump to nl2
nl111    
    inc nbct        ; increment neighbors count
nl2 ; north neighbors check
    lda xind
    beq nl4         ; skip north neighbors check if row=0
    jsr sb40zpga1   ; subtract 40 from ZPGA1 (north neighbor)
    ldy yind
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl222
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl22        ; jump to nl22
nl222    
    inc nbct        ; increment neighbors count
nl22  ; north-west (NW) neighbor check
    ldy yind
    beq nl3         ; skip NW neighbor check if column=0
    dey             ; decrement ZPGA1 pointer (NW side neighbor)
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl2220
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl220       ; jump to nl220
nl2220    
    inc nbct        ; increment neighbors count
nl220
    iny             ; return ZPGA1 pointer to north neighbor's cell
nl3
    cpy #MAXCOL     ; if cell at the far right side
    beq nl33        ; then skip the right neighbor check
    iny             ; increment ZPGA1 (right side neighbor)
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl333
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl33        ; jump to nl33
nl333    
    inc nbct        ; increment neighbors count
nl33
    jsr rldsm2zpga1 ; reload smct to ZPGA1
nl4 ; south neighbor check
    lda xind
    cmp #MAXROW     ; if row at maximum,
    beq nl6         ; skip south neighbors check
    jsr add40zpga1  ; add 40 to ZPGA1 (now ZPGA1+Y -> south neighbor's cell)
    ldy yind
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl444
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl44        ; jump to nl44
nl444    
    inc nbct        ; increment neighbors count
nl44  ; south-west (SW) neighbor check
    ldy yind
    beq nl5         ; skip SW neighbor check if column=0
    dey             ; decrement ZPGA1 (SW side neighbor)
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl4440
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl440       ; jump to nl440
nl4440    
    inc nbct        ; increment neighbors count
nl440
    iny             ; return ZPGA1 pointer to south neighbor's cell
nl5
    cpy #MAXCOL     ; if cell at the far right side
    beq nl6         ; then skip the right neighbor check
    iny             ; increment ZPGA1 (SE side neighbor)
    lda (ZPGA1),y   ; load cell's value
    cmp #LCELL      ; if not a live cell
    beq nl55
    cmp #DCELL      ; or not a 'died' cell (in this iteration)
    bne nl6         ; jump to nl6
nl55    
    inc nbct        ; increment neighbors count    
nl6
    jsr rldsm2zpga1 ; reload smct to ZPGA1 (restore address of the row)
    lda yind        ; store old column# before incrementing
    sta yold        ; for further calculations
    inc yind        ; increment column#
    lda yind
    cmp #(MAXCOL+1)
    bne nl66
    lda #0
    sta yind
    jsr add40smct   ; increment smct (point to the next row of cells)
    inc xind        ; increment row#
nl66  ; now mark the cells to live/die/be born
    ldy yold
    lda (ZPGA1),y   ; load current cell
    cmp #LCELL      ; check if a live one
    beq nl666
    cmp #DCELL
    bne nl7         ; not a live one, jump to nl7
nl666 ; live cell, determine its fate
    lda nbct        ; load neighbors counter
    cmp #0          ; if nbct<2, cell dies
    beq nldie
    cmp #1
    beq nldie
    cmp #2
    beq nlnext
    cmp #3          ; if nbct==3, cell does not change
    beq nlnext      ; if nbct>3, cell dies
nldie
    lda #DCELL
    ldy yold
    sta (ZPGA1),y   ; update cell with 'died' code
    clc
    bcc nlnext      ; prepare for next cell
nl7 ; not a live cell, determine its fate
    lda nbct        ; load neighbors counter
    cmp #3          ; only if nbct==3, a new one is born
    bne nlnext
    lda #BCELL
    ldy yold
    sta (ZPGA1),y   ; update cell with 'born' status.
nlnext
    lda xind        ; check if the end
    cmp #(MAXROW+1)
    beq nlend       ; yes, jump to nlend
    jsr rldsm2zpga1 ; reload smct to ZPGA1
    lda #0          ; initialize neighbors counter
    sta nbct
    jmp nl0         ; do the next cell
nlend

    rts

Before saving, colony's editor screen is encoded into binary form (so each byte holds information about 8 cells) into buffer with this routine:

; convert screen (editor's format) into binary format
; store in colb buffer
encodeed2colb
    lda #<MSCR
    sta ZPGA1
    lda #>MSCR
    sta ZPGA1+1
    lda #0
    sta gpct        ; gpct - encoded byte
    sta gpct+1      ; index to colb buffer (encoded colony)
    lda #8
    sta gpbyt       ; gpbyt - bit counter
ee2cloop000
    ldy #0
    lda (ZPGA1),y   ; load byte from screen memory
    cmp #'*'        ; is it live cell?
    bne ee2cloop002 ; no, branch to ee2cloop002
    lda gpct        ; load encoded byte to Acc
    ldx gpbyt       ; load bit counter to X
    ora encodearr,x ; set the bit in Acc masked by encodearr,X
    sta gpct        ; store updated encoded byte
ee2cloop002    
    dec gpbyt       ; decrement bit counter
    lda gpbyt
    beq ee2cloop001 ; if byte counter is 0, branch to ee2cloop001
ee2cloop000a    
    jsr SystemZone.inczpga1 ; increment ZPG1 (screen memory)
    lda ZPGA1       ; check if end of screen memory
    cmp #<MESCR
    bne ee2cloop000
    lda ZPGA1+1
    cmp #>MESCR
    beq ee2cfinished
    clc
    bcc ee2cloop000 ; do next bit
ee2cloop001         ; single byte encoding finished
    ldx gpct+1      ; load encoded colony buffer index
    lda gpct        ; load encoded byte
    sta colb,x      ; store byte in the encoded colony buffer
    inc gpct+1      ; increment index to encoded colony buffer
    lda #8          ; reload bit counter
    sta gpbyt
    lda #0          ; reset encoded byte
    sta gpct
    clc
    bcc ee2cloop000a  ; do the next bit
ee2cfinished

    rts

Here is how the encoded binary format colony look like, this example is a built in demo colony:

; shooter colony, binary encoded    
dcshootenc    

    !byte 100    ; first byte is the number of encoded bytes that follow
    ; encoded colony
    !text B00000000,B00000000,B00000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B11000000,B00011000
    !text B00000000,B00000000,B00000001,B01000000,B00011000
    !text B01100000,B00110000,B00000001,B10000000,B00000000
    !text B01100000,B01010000,B00000000,B00000000,B00000000
    !text B00000000,B01100000,B01100000,B00000000,B00000000
    !text B00000000,B00000000,B01010000,B00000000,B00000000
    !text B00000000,B00000000,B01000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B00000000,B00001100
    !text B00000000,B00000000,B00000000,B00000000,B00001010
    !text B00000000,B00000000,B00000000,B00000000,B00001000
    !text B00000000,B00000000,B00000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B00000000,B00000000
    !text B00000000,B00000000,B00000000,B01110000,B00000000
    !text B00000000,B00000000,B00000000,B01000000,B00000000

    !text B00000000,B00000000,B00000000,B00100000,B00000000


Features and presentation.

After the welcome screen, user presses a key and the help screen is displayed showing keyboard shortcuts to the functions of the program. Due to the presentation environment being text based, that information is not present on the screen during colony editing or simulation, therefore it is a good idea to read and memorize this screen or print it before proceeding.

Game of Life simulator - help screen.
In the next step, user is presented with the program's start menu. Possible choices consist of two template/demo colonies, ability to start with an empty editor or editor filled with random colony. There is also a load from file option available and option to terminate the application (confirmation is required).

Game of Life - start menu.
Depending on the user's choice, the editor starts filled with the colony or empty. Editor encodes the empty and life cells differently than the simulator. The empty cells are represented by minus '-' signs, while the life cells are represented with asterisks '*'. This approach has 2 advantages:

  1. User can recognize immediately in what mode the application is currently working (remember – there is no extra text information, the whole screen is taken by colony data presentation).
  2. The empty cells done with minus sign present a grid which makes it easier for user to design/modify the colony.
Game of Life - editor screen filled with random colony.
In editor, user can position the cursor (visible as a reverse color rectangle) using cursor keys on the keyboard and alter the cell status with space key. Other possible functions are 'H' to display help screen, 'C' to clear all the cells (requires confirmation), 'R' to fill cells with random values (requires confirmation) and 'Q' to exit the editor and start simulation. At the exit, user is prompted to save the colony to file, which can be skipped.

Game of Life - exit editor, save to file prompt.
If user chooses to save the colony to file, a prompt appears to enter the colony file name.

Game of Life - save colony, file name prompt.
The simple file name editor allows to enter alpha-numeric string of up to 12 characters in length. User can press DEL key to remove incorrectly entered characters. If the entered file name is empty (RETURN key pressed with the cursor positioned at the 1st character of the file name), the Save operation is considered as canceled and program proceeds to simulation. Otherwise, the program attempts to save the colony to file. In case of I/O error, there is no action. Extension “.COL” is added to the file name automatically.

Simulator starts in paused mode. User can immediately see that program entered simulation mode because the cells are now presented differently on the screen (Illustration below).

Game of Life – paused simulator.
Pressing any key starts the simulation. Please note the donut style cells (see Illustration below), which are the cells marked to die in the next generation by the algorithm. Newborn dots are not visible until the next generation is fully created and the screen codes converted to the full dots or spaces accordingly.
(NOTE: on the screen shot below, not all the cells that are supposed to die in the next generation are yet marked like donut, because the screen shot captured the screen in the middle of the process)

Game of Life - running simulation.
At any moment during simulation user can choose to quit application (requires confirmation), pause it, go to editor and alter/save the colony, display the help screen or go back to start menu (requires confirmation) using the keyboard shortcuts presented on the help screen at the program start up.

Game of Life - quitting the application.
Game of Life - the fun is over.

Here is the link to source code. Look for a ZIP archive named ConwaysLife.
Thank you for visiting.

Marek Karcz
9/15/2013.