Conway’s Game of Life Challenge: Hat jemand Lust mitzuspielen?

Moin, moin!

Life ist irgendwie eine Referenz für mich. Deswegen implementiere ich es auf so ziemlich jeder Hardware, die mir in die Hände fällt...

Genaugenommen geht es hierum: https://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens

Aktuell ist mir ein C64u in die Hände gefallen, für den ich ein wenig herumtippe...

Mein erstes, nennenswertes, Programm wird Turbofast Life sein, bei dem ich versuche, die maximale Geschwindigkeit, so maschinennah wie möglich, aus dem 64er herauszuholen.

Als jemand, der in der 8-Bit-Zeit extrem fest mit dem ZX Spectrum verbandelt war, wird mir der 6502 mit seiner Maschinensprache vermutlich nicht all zu leicht fallen... 😉

Hat jemand von Euch Interesse ein richtig schnelles "Game Of Life" für den CPC zu basteln?

Außerdem: Möchte jemand von Euch sehen, was mein Life auf dem Klassenfeind, also dem 64 so entwickelt?


P.S.: Den 64er werde ich übrigens verwenden, da er einen Textmodus hat. Ich erwarte, dass die Ausgabe auf dem Bildschirm bei dem Gerät ziemlich schnell sein wird.

Der CPC, den ich ja auch erst seit ein paar Wochen besitze, stand auf Platz 2 der Optionen. Deshalb die Frage an Euch nach einem Konkurrenzprogramm.

Das Spielfeld auf dem 64er wird übrigens 38x23 sein. - Wer weiß warum?!  😎

P.S.: Hier mein erster Test des Text Modes beim 64er
Das ist schon beeindruckend. Daneben könnte sogar mein Programm für den Amiga bei 7MHz blass aussehen!

Zum Test das Programm auf dem 64er(-Emulator) laden ",8,1" und ausführen...

Edit: Bild eingefügt.
📎 turbolife.d64
📎 c64_life_hacking.jpeg

Habe das mal in die Commodore-Rubrik verschoben, wo es hingehört.  🙂

Danke! - Hatte ich gar nicht gesehen, dass es das gibt. 😉

Inzwischen habe ich das Programm fertig und ein wenig optimiert (s.u.)

Geschwindigkeit bei 1MHz und 38*23 Zellen: 5 Iterationen in ca. 12s
Und das inklusive Ausgabe auf dem Bildschirm.

Neben dem Test der Bildschirmausgabe befindet sich nun noch die Datei LIFE.PRG auf der Diskette.

Laden u. Starten:

LOAD "LIFE",8,1
RUN

Ein guter Wert für die Initialisierung des Zufallsgenerators (limit) ist 8900. Die Iterationen dann auf 100, oder höher. Dann sieht man wie sich das Bild einpendelt...

Edit: [member=5]TFM[/member]
Hoffentlich findet sich auch hier im Forum des Klassenfeinds jemand, der das liest und auf dem CPC umsetzt.

Edit: Schön, dass man Beiträge hier auch nach längerer Zeit noch editieren kann.

Es gibt doch noch eine Überraschung:
Nachdem ich gestern Abend noch ein wenig herumgespielt habe, habe ich den Code noch deutlich optimiert bekommen.

Die Optimierung war allerdings eher zufällig. 😉
Ich hatte noch einen Fehler gesehen bei der Ausführung und wollte den fixen.

Auch wenn es vermutlich niemandem aufgefallen wäre: Der Algorithmus in LIFE.PRG hat einen Fehler bei Zellen in der ersten Zeile oder ersten Spalte. Das Resultat ist nun eine deutlich schnellere- und vermutlich auch fehlerfreie Version.

Nun läuft die gepimpte Version mit ca. 3 Iterationen pro Sekunde.
Fünf Iterationen brauchen also nicht mehr 12s, wie in der ersten Version, sondern nur noch etwas mehr als 1,5s...

Im Disk Image sind beide Versionen.
Das Binary der schnelleren Version ist ca. 40% größer als das Normale.

Wer es probieren möchte:
Normale Version

LOAD "LIFE",8,1
RUN

Schnellere Version

LOAD "FASTLIFE",8,1
RUN

📎 turbolife.d64

Saubere Arbeit!  :jubelaola:

Für den CPC gibt es schon einige Versionen. Deshalb hab ich bisher auch selber noch keine gemacht.  🙂

Danke für die Blumen.

Hast Du vielleicht einen Link auf eine Version inklusive Source Code für mich? - Assembler, oder C. Der Rest ist wohl zu langsam.

Die könnte ich als Basis nehmen und versuchen zu tunen. Schliesslich soll der Z80 ja gegen den popeligen 6502/6510 gewinnen, oder?  >😄

Übrigens: Ca. 3 Iterationen pro Sekunde meint, dass der C64u bei maximaler Taktfrequenz von 64MHz über 150 Iterationen pro Sekunde schafft!
Ich werde wohl mal einen V-Sync einbauen. Es sieht bestimmt beeindruckend aus, wenn die Aktualisierung flimmerfrei mit 50Hz Updaterate dargestellt wird...

Meine Version hat dank des Setups ein lustiges Feature: Den God Mode(*1)...
Meint: Über den Remote Debugger kann ich im laufenden Betrieb vom PC aus Muster in das Spielfeld injizieren.

Das ist ziemlich lustig. Ich muss mal ein Video davon machen.

Ad (*1): Der God Mode ist leider noch nicht perfekt weil die neuen Zellen während der laufenden Berechnung eingefügt werden. Dadurch kommt es vor, dass die Muster für die nächste Iteration falsch berechnet werden, was beim ersten Bilderwechsel ein inkorrektes Ergebnis erzeugt.

Vielleicht erweitere ich das, auf dem nächsten Retro Event, an dem ich teilnehme, so, dass die Berechnung mit der Remote Aktualisierung synchronisiert wird. Das ist aber etwas aufwändiger...

Edit: Bilder eingefügt - Impressionen: Life In Action  😎
📎 turbo_life_disk.jpg
📎 fast_life_setup.jpg
📎 fast_life_live.jpg

Das Problem beim CPC ist die langsame Bildschirmausgabe. Da wirst Du leider abgestraft - das ist beim Speccy "besser" gelöst, wenn auch mit Color Clash, aber ~6 KB Bitmap sind eben sehr viel schneller zu beschreiben als volle 16 KB... einen Text-Mode gibt es ja leider nicht. Alles ist Grafik.  Drei Frames / sec sollten aber auch drin sein.

Das weiß ich. - Falls der Algorithmus, wie auch von mir erwartet, langsamer sein wird, werde ich die Berechnung und die Ausgabe trennen.

So kann ich dann die Rechenleistung vergleichen...

— LambdaMikel
Das Problem beim CPC ist die langsame Bildschirmausgabe. Da wirst Du leider abgestraft - das ist beim Speccy "besser" gelöst, wenn auch mit Color Clash, aber ~6 KB Bitmap sind eben sehr viel schneller zu beschreiben als volle 16 KB... einen Text-Mode gibt es ja leider nicht. Alles ist Grafik.  Drei Frames / sec sollten aber auch drin sein.

Da geht viel mehr 🙂

— TFM...
Da geht viel mehr 🙂

Bist Du Dir Sicher? Da müsstest Du aber sicher ganz viel Super-Zauber-Magie anwenden!

Ich halte 3Hz schon für eine ziemliche Herausforderung!

Dir ist sicher klar, dass man bei so einem Z80 quasi nur eine Handvoll CPU Zyklen pro Sekunde hat...

Bei angenommen 4MHz und einem Ziel von 4Hz bleiben Dir ziemlich genau eine Million davon. - Das klingt erst mal viel, ist es aber nicht.  😎

Immerhin müssen 38*23, also 874 Zellen in jedem Durchlauf neu berechnet werden.

Bei 1e6 Zyklen bleiben Dir im Mittel 1144 Taktzyklen pro Zelle um das Ziel nicht zu reißen!

Wenn DU eine Idee hast: Lass Dich herausfordern.
Falls Du ein schnelles Beispiel findest: Her damit!

P.S.: Ich hab' mal etwas in meinem angestaubten Z80-Assembler-Gedächtnis herumgeforscht: Schon RAM Zugriffe sind verdammt teuer.

; 1. Direct Address (16 cycles)
; 1. Direct Address (16 cycles)
LD A, ($4000)
LD B, ($1234)

; 2. Register Indirect 
LD A, (HL)        ; 7 cycles
LD A, (IX)        ; 19 cycles
LD A, (IY)        ; 19 cycles

; 3. Indexed Offset (19 cycles)
LD A, (IX+5)
LD A, (IX-3)
LD C, (IY+$10)

; 4. Block Copy 874 Bytes $4000 → $6000
LD HL, $4000      ; 10 cycles
LD DE, $6000      ; 10 cycles
LD BC, #874       ; 10 cycles  
LDIR              ; ~4 cycles/byte → ~3500 cycles total

Selbst simple Rechenoperationen fallen Einem da schnell auf die Füße, wenn man nicht geschickt Bitshiftet, o.ä.

P.S.: Edit
Der C-Compiler für den 6502 hat den Code, den ich in native C geschrieben habe, unfassbar gut optimiert.

Ich habe ein bisschen darauf geachtet möglichst immer Bytes zu nutzen und den Zugriff auf die Daten über array[][]-Pointer gemacht. Den Rest hat der Compiler optimiert.

Wenn ich mich nicht verrechnet habe, sind das bei 3Hz unter 380 CPU-Zyklen pro Zelle im Schnitt für die komplette Verarbeitung...

Unfassbar! - Da habe ich dann nicht mehr versucht über den Inline-Assembler weiter zu optimieren.

— Eratosthenes

— TFM...
Da geht viel mehr 🙂

Bist Du Dir Sicher? Da müsstest Du aber sicher ganz viel Super-Zauber-Magie anwenden!

Ich halte 3Hz schon für eine ziemliche Herausforderung!

Dir ist sicher klar, dass man bei so einem Z80 quasi nur eine Handvoll CPU Zyklen pro Sekunde hat...

Bei angenommen 4MHz und einem Ziel von 4Hz bleiben Dir ziemlich genau eine Million davon. - Das klingt erst mal viel, ist es aber nicht.  😎

Immerhin müssen 38*23, also 874 Zellen in jedem Durchlauf neu berechnet werden.

Bei 1e6 Zyklen bleiben Dir im Mittel 1144 Taktzyklen pro Zelle um das Ziel nicht zu reißen!

Wenn DU eine Idee hast: Lass Dich herausfordern.
Falls Du ein schnelles Beispiel findest: Her damit!

P.S.: Ich hab' mal etwas in meinem angestaubten Z80-Assembler-Gedächtnis herumgeforscht: Schon RAM Zugriffe sind verdammt teuer.

; 1. Direct Address (16 cycles)
; 1. Direct Address (16 cycles)
LD A, ($4000)
LD B, ($1234)

; 2. Register Indirect 
LD A, (HL)        ; 7 cycles
LD A, (IX)        ; 19 cycles
LD A, (IY)        ; 19 cycles

; 3. Indexed Offset (19 cycles)
LD A, (IX+5)
LD A, (IX-3)
LD C, (IY+$10)

; 4. Block Copy 874 Bytes $4000 → $6000
LD HL, $4000      ; 10 cycles
LD DE, $6000      ; 10 cycles
LD BC, #874       ; 10 cycles  
LDIR              ; ~4 cycles/byte → ~3500 cycles total

Selbst simple Rechenoperationen fallen Einem da schnell auf die Füße, wenn man nicht geschickt Bitshiftet, o.ä.

P.S.: Edit
Der C-Compiler für den 6502 hat den Code, den ich in native C geschrieben habe, unfassbar gut optimiert.

Ich habe ein bisschen darauf geachtet möglichst immer Bytes zu nutzen und den Zugriff auf die Daten über array[][]-Pointer gemacht. Den Rest hat der Compiler optimiert.

Wenn ich mich nicht verrechnet habe, sind das bei 3Hz unter 380 CPU-Zyklen pro Zelle im Schnitt für die komplette Verarbeitung...

Unfassbar! - Da habe ich dann nicht mehr versucht über den Inline-Assembler weiter zu optimieren.

Hu, ja, naja... das schöne Programm da oben benutzt ja den 38*23 Zellen Modus.  🙂  🙂  Wäre das in Ordnung, wenn ich am CPC mit 62 * 30 Zellen arbeite? Dann könnte ich nämlich aus dem Versuch eventuell einen Bildschirmschoner machen, falls es läuft.

Gibt es sonst noch Regeln die ich beachten müsste?

— Eratosthenes

— TFM...
Da geht viel mehr 🙂

Bist Du Dir Sicher? Da müsstest Du aber sicher ganz viel Super-Zauber-Magie anwenden!

Ich halte 3Hz schon für eine ziemliche Herausforderung!

Magie? Gerne! Also nehme ich FutureOS, dann kann ich die Zweitregister nutzen, das bringt hier sehr viel.

12Hz oder so könnte es schon geworden sein, sieh selbst:



Habe das heute mal schnell gecodet, also ja, Politur fehlt noch 😉

Viel Spaß damit!  🙂  🙂  🙂

Edit: DSK angehängt 🙂
📎 LBSS.dsk

WOW! - Großes Kino! - DAMIT ist die echte Challenge eröffnet würde ich sagen.

Wirklich gute Performance. - Ich habe inzwischen Versionen mit ähnlicher Performance auch auf dem 64er gesehen.

Die rechnen die Zellen aber nicht sequenziell aus. - Den Algorithmus kannte ich bisher noch nicht.

Soll ich den meines Programmes mal anpassen, damit er ähnlich rechnet?

Dann kämen Wir dem tatsächlichen Geschwindigkeitsvergleich näher...

P.S.: Edit
Ich lege, die Tage, mal ein git-Repo an, in dem ich meinen Kram poste. Falls Du Lust hast, kannst Du Deine Lösung mit dazupacken.

P².S.: Eigentlich wollte ich ja die CPU Leistung der Rechner vergleichen. Die beste Optimierung zu suchen, ist latuernich auch eine coole Challenge.

Ich werde einen Bereich für den klassischen Algorithmus und einen für optimierten Code anlegen. Was mir vorschwebt, ist, die Algorithmen dort inkl. Dokumentation, also der Beschreibung welche Optimierung gemacht wurde, wie man es kompiliert-/assembliert bekommt, usw. dort findet.

P³.S.: Habe das git-Repo <klick> gerade mal erstellt...

Vielen Dank für das Lob!  ❤️ Meinen Source hab ich hier ja als DSK angehängt, es ist ASCII für den MAXAM II Assembler. Den kannst Du gerne in ein Git-Repo o.ä. übernehmen. Viel Spass damit!  :smiley027:

Die Methode hier ist sequenziell, Zelle für Zelle von links nach rechts, dann Zeile für Zeile. Aber die Geschwindigkeit kommt durch die Nutzung von regulären Registern und Zweitregistern des Z80, was ja bei FutureOS völlig normal ist.

Viel Glück für Deine Optimierungen  :smiley027:

Danke! - Ich werde das vermutlich da mit hochladen. Habe tatsächlich noch nicht auf das Image geschaut.

Ich schließlich wichtig, dass der Z80 gewinnt, oder?!  :bgdev:

— Eratosthenes
Danke! - Ich werde das vermutlich da mit hochladen. Habe tatsächlich noch nicht auf das Image geschaut.

Ich schließlich wichtig, dass der Z80 gewinnt, oder?!  :bgdev:

Hmmmm... das kommt wohl immer darauf an was man macht... jede CPU hat ihre Stärken.  :jubelaola:

Der Hauptvorteil des 64ers ist, dass das (Text-) Feld direkt im Video RAM dargestellt werden kann.

Der Nachteil - insbesondere der CPU - sind imho die Taktfrequenz und die wenigen Register.

Entsprechend, insbesondere wenn ich Deine Lösung sehe, bin ich optimistisch, dass der Z80 hier die schnellere Lösung hin bekommt.

By the Way: Welche Taktfrequenz hat der 6128+ eigentlich?

Der 6128plus und der CPC laufen beide mit 4 MHz, jedoch werden die Befehle "etwas gestreckt", also auf die Mikrosekunde aufgerundet. Man könnte also sagen, daß der Z80 im CPC / Plus mit etwa 3.6 MHz arbeitet. Es kommt hierbei natürlich darauf an, wie man programmiert.

Anbei ein bisschen Infomaterial...
📎 Ausführungszeiten für die einzelnen Befehle der CPC-Z80.docx
📎 True_Z80-CPC_Timings_2021.txt
📎 Undocumented Z80 documented.pdf
📎 Z80_CPC_Timings_2013-10-19.pdf

OK, ich werd's testen.

Bekomme ich es nicht ans Laufen, wirst Du einem CPC-NOOB erklären müssen, wie es geht... 😄

Darf ich das ins Repo pushen?

Das Repo ( https://github.com/Eratosthenes0815/Conway-s-Game-Of-Life-8-Bit-Challenge/tree/main ) hat eine MIT Lizenz. Somit ist es dann öffentlich und frei kopierbar...

Würde dann Dein Video im README mit verlinken inkl. Dank und dass Du aktuell das Rennen anführst. 😉

— Eratosthenes
OK, ich werd's testen.

Bekomme ich es nicht ans Laufen, wirst Du einem CPC-NOOB erklären müssen, wie es geht... 😄

Darf ich das ins Repo pushen?

Das Repo ( https://github.com/Eratosthenes0815/Conway-s-Game-Of-Life-8-Bit-Challenge/tree/main ) hat eine MIT Lizenz. Somit ist es dann öffentlich und frei kopierbar...

Würde dann Dein Video im README mit verlinken inkl. Dank und dass Du aktuell das Rennen anführst. 😉

Darfst Du gerne machen  🙂  🙂  🙂

Der Source Code ist schon einigermaßen selbsterklärend, bin aber immer gerne da um zu helfen.  🙂  🙂  🙂

Na dann will ich mich mal auch nicht lumpen lassen - damit Ihr auch mal nen echten Computer seht 😄

https://youtu.be/nWf_sNNvUuM

64 x 16, Z80 (kein A!) @ 1.77 Mhz. Der Fairness halber muss man die Framerate mit ca. 2 für das CPC-MHz-"Äquivalent" multiplizieren. Das dürften dann so 8 bis 10 Frames pro Sekunde sein. Wenn der CPC denn schnellen Bildschirmspeicher hätte... also rein hypothetisch.

PS Wenn ich das mal am Model 4 laufen lassen mit seinen 4 MHz, dann wird's zu schnell, will ich gar nicht zeigen :rofl