Ich habe diese Frage erst kürzlich gestellt und die Schlussfolgerung scheint zu sein, dass es nicht wirklich gelungen ist, genetische Programmierung ( GP ) für die Erstellung prozeduraler Spielinhalte zu verwenden. Ich möchte das ändern.

Ich bin mir ziemlich sicher, dass GP eingesetzt werden könnte, um einen neuen Geländegenerator zu finden. Die Frage, auf die ich komme, ist, wie dies erreicht werden kann.

Alle Hausärzte haben einige grundlegende Teile, die für alle Hausärzte verallgemeinert werden können (Elternselektion, Rekombination, Mutation, Überleben). Ich kann das selbst herausfinden. Das Problem tritt in den problemspezifischen Teilen auf. Auf diese Weise stellen Sie das Problem im Code dar (normalerweise wird ein Baum verwendet) und bewerten, wie gut ein Generator sein kann (dies können ein oder mehrere Werte sein).

Die Fragen auf den Punkt gebracht:

• Wie würden Sie einen Geländegenerator so darstellen, dass er in einen Baum zerlegt werden kann?
  

• Welches Terrain müsste das erzeugen? (Höhenkarte, Scheitelpunktdiagramm, ...)
  

  Je weniger dies auf einer Hightmap basiert, desto besser.
  

• Was würde verwendet, um die Eignung einer Lösung zu bewerten?
  

  Beispiel: Wir möchten ein interessantes Terrain, damit einer der Werte die durchschnittliche Änderung der Normalen für jeden Scheitelpunkt im Terrain ist.

Vielleicht haben Sie etwas Glück mit einem Ansatz , der den genetischen Bildern von Karl Sims ähnelt .

Er verwendet eine einfache Menge von Operatoren in einer LISP-ähnlichen Sprache, so dass die Ausgabe jedes Operators verwendet werden kann, um das Bild zu beeinflussen, ähnlich wie in einigen Shader-Sprachen (dh ein Skalar wäre ein Graustufenwert, ein vector3wäre RGBusw.). ).

Obwohl ich denke, dass das Implementierungsmaterial ist, möchten Sie wahrscheinlich seine Schlüsselwörter, die (iirc) alle Grundlagen enthalten:

• Triggerfunktionen ( sin, cos, tan, etc ..)
• position ( x, y)
• grundlegende mathematische Operatoren ( sqrt, pow, abs, inverse)
• Rauschfunktionen ( fBm, noise2, noise3)
• andere fraktale ( mandelbrot, julia)
• Interpolationsfunktionen ( lerp, quad, step, smoothstep)

(Einige der oben genannten Punkte sind möglicherweise nicht in seiner Implementierung enthalten. Ich habe seine Arbeit vor langer Zeit gefunden und tatsächlich ein paar Versuche unternommen, was Sie im Laufe der Jahre beschrieben haben - so dass möglicherweise Erinnerungen verloren gehen :)

Interessant (und schnell) bleiben

Ich hatte ein bisschen Glück mit einem vielschichtigen Ansatz, der die Anzahl toter Entwicklungen massiv reduzierte.

1. Für jeden Operator wird eine Reihe von Bereichen generiert (oder aus vorherigen Runden mutiert).
   • Diese halten die Werte idealerweise innerhalb eines "vernünftigen" Bereichs für jede Funktion, können sich jedoch zu Bereichen entwickeln, die überraschend nützliche Ergebnisse liefern, was als "richtig" erscheint
2. Generiere ein paar Algorithmenbäume
   • für jede dieser generieren Sie ein paar Höhenkarten an zufälligen Positionen und bewerten Sie die Fitness
   • Wenn wir viele gute Übereinstimmungen haben, entwickeln Sie diesen Zweig etwas weiter und stören dabei die Bereiche von Schritt 1 bei jedem Kind geringfügig
   • Andernfalls haben wir wahrscheinlich schlechte Reichweiten. Kehren Sie zu Schritt 1 zurück

Jedoch...

Jetzt habe ich den Fitness- Algorithmus übersprungen. Ich habe hauptsächlich Karl Sims Ansatz der "unnatürlichen Selektion" verwendet, bei dem Sie die aktuelle Generation auf dem mittleren Feld einer Gruppe von Nachkommen sehen (damals bekannt durch Kai's Power Tools) ein bild von dem was ich meine ) ..

Allerdings könnten Sie wahrscheinlich eine Reihe von Trainingsbildern haben, möglicherweise einige aus Satellitenbildern und einige künstliche Bilder mit bestimmten Qualitäten, und dann möglicherweise eine Wavelet- oder 2D-FFT-Analyse auf ihnen im Vergleich zu dem Gelände, das Sie testen?

Dies ist ein interessantes Thema, aber ich bezweifle, dass Sie eine Antwort auf :) brauchten

EDIT: ahh. musste eine Reihe von Links entfernen, weil ich ein neuer Benutzer bin: - |

Ich bin mir nicht sicher, ob Sie diese Frage beantworten können, aber ich fühle eine Erklärung, warum diese Antwort hilfreich genug sein könnte. Also, Antworten auf den Punkt gebracht:

• Sie möchten eine Geländegeneration auswählen, bei der bestimmte Aspekte einfach auf Datenwerten basieren können. Dies ist nicht schwierig, erfordert jedoch die Auswahl einer Geländegeneration. Da der Bereich, in dem ich arbeite, in der Voxelerzeugung liegt, sind Dinge wie Abtastraten, Tunnelpässe, Höhenstufen usw. Dinge, die in Daten eingefügt und "weiterentwickelt" werden können.
• Art geht Hand in Hand mit dem ersten Teil. Es spielt keine Rolle, mit welcher Generationsform Sie arbeiten, solange Sie verschiedene Eigenschaften festlegen können. Diese Wahl sollte mehr mit der Art des Spiels zu tun haben, das Sie machen möchten.
• Hier bricht es zusammen. Ich kann mir keinen Weg vorstellen, dies zu messen, abgesehen von einer Person, die tatsächlich die Welt betrachtet und sagt: "Oh, das ist schön". Dadurch wird jedoch der Computer entfernt, der seine eigene Iteration ausführt. Dies impliziert auch, dass Sie diese Form der Generierung verwenden werden, um am Ende eine einzige Welt zu erschaffen, die nach der 'besten' Welt sucht und nicht jedes Mal nach einer zufälligen.

Genetische Algorithmen werden normalerweise verwendet, um ein bekanntes Problem zu lösen, bei dem Sie die Umgebung durch Regeln definieren können. Anschließend können Sie Datensätze erstellen, die verschiedene Eigenschaften darstellen, die sich darauf auswirken, wie die Dinge auf die Regeln reagieren. Der Computer spielt dann eine "Runde" mit dem ursprünglichen Datensatz, wählt die oberste X - Zahl aus, mischt ihre Werte nach dem Koppeln und führt eine weitere Runde durch Finde eine Reihe von Werten, bei denen der Troll im Allgemeinen in seiner Umgebung sehr gut abschneidet (Kann jagen und fressen, töten oder sich von Dorfbewohnern fernhalten, Beute sammeln und all die glänzenden Gegenstände anhäufen, die er wünscht usw.).

Ich bin mir einfach nicht sicher, was Sie erreichen wollen, wenn es um die Geländegenerierung geht. Das Einzige, was ich mir einfallen lassen kann, sind Bewertungen von Spielinhalten, bei denen Sie keine Welt planen wollten, sondern eine erstellen wollten, in der AI-Pfade gut berechnet werden können. Trotzdem suchen Sie nach einer einzigen oder zumindest einer begrenzten Anzahl von Welten.

Welches Terrain müsste das erzeugen? (Höhenkarte, Scheitelpunktdiagramm, ...)

Definitiv ein Vertex-Graph (ein Mesh), ist er kompakt in Bezug auf den Speicher und kann bei Bedarf gerastert (tesseliert) werden.

Wie würden Sie einen Geländegenerator so darstellen, dass er in einen Baum zerlegt werden kann?

Zelluläre Automaten. Ich kann mir zwei Implementierungen vorstellen:

1. Regelsatzautomaten, möglicherweise mit Elementen von endlichen Automaten (wenn der aktuelle Status, wie Versuchszähler oder Leerlaufzeit, berücksichtigt wird).

   • Jeder Knoten wird mit einem zufälligen Zustand initialisiert
   • Jedem Knoten ist eine Instanz des Lösers zugeordnet
   • Jeder Solver berechnet so lange den nächsten Zustand, bis ihm die Regeln ausgehen oder er seinen idealen Zustand erreicht (hier bin ich fertig).
   • Alle nächsten Zustände werden zuerst berechnet und dann sofort angewendet, bevor die nächsten Berechnungen beginnen, sodass die Berechnungsreihenfolge keine Rolle spielt

Regelsatz selbst kann als Verzweigungsentscheidungsbaum oder einfacher Befehlsstapel dargestellt werden (nicht sicher, ob er funktioniert)

Es ist nur ein Regelsatz für jeden Knoten

2. Weltenbauer. Anstatt einen Solver für jeden einzelnen Knoten anzuwenden, können Sie nur eine Reihe von Solvern erstellen und ihnen erlauben, durch das Netz zu navigieren.

   • Jeder Builder hat einen eigenen Regelsatz
   • Verhindern Sie, dass sie den von einem anderen Builder belegten Knoten betreten
   • Jeder Builder kann als Zweig des Baums dargestellt werden
   • Während der Evolution können Builder duplizieren

Trotzdem befürchte ich, dass der zweite Ansatz vom ersten unterstützt werden muss: Die anfängliche Zufälligkeit muss geglättet werden, und ich bin nicht sicher, ob die Bauherren den Trick machen können. Schließlich hat jede lebende Zelle Mitochondrien.

Was würde verwendet, um die Eignung einer Lösung zu bewerten?

Die Integrität des resultierenden Terrains - es sollte nicht wie ein Mischmasch aussehen. Und die Vielfalt - im Allgemeinen möchten wir, dass möglichst viele verfügbare Variationen dargestellt werden (die flache Einöde von einer Kante zur anderen macht keinen Spaß). Vielleicht etwas komplexeres wie die gegenseitige Anpassung benachbarter Knoten (Tundra mitten in der Wüste, was?)

Muss ich selber mit meinem Netzgenerator ausprobieren, wenn ich etwas Freizeit habe =)