spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo Leute,
hier tummeln sich doch einige Performancespezialisten für Algorithmen herum, vielleicht könnt ihr mir bei folgendem Problem helfen:

Sämtliche Wegfindungsalgorithmen auf Gittern basieren ja auf einer Kollisions-Karte, die sagt, ob ein Feld in dem Gitter frei ist, oder nicht. So auch für mein Spiel Galactineers.
Der Wegfindungsalgorithmus selbst bei einer vorhandenen Karte ist nicht das Problem, aber ich bin mit der Performance für die Erstellung dieser Kollisions-Karte noch nicht zufrieden. Folgende Bedingungen sind gegeben:
* Ich erhalte vom Server eine komplette Liste von (3-dimensionalen) Block-Koordinaten für einen Chunk. Auf Clientseite, wenn ich diese Blockliste in die entsprechenden Clientobjekte umsetze, berechne ich die Kollisions-Karte, die aber nur X- und Z-Koordinaten braucht, da Schiffe sich nur in der Ebene bewegen und nicht in der Höhe.
* Ein Schiff, das sich auf dieser Karte bewegen soll, soll aufgrund seiner Größe auch einen gewissen Abstand zu den vorhandenen Blöcken halten, d.h. die Blöcke um diesen vorhandenen Block herum nicht betreten, sondern erst ab einem Abstand von 3. Ein erhaltener Block sollalso direkt 5x5 = 25 Gitterfelder auf der Kollisions-Karte unpassierbar machen.
* Das gleiche gilt umgekehrt auch in der dritten Dimension, d.h. die Schiffe fliegen auf Höhe 0, d.h. nur Blöcke mit Y-Koordinate > 2 oder < -2 blockieren überhaupt den Weg.

Ich habe nochmal ein Bild angehängt, um deutlich zu machen, wie ich das brauche. In Schwarz sind Blöcke mit Y-Koordinate zwischen -1 und 1 eingezeichnet, da alle darüber oder darunter liegenden ja nicht in die Wegfindung einfließen sollen.

Bruteforce und völlig unoptimiert sähe die Berechnung dafür so aus (pseudo-code):


Das ist allerdings bei durchschnittlich 3000 Blöcken pro Chunk extrem langsam, weil ich in dieser Implementierung natürlich pro Block 25 Felder um den Block herum prüfe, auch wenn ggf. der Nachbarblock bereits abgehandelt wurde und sich ggf. nur ein paar neue blockierte Felder ergeben, wenn überhaupt.

Hat da jemand eine Idee, wie man das optimieren kann? Gibt es für sowas auch bekannte Algorithmen?
Wäre für Hilfe dankbar, die Performance an der Stelle ist wirklich kaum tragbar.

Danke schon mal für die Antworten. Hat jemand das Auslagern auf die Grafikkarte schon mal mit XNA gemacht? Soweit meine erste Recherche ergeben hat, gibt es die Compute Shader erst seit DirectX 10/11? Und XNA verwendet ja DirectX 9 und bietet da keine passenden Klassen an. Oder muss ich da den Umweg gehen, etwas zu rendern in ein separates RenderTarget und das dann als meine Rückgabe zu interpretieren?

@TGGC: Ja, die Karte ändert sich, immer wenn ein Block oder Gebäude platziert oder abgerissen wird. Allerdings reicht es dann ja, die Berechnung für den einen Block zu machen und den Umkreis des Blocks zu betrachten, da fällt dann im Pseudocode quasi die äußere Schleife weg und damit ist das nicht mehr sehr rechenaufwändig. Das Problem ist tatsächlich das initiale Befüllen mit 3000+ Blöcken.

Ich habe gestern bereits das Datenmodell geändert. Ein bool[32,32] pro Chunk gegenüber einer Liste von blockierten Koordinaten ist da offensichtlich wesentlich schneller, auch wenn der Großteil des Raums leer ist. Da braucht man dann beim Setzen der Werte in der Schleife auch nicht mehr zu prüfen, ob die Koordinate bereits in der Liste ist, oder nicht.