Hallo,
Ich suche für mein derzeitiges Projekt eine brauchbare Routine, die Zufallszahlen zwischen 0-10 liefert.
Zufallszahlen in ASM wurden hier ja schon öfters diskutiert und ich habe auch schon mit mehreren Routinen rumgetestet.
Die naheliegende Lösung mit Branches (cmp#0 /cmp#10) den Bereich zu wählen und die Funktion solange anzuspringen bis die Zahl in diesem Bereich liegt liefert nicht den gewünschten Erfolg, da das natürlich jedesmal unterschiedlich lange dauert was zu einer 'Unwucht' in der Mainloop führt.
Vielleicht hat ja jemand hier im Forum eine Idee.
Hallo Besucher, der Thread wurde 13k mal aufgerufen und enthält 102 Antworten
letzter Beitrag von Hanno Behrens am
RND-Zahlen von 0-10 in ASM
- mactron
- Erledigt
-
-
der weg den du beschreibst ist aber der einzige weg um gleichverteilte zufallszahlen in einem vorgegebenen bereich zu kriegen, bei jeder anderen methode würden manche zahlen häufiger vorkommen als andere.
(nein, ist natürlich falsch. die "richtige" methode wäre zufallszahlen im fliesskommaformat im bereich von 0 bis 1 zu erzeugen, und diese mit einer konstante zu multiplizieren so das du auf den gewünschten wertebereich kommst..... auf dem c64 allerdings eher nicht so wahnsinnig praktikabel =))
wofur genau brauchst du denn diese zufallszahlen? ist es wirklich wichtig das die werte gleichverteilt sind? ansonsten funktioniert folgendes ganz gut:
- erzeuge eine 256 bytes grosse tabelle in denen alle werte aus dem gewünschten wertebereich (ungefähr) gleich oft vorkommen
- erzeuge zufallszahlen von 0 bis 255
- nimm diese zufallszahl als index auf diese tabellewenn es nicht wirklich "perfekte" zufallszahlen sein müssen ist das (finde ich) noch die praktikabelste möglichkeit.
-
Ist für ne 'bomben-fall-routine', die eben an 10 verschiedenen Positionen ne bombe werfen soll.
Ich denke mal dafür ist deine Lösung gut geeignet.
Genial einfache Methode, wäre ich gar nicht drauf gekommen.
Ich werde das mal ausprobieren und das Ergebnis hier bekanntgeben. -
So, habe die Theorie mal umgesetzt. Hier der Source-Code:
Code- ; RND-Zahlen zwischen 0-10 in ASSEMBLER erzeugen
- ; Complier: ACME
- ; Author: Mactron
- ; Datum: 02.12.2007
- ;
- !to "rnd10.prg",cbm
- ;
- *=4096 ; SYS 4096 / Startadresse
- ;
- ldy #0 ; Ausgabe bei 1024 beginnen
- ;
- rnd255 lda $dc04 ; Zufallszahl zwischen 0 und 255 erzeugen
- eor $dc05
- eor $dd04
- adc $dd05
- eor $dd06
- eor $dd07 ; liegt im Akku
- ;
- tax ; Akku(Zufallszahl von 0 -255) nach X damit er als Index benutzt werden kann
- lda rndtab,x ; Per X-Index den Wert aus Tabelle in Akku holen
- ;
- sta 1024,y ; ganz billige Bildschirmausgabe des Wertes als Zeichen zwischen @ und J
- iny ; nächstes Zeichen an 1025, unsw...
- cpy #255 ; schon 255 mal durchlaufen ?
- bne rnd255 ; nein dann nächsten Wert berechnen lassen
- ;
- rts
- ;
- rndtab !byte 0,3,5,7,2,8,9,1,4,10,6 ; Tabelle mit Werten zwischen 0-10
- !byte 1,2,3,4,5,6,7,8,9,10,0 ; Tabelle ist 256 Byte lang
- !byte 10,9,8,7,6,5,4,3,2,1 ; muss nochmal überarbeitet werden,
- ;
- !byte 0,3,5,7,2,8,9,1,4,10,6 ; musste schnellgehen ;-)
- !byte 1,2,3,4,5,6,7,8,9,10,0
- !byte 10,9,8,7,6,5,4,3,2,1
- ;
- !byte 0,3,5,7,2,8,9,1,4,10,6
- !byte 1,2,3,4,5,6,7,8,9,10,0
- !byte 10,9,8,7,6,5,4,3,2,1
- ;
- !byte 0,3,5,7,2,8,9,1,4,10,6
- !byte 1,2,3,4,5,6,7,8,9,10,0
- !byte 10,9,8,7,6,5,4,3,2,1
- ;
- !byte 0,3,5,7,2,8,9,1,4,10,6
- !byte 1,2,3,4,5,6,7,8,9,10,0
- !byte 10,9,8,7,6,5,4,3,2,1
- ;
- !byte 0,3,5,7,2,8,9,1,4,10,6
- !byte 1,2,3,4,5,6,7,8,9,10,0
- !byte 10,9,8,7,6,5,4,3,2,1
- ;
- !byte 0,3,5,7,2,8,9,1,4,10,6
- !byte 1,2,3,4,5,6,7,8,9,10,0
- !byte 10,9,8,7,6,5,4,3,2,1
- ;
- !byte 0,3,5,7,2,8,9,1,4,10,6
- !byte 1,2,3,4,5,6,7,8,9,10,0
- !byte 10,9,8,7,6,5,4,3,2,1
-
Wo das grad mit der 0..1 erwähnt wurde: Eine leicht angepasste 16Bit-Multiplikation wäre ein bisschen langsamer als die Tabelle, würde aber Platz sparen.
-
Zitat
Eine leicht angepasste 16Bit-Multiplikation wäre ein bisschen langsamer als die Tabelle, würde aber Platz sparen.
ein "bischen" langsamer....naja
-
Kann man nicht einfach irgendwo ins "Rauschen" greifen und ein paar Bits maskieren ?
Michael
-
wie genau kommst du durch ausmaskieren von bits auf einen wertebereich von 0-10 ? (brauchbares "rauschen" kann man davon ab auch nur am sid abgreifen, der ja in der regel musik spielen soll)
-
Ich habe das ganze jetzt mal in mein Programm eingebaut und siehe da: Es fluppt prima :-).
Damit wäre das Problem an sich gelöst und ich habe wieder was dazugelernt. Ist aber ein interessantes Thema.
Ich werde mir mal im Romlistning ansehen wie der Basic-Interpreter das macht. (Falls ich schlau draus werde) -
basic macht es soweit ich mich erinner "richtig"....also ein generatorpolynom das floatingpoint zahlen von 0 bis 1 ausspuckt.
-
Hi,
fuer den fall das das heir jemanden interessiert, ich hab' mal 'ne routine geschreiben, die 8bit zahlen liefert, die sich erst alle 64k wiederholen, nicht soo schnell ist, aber es ist halt wie ueblich ein seed, der dann immer die selben "zufallszahlen" liefert, was manchmal sehr praktisch seinen kann. bei interesse suche ich sie heraus, und poste sie hier.
Ciao, ALeX.
-
Zitat
ie 8bit zahlen liefert, die sich erst alle 64k wiederholen,
? wie kommst du mit 8 bit auf mehr als 2^8 möglichkeiten ? du meintest warscheinlich die periodenlänge oder?
-
Zitat
Original von sauhund
? wie kommst du mit 8 bit auf mehr als 2^8 möglichkeiten ? du meintest warscheinlich die periodenlänge oder?Ja, erst nach 64k kommen die gleichen muster wieder (die gleiche zahl haeufiger) also das koennte man wohl periodenlaenge nennen...
die periodenlaenge war mir wichtig, da die schnellen periodischen zufallszahlen sich alle 256 zeichen wiederholen (sogar einige 16bit randoms wiederholen sich alle 256!!). -
Es gibt verschiedene Methoden für die Aufgabe. Dabei ist aber als erstes wichtig, was der Zweck von deiner Zufallsroutine sein soll? Für Kryptographie sind etwa ganz andere Sicherheitsbestimmungen nötig als für ein Game. Und die "Rauschgeneratoren" aus dem C=64, die üblicherweise genommen werden sind entweder Rauschen vom SID oder "Rauschen" von CIA-Timern -wie unten gerade vorgeschlagen- sowie "Rauschen" von Rasterzeilen oder Rauschen von Potis oder Rauschen von Lichtgriffel-Registern.
Das alles sind Eingaben von Hardwarerauschen und für Zwecke der Kryptographie sind die alle für sich allein genommen mehr oder weniger Schrott wert. Das fängt schon damit an, wenn du diese Werte mal in Abhängigkeit voneinander nimmst. Also teste mal point(rnd()*320, rnd()*200) auf Grafik. Du wirst schnell feststellen, dass die Zufallsroutinen vom C=64 dort eben keine gleichmäßig verteilten Flächen ergeben, sondern Punkthäufungen. Und das ist für Krytozwecke ganz schlecht.
Deshalb sind diese Quellen nicht gleich Mist, aber du musst die Quellen eben auf jeden Fall noch durch einen starken Rauschalgorithmus jagen. Auch das C=64 Rauschen per Polynom ist ein mieser Algorithmus. Und ich sage "mies" weil es mir möglich war schon zu Beginn meiner Experimente mit Kryptographie Zufallsketten, die aus diesem Generator stammen nach wenigen Werten vorherzusagen.
Deshalb nimm statt der gegebenen Algorithmen lieber einen der starken bekannten Algorithmen und benutze die. Ein starker Algorithmus ist zum Beispiel der Mersenne Twister, verbreitet sind ansonsten Algorithmen, die auf Box-Muller-Verfahren basieren.
Am Ende musst du wissen, was du willst? Einen schnellen, schlechten Algorithmus, einen guten, langsamen oder ein hingewurschtel mittels der schlechten Zufallsgeneratoren, die dir die Hardware im C=64 zur Verfügung stellt? Mein Tipp ist in jedem Falle eine etwaige Hardwarequelle noch mit einer algorithmischen Ausgangsverwürfelung zu versehen, also zumindest einem Hashalgorithmus. Denn selbst für das billigste Spiel sollte dein Zufallswert für einen einfachen 2D-Test wie oben vorgeschlagen funktionieren. Oder das Spiel fängt an zu sucken.
Sobald du mehrere Folgewerte hast und du immer noch Unabhängigkeit erwartest, wird es immer schwerer und schwerer einen guten Algorithmus hinzubekommen. Sprich wenn du Würfelwürfe 1-10 hast, muss die Wahrscheinlichkeit von 10 hintereinander gefallenen 10ern statistisch hinkommen. Und bei solchen Abhängigkeiten versagen die meisten einfachen Algorithmen.
-
Da will jemand ne einfache Methode, um auf einen 8bit, 64k, 0.98Mhz Rechner ein paar Zufallszahlen für sein Spielchen zu generieren und Du kommst hier mit Mersenne Twister...
-
vor allem nutzt man nichtmal auf deutlich leistungsfähigeren geräten wesentlich bessere algos in spielen. in den allermeissten fällen ist es in einem spiel nämlich völlig egal ob irgendein wert ein bischen häufiger vorkommt. und noch dazu *will* man grade "vorhersagbare" zufallszahlen in einem spiel, weil man es nur so ordentlich debuggen kann. (hint: die allermeissten spiele simulieren keine würfel oder roulette oder sowas)
-
Vorhersagbare Zufallszahlen, da würde ich ein LFSR für nehmen.
-
btw,
soweit ich weiss ergibt rnd für gfx 320x200 sehr wohl ausreichende zufällige Verteilung!
Und zwar echt übers Frequenzspektrum!
Zufall ist NICHT alle Pixel gleichmäßig verteilt -
Naja, was heißt vorhersagbar? Vorhersagbar, damit meine ich nicht "deterministisch". Deterministische Algorithmen sind natürlich vorhersagbar, wenn man den kompletten Seed kennt. Doch kennt man vom Seed nur einen Teil und wird nur dieser Teil als Zufallswert benutzt, dann wird die Vorhersage eben schwieriger.
Bei einer sich schon nach 256 Werten wiederholenden Folge ist das für ein Kartenspiel beispielsweise verflucht schlecht. Deshalb meine Frage, wozu der Algorithmus verwendet werden soll. Bei einem Kartenspiel beispielsweise würde der Random-Algorithmus die Karten durchmischen. Sagen wir, typischerweise bei Blackjack haben wir 2*52 Karten im Stapel. Typischerweise legt man einen 104 Byte großes Array an, packt alle Karten da rein und beginnt per Random die n und x zu vertauschen und zwar n=1..103 und x=n+1+rnd()*(104-n) bei rnd()=0..1)
Das bedeutet, wir haben 103 von einander abhängige Zufallswerte (abhängig heißt, wenn sie nicht unabhängig sind, sind nicht alle möglichen Kartenverteilungen möglich). Nehmen wir an, dass wir einen Algorithmus mit einer Periode von 256 Werten hätten, dann haben wir nur 256 mögliche Blattverteilungen. Und diese Verteilungen sind dann auch noch extrem wiederkehrend.
Und das Spiel würde megasucken.
Daher mein Einwurf auf die benötigte Stärke. "Spiel" bedeutet ja nicht gleich, dass es nur um das Auftauchen eines Sprites geht. Es gibt eine Menge Spiele, die ohne eine starke Zufallsroutine überhaupt keinen Sinn machen.
Wenn die Zufallswerte von einander unabhängig sind, gibt es keine Häufungen auf 320x200 bei x=rnd() und y=rnd(). "Weisse" Algorithmen streuen schön verteilt und es gibt keine Pixelhaufen. Macht man das allerdings mit dem Basic-Random... Naja, kann ja jeder selbst ausprobieren. Muss man nichts zu sagen. Und ich rede hier nur von einer 2fachen Abhängigkeit, also Abhängigkeit von x und y also rnd(n) und rnd(n+1). Das ist ein geringer Anspruch. Oben genannte Kartenmischung ist da sehr viel anspruchsvoller. Einer der Gründe, warum viele Kartenspiele auf dem C=64 gesuckt haben. Und einige Spiele. Wie hieß nochmal der Flipper damals? Schlechte Randomisierung, das weiss jeder, der länger damit gespielt hat.
Und auch die Hardware-Randomgeber sind nicht wirklich unabhängig und schon gar nicht gleichverteilt "weiss". Wäre das so einfach, würds deswegen nicht so ein riesiges Gewese geben, schätz ich. Und die Randomgeber von Windows XP/2000 und sogar von Linux hätten nicht gerade vor einer Woche einen Rüffel gekriegt...
-
Zitat
Vorhersagbare Zufallszahlen, da würde ich ein LFSR für nehmen.
genau das wird bei den meissten spielen benutzt und der reicht auch locker für ein kartenspiel wenn man ihn nicht grade nur mit 8 bit macht bei 32bit ist die periodenlänge schon lang genug das man den wraparound wohl nicht mehr in diesem leben erlebt ;=)
bei sowas wie einem kartenspiel ist viel wichtiger als der generator ansich das der seed halbwechs zufällig ist. bei spielen nimmt man da typischerweise irgendeinen zähler abhängig von irgendeiner benutzereingabe (zeit die vergeht bis "start" gedrückt wird oder sowas).
(wofür braucht man denn bei einem flipper grossartig zufallszahlen? *kratz*)