Du bist nicht angemeldet.

Werbeanzeige

LInsoDeTeh

Treue Seele

  • »LInsoDeTeh« ist der Autor dieses Themas

Beiträge: 370

Wohnort: Essen, Deutschland

Beruf: Softwareentwickler & Projektleiter

  • Private Nachricht senden

1

09.07.2015, 10:27

Algorithmus zur Erstellung einer Kollisions-Karte für Wegfindung

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.
»LInsoDeTeh« hat folgendes Bild angehängt:
  • map.png

Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von »LInsoDeTeh« (09.07.2015, 11:05)


2

09.07.2015, 11:31

Brute Force sollte eigentlich gar nicht so schlecht sein. Ich meine, klar kann man ein bisschen optimieren, wenn du viele schwarze Blöcke in der Nähe hast, aber letztendlich sind 25 Schreiboperationen pro Block jetzt auch nicht soo viel und die Abfrage, ob überhaupt optimiert werden kann, dürfte in vielen Fällen die Gewinne zunichte machen. Außer du hast tatsächlich viele regelmäßige Strukturen, z.b. viele lange 'Mauern' ohne Lücken.

Was du aber vielleicht tun solltest, ist die Berechnung auf die Grafikkarte auslagern. Ob jetzt per Compute Shader, Cuda oder herkömmliches Rendern macht zunächst vermutlich keine so großen Unterschiede. Aber es ist halt ein traditionelles Grafikproblem (render 3000 Quads an verschiedenen Stellen), und dafür gibt es spezialisierte Hardware, also sollte sich das sehr gut ausnutzen lassen. Ansonsten könntest du deinen CPU Algorithmus gewiss noch optimieren, d.h. ein optimales Speicherlayout wählen, die Schleife parallelisieren oder sämtliche überflüssige Logik entfernen. Wofür brauchst du z.b. die Abfrage in der inneren Schleife? Und hast du wirklich komplexe Objekte pro Zelle oder einfach nur ein ganz gewöhnliches bool-oderwasauchimmer-Array (möglicherweise kannst du es auch schneller machen, wenn dein Array-Typ kleiner ist, weil dann mehr in die Caches passt).
Lieber dumm fragen, als dumm bleiben!

David Scherfgen

Administrator

Beiträge: 10 195

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

09.07.2015, 16:42

Was du hier machst, ist in der Bildverarbeitung auch als Dilatation bekannt. Da gibt's sicherlich ein paar effiziente Algorithmen, und der Hinweis auf GPU ist auch sehr gut.

TGGC

1x Rätselkönig

Beiträge: 1 803

Beruf: Software Entwickler

  • Private Nachricht senden

4

09.07.2015, 21:52

Aendert sich die Karte denn und wenn ja wie oft?

LInsoDeTeh

Treue Seele

  • »LInsoDeTeh« ist der Autor dieses Themas

Beiträge: 370

Wohnort: Essen, Deutschland

Beruf: Softwareentwickler & Projektleiter

  • Private Nachricht senden

5

10.07.2015, 10:24

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.

6

10.07.2015, 12:27

Ähm, ok, wenn du eine Liste (im Sinne von std::list) benutzt hast, dann kann das ja auch gar nicht schnell sein. Und 3000 Blöcke ist nun echt gar nix, 3000*25 Speicherzugriffe sollte man ansich sogar schon per Frame machen können, ohne dass es ruckelt. Und zwar auf der CPU, wenn das also wirklich deine Größenordnung ist, dann vergiss die Grafikkarte erstmal wieder.
Evtl. solltest du mal den tatsächlichen Code posten. Im Pseudo-Code sieht man halt nicht, ob du nicht (für dein Problem) wahnsinnig ineffiziente Strukturen benutzt hast.
Lieber dumm fragen, als dumm bleiben!

BlueCobold

Community-Fossil

Beiträge: 10 880

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

7

10.07.2015, 12:40

Das scheint er zu haben, in einem anderen Topic, wo es um Raycasting/Picking in einer Minecraft-Welt ging, kam auch schon indirekt rüber, dass er keine Direktzugriffe auf Blöcke anhand von einer Position im Raum tätigen kann, sondern irgendwie erst die Blöcke suchen muss. Definitiv nicht sonderlich effizient. Dabei wäre es selbst bei einer dynamischen Struktur von Blöcken noch immer keine Speicher-Hürde eine Matrix aus Chunks und Blöcken zu erstellen, die nur Pointer auf die eigentlichen Daten beinhalten, damit Lookups wesentlich beschleunigt werden können.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

David Scherfgen

Administrator

Beiträge: 10 195

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

8

10.07.2015, 13:21

Das generelle Problem bei dieser Art von Spiel ist wohl, dass die Welt sehr groß werden kann und nur sehr spärlich besetzt ist. Es spielt schließlich im Weltraum.
Stell dir beispielsweise mal vor, du setzt einen Block an Position (0, 0, 0) und einen anderen an Position (1000, 1000, 1000). Ein einfacher Matrix-Ansatz würde da direkt mal eine Größe von 1001*1001*1001 Zellen reservieren, wovon dann nur zwei besetzt sind.

TGGC

1x Rätselkönig

Beiträge: 1 803

Beruf: Software Entwickler

  • Private Nachricht senden

9

10.07.2015, 14:25

Ich wuerde dann einfach diese Kollisionsmap mit in den Leveldaten speichern, wenn die Aenderungen zur Laufzeit schnell genug sind. Egal wie lange man optimiert, schneller als direkt binaer laden wirds eher nicht.

BlueCobold

Community-Fossil

Beiträge: 10 880

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

10

10.07.2015, 18:30

Das generelle Problem bei dieser Art von Spiel ist wohl, dass die Welt sehr groß werden kann und nur sehr spärlich besetzt ist.
Dann sind die meisten Chunks eben leer, stört das jemanden?
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige