Deterministischer Pseudozufallszahlengenerator gesucht

[Florian H]

Aloha,

ich entwickle im Moment ein Spiel und möchte bei diesem Spiel "zufällig" Levels generieren können.
Bisher nutze ich dazu einfach ein Math.random() (Java), was mir eine double-Zahl zw. 0 und 1 liefert.
Jetzt habe ich mir aber überlegt, dass ich zwecks Vergleichbarkeit in einer Online-Highscore-Liste bei allen Spielern dieselben zufälligen Levels erzeugen will.

Deshalb möchte ich mir einen möglichst einfachen Pseudozufallszahlengenerator basteln, der je nach Startwert (Seed) eine Folge von bestimmten, aber eben zufällig erscheinenden, Zahlen zurückliefert. Setze ich den Startwert irgendwann wieder auf denselben alten Startwert, kommen dieselben "Zufalls"zahlen.

Da gibts natürlich hunderte Möglichkeiten, aber vielleicht hat ja schon jemand Erfahrung und kann wertvolle Tipps geben?
Wenn man "einfach mal so" aufm Papier sich was ausdenkt und das dann umsetzt, gibt das wohl keine wirklich guten Zahlen (Gleichverteilung, Wiederholungen, erkennbare Nicht-Zufälligkeit, ...). Andererseits will ich auch keine 20 Seiten Quellcode portieren, zumal es möglichst performant laufen sollte.


Schöne Grüße
flo

[FaTaLGuiLLoTiNe]

Zitat:

Zitat von Florian H

Deshalb möchte ich mir einen möglichst einfachen Pseudozufallszahlengenerator basteln, der je nach Startwert (Seed) eine Folge von bestimmten, aber eben zufällig erscheinenden, Zahlen zurückliefert. Setze ich den Startwert irgendwann wieder auf denselben alten Startwert, kommen dieselben "Zufalls"zahlen.

Ist das nicht schon genau das, was der Delphi-eigene PRNG (und jeder andere PRNG den ich kenne) macht?

//edit: Oh, ich sehe gerade: Java. Was der Zufallszahlengenerator von Java macht, weiss ich leider nicht. Sollte aber vom Prinzip her auch nichts anderes sein.

[Nikolas]

In Java:

Delphi-Quellcode:

import java.util.Random;
Random generator2 = new Random( 19580427 ); // irgendein long int als Seed

Wie man nachlesenkann, setzt math.random genau diesen Generator ein.

[himitsu]

Bei Java hast du aber ein Problem.

Da ja der "Zufalls"Generator der Java-Runtime-Library verwendet wird
und sich die Berechnung des Zufalls in verschiedenen Version der JRE unterscheiden kann,
kann es vorkommen, daß auf unterschiedlichen PCs auch eine unterschiedliche Zahlenfolge enstehen kann, selbt wenn der Startwert (Seed) gleich ist.

[Florian H]

Zitat:

Zitat von Nikolas

In Java:

Delphi-Quellcode:

import java.util.Random;
Random generator2 = new Random( 19580427 ); // irgendein long int als Seed

Wie man nachlesenkann, setzt math.random genau diesen Generator ein.

Danke, das ist perfekt :)

@himitsu: Hm, das ist natürlich ärgerlich .. muss mir da mal was überlegen. Aber im Moment reicht die Lsg von Nikolas vollkommen.

[himitsu]

im Prinzip kannst dir auch einfach einen eigenen bauen ... wie der von Delphi arbeitet, sieht man in einigen DP-Threads

[Apollonius]

Schaut doch mal in die Dokumentation zu java.util.Random:

Zitat:

If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers. In order to guarantee this property, particular algorithms are specified for the class Random. Java implementations must use all the algorithms shown here for the class Random, for the sake of absolute portability of Java code.

Mit anderen Worten: Der Algorithmus ist festgelegt und damit in allen VMs gleich. Das von himitsu angesprochene Problem besteht daher nicht.

[himitsu]

also wenn der Algo unveränderlich festgelegt ist, dann gibts da keine Probleme.

z.B. in der Delphi-Hilfe steht schon seit vielen Jahren, daß man den Generator aus soeinem Grund nicht für Verschlüsselungen nehmen so,
aber bis jetzt hat weder Borland noch Codegear oder Embarcadero da was umgebaut :roll:

[Cyf]

Ich würde dazu spontan mal mehr auf sowas wie lineare Abhängigkeit der Pseudozufallszahlen und die Tatsache, dass man den Algorithmus weiter- und rückrechnen kann, tippen. :wink:
Gute Zufallszahlen für Verschlüsslungen müssen möglichst viel Entropie aufweisen (also baut man sich am besten radioaktiv zerfallende Stoffe in den Rechner ein und errechnet sie daraus).

[omata]

Hier mal ein Vorschlag in Delphi...

[alzaimar]

omata, wenn Du nun noch den Unterschied zum Delphi-PRNG erklären könntest, wäre das ... :thumb:

[himitsu]

abgesehn davon, das TRandomClass nur maximal 256 (vermutlich weniger) Werte kennt und demnach recht schnell eine sich wiederholende Zahlenfolge liefern dürfte?

[gammatester]

Zitat:

Zitat von himitsu

abgesehn davon, das TRandomClass nur maximal 256 (vermutlich weniger) Werte kennt und demnach recht schnell eine sich wiederholende Zahlenfolge liefern dürfte?

Die 256 möglichen Ergebniswerte sind kein Problem (es gibt halt nur 256 mögliche Bytes). Deine Argumentation ist falsch, so falsch wie: Es gibt nur zehn Dezimalziffern, also sind alle reellen Zahlen rational, denn wie haben ja eine "recht schnell sich wiederholende Ziffernfolge".

Das eigentliche Problem ist, daß der Generator nur max. 2^8 interne Zustände hat. Und das ist auch ein Problem des Delphi-Generators mit seinen 2^32 Zuständen. Das ist einfach zu wenig für kryptographische Anwendungen, weil 2^32 Zustände einfach durch Bruteforce durchgetestet werden können. Selbst bei einem sonst "sicheren" Generator, was Delphi-Random als Linearer Kongruenzgenerator nun mal auch nicht ist.

Als einfachen kryptographischen Generator, der für viele Sprachen verfügbar ist, kann man ISAAC verwenden.

Gruß Gammatester

[omata]

Danke gammatester, wenigstens einer der es verstanden hat.

Im Übrigen ist die Rauschkette mit 255 Werten auch leicht erweiterbar, 255 Werte waren nur leichter zu testen, ob der Generator auch wirklich richtig arbeitet.

Warum redet ihr alle von einem "kryptographischen Generator"? Ich dachte es geht hier nicht um Verschlüsselung, sondern nur um einfachen (vorhersagbaren) Zufall.
Naja, war ja auch nur ein Beispiel, wie man in Hardware oder auch Software einen Zufallsgenerator realisieren kann.

[himitsu]

es bezog sich nur auf TRandomClass für sich alleine betrachtet und da stimmt es wohl,
aber was den anderen Generator (dessen Name mir grad nicht einfällt) betrifft, da könntet ihr schon recht haben.