Level Generierung

[AMatutat]

Wir haben schon ein paar mal besprochen, dass es für unsere Rätsel gut wäre, wenn wir Level aus Graphen generieren könnten.

In meiner Master-Arbeit habe ich das ganze schonmal umgesetzt.
Prinzipiell funktioniert das ganze auch, ist aber sehr sehr langsam. Liegt vor allem am Backtracking.

Die Generierung der Level aus einem Baum hingegen sollte relativ flott gehen. Dafür muss der Algorithmus natürlich aufgeräumt werden.
Außerdem muss das Ganze an das neue Dungeon angepasst werden.

Ich muss mir noch genau anschauen, WAS alles verändert/neu gemacht werden muss.

Gibt es ggf. alternativen die schneller Einsatzbereit sind?
Haben wir noch weitere Anforderungen an unseren Generator?

[malt-r]

Es ist in verschiedenen Diskussionen immer wieder die Idee von Teleporter-Türen aufgekommen (bspw. hier). Das ist auch relevant für die Levelgenerierung.

[AlexJ2017]

3D Dungeon (Isometrisch vs. "Fake-Schrägperspektive")

Nach dem ersten Schritt der Generierung liegt ein 2D Array des Levels vor, in dem die begehbaren Flächen sowie leere Felder (nicht Teil des Dungeons) eingetragen sind.
Um dem Dungeon mehr Tiefe zu verleihen, stand eine Veränderung der Ansicht auf die Spielfläche im Raum.

Isometrisch

Zum einen könnte das Spiel in einer Isometrischen Perspektive angezeigt werden, wie in diesem Beispiel.
Vorteile:

• relativ realistische 3D Ansicht der Level

Nachteile:

• Steuerung des Helden erfolgt entweder gedreht und damit parallel zu dem Tile-Grid (Taste rechts -> rechts unten, hoch, Taste hoch -> rechts oben, Taste links-> links oben, hoch, Taste runter -> links unten)
  oder Held bewegt sich schräg durch die Level
• Texturen für die Helden, Gegner, Objekte ... müssten in isometrischer Form vorliegen, da sie sonst sehr flach wirken.
• Wände im Vordergrund können Teile des Spielfeldes verdecken und müssen evtl. transparent dargestellt werden

Schrägperspektive

Alternativ kann das Level auch in einer Art Schrägperspektive angezeigt werden, in der nur die Wände des Dungeons perspektivisch dargestellt werden. Dadurch entsteht ein Gefühl von Tiefe, ohne großen Mehraufwand in der Darstellung der Level.
Es gibt verschiedene Möglichkeiten, diese Schrägperspektive umzusetzen. Eine Möglichkeit ist nur die hinteren Wände und die Türen des Levels darzustellen wie in diesem Beispiel. Eine andere Möglichkeit wäre die Darstellung aller Wände in Schrägansicht (Beispiel).

Die Wandtexturen müssten für die beiden unteren Möglichkeiten nur rotiert werden. Außerdem werden Texturen für die Ecken, Löcher und oder Säulen benötigt. Es sind außerdem schmalere Trennwände denkbar, welche statt der Löcher innerhalb der Räume eingesetzt werden könnten. Deren Darstellung könnte allerdings schwieriger sein, da viele Sonderfälle betrachtet werden müssen (mehr Texturen).

[AMatutat]

Die Isometrische Ansicht gefällt mir zwar optisch am besten, aber durch die aufgeführten Nachteile (und Sorge das sich dadurch noch mehr Probleme ergeben) bin ich für die Schrägperspektive wie im zweiten Beispiel.
Das scheint mir in der Umsetzung die wenigsten Fallstricke zu liefern, sollte gut mit unserem aktuellen System kompatibel sein und zusätzlich sieht es auch noch recht modern aus.

[AlexJ2017]

Ich habe mal das obige Beispiel mit den Texturen vom alten Dungeon nachgebaut, um zu sehen wie es aussieht.

[AMatutat]

unten links find ich spitze

[AlexJ2017]

Nachträglich können dann ja einige Wände noch durch Türen ersetzt werden, je nach Bedarf.

[AMatutat]

Single-Room Graphen Ansatz

Um diese Diskussion mal in eine konkretes Gerüst zu Giesen.

Konzept

Für viele unsere Ideen brauchen wir ein Graphenbasierte Levelstruktur (vgl. #6 (comment) und #6 (comment))

Wie in/unter #19 (reply in thread) besprochen, ist eine *Single-Room Lösung (brauchen wir ein Glosar?) zwar nicht die immersivste Lösung aber die einfachste in der Implementierung und zusätzlich erlaubt uns das einiges an Freiheiten.

Daher wäre die Idee einen Graphen zu generieren (entweder zufällig, oder per DSL Eingabe). Jeder Knoten ist ein Raum der generiert wird und jede Kante eine Tür zu einen nächsten Raum.

Graphen Generierung

Die Level-Graphen würde ich mit einer DOT-Ähnlichen Sprache beschreiben. Per DSL kann dann der genaue Graph übergeben werden, alternativ (quasi wenn die Struktur des Levels keine Rolle spielt) generieren wir eine Beschreibung.

Egal ob die Beschreibung per DSL oder Generator erzeugt wurde, aus dieser machen wir dann einen. Graphen.

Anforderungen:

• Beschreibungssprache für die Graphen
• Beschreibungsgenerator
• Umwandeln der Beschreibung in einen Graphen

Template/Raum Generierung

Für die Räume könnten wir Templates verwenden. Jedes Template gibt dabei die Größe und Form des Raums vor. Im Template selber könnte Platz für Mutation sein. In meiner Masterarbeit habe ich das so gemacht. Im Template gab es Wildcard-Flächen. Diese konnten dann durch Wildcard-Templates ersetzt werden. So hat man etwas mehr Abwechslung ohne sich die Mühe zu machen und viele Assets erstellt.

Anforderungen

• Anzahl der Türen (und Position der Türen?) muss konfigurierbar sein.
• Abwechslungsreich (evtl. ist das aber eher was für später und für den Anfang reicht uns eine Handvoll "Hardcoded" Räume)

Anbindung an das Dungeon

Hier gibt es einige Fallstricke denen ich mich langsam versuche zu stellen.
Meine Grundidee ist es, jeden Raum als TileLevel Objekt zu betrachten. Also so wie wir jetzt ein normales Level betrachten.
Ein GraphLevel ist dann eine Liste mit TileLevel und die Verbindungen dazwischen.

Probleme vor denen ich noch stehe

• Wie bindet man den GraphLevel an das ÌLevelbzwLevelAPI` an. Wir benötigen spezielle Abfrag-Methoden, welche andere Level nicht benötigen. (Vielleicht Not.Supported Exception und die Graphen Methoden auch ins Interface?)
• Wie stellt man am besten Sicher, dass die Türen in sich logisch sind. Geh ich von Raum A nach unten in Raum B, muss ich wenn ich in Raum B nach oben gehe wieder in Raum A landen

Pathfinding

Das libGDX Pathfinding, welches wir verwenden, geht immer von Tile zu Tile. Es sollte nichts dagegen sprechen, das Tür-Tile aus Raum A mit dem Tür-Tile aus Raum B zu verbinden. Das Pathfinding sollte weiter funktionieren.

tbd: Skizze

Perspektive

#19 (reply in thread)
Die Art und weise wie wir auf das Dungeon schauen, sollte für die Generierung egal sein, oder?