C++ Allgemeine Frage zu Multithreading/Spieleentwicklung

[Magogan]

Hi,

ich habe es jetzt geschafft, ein "Spiel" zu schreiben, in dem man durch eine zufällig generierte Welt laufen kann. Die Welt wird auch immer nachgeladen, wenn man in eine Richtung läuft. Ich habe die Welt in Quadrate aufgeteilt, jedes durch einzelne Instanz einer Terrain-Klasse repräsentiert. Aktuell läuft das folgendermaßen: Wenn man in eine Richtung geht, werden die Klassen-Instanzen der Quadrate, die am weitesten entfernt sind und in der entgegengesetzten Richtung liegen, durch neue Klassen-Instanzen ausgetauscht, deren Quadrate in der Bewegungsrichtung direkt hinter den bereits vorhandenen Quadraten liegen. Das Problem ist nur, dass das Nachladen "ziemlich lange" dauert. Das kann ich wohl auch nicht beschleunigen. Aktuell sind alle Pointer zu den einzelnen Terrain-Klassen-Instanzen in einem Array gespeichert.

Ich habe leider gerade keine Idee, wie ich die Berechnungen für das Nachladen, die zwischen dem Rendern der Frames stattfinden, in einen anderen Thread auslagern kann, sodass das Rendern von den Quadraten, die bereits berechnet sind, trotzdem nebenbei laufen kann und man keine kurzen Ruckler hat, wenn man sich bewegt und Quadrate nachgeladen werden müssen. Wenn ich das in einen anderen Thread auslagere, macht mir der CPU-Cache einen Strich durch die Rechnung, da in dem Render-Thread ja immer noch die alten Pointer im Cache sind. Ich habe ich schon überlegt, einfach ein zweites Array für die Pointer zu benutzen, das ich als volatile definiere, um dann die geänderten Pointer zu kopieren. Ich bin mir aber nicht sicher, ob das eine sinnvolle Lösung ist, da ich nicht weiß, was passiert, wenn die Pointer dorthin zeigen, wo im Cache noch Daten der alten Klasse vorhanden sind.

Allgemein weiß ich auch nicht, ob und wie ich die Berechnungen für Bewegungen von NPCs, Objekten etc. in einen anderen Thread auslagern kann, da diese ja synchron mit den anderen Frames sein sollen. Oder müssen sie das gar nicht sein? Wenn es zu viele NPS/Objekte/andere Spieler werden, sinken die FPS ja drastisch, wenn alles in einem Thread läuft.

Ich will keinen kompletten Quellcode als Antwort auf diesen Thread, mir reichen auch Hinweise, welche C++-Funktionen, die ich vielleicht noch nicht kenne, für mein Anliegen nützlich wären bzw. wie man das im Allgemeinen machen kann.

Grüße,
Magogan

Edit: Kleine Korrekturen.

 

[Green Mamba]

Du verwechselst glaube Klassen mit Objekten. Was genau meinst du mit "Nachladen"? Das generieren der Terrain-Objekte oder lädst du tatsächlich Geometrien auf die Grafikhardware? Ich komme bei deiner Erklärung nicht mit, da du die Begrifflichkeiten teils falsch benutzt.

 

[benneq]

Du kannst für alles Mögliche Threads benutzten. Z.B. könnte man sämtliche NPC Berechnungen in einen eigenen Thread packen. Diese Thread speist dann nach und nach immer wieder den Main-Thread, der quasi das Endergebnis bereitstellt.
Beim Laden der Terrain Quadrate ist das natürlich auch möglich. Wenn du dich "quer" bewegst, lädst du ja vermutlich meist 3 (oder mehr) Quadrate gleichzeitig (bzw. aktuell wohl noch nacheinander). Diese 3 Quadrate könnte man natürlich auch einfach in 3 Threads parallel berechnen und danach die Ergebnisse zusammenführen.

Schau mal hier, für ein kleines Bsp: http://stackoverflow.com/questions/266168/simple-example-of-threading-in-c

 

[Tumbleweed]

Ich würde es nicht übertreiben mit dem Threading. Spiele sind weitestgehend single threaded und Threads kommen immer auch mit overhead (Synchronisierung bei state-behafeteten Objekten, Verwaltung der Threads) und Fehleranfälligkeit (race conditions, dead/live locks).
Sowas lösen Engines durch clevere Algorithmen, Caches und object pooling , um die Arbeit zu reduzieren, statt zu parallelisieren. Schon eine simple Heuristik, die anhand der Bewegungsrichtung des Spielers das Terrain lädt bevor es tatsächlich angezeigt wird und zwischenspeichert, solang der Spieler "in der Gegend" ist, würde da Entlastung bringen.

Bei Texturen kannst du z.B. eine Hand voll Grundtexturen haben (z.B. grüne Wiese, Wüste, wie auch immer), die einfach nur mit leichtgewichtigen Dekoobjekten geschmückt werden. Die Grundtexturen könntest du dann permanent vorhalten für das aktuelle Level. Die Dekoobjekte könnten 10-20 Objekte (Bäume, Büsche, …) sein, die allein durch die zufällige (aber sinnvolle) Verteilung eine natürlich wirkende Umgebung schaffen. Fette 2048x2048 Hintergründe zu laden ist halt overkill an der Stelle.

 

[benneq]

Aber man könnte auf 'nem Quadcore z.B. 4 Terrian-Quadrat-Threads dauerhaft laufen lassen und diese dann halt immer wieder mit Daten füttern. Allerdings wurde auch noch kein Wort darüber verloren, WIE er die 3D Landschaft baut. Vielleicht ist es ja ein Raytracer. Dann wäre Threading extrem einfach einzubauen und dazu noch sehr sehr sinnvoll.

 

[Magogan]

Ja, da habe ich offensichtlich wirklich Klassen mit Objekten/Instanzen von Klassen verwechselt. Es ist wohl zu warm hier...

"Nachladen" bedeutet tatsächlich, dass die Terrains generiert werden, also von der allgemeinen Struktur (Heightmap aus Perlin-Rauschen) bis hin zu den einzelnen Dreiecken, die dann in den Vertex- und Index-Buffer kopiert werden.

Aktuell habe ich nur eine Textur und lege manuell fest, welcher Bereich der Textur auf dem Dreieck liegt, indem ich die Koordinaten der Textur anpasse. Ich habe leider keine andere Möglichkeit gefunden, das im Pixel-Shader umzusetzen, der nimmt leider keine Eingabeparameter, die aus dem Vertex-Struct stimmen, als Index eines Texturen-Arrays an. Vielleicht war das auch einfach der falsche Ansatz, keine Ahnung.

Mein Problem beim Multithreading ist, dass ich nicht weiß, wie ich dem Thread, der das Array aus Pointern zu Terrain-Klassen-Instanzen durchgeht und die einzelnen rendert, sagen soll, dass sich dieses Array geändert hat. Der hat das ja im CPU-Cache und greift deshalb gar nicht auf den RAM zu, wo ich das schon geändert habe...

 

[antred]

Ich habe ich schon überlegt, einfach ein zweites Array für die Pointer zu benutzen, das ich als volatile definiere, um dann die geänderten Pointer zu kopieren.

Vergiß das geich mal wieder. volatile ist kein Ersatz für gescheite threading-taugliche Synchronisationsmechanismen. Wenn du Daten zwischen Threads teilen möchtest, kommst du um einen Mutex nicht herum (zumindest nicht, wenn du standardkonformen Code schreiben möchtest).

Ergänzung (6. Juli 2014)

Mein Problem beim Multithreading ist, dass ich nicht weiß, wie ich dem Thread, der das Array aus Pointern zu Terrain-Klassen-Instanzen durchgeht und die einzelnen rendert, sagen soll, dass sich dieses Array geändert hat. Der hat das ja im CPU-Cache und greift deshalb gar nicht auf den RAM zu, wo ich das schon geändert habe...

Du setzt ein bool-Flag arrayContentChanged (geschützt durch einen Mutex), daß dein Render-Thread eben in jedem Durchgang einmal prüft und dann entsprechend reagiert (nicht vergessen, Flag wieder auf false zurückzusetzen). Wo ist denn da jetzt das Problem?

 

[Magogan]

Okay, das Array besteht ja aus Pointern (zu Instanzen der Klasse Terrain), die sich gar nicht ändern, wenn ich nur Methoden der Klasse Terrain aufrufe und keine neue Instanz der Klasse Terrain erstelle. Aber wenn die Instanzen der Klassen im CPU-Cache von Kern 1 sind und im Thread 2 auf Kern 2 geändert werden, wird dann auch der Cache von Kern 1 geändert, sodass Kern 1 nicht mehr auf die alten Daten im Cache zugreift? Bin mir da gerade nicht so sicher.

Gibt es beim Mutex unter Windows auch eine Funktion, die true oder false zurückgibt, je nachdem, ob der Mutex gerade gelockt ist? Dann könnte ich nämlich das entsprechende Quadrat überspringen und das nächste rendern. Edit: Gefunden. Ist einfach nur WaitForSingleObject mit 0 als Wartezeit: http://msdn.microsoft.com/en-us/library/windows/desktop/ms687032(v=vs.85).aspx

Wenn ich über die Pointer auf die Methoden der Klasse Terrain zugreife, geht das überhaupt multithreaded? Die virtuelle Adresse mag zwar stimmen, aber die physische Adresse stimmt doch nicht unbedingt überein. Wie wird denn sichergestellt, dass die Variablen der Instanz der Klasse, die ich in Thread 2 ändere, in Thread 1 auch geändert sind, wenn die da ggf. an einer anderen physischen Adresse liegen?

 

[kuddlmuddl]

Okay, das Array besteht ja aus Pointern (zu Instanzen der Klasse Terrain), die sich gar nicht ändern, wenn ich nur Methoden der Klasse Terrain aufrufe und keine neue Instanz der Klasse Terrain erstelle. Aber wenn die Instanzen der Klassen im CPU-Cache von Kern 1 sind und im Thread 2 auf Kern 2 geändert werden, wird dann auch der Cache von Kern 1 geändert, sodass Kern 1 nicht mehr auf die alten Daten im Cache zugreift? Bin mir da gerade nicht so sicher.

Um solche Dinge musst du dich absolut nicht kümmern bei Multithread-Anwendungen. Nur weil du bei 4 Cores dein Programm mit 4 Threads startest heißt das noch lange nicht, dass jeder Thread in einem eigenem Kern läuft. Diese Planung übernimmt das OS und es könnte auch passieren dass alle Threads (nacheinander) im selben Kern abgehandelt werden, falls ein anderer Prozess mit höherer Prio irgendwas erledigt haben will.
Um synchronisierung zwischen den Cores musst du dich also überhaupt nicht kümmern, das funktioniert automatisch.
Trotzdem darfst du natürlich nicht in einem Thread Daten ändern die auch ein anderer Thread gleichzeitig verwendet. Hierfür verwendet man eben den genannten Mutex um zu verhindern, dass während einer write-Operation eine Read-Operation auf den selben Daten stattfindet. Gleichzeitiges lesen ist ja kein problem - nur schreiben muss exklusiv stattfinden.
Hier mit minimal-Beispiel: http://www.cplusplus.com/reference/mutex/mutex/
Der .lock() lässt andere Threads warten die auch an die Daten ranwollen und der unlock() gibt sie wieder frei.
Falls du kein C++11 hast dann zB http://www.boost.org/doc/libs/1_54_0/doc/html/thread/synchronization.html

 

[Magogan]

Und was ist mit den Variablen, die ich in der Klasseninstanz ändere? Werden die auch zwischen den Threads synchronisiert? Oder liegen die auf dem Stack?

 

[kuddlmuddl]

Und was ist mit den Variablen, die ich in der Klasseninstanz ändere? Werden die auch zwischen den Threads synchronisiert? Oder liegen die auf dem Stack?

Du meist wenn eine Klasse seine Member verändert und ein anderer Thread an diese Member rankommt?
Du musst halt durch einen Mutex sicherstellen, dass diese Klasse sich nach außem hin immer konsistent darstellt. Dh Veränderungen müssen wie eine atomare Operation durchgeführt werden.
Dh wenn ein Thread lesend auf eine Instanz zugreift bekommt er immer konsistente Werte: Entweder noch bevor sie verändert wurden oder nachdem sie (alle) verändert wurden aber niemals wo einige bereits verändert wurden und andere nicht.
Jede verändernde Operation (write) muss eben durch einen Mutex sicherstellen, dass dieser Thread exklusiv mit den Daten arbeitet - dh kein anderer Thread kann während des Locks lesen oder schreiben.
Wenn du mit Stack den Prozessorcache meinst: Du weißt nie wann wo welche Daten liegen und es sollte dir auch egal sein. Das wird auch wieder vom OS behandelt. Durch Prioritäten könnte es sein, dass längere Zeit dein Prozess nicht weitermacht und der komplette Cache von ganz anderen Programmen zu 100% beansprucht wird und alle Daten daher nur im RAM oder sogar auf HDD (swap) liegen.

 

[Magogan]

Mit Stack meine ich den Stack, auf dem zum Beispiel lokale Variablen liegen, wenn ich mich nicht ganz irre. Das ist ein Bereich im RAM, der dem Thread zugeordnet wird. Da landen dann auch z.B. Variablen bei rekursiven Funktionsaufrufen drauf. Da jeder Thread einen eigenen Stack hat, wäre es natürlich nicht sehr hilfreich, wenn die Instanzen der Klasse Terrain auf dem Stack liegen würden.

 

[BlackMark]

@Magogan: Du machst dir hier viel zu viele Gedanken über Dinge, die dein OS für dich erledigt. Würdest du ein Betriebssystem programmieren, müsstest du dir über sowas Gedanken machen, aber als Anwendungsentwickler, wird dir diese ganze Arbeit vom OS abgenommen.

Was wo gespeichert wird kann dir ganz egal sein, ob das nun Stack, Heap, RAM, HDD oder sonst was ist, für dich ist das alles gleich zu programmieren. Du hast einen Pointer und der zeigt ( sofern Speicher allocated wurde ) auf deine Daten, das garantiert dir das OS. Solang du im selben Prozess bist kannst du mit diesem Pointer auf deine Daten zugreifen, egal in welchem Thread oder in welcher Funktion. Du musst dich nur darum kümmern, wie oben schon ausführlich erklärt wurde, dass du nicht gleichzeitig auf diese Daten zugreifst ( außer es sind beides Lesezugriffe ).

Gruß
BlackMark

 

[Magogan]

Okay, kann sein, dass ich mir zu viele Gedanken mache. Danke für die Klarstellung

Jetzt muss ich nur noch gucken, wie ich das alles umsetzen kann... Gar nicht so einfach, so ein Spiel zu entwickeln Vor allem, wenn man absolut keine Erfahrung darin hat. Ich weiß aktuell noch nicht, wie ich Animationen umsetzen soll, aber mir fällt schon etwas ein

 

[Green Mamba]

Dir fehlt vor allem das Grundverständnis fürs Multithreading glaube ich. Ich empfehle daher ein paar Übungsaufgaben bevor du daran gehst.

 

[Magogan]

Doch, verstanden habe ich das schon, ich wusste nur nicht, was mir alles das Betriebssystem abnimmt. Und ich habe noch nie damit gearbeitet. Und ich muss noch herausfinden, wie sich das in der Praxis verhält in Bezug auf die Ausführungszeit bzw. Verzögerungen, wenn ein Thread gestartet wird, und wie schnell er darauf reagiert, dass ein Mutex von einem anderen Thread released wird (wahrscheinlich sofort, weil vermutlich ein Interrupt an den wartenden Thread gesendet wird). Da muss ich wohl noch ein wenig experimentieren und Dokumentationen lesen.

 

[kuddlmuddl]

Verzögerungen, wenn ein Thread gestartet wird

Das kreieren von einem Thread kann schon Zeit kosten wenn man es oft pro Sekunde durchführt, weswegen man die meisten Threads auch nur zum Programmstart anlegt und im laufe dann pausiert und erneut startet.
Theoretisch kann man auch http://en.wikipedia.org/wiki/Thread_pool_pattern sowas machen aber das ist am Anfang overkill. Außerdem hört es sich bei dir so an, als ob du eine konkrete Aufgabe hast die permament erledigt werden soll. Dafür wäre ein einzelner fester Thread ideal.
Das reine "starten" wird ähnlich viel Zeit kosten wie ein Funktionsaufruf.. also im Grunde garkeine (auf jeden fall weniger als eine Mikrosekunde).

und wie schnell er darauf reagiert, dass ein Mutex von einem anderen Thread released wird

Der Thread wartet halt bis der Mutex frei ist und legt dann sofort los, da er "aufgeweckt" wird. Da vergeht auch keine messbare Zeit.
Über Laufzeitprobleme durch Threads musst du dir hier also überhaupt keine Gedanken machen - das wichtigste ist die Synchronisation.

 

[Magogan]

Noch eine Frage: Ich habe jetzt eine Heightmap aus einem Perlin-Rauschen erzeugt und diese auch dargestellt, man kann also durch eine Welt laufen, die aus dem Perlin-Rauschen erzeugt wird. Aber nun habe ich leider keine Ahnung, wie ich diese in Gebiete unterteilen soll, ähnlich den Biomen in Minecraft. Ich bräuchte also eine Funktion, die jedem (x, z) einen Wert zuordnet, sodass Punkte mit gleichen Werten zu einigermaßen sinnvoll gegliederten Gebieten zusammengefasst werden können. Oder geht das auch mit dem Perlin-Rauschen? Das muss ich mal testen... Wenn ich mir die bisherige Spielwelt so ansehe, bezweifle ich, dass ich mit dem Perlin-Rauschen Biome generieren kann.

 

[kuddlmuddl]

Ich bräuchte also eine Funktion, die jedem (x, z) einen Wert zuordnet, sodass Punkte mit gleichen Werten zu einigermaßen sinnvoll gegliederten Gebieten zusammengefasst werden können

Ich weiß ja nicht wie es anderen hier geht aber ich bin etwas zu weit weg von deinem Problem um da helfen zu können bzw um das zu verstehen.
Was ich verstehe: Du hast rauschen und willst daraus eine "zufällige" klötzchenwelt (ala minecraft) generieren.
Wo genau ist jetzt das Problem?
Soll jeder Pixel ein Klotz werden? Ist hell=hoch und dunkel=tief? Dann sind die graustufen der verrauschten Textur doch schon ein Grauwertgebirge? Oder geht es dir jetzt darum das geglättet in eine vernünftig benutzbare 3D welt umzuformen die eben nicht so verpixelt aussieht wie minecraft? Dann könntest du die Grauwerte deiner Textur als stützpunkte von Splines verwenden und die Splinewelt dann dem Spieler präsentieren.

 

[daemon777]

Glätte muss man nicht bei jedem Rauschen durchführen. Wenn ich es jetzt richtig im Kopf habe ist beim Perlin-Rauschen sozusagen eine Art glätten inbegriffen.

Ich würde mehrere Funktionen überlagern. Erstmal ein Rauschen mit großer Auflösung, das die Biome auswürfelt und dann eben in diesen Bereichen mit den stärker auflösenden Rauschfunktionen das Gelände ermitteln.

Aber ganz wichtig: du willst ein Spiel programmieren! Lern mal wie man Probleme löst statt andere nach (relativ einfachen) Lösungen zu fragen. Ein bisschen ausprobieren wäre ja auch nicht schlecht. Oder willst du einen exakten Minecraft-Klon programmieren? Es gibt doch tausende Möglichkeiten!