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):
|
C#-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
|
Vector2[] blockedFields;
foreach(block received from server) {
if (block.Y < 2 && block.Y > -2) {
for (x = -2; x <= 2; x++) {
for (z = -2; z <= 2; z++) {
var blockedFieldCoordinates = new Vector2(block.X +x, block.Z + z);
if(!blockedFields.Contains(blockedFieldCoordinates) blockedFields.Add(blockedFieldCoordinates);
}
}
}
}
|
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.