Zerstörbare Höhlenwelt

[shampoo]

Erstmal Hallo (mein erster Beitrag)

Seit einigen Tagen schwebt mir eine "kleine" Spielidee im Kopf herum die mich nicht loslassen will:

Man ist Bergarbeiter mit anderen (Multiplayer), und hat die Aufgabe Metalle/Edelsteine (was auch immer) zutage zu fördern.
Das ganze fängt an mit... nichts. Einer Felswand!
So muss man beginnen sich erstmal ein kleines Loch in die Wand zu Buddeln/Bohren/Sprenden (Je nach Gestein etc, muss auch net unbedingt in der Gegenwart spielen, kann auch Vergangenheit oder Zukunft sein)
Das an sich ist ja kein Problem, allerdings will ich mehr, und zwar das man Beliebig Hoch, Runter, Links uns Rechts graben kann mit beliebigen Tunnelgrößen. (Später für Fahrzeuge etc)
So weit so gut, aber ich stehe nun vor einem Problem, und zwar wie Baue ich so eine Welt auf?
Ich hab schon eine Grobe idee, und Zwar ein gigantisches 3D Array mit 3 (<- Stark vereinfacht):
0 <- Luft
1 <- Wand
2 <- Stein (nicht sichtbar, da unter Wand)

Jetzt ist mein Plan das Luft und Stein eben einfach ausgelassen werden, die Wand in Dreiecke umgewandelt wird, und dann das ganze gerendert wird.
Somit könnte man sich beliebig durchbuddeln. Dann wenn man Bohr muss man ja einfach nur die Wand in Luft umwandeln, und den Stein dahinter in Wand.
Hört sich eigentlich ganz einfach an, aber nach kurzem Überlegen bringt mir das starke Kopfschmerzen, weil wie erkläre ich dem PC wie er aus dem Array eine vernünftige Wand baut, ohne das ich lustige Dreiecke habe die quer durch die Landschaft gehen. Das wäre auch noch nicht das Problem, Das eigentliche Problem ist, wie find ich raus wo schon ein Polygon ist, damit ich nicht alles Tausend mal berechnen muss. (Ich kann meine Gedankengänge leider nicht wirklich gut in Worte fassen).


Ich hoffe irgendjemand kann mir diverse Tipps geben, sodass aus der Idee vielleicht ein "kleines" Spielchen wird.

Danke im Vorraus

[Aramis]

Ich hoffe irgendjemand kann mir diverse Tipps geben

Ja, guck mal nach Voxelgrafik und den „Marching Cubes”. Zumindest fuer das Triangulationsproblem hast du da eine fertige Loesung.

[Chromanoid]

für inspirative zwecke würde ich mir mal minecraft (leider nicht open source) anschauen und dann vielleicht infiniminer (open source) (im grunde eine art vorgänger von minecraft) hier der code dazu http://code.google.com/p/infiniminer/ (ich glaube da wird XNA benutzt)

[shampoo]

Armis:
Ah, das mit den Marching Cubes is klasse, danke!

Chromanoid:
Ich kenne Minecraft und Infiniminer (wobei ich infiniminer besser finde) und muss auch zugeben, das meine Idee beim minecraft spielen gekommen ist ^^"
Allerdings will ich keine Würfelwelt, sondern echte Polygone für etwas weichere Wände.

[eXile]

Na na, kennt hier denn keiner mehr Red Faction mit seiner Geo-Mod-Engine?! Hier wird schön in einem nun acht Jahre alten Post beschrieben, wie der Kern davon funktioniert. Und hier ist der Originalartikel darüber. Dieser Artikel wurde wiederum in zwei wissenschaftlichen Publikationen aufgegriffen, nämlich hier und hier. Ich hoffe, das reicht für den Anfang.

[Despotist]

Du musst bedenken dass diese riesige Spielwelt die dir vorschwebt in ein Array zu packen Unmengen Speicher benötigt der dann auch nur ganz selten benutzt wird.
Ich würde dafür einen prozeduralen Ansatz wählen. Du startest mit einer Felswand oder der Erdoberfläche und der Miner wählt einen Punkt wo er graben will. Du gehst dann senkrecht zb 1m von dem Punkt nach innen und erzeugst da einen "Tunnelpunkt". Von diesem Punkt erzeugst du einfach in einem Abstand die Polygone die alle zu ihm ausgerichtet sind als Tunnel und am Ende eine Wand. Die Punkte sind miteinander verbunden (kennen ihre direkten Nachbarn als alle Tunnel die von da aus gestartet wurden) um auch einen Baum zb für Sichtbarkeits- und Kollisionstests und für Wegfindung erstellen zu können und um zu sehen wo eine Sackgasse ist die von einer Wand abgeschlossen wird. So kann der Miner sich jetzt tiefer Graben und durch die Richtung in die er schaut kann er die Richtung bestimmen in die er gräbt (da wird im gewählten Abstand ein neuer Tunnelpunkt gesetzt). Durch die Grabdauer oder so kannst du auch den Durchmesser des Tunnels bestimmen der für jeden Tunnelpunkt mit gespeichert wird.

Analog kannst du auch Rohstofe und Erze speichern die Ebenfalls als Punkte mit Durchmesser abgelegt werden. Dann machst du einfach einen Kollisionstest der neuen Tunnelpunkte mit den Erzen um rauszufinden welche Vorkommen erschlossen wurden. Und du kannst ja auch einen Nahbereichssensor bauen der die Richtung der Rohstoffe anzeigt damit man nicht blind buddelt. Und eine Art Minimap wirst du ja eh benöitgen.

Der Vorteil dieser Methode ist dass sie Speichersparend ist da du nur ein kleines Array der Tunnelpunkte erzeugen musst und die Polygone "on the fly" erzeugst wenn sie benötigt werden (also wenn der Bereich für den Spieler sichtbar wird).

[joeydee]

So ähnlich hab ich mal einen Leveleditor angefangen. Vorlage war das Spiel "Descent" (Levelprinzip von D1 und D2), welches ebenfalls in Minen spielt. Auch wenn das dort nur von einem Würfel als Grundkörper ausging sind prinzipiell vielfältige Formen möglich. Die Wände müssen auch nicht senkrecht zueinander bleiben.

Das Prinzip ist wie folgt: Man geht von einem Polygon aus (Tunnelquerschnitt), berechnet die Normale (ggf. gemittelt, falls das Polygon nicht planar ist) und extrudiert alle Vertices entlang der Normalen um einen bestimmten Betrag. Es ergeben sich Seitenwände und eine neue Stirnwand. Das alte Polygon wird als "Portal" markiert (das muss allerdings nicht zwangsweise in einer Portalengine als solches benutzt werden, da es für heutige Bedürfnisse in der Regel viel zu viele Portale wären, ich nenns hier nur mal so).
Nun kann man jede Wand (Stirn- sowie Seitenwände) als neue Basis auswählen. Die Richtung der Extrusion kann man jedesmal in bestimmten Grenzen ändern. Im Editor konnte man noch einzelne Vertices verschieben oder ganze Wände verschieben und um mehrere Achsen drehen, was für deinen Zweck allerdings wegfallen kann.

Herausforderungen dabei sind u.a.
- das Mesh-Format (ich habe damals ein Render Dynamic Mesh gewählt, da es auch zur Laufzeit schnell verändert werden kann),
- das Überprüfen ob man in einen vorhandenen Tunnel bricht (hier dürfte ein Octree bei der Suche helfen),
- sowie das brechen beliebiger Formen in den Fels, statt auf die vorhandenen Polygone angewiesen zu sein (läuft wohl auf CSG-Operationen hinaus).

Voxel und Marching Cubes sind evtl. ein flexiblerer Ansatz, muss aber vermutlich viel höher optimiert werden und ist schwieriger zu cullen. Wenn du dich aber mal von der heute möglichen Performance und Qualität überzeugen willst, schau dir die Demo von 3dcoat oder eins der Tutorial-Videos zum Thema "Voxel Sculpting" an.

[Thoran]

Eventuell ist ja folgendes Projekt auf Ogre3D basierend was für dich:
http://www.ogre3d.org/forums/viewtopic.php?t=27394

Thoran