Objekte in 3D Spielen

Hi,

gegeben sei ein normales 3D Spiel. So etwas wie ein Rollenspiel, oder ein recht offener Shooter. Diese "Welt" besteht also erst mal aus einer großen statischen Umgebung, die eigentlich als ein Model dargestellt werden könnte. Aber sie ist wohl zu groß zum kompletten Laden / Rendern.
Weiter befinden sich in der Welt einige Objekte. Diese können eine AI haben, (also irgendwie aktiv werden), oder Spielergesteuert sein. Natürlich gibt es auch Lichter in dieser Welt. Und Partikeleffekte, wobei da wohl erst mal nur die Emitter echte Objekte sind. Und Wasser gibt es auch noch, in dem man schwimmen kann, wie das da rein passt weiß ich auch noch nicht so.

So, ich denke jeder sollte in etwa eine Vorstellung davon haben, so etwas ist ja nun nicht unüblich.

Meine Frage ist: In welchen Datenstrukturen hält man so viele unterschiedliche Objekte? Es gibt da einfach soo viele Möglichkeiten, und ich bin mir nie so sicher ob das auch alles hält und klappt etc.
Im Internet findet man zwar viele Tutorials für Grafik oder sonstige Basics, aber üblicherweise sind da dann maximal 3 völlig unabhängige Würfel auf dem Bildschirm. Wie man eine solche komplexe Welt performant aufbaut, ohne dabei zu stark an Dynamik zu verlieren, dazu habe ich noch nichts gefunden. (Links sind als Antwort natürlich auch willkommen!)
Andererseits habe ich nicht das Gefühl, dass so etwas besonders "geheim" oder unmöglich ist. Schließlich hantieren ziemlich viele Spiele mit solchen Umbebungen, und die müssen das ja auch irgendwie hinbekommen haben.

Eine solche Datenstruktur müsste also folgende Fragen performant beantworten können:
- Kann Objekt x von A nach B laufen? (Ohne dabei durch eine Wand zu rennen.)
- Welche Objekte berühren eine Strecke / eine Kugel. (Kollisionsfindung halt.)
- Was muss von Position A mit Blickrichtung Y gerendert werden? (Man kann ja schlecht immer die ganze Welt rendern.)
- Welche Lichter haben einen Effekt auf die Szene?

Weiter muss man natürlich alle Objekte die selbst etwas machen (also irgendeine Form von AI haben) durchgehen können, und die machen lassen was sie wollen. Die brauchen aber natürlich wieder Zugriff auf die "Welt", in der sie sich bewegen.

Die Frage ist eigentlich nicht sprachspezifisch, aber die Sprache meiner Wahl ist C++. Mit Konzepten die Polymorphie, RAII, Shadern, etc. bin ich vertraut, in dieser Richtung muss man nun keine großen Erklärungen starten.

Wäre super toll wenn ihr mir da ein paar Denkanstöße und vielleicht etwas zu Lesen geben könntet!

dot

Für das Rendering wirst du wohl irgendeine Spatial Datastructure verwenden wollen, um schnell mal ein bisschen Frustrum Culling betreiben zu können. Die Spiellogik interessiert sich für Frustrum Culling überhaupt nicht, oder nur am Rande. Die will vielleicht ein Navigation Mesh haben. Für irgendwelche Physiksimulationen oder Schnittpunktstests, willst du vermutlich nicht die gleichen Modelle verwenden wie für das Rendering, denn dort braucht es nicht den vollen Detailgrad und evtl. auch wieder völlig andere Datenstrukturen...

Der "Trick" ist, nicht alles in eine Datenstruktur zu quetschen, sondern in den jeweiligen Bereichen die jeweils sinnvolle Datenstruktur auszuwählen

Hm.. so richtig vorstellen kann ich mir das noch nicht. Was mache ich z.B. mit Lichtern? Am schönsten wäre es ja, wenn ich Licher einfach als Member implementieren könnte. z.B. alle Fackeln haben ein Licht. Und wenn ich jetzt Fackel->render() aufrufe, würde das Licht mitgerendert. Aber ich fürchte das geht so nicht, weil das Licht ja andere Objekte beeinflusst. Also muss ich die Lichter wohl einzeln halten, aber wie binde ich sie dann ordentlich an ein Objekt? (Das Licht soll sich ja bewegen, wenn die Fackel sich bewegt.)

Und wie kann man hier hängenden Pointern ausweichen? IDs speichern und Zugriff nur über die Welt? (shared_ptr würde ja das Problem nicht lösen, sondern einfach ein memory Leak produzieren.)

Und was meinst du mit Spatial Datastructure? So etwas wie einen octree? Weil ich habe mir schon gedacht, dass ich die Objekte irgendwie ordnen muss, sodass ich schnell entscheiden kann wie viele Objekte in einer Kugel sind etc.
Aber wenn ich mir das jetzt mit einem octree so überlege, scheint mir das ganzschön rechenintensiv, wenn nur 100 Objekte sich die ganze Zeit hin und herbewegen, muss ich das Ding ja dauernd umsortieren. Ist das vielleicht gar nicht so schlimm, wie ich mir das denke?

Danke jedenfalls und entschuldige diese Fragenflut, dazu findet man nur so wenig mit Netz.

RedPuma

Ungefähr so?

class Light
{
public:
	void render( void );
	void setPos( const Vector3d &Pos ) { pos = Pos; }
private:
	Vector3d pos;

	//...
}

class LightManager
{
public:
	Light *createLight( void );
	void deleteLight( Light* light );
	void renderLights( void );
private:
	std::vector<Light*> lights;
}

class Fackel
{
public:
	void init( void ) { light = singletons::lightManager->createLight(); }
	void render( void );
	void onPosChanged( const Vector3d &pos ) {light->setPos(pos);}
private:
	Light *light;
}

dot

player123 schrieb:

Aber ich fürchte das geht so nicht, weil das Licht ja andere Objekte beeinflusst.

Das hast du richtig erkannt.

player123 schrieb:

Und wie kann man hier hängenden Pointern ausweichen?

Indem man sie nicht produziert.

player123 schrieb:

Und was meinst du mit Spatial Datastructure? So etwas wie einen octree?

Ja, z.B. einen Octree, BSP-Tree, kd-Tree, ein Grid oder eine Bounding Volume Hierarchy...

player123 schrieb:

Aber wenn ich mir das jetzt mit einem octree so überlege, scheint mir das ganzschön rechenintensiv, wenn nur 100 Objekte sich die ganze Zeit hin und herbewegen, muss ich das Ding ja dauernd umsortieren.

Ja, ein Octree ist nicht so toll für dynamische Daten, das hast du auch richtig erkannt. Das ist mitunter eines der großen Probleme bei Realtime Raytracing...

Wie du also bemerkt hast, sind größere Spiele eben doch ganz schön komplexe Software. Ich empfehle, sich einfach mal etwas mit Software Architektur zu befassen und dann einfach Spiele zu programmieren um Erfahrung zu sammeln. Und dabei eben klein anzufangen...

RedPuma

Eventuell solltest du dir auch etwas Literatur zu dem Thema zulegen, ich kann dir "Game Coding Complete" von Mike Shaffry oder so ähnlich empfehlen. Das Buch beschreibt sehr gut den kompletten Ablauf einer Spieleentwicklung, die einzelnen Komponenten eines Spiels und wie man sie zusammenfügt bzw. wie alles zusammen passt. Das Buch reißt jede Komponente so an dass man genügend Ideen und Inspiration für eine eigene Implementierung bekommt. Sehr gut wenn man, so wie du, schon Ahnung in Teilbereichen im Detail besitzt aber einem irgendwie das Gesamtkonzept fehlt.

dot schrieb:

Wie du also bemerkt hast, sind größere Spiele eben doch ganz schön komplexe Software. Ich empfehle, sich einfach mal etwas mit Software Architektur zu befassen und dann einfach Spiele zu programmieren um Erfahrung zu sammeln. Und dabei eben klein anzufangen...

Hm.. ok. Zur Sortierung der Objekte habe ich jetzt schon ein besseres Bild, und wegen dem Licht, da habe ich auch etwas interessantes gefunden. Danke dafür!

Eine Frage brennt mir allerdings noch etwas auf der Seele:

Objekte/Models werden ja eher in externen Programmen erstellt. (Blender/Maya oder so.)
Gilt das auch für "die Welt"? Also ist es üblich, dass diese einfach ein überdimensionales Model ist? (In Spielen in denen man den Großteil der Objekte nicht zerstören kann, ist "die Welt" ja recht statisch.) Weil das kann man dann ja schlecht in einem in dem Speicher laden. Wie teilt man so was? (Auch für Collision Detection / Frustum-Culling etc.)

dot

player123 schrieb:

Objekte/Models werden ja eher in externen Programmen erstellt. (Blender/Maya oder so.)
Gilt das auch für "die Welt"? Also ist es üblich, dass diese einfach ein überdimensionales Model ist? (In Spielen in denen man den Großteil der Objekte nicht zerstören kann, ist "die Welt" ja recht statisch.) Weil das kann man dann ja schlecht in einem in dem Speicher laden. Wie teilt man so was? (Auch für Collision Detection / Frustum-Culling etc.)

In der Regel wohl eher kaum. Hängt natürlich vom konkreten Spiel ab inwiefern das Praktikabel ist, aber normalerweise wird man wohl eigene Editoren haben mit denen die Welt gebaut wird. Zumindest irgendein Tool wirst du normalerweise brauchen, das die Daten in ein für den Spiel brauchbares Format übersetzt. Der Input dafür kann theoretisch natürlich auch z.B. rein aus Maya kommen...

Natürlich kann man die komplette Welt in Maya etc. bauen, aber oft fehlen dir die entsprechenden Exportmöglichkeiten um alle Informationen im Editor festzulegen. Deswegen schreibt man sich entweder Scripte/Plugins, die alle Inhalte in ein entsprechendes Format konvertieren oder du benutzt gleich einen eigenen Editor, indem du alle Objekte aus Maya entsprechend "zusammenfügst" mit allen relevanten Informationen für die Gamelogik/Physic-Engine etc.

Ehm.. vielleicht habe ich die Frage etwas undeutlich gestellt, aber so war das nicht gemeint. Mir ist schon bewusst, dass ich auch Spielbezogene Dinge in das Mapformat packen muss. Aber das beantwortet nicht

player123 schrieb:

Also ist es üblich, dass diese einfach ein überdimensionales Model ist? (In Spielen in denen man den Großteil der Objekte nicht zerstören kann, ist "die Welt" ja recht statisch.) Weil das kann man dann ja schlecht in einem in dem Speicher laden. Wie teilt man so was? (Auch für Collision Detection / Frustum-Culling etc.)

cooky451

Hm.. das würde mich in der Tat auch mal interessieren. Man ( <- ich) findet auch nicht wirklich was dazu im Netz. Irgendwie muss man sehr große Strukturen ja aufteilen können.

Edit: Wobei man natürlich auch gleich den Künstlern sagen kann, sie sollen ein einzelnes Objekt nicht zu groß machen. (Wände etc. müssen ja eh einzeln gemacht werden um einen großen Turm zu bauen, da sollte das ja kein Problem sein.)