How_to_code_a_really_fast_"Game_of_Life"_on_a_6510...

with 1 MHz... Impossible? Too slow? NO! All you need is Brain, Power and Motivation.

Deutsch/German: Für echte Freaks gibts hier noch Handnotizen (13 Seiten DIN A4, 150 dpi, 2 MB)

Please forgive my crazy "special" English. I know it is not the right Way to write Nouns in Uppercase, but if I like it too much ;-) Also forgive my not so correct Phrases in here. The only important Thing to write this Article in English was it to present it to the international Interest.

For those, who still not know what the Game of Life is: it was invented in the 80´s by John Conway at the MIT. Simply explained it is a Cellular Automata, Cells placed on a wide Field. Their Survival is depending from their Neighbors, also the still not existing Cells around can suddenly change from Death to Life.

General Rules are:
1. A Cells Status can be live or dead.
2. A Cells Survival or Awakening depends from its eight Neighbors around.
3. The Neighbors are the Cells up, left, right, down and the four diagonal ones.
4. The Field is a Thorus, which means right End is the left and bottom End is the top Beginning of the Field.

Rules for a Generation Run:
1. Dead Cell changes to Live Cell when there are 3 Neighbors.
2. Live Cell survives only when there are at least 2 and not more than 3 Neighbors.

Maybe you have seen it already somewhere, but did not know about its Mystery. It is more than Fascination! There are "Life" Clubs existing, like for Chess.

Once upon the Time I started with my friend Dolphin the GREEN LIFE Project. All what we had in the Beginning was this:
1. A PC 386SX (16 MHz) with a Program named "Green Life". Real fast.
2. A Scientific American Magazine with Background Information.

One Day, Dolphin wrote a LIFE in BASIC V2 on the famous C64. It was fast, but a Cell was represented by an inverted Blank - so the maximum Resolution of the Field was 40x25. Too less... and too big Cells, so the Fascination did not come up.

It was himself asking me why not coding a LIFE in 6510 Assembler. So the next Days we meet so often as possible, he explained me how LIFE works and I tried to do it in Turbo Ass 5.0. Howdy, I defined a Charset so a Char could contain up to four Digits (in the Following I mean with Digit a Cell) in binary Order (16 Chars).

Projects Start was the 5th June of 1995 and on this Day "GL1" came up to Life. It was in no Way optimized, but had a better Resolution, and: IT WORKED, although it did it very slowly. Reason: For a Field of e.g. 56x34 Digits (1904 Digits) there are 17136 possible Comparations. And every Comparation costs several Cycles. But better Versions should follow.

Many Days went along, and I coded and coded and coded...

When it was Time for "GL37" (37th Version :-)),  this was already implemented:
1. A CIA Timer Routine which counts the Cycles for a complete Generation Run.
2. A Field of 56x34 Digits, with Thorus Property.
3. Access to the Field Addresses via Tables and Tables with Bitmasks for the Digits.
4. Display with Generation Counter, Living Cells, recently awakened/died.
5. A Field for marking Digits with no Neighbors to run faster.

It was fast, and Dolphin was really amused about it. Both of us showed it some Friends and Scene Dudes. The most were really fascinated.

At this Place I tell you that GL37 had no Editor inside, so I had to place every Start Situation manually in the Editor of PROMON. The famous Glider Canon became the Default Start Situation. 

Coming back from my Holidays I lost the Fun to continue. So "GL37", last edited on the 21th of June 1995, sleeped several Years. 1995, 1996, 1997 went and nothing happened.

01.06.1998. The Fever come back. No One know why. When I watched the Source Code of "GL37" I thought: That can go much faster! The Routine for comparing all Neighbors of a Digit and then to set or clear it took 342 Cycles: if the "Mark Digits without any recently Action"-Routine would not exist, that would be 651168 Cycles and on the 6510 this means less than 2 Frames per Second. So I optimized some Routines on Paper, but did not code them in Reality. One Day I lost the Fun again.

22.03.1999. Thinking about the "GL37" I had several new Ideas and wrote them down on Paper again. Saying it with the nasty Words from DOLPHIN:
"it´s such a lame Code so that you can do it so with Müsli in the Bauch only."

26.03.1999. On this Day I had a real Idea Flash. And so I reduced the Neighbor Routine from 342 (lame, lame...) to 17 (!!!) Cycles. Here the final Code:

[3] lda FIELD-WHERENOW
[4] ldx FIELD-DIAGONAL, y
[4] adc AND-MASK-TABLE, x
[3] adc FIELD-LEFT-or-RIGHT
[3] adc FIELD-UP-or-DOWN

Where all Field-Addresses except FIELD-DIAGONAL are saved in the Zeropage and LEFT-RIGHT/UP-DOWN contain already the Result of a special Operation, which can also run faster with four further Tables.

FIELD AND #$0A - Amount of Bits set as Hi-Nibble > LEFT
FIELD AND #$05 - Amount of Bits set as Hi-Nibble > RIGHT
FIELD AND #$0C - Amount of Bits set as Hi-Nibble > UP
FIELD AND #$03 - Amount of Bits set as Hi-Nibble > DOWN

Storing the Cells Status could look like this:

[2] tax
[3] lda FIELD-WHERENOW
[4] eor CELL-ORIGIN-DEAD/LIFE-1..4-TAB, x
[4] sta FIELD-WORK-WHERENOW, y

Tricky: This Routine adds in the Hi-Nibble the Amount of External Neighbors (0..5 represented as $0X..$5X), the Lo-Nibble contains all Digits in the Char where the central Digit is. This saves an otherwise 4 Cycles expensive further Table Access.

Digit with binary Value 1: %NNNNBBBC
Digit with binary Value 2: %NNNNBBCB
Digit with binary Value 4: %NNNNBCBB
Digit with binary Value 8: %NNNNCBBB

Looks hard to decode, but it isn´t. As so often, Tables solve the Problem.
Here a sample Code for the left up Digit in the Char at $0452:

; $0002 : Field with Central-Digit
; $0C00 : here Table Cell-Origin-Dead-Life-Toggle-Bit0
; $0429 : here Diagonal-Field left up
; $0A80 : here Table Set-Bits-as-Hi-Nibble-when-AND-#$08
; $005A : here UP-Field-Result
; $005B : here LEFT-Field-Result
; $6452 : here Work-Field-Address for $0452

lda $02
ldx $0429, y
adc $0A80, x
adc $5A
adc $5B
tax
lda $02
eor $0C00, x
sta $6452, y

This is in my Opinion the fastest Routine I can use to count Neighbors and toggle (if needed) the central Digit. If you think you can do it better or faster, please let me know.

This Text will be continued in next Time. There exists already an OPTIMIZED Routine not explained here (yet).

BACK TO AIRPORT1 HOMEPAGE