Erstellt: 12. Mai 2013 (zuletzt geändert: 1. Januar 2018)

Zufallszahlen in Assembler

Zufallszahlen in Assembler erzeugen

C64 Studio, AMCE & TASM

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).

Die Zufallszahlen-Routine von Boulder Dash.
Die Zufallszahlen-Routine von Boulder Dash.

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.


Schrott!!Naja...Geht so...Ganz gut...SUPER! (16 Bewertungen | Ø 5,00 von 5 | 100,00%)

Loading...


Zurück

3 Gedanken zu „Zufallszahlen in Assembler“

  1. 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,…).

  2. 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.

    1. 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.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Protected by WP Anti Spam