Generische Höhle/Korridorsystem

[joggel]

Guten Morgen ZFX,

ab und an versuche ich ja mal weiter an meinem Spiel zu basteln.
Nun stelle ich mir die Frage, wie ich das Level (Höhlensystem) generiere. Modellieren kommt für mich irgendwie immer weniger in Frage.
Ich frage mich, ob es nicht möglich ist das generisch zu erzeugen. Quasi ein vorberechnetes Höhlen- oder Korridorsystem.
Ein Korridorsystem ist glaube ich noch relativ einfach, da es überwiegend aus geraden Flächen besteht, aber wie könnte man das denn bei einem Höhlensystem machen?
Hat jemand von Euch da eine Idee oder eine Quelle?

Gruß

[Matthias Gubisch]

Spontan fällt mir als Quelle dieser Artikel aus der GPU GEMS ein:

http://http.developer.nvidia.com/GPUGem ... _ch01.html

mit etwas Hirnschmalz lässt sich das auch so umbiegen dass da eine schöne Höhle entsteht.

Die größte Schwierigkeit aus meiner Sicht ist bei sowas immer es so hinzubekommen dass nicht alles gleicht bzw sich wiederhohlend aussieht.
Das fängt bei der Vertexerstellung an und hört beim Texturieren auf.

[joggel]

Autsch!!
Der Artikel sieht extrem schwierig aus.
Aber ich werd mal reinschauen. danke

[Matthias Gubisch]

Ist einfacher als es aussieht.

Im Grunde wird da nur ein generisch generiertes Terrain in eine 3D Textur gerendert, aus den Voxeln dann (mit Marching Cubes glaub ich) ein Mesh erzeugt und das Mesh dann texturiert, beleuchtet und gerendert.

Das erzeugen des Terrains it für dich erstmal der Hauptpunkt denke ich, im Prinzip ist das System ganz gut parametrisierbar, und man kann auch benutzerspezifische Areas recht einfach integrieren. Die Schwierigkeit für dich ist das ganze so zu parametrisieren dass eine entsprechend große Höhle entsteht, das hab ich noch nie probiert und auch auf die schnelle keinen Ansatz.

Der Rest ist geschenkt und du kannst imo 1:1 die implementierung daraus übernehmen. Irgendwo sollte sogar der Source zu finden sein, wenn nicht sag kurz bescheid dann schau ich ob ich die CD von dem Buch noch finde.

[joggel]

Aha. Na so verstehe ich das schon etwas besser.
Was ich mich nur gerade dabei frage:
Wenn diese ganze Generierung auf der GPU abläuft (Terrain durch Voxels und dann anschließend zu einem Mesh) komme ich da von der Applikation an die Meshdaten heran? Ich bräuchte die ja um bspw Kollisionserkennung mit dem Geleände durchzuführen...

Sorry wenn ich so frage, aber ich habe da NULL ahnung.

[joggel]

Ich habe mir gerade überlegt, dass ich doch auch ein Höhlensysem mit einem Voxeleditor "modellieren" und dann durch marching cubes-algorithmus dieses rendern kann. :)

[Spiele Programmierer]

Also eine Voxelstruktur zu generieren, die Höhlen beschreiben, stelle ich mir nicht besonders schwer vor. Ein guter Ansatz scheint mir dort ein Signed Distance Field zu sein. Im Prinzip eine Funktion, die zu jedem Punkt im Raum approximiert, wie weit er von der nächsten Höhlenwand entfernt ist. (Distanzen in der Wand sind negativ, deshalb "signed") Das kann man dann ganz einfach als Voxelfeld abbilden, in dem eine Distanz kleiner 0 für einen Block und eine größer 0 für ein leeres Feld steht.

Man braucht also eigentlich nur eine Signed Distance Field approximation, die eine Höhle beschreibt. Das schöne an Signed Distance Fields ist, dass man sie sehr leicht deformieren und kombinieren kann. Einige Funktionsbeispiele findest du zum Beispiel hier. Verschiedene Höhlenabschnitte kannst du mit Kugeln und Kapseln beschreiben und dann mit der "Blend"-Funktion weich verbinden. Zufälligkeit kannst du zur Höhle dann ganz leicht hinzufügen in dem du einfach zur Funktion am Ende ein wenig Noise hinzuaddierst.

Mit ein wenig Mühe sollte es auch möglich sein, den Abstand zu einem Bezier Spline zu approximieren.

[joggel]

@Spiele Programmierer
Danke für den Link. Sieht wirklich sehr interessant aus. Nur verstehe ich die Funktionen nicht recht. Kann sein das mir da das mathematische know-how fehlt...
Wieso geben diese Funktionene die du verlinkt hast _nur_ einen float-Wert zurück. Was ist das für ein Wert und was kann man damit machen?

[BaneBlack]

Hallo joggel,

vielleicht ist der Artikel für dich interessant: http://procworld.blogspot.de/2013/01/tile-genetics.html

Man könnte die vorgeschlagene Technik als Basis verwenden. So als Idee.

Liebe Grüsse,
BaneBlack

[Matthias Gubisch]

Das Signed Distance Field wird auch vor die Mesherzeugung in dem von mir verlinkten Artikel genutzt.

Das Höhlensystem modellieren und dann mit Marching Cubes das Mesh erzeugen und rendernd ist eine Möglichkeit, ausserdem gibt es Möglichkeiten die vom Geometryshader erzeugen Vertices, bzw das Mesh von der GPU zu lesen, dazu müsstest du allerdings in die Doku deiner API (OpenGL oder DX) schauen wie das genau geht.

Zum Link von Spieleprogrammierer:
Der Floatwert gibt dir an ob sich dein Punkt in dem Objekt, ausserhalb oder auf der Kante befindet.

Die Seite nimmt an dass die Objekte alle im Ursprung liegen also brauchst du vorher noch ein bischen Transformation.
Am beispiel der Kugle:

Code: Alles auswählen

float sdSphere( vec3 p, float s )
{
  return length(p)-s;
}

p ist dein Punkt im 3D-Volumen den du evaluieren möchtest, s ist der Radius der Kugel
Den Punkt musst du jezt um den gewünschten Mittelpunkt der Kugel verschieben, so als ob der Kugelmittelpunkt der Ursprung wäre.
Dann die Funktion aufrufen mit dem Transformierten Punkt. ein Wert > 0 sagt dir dass dein Punkt in der Kugel liegt, < 0 dass du im Freien bist und genau 0 heist auf der Kugeloberfläche.
Diesen Wert speicherst du in das Volumen. Wie du daraus dann das Mesh erzeugst steht oben im Artikel.

[joggel]

Ich danke euch erstmal.
Werd mir auch den Link anschauen und mal gucken ob es mir hilft.

Bis dahin erstmal :)

[Matthias Gubisch]

Wir warten gespannt auf die Ergebnise :)

[joggel]

Wir warten gespannt auf die Ergebnise :)

Das setzt mich aber so unter druck :( ^^
Mal sehen ob ich überhaupt etwas hinbekomme...

[Schrompf]

Lass Dich nicht unter Druck setzen, aber bis heute nachmittag solte das schon fertig sein.

[joggel]

Okay.
Und was mach ich dann ab 11Uhr? :D

[Spiele Programmierer]

Wieso geben diese Funktionene die du verlinkt hast _nur_ einen float-Wert zurück.

In einem gefüllten Bereich liefert die Funktion einen negativen Wert zurück, der eine Abschätzung der Entfernung zum nächsten leeren Bereich ist. In einem leeren Bereich liefert die Funktion einen positiven Wert zurück, der eine Abschätzung der Entfernung zum gefüllten Bereich ist.

Die Entfernungabschätzung erlaubt eben einige elegante Tricks. Zum Beispiel könnte man eben von der Abschätzung einfach 1 abziehen um das Objekt um 1 Längeneinheit zu extrudieren. Und wenn man ein Noise drauf addiert, extrudiert man eben zufällig um den Noise die Oberfläche. Oder man kann damit eben Mengenoperatoren zaubern. Das sogar mit weichen Übergängen.

[dronus]

Vielleicht wäre es schlau, die grobe Topologie vorher zu erzeugen (einen zufälligen 3d Graph mit Knotenpunkten und Verbindungen dazwischen) und dann beide Bausteine zu tesselieren.

Die Verbindungen kann man leicht als viereckige Röhren erzeugen, die dann iterativ unterteilt werden (so wie Subdivision Surfaces). Beim iterativen Unterteilen ist es immer recht leicht, Bedingungen zu formulieren, dass keine Entartungen entstehen (Überschneidungen etc.). So kann man runde, schroffe und gewundene Röhren erhalten. Die Knotenpunkte sind etwas schwieriger, aber die kann man durch einige gegebene Meshes für verschiedene Anzahl an "Anschlüssen" erzeugen, deren Anschlüsse einfach ein viereckiger Ring sind an die eine ununterteilte Verbindung passt.

Den Graph kann man direkt durch Zusammenflicken der Meshes in eine ganz grobe Höhle umwandeln, die man dann erst durch Subdivision schön macht. Wenn man enstsprechende Metadaten zu den Vertices der Verbindungen und Knotenpunkte anlegt, kann man die direkt verbinden ohne groß rechnen zu müssen.

Da die Gänge sehr kurz werden können, und die unverfeinerten Knotenpunkte bei geschickter Tesselierung eine gewisse Beweglichkeit der Anschlüss-Vertices ermöglichen, sind auch extreme Formen, wie z.B. eine Halle mit Säulen darin, möglich, ohne dass der Mesh entartet.