Zufallszahlen in Assembler erzeugen
Früher oder später kommt jeder Assemblerprogrammierer in die Verlegenheit, zufällige Werte erzeugen zu müssen. Sei es um ein Puzzel durcheinander zu würfeln, den Startpunkt für die nächste Gegnerwelle zu bestimmen oder um ein komplettes Labyrinth (z. B. einen Dungeon für ein Rollenspiel) zu erstellen.
Da ein Computer rein logischen Abläufen folgt, sind zufällige Werte relativ dünn gesäht. Genaugenommen gibt es nichts wirklich zufälliges, es sei denn ein Bauteil schmorrt mal durch 😉 .
Wie kommen wir nun an Zufallszahlen?
Wenn es nichts Zufälliges im Computer gibt, wie kommen wir denn dann an zufällige Werte? Schauen wir uns erstmal eine aus der BASIC-Einführung bekannte Methode an.
Warum das Rad neu erfinden?
Vom BASIC kennt ihr bestimmt den RND()-Befehl. Also, warum sich den Kopf zerbrechen und etwas Neues erfinden, weshalb nicht einfach den BASIC-Befehl nutzen? Zunächst mal haben wir uns ja für Assembler entschieden, da das BASIC nicht unbedingt schnell ist. Dies trifft auch auf die Zufallszahlen zu. Außerdem muss das ROM dazu sichtbar sein, was evtl. nicht immer gewünscht ist. Wer es dennoch nutzen möchte, der findet den Einsprung zur Random-Funktion im ROM an der Adresse $e097.
Um gleich die Funktionsweise der ROM-Routine besser zu verstehen, werfen wir zunächst mal einen Blick auf den BASIC-Befehl. Unter BASIC gebt ihr bekanntlich etwas wie RND(175) ein. Ihr erhaltet dann eine Zufallszahl im Fließkommaformat, die zwischen 0 und 1 liegt, wobei weder die 0 noch die 1 jemals als Ergebnis auftauchen werden. Für uns ist als Erstes der Wert in den Klammern von Interesse. Dieser wird verwendet, um den Ursprung für unsere Zufallszahlen zu ‚sähen‘ (im engl. lest ihr häufig etwas von ‚seed‘ hier nur mit zwei e 😉 ). Steht in den Klammern eine Zahl > 0, dann wird als ‚seed‘ der Wert genommen, den ihr auf der Zero-Page an den Adressen $8b-$8f findet, es handelt sich hier um eine fünf Byte lange Fließkommazahl. Nach dem Einschalten oder einem Reset, wird diese immer auf den selben Startwert $80, $4f, $c7, $52, $58 gesetzt. Somit bekommt ihr dann mit RND(<positive Zahl>) auch immer die selben Zufallszahlen. Außerdem ist nur das Vorzeichen hier + wichtig und nicht die Zahl. Steht in den Klammern eine Null, dann wird der TIMER verwendet, um den Ursprung festzulegen, was relativ zufällig ist. Gebt ihr eine negative Zahl in den Klammern an, dann wird diese durch verwürfeln als Ursprung benutzt. Das ist für Testzwecke hilfreich, da ihr so immer den gleichen Ursprung bekommt, unabhängig davon, was vorher geschehen ist und so immer die selben Zufallszahlen erhaltet. RND(0) ist zwar eigentlich die empfohlene Methode, aber auch die kann auf dem C64 problematisch sein, RND(-RND(0)) scheint bessere Ergebnisse zu liefern (s. Compute‘s – Mapping the Commodore 64, Seite 26).
Schauen wir jetzt weiter, wie das unter Assembler genutzt werden kann. Wie erwähnt, müssen wir nach $e097 springen, um den RND()-Befehl aufzurufen. Der Wert aus den Klammern muss im Akku und ggf. im FAC1 (Floting Point ACcumulator #1) stehen. Haben wir im Akku eine Null $0, dann wird, wie eben erwähnt, der TIMER (Timer A und die Echtzeituhr aus dem CIA-1) als Ursprung genommen. Bei einer positiven Zahl $01-$7f, wird wieder der Wert aus $8b-$8f als Ursprung verwendet. Ist die Zahl im Akku aber negativ $80-$ff, dann wird der Ursprung aus dem FAC1 genommen, den wir natürlich vorher füllen müssen (der FAC1 liegt auf der Zero-Page an den Adressen $61-$66). Hier im FAC1 finden wir dann auch das Ergebnis des RND()-Befehls. Na toll, was sollen wir jetzt mit einer Fließkommazahl? Uns würde in Assembler ein Byte viel besser passen. Es hat sich rausgestellt, dass in FAC1, in den Bytes an den Adressen $63 & $64 passende Werte auftauchen. Kontrollieren könnt ihr das mit dem Beispielprogramm, am Ende der Seite. Wie bereits anfangs erwähnt, ist diese Funktion nicht besonders schnell. Wie ihr evtl. durch das Setzen des Ursprungs bemerkt habt, liefert RND() pseudo Zufallszahlen. Es wird ausgehend vom gewählten Ursprung, eine Reihe von Zufallszahlen erzeugt, die aber bei gleichem Ursprung auch immer gleich (und somit berechenbar) sind. Sie wirken auf uns nur zufällig.
Bitte kein BASIC
OK, machen wir uns Gedanken, wie wir einfacher und schneller an Zufallszahlen kommen können.
Die Rasterzeile
Einsteiger kommen hin und wieder auf die Idee, die aktuelle Rasterzeile zu nehmen. Wie ihr bestimmt wisst, baut der C64 sein Bild von oben nach unten auf. Dazu läuft der sog. Rasterstrahl über den Bildschirm. Er wandert auf PAL-Systemen 50 mal und bei NTSC 60 mal in der Sekunde über den kompletten Bildschirm. Wir können nun die aktuelle Position des Rasterstrahls abfragen und so an eine vermeintliche Zufallszahl kommen. Allerdings müssen wir hier sehr aufpassen. Wenn wir z. B. in einer Routine immer erst auf eine bestimmte Rasterzeile warten und erst danach unsere Zufallszahl ermitteln, wird die schon nicht mehr so zufällig sein. Aber man könnte zu Beginn die Rasterzeile nutzten um einen eigenen Startwert zu erzeugen. Wie ihr euch auch immer entscheidet, ihr könnt mit einem lda $d012 die aktuelle Rasterzeile auslesen und direkt als Zufallszahl verwenden, wirklich ratsam ist das aber nicht! Also, vergesst das ganz schnell wieder!!
Der SID macht nicht nur Musik
Der SID-Chip schmeichelt unseren Ohren nicht nur mit dem unvergesslichen C64-Sound, er taugt auch zur Erzeugung von Zufallszahlen (s. Compute! Ausgabe 72 vom Mai 1986). Dazu müsst ihr nur einige Register setzen. Stellt die dritte Stimme des SID auf Rauschen (noise) und dann müsst ihr noch die Frequenz auf einen Wert <> 0 setzen. Ab jetzt findet ihr an $d41b Zufallszahlen im Byte-Format. Keine Angst, wir aktivieren die Ausgabe nicht, man wird also keinen unerwünschten Ton vernehmen. Diese Einstellungen müsst ihr übrigens nur einmal vornehmen. Aber auch hier bekommen wir evtl. Probleme: Was ist, wenn wir den SID und besonders die 3. Stimme für unsere Musik brauchen?
lda #$80 ;Frequenz sta $d40e ;Low-Byte der Frequenz für Stimme 3 sta $d40f ;High-Byte der Frequenz für Stimme 3 sta $d412 ;Rauschen für die 3. Stimme setzen
Ab jetzt bekommt ihr mit lda $d41b eure Zufallszahlen.
Der Timer
Der TIMER des C64 wird evtl. am häufigsten für die Ermittlung von Zufallszahlen benutzt. Wenn wir den Timer verwenden, dann sollten wir mehrere TIMER Register miteinander verknüpfen und nicht nur ein einzelnes Byte betrachten. Die folgende Lösung liefert sehr gute Ergebnisse und wird auch von mir verwendet.
lda $dc04 ;Low-Byte von Timer A aus dem CIA-1 eor $dc05 ;High-Byte von Timer A aus dem CIA-1 eor $dd04 ;Low-Byte von Timer A aus dem CIA-2 adc $dd05 ;High-Byte von Timer A aus dem CIA-2 eor $dd06 ;Low-Byte von Timer B aus dem CIA-2 eor $dd07 ;High-Byte von Timer B aus dem CIA-2
Genau diese Code-Sequenz findet ihr übrigens auch im Klassiker „Boulder Dash“, so schlecht kann dieses Vorgehen dann ja nicht sein.
Hier mal mit dem VICE Monitor herausgesucht (nach einem Klick aufs Bild wird es lesbarer).
Evtl. sollten wir noch beachten, dass der TIMER beim Einschalten immer wieder beim selben Wert beginnt und das kann bei den heutzutage häufig genutzen Emulatoren dazu führen, dass immer die selben Zufallszahlen erzeugt werden. Dies passiert, wenn euer Programm direkt mit der Generierung von Zufallszahlen beginnt (z. B. bei einer Demo). Wartet ihr zunächst aber auf eine Eingabe vom User (z. B. das Drücken des Feuerknopfes zum Starten), dann erledigt sich das Problem von selbst, da der Spieler sicherlich nicht jedes Mal in der selben Mikrosekunde nach dem Laden den Feuerknopf drückt.
Die Mischung machts
Um das eben beschriebene Problem in den Griff zu bekommen, kann man jetzt versuchen, über den Rasterstrahl oder den SID einen Quellwert für die Erzeugung von Zufallszahlen zu ermitteln. Beim Programmstart holen wir uns dann ganz zu Anfang diesen Wert und speichern ihn im RAM. Für die Zufallszahlen verwenden wir die Timer-Routine von oben und machen zum Schluß noch ein letztes eor mit unserem Startwert.
lda $dc04 ;Low-Byte von Timer A aus dem CIA-1 eor $dc05 ;High-Byte von Timer A aus dem CIA-1 eor $dd04 ;Low-Byte von Timer A aus dem CIA-2 adc $dd05 ;High-Byte von Timer A aus dem CIA-2 eor $dd06 ;Low-Byte von Timer B aus dem CIA-2 eor $dd07 ;High-Byte von Timer B aus dem CIA-2 eor rndseed ;Unsere Rasterzeile
Wollt ihr nur Zufallszahlen aus einem bestimmten Bereich, dann könnt ihr solange Zahlen erzeugen, bis ihr eine gültige Zufallszahl habt. Schauen wir uns mal ein Beispiel an. Wir möchten nur Zahlen von 15 (untere Grenze UG) bis 42 (obere Grenze OG).
loop jsr getRandom ;die Zufallszahl steht im Akku cmp #42-15+1 ;ist die Zahl größer als OG (42) - UG (15) + 1? bcs loop ;wenn ja, neue Zahl holen adc #15 ;sonst 15 addieren (Carry ist bereits gelöscht!)
Das kann natürlich auch direkt in die getRamdom-Routine eingebaut werden und / oder ihr macht die UG und OG dynamisch, indem diese z. B. im X- & Y-Register übergeben werden.
Beispielprogramm
Hier folgt jetzt das kleine Beispielprogramm, mit dem ihr die verschiedenen Funktionen testen könnt, die wir oben besprochen haben. Das Programm löscht beim Start den Bildschirm und füllt diesen anschließend zufällig mit inversen Leerzeichen. Ihr könnt dabei z. B. die Probleme bei der Verteilung (besonders beim Rasterstrahl) erkennen. Um ein Gefühl für die Geschwindigkeit zu bekommen, blinkt der Rahmen, umso breiter die Balken im Rahmen sind, desto langsamer läuft das Programm!
Vergleicht jetzt mal alle Routinen und beobachtet, wie der BS gefüllt wird und wie schnell das jeweils geht. Kommentiert dazu bei getRandom einfach die gerade gewünschte Routine ein und die anderen aus.
Euch sollte auffallen, dass rndBASIC zwar am langsamsten ist, aber den gesamten BS im Laufe der Zeit gut abdeckt und dabei anscheinend sehr zufällig vorgeht. rndRaster ist zwar sehr flott, aber es wird nach einem erkennbaren Muster gefüllt und es bleiben viele Lücken. Die rndSID-Routine ist mit Abstand die schnellste, zeigt kein erkennbares Muster und der komplette BS ist sehr zügig gefüllt. Die rndTIMER-Funktion ist etwas langsamer und benötigt mehr Zeit als rndSID, außerdem kann man eine Art von Muster erkennen. Um diese Unzulänglichkeiten jetzt zu kompensieren könnt ihr am Ende von getRandom die beiden Befehle mit rndSeed einkommentieren und die vier Tests erneut durchführen. Nun sollte sich bei allen eine bessere Verteilung der Zufallszahlen zeigen und der gesamte Bildschirm sollte auch schneller gefüllt werden, außer beim natürlich immer noch sehr langsamen rndBASIC. Als letztes könnt ihr noch mit getRandom_Range testen, wie es sich verhält, wenn wir auf eine Zufallszahl innerhalb eines sehr kleinen Bereichs warten, kommentiert dann das and, clc, adc aus und lasst euch überraschen. Auch hier ist ein gewaltiger Unterschied, ob rndSeed verwendet wird, oder nicht!
RND_UG = 4 RND_OG = 7+1 ;+1 wg. cmp & bcs JT_CHROUT = $ffd2 ;*** Startadresse *=$0801 ;*** BASIC-Zeile !byte $0c,$08,$e2,$07,$9e,$20,$32,$30,$36,$32,$00,$00,$00 ;*** BS löschen lda #147 jsr JT_CHROUT ;*** eigenen Startwert ermitteln jsr rndSIDInit jsr rndSID sta rndSeed ;für rndBASIC lda #$00 loop jsr getRandom ;einfaches Random ; jsr getRandom_Range ;Random mit Unter- / Obergrenze ;*** Page für BS-Speicher wählen and #%00000011 ;wir brauchen nur 0-3 clc adc #RND_UG ;Untere Grenze addieren sta putChar+2 ;und als MSB speichern ;*** Byte auf der Page jsr getRandom sta putChar+1 ;als LSB für BS-RAM speichern lda #$A0 ;invertiertes Leerzeichen putChar sta $0400 ;an der oben ermittelten Position ausgeben inc $D020 ;um ein Gefühl für die Geschwindigkeit ;zu bekommen den Rahmen blinken lassen jmp loop ;Endlosschleife ;*** gewünschte Zufallsfunktion wählen getRandom jsr rndBASIC ; jsr rndRaster ; jsr rndSID ; jsr rndTIMER ; eor rndSeed ;für eine bessere Streuung, diese ; sta rndSeed ;beiden Zeilen einkommentieren rts ;zurück getRandom_Range jsr getRandom ;Zufallszahl holen cmp #RND_OG-RND_UG ;prüfen ob im gewünschten Bereich bcs getRandom_Range ;wenn nicht, neue Zufallszahl adc #RND_UG ;untere Grenze addieren rts ;zurück rndBASIC jsr $e097 lda $63 rts rndRaster lda $d012 rts rndSIDInit lda #$80 ;Frequenz sta $d40e ;Low-Byte der Frequenz für Stimme 3 sta $d40f ;High-Byte der Frequenz für Stimme 3 sta $d412 ;Rauschen für die 3. Stimme setzen rts rndSID lda $d41B rts rndTIMER lda $dc04 ;Low-Byte von Timer A aus dem CIA-1 eor $dc05 ;High-Byte von Timer A aus dem CIA-1 eor $dd04 ;Low-Byte von Timer A aus dem CIA-2 adc $dd05 ;High-Byte von Timer A aus dem CIA-2 eor $dd06 ;Low-Byte von Timer B aus dem CIA-2 eor $dd07 ;High-Byte von Timer B aus dem CIA-2 rts ;*** Platzhalter für unseren Startwert rndSeed !byte $00
Wie ihr seht, gibt es einige Möglichkeiten Zufallszahlen in Assembler zuerstellen, welche ihr nutzt hängt ganz von euch und evtl. dem jeweiligen Einsatzgebiet ab.
Braucht ihr größere Zufallszahlen, dann könnt ihr übrigens einfach zwei, drei oder wieviele Bytes ihr auch immer benötigt, einzeln ermitteln und abschließend zu einer großen Zahl zusammenfügen.
Solltet ihr den Turbo Assembler verwenden, dann beachtet wieder die Besonderheiten, z. B. dass ihr keine Unterstriche verwenden könnt, auf die Länge der Zeilen achten müsst usw.
So, ich hoffe das Mysterium „Zufallszahlen in Assembler“ ist nicht mehr ganz so unheimlich und wünsche euch nun viel Spaß beim Umsetzen in euren eigenen Programmen.
Als Dankeschön für Deine informativen Seiten hier:
Vielleicht sollte man einmal auf die Wichtigkeit des “Seed”, des Startwertes eines Zufallsgenerators hinweisen: Ist dieser 1 Byte groß (256 verschiedene Werte), dann hält sich sämtlich nachfolgende “Zufälligkeit” auch auf 256 verschiedene Zufallswert-Folgen begrenzt. Wer “viel” Zufall will, der benötigt auch viele, viele verschiedene Seeds. Vom Generator selbst noch gar nicht gesprochen (Ebenenbildung,…).
Hi. Ich will möchte Dummheit hier schreiben, aber ich denke unter rndSIDInit: müsste das Low-Byte “$D40E” sein, oder? An der Funktion scheint es aber aus optischer Sicht nichts zu ändern.
Cool, gut gesehen und vollkommen richtig.
Das Low-Byte für die Frequenz gehört nach
$D40E
.Hier hat es, wie von dir erwähnt, zwar keinen direkten Einfluß auf die Funktionsweise, das Programm sollte aber schon korrekt sein.
Danke für den Hinweis, habe es korrigiert.