Random-Seed-Funktion zur Kartengenerierung?

28

Ich suche nach einer Funktion zum Erzeugen einer zufälligen kachelbasierten Karte, wenn sich die visuellen Grenzen der Karte ändern (indem ich durch die Karte gehe). Ich möchte, dass die Karte unendlich groß ist und eine labyrinthartige Struktur hat.

Wenn die Welt jedoch unendlich ist, wirft es ein Problem auf, dorthin zurückzukehren, wo ein Spieler schon einmal war. Das Spiel muss sich daran erinnern, wie alles dort hinten tatsächlich aussah.

Also dachte ich: "Wie löst Minecraft dieses Problem?" und ich dachte mir, dass sie eine Art Zufallszahlenfunktion mit einem Startwert verwenden müssen, die sowohl vorwärts als auch rückwärts gehen kann und auf diese Weise alte Kacheln genauso wie sie waren, aber in neuen Fällen neu erzeugt.

Was denkst du darüber?

Mathias Lykkegaard Lorenzen
quelle
Wie ist es, dass meine Antwort bei +5 ist und die Frage nur bei +2 ist? Dies ist derzeit eine der besten Fragen auf der Titelseite.
2
Speichert Minecraft nicht einfach die Chunks, die Sie bereits besucht / geändert haben?
FxIII
@FxIII: Minecraft muss, weil man die Landschaft verändern kann. Wenn Sie das nicht tun können, ist das Lagern der Stücke wahrscheinlich eine Verschwendung oder zumindest eine Überkomplikation.
@ Joe Wreschnig: Ok, ok ... ich hatte Angst, dass ich etwas wirklich Großes verpasst habe!
FxIII

Antworten:

20

Was Sie bemerkt haben, ist der Unterschied zwischen einem Zufallszahlengenerator und einer Rauschfunktion . Ein Zufallsgenerator spuckt bei jedem Anruf eine andere Zahl aus. Eine Rauschfunktion verwendet einige Argumente - beispielsweise eine Map x und y - und gibt Zahlen mit zufallsähnlichen statistischen Eigenschaften aus , jedoch jedes Mal denselben Wert für dieselben Argumente , dh es handelt sich um eine geeignete mathematische Funktion.

Die beiden sind sehr eng miteinander verbunden. Eine Rauschfunktion kann einen Zufallszahlengenerator, simulieren , indem jedesmal in einem anderen Wert Passing - zB noise(1), noise(2)und so weiter. Und ein Zufallsgenerator, der in einen riesigen Tisch geworfen wird, kann als Rauschfunktion fungieren. In beiden Fällen verwenden Sie jedoch das falsche Werkzeug für den Job.

Minecraft verwendet insbesondere Perlin-Rauschen , eine Art von Rauschen, das kostengünstig zu berechnen ist und die wünschenswerte Eigenschaft hat, in so vielen Dimensionen kontinuierlich zu sein, wie Sie benötigen. Wenn Sie grafisch darstellen f(x), f(x + 1)treten keine plötzlichen Sprünge auf. Dies macht es sehr nützlich für viele Dinge wie Texturmodulation, volumetrische Wolken und Gase und Geländegenerierung.

Wenn Sie nach einer Implementierung suchen, mit der Sie gleich loslegen können, ist Ken Perlins verbesserter Perlin-Rauschgenerator eine der einfachsten Implementierungen.


quelle
3
Beachten Sie, dass viele Zufallszahlengeneratoren einen Startwert verwenden und bei gleichem Startwert denselben Satz von Zahlen generieren.
Thedaian
3
@ thedaian: Was in diesem Fall nicht besonders nützlich ist, es sei denn, Sie möchten jede Zahl neu generieren. Mit einer Noise-Funktion können Sie die 500. Nummer ermitteln, ohne vorher 499 generieren zu müssen.
Ist es möglich, den Perlin Noise-Algorithmus zu kalibrieren? Bedenken Sie, dass der Algorithmus mit größerer Wahrscheinlichkeit ein Paket von Wandfliesen und dann ein Paket von Raumfliesen erzeugen soll.
Mathias Lykkegaard Lorenzen
3
Sie haben die Links, die ich in sechs Minuten gegeben habe, nicht gelesen und verstanden.
1
Diese Antwort wäre gewesen , komplett mit Notch Blog - Post: notch.tumblr.com/post/3746989361/terrain-generation-part-1
deceleratedcaviar
3

Die Art und Weise, wie Minecraft seine Erzeugung steuert, besteht darin, einen Level-Startwert zu erstellen, mit dem die gesamte Zufallszahlenerzeugung für das Spiel festgelegt wird. Wenn ein Block auf der Festplatte nicht vorhanden ist, wenn er angefordert wird, wird er mithilfe der Notch- Generierungsfunktion basierend auf dem Startwert des Levels generiert . Es wird dann für später auf der Festplatte gespeichert .

Es hört sich so an, als ob Sie ein ähnliches Verhalten anstreben. Das ist also ein sicherer Weg.

Keeblebrox
quelle
2

Joe hat darauf hingewiesen, dass Sie nach einer Hash-Funktion suchen. Im Allgemeinen sind Zufallsfunktionen nur Hash-Funktionen, die mit der zuletzt zurückgegebenen Zahl erstellt wurden. Also , wenn Random()zurückgegeben Hash(seed)=1234, ein zweiter Anruf Random()zurückkehren würde Hash(1234), um so weiter.

Wenn Sie nach einer einfachen Hash-Funktion für Pseudozufallszahlen suchen, schauen Sie sich MurMurHash an . Ich habe es in C # implementiert und kann es bei Interesse irgendwo posten. Ausführlichere Informationen zu Perlin Noise, das eine solche Hash-Funktion verwendet, finden Sie hier . Eine Implementierung in C # finden Sie hier .

All diese Informationen stammen aus einer Frage, die ich vor einem Jahr hier bei Stack Overflow gestellt habe. Was Sie sich ansehen, wird als prozedurale Inhaltsgenerierung bezeichnet. Wenn Sie also mehr Informationen benötigen, suchen Sie danach. Viel Spaß beim Erstellen von Terrains!

dlras2
quelle
-1. Der Hash von Perlin-Rauschen hat keine Ähnlichkeit mit den Techniken, die in MMH oder anderen kryptografischen Hash-Routinen verwendet werden. dieser C # -Code ist Müll, der scheinbar nur eine lineare Interpolation zwischen Zufallswerten durchführt; es benötigt viel mehr Speicher als richtiges Perlin-Rauschen und läuft wahrscheinlich langsamer.
1
@ Joe - Es tut mir leid, dass Sie Ihre Implementierung von Perlin Noise so ernst nehmen. Perlin Noise ist selbst ein Konzept, bei dem eine Hash-Funktion in eine kontinuierliche Rauschfunktion umgewandelt wird. Ich habe mit MurMurHash sehr effektiv viele Perlin-Geräusche erzeugt. Der C # -Code ist ein Beispiel für die programmgesteuerte Bestimmung des Werts eines einzelnen Punkts in 2D-Perlinrauschen. Ich würde es nie in der Produktion verwenden, aber es ist meiner Meinung nach einfacher zu durchlaufen als der Code, den Sie gepostet haben.
dlras2
1
Das OP hatte keine Kenntnis von Lärm oder Hashing, daher habe ich lediglich versucht, Referenzen zu liefern, in der Hoffnung, dass sie weiter nachforschen und selbst entscheiden, wie sie das umsetzen sollen, was sie tun müssen.
dlras2
"Perlin Noise ist selbst ein Konzept, eine Hash-Funktion in eine kontinuierliche Rauschfunktion umzuwandeln." Nein, Perlin-Rauschen ist eine der von Ken Perlin erfundenen Funktionen für kontinuierliches Rauschen (und nicht die, die er "Simplex-Rauschen" nennt). Nicht alle Funktionen für kontinuierliches Rauschen sind Perlin-Rauschen. Nicht alle Funktionen für kontinuierliches Rauschen sind gleichmäßiges Gradientenrauschen, wofür Perlin-Rauschen ein besonderes Beispiel darstellt. Das, mit dem Sie verbunden sind, ist kein Gradientenrauschen, sondern ein Wertrauschen.
Der Code in Ihrem Link ist "leichter zu durchlaufen", da es sich nicht um Perlin-Rauschen handelt. es ist nicht so glatt; es verbraucht weit mehr Ressourcen; Kurz gesagt, es ist einfacher zu durchlaufen, weil es dümmer ist.