Effektive Datenstruktur für überlappende räumliche Bereiche

Wenn Sie wirklich viele Flächeneffekte gleichzeitig haben und sie willkürliche Formen haben, würde ich es so machen:

• wenn ein neuer Effekt erstellt wird, ist es das in einer globalen Liste von Effekten gespeichert (nicht unbedingt eine globale Variable, nur etwas, was für die ganzes Spiel oder die aktuelle Spielkarte)
• es berechnet welche Kacheln Es beeinflusst und speichert eine Liste dieser Kacheln gegen den Effekt
• jede dieser Kacheln ist über den neuen Effekt informiert, und speichert eine Referenz zurück in a per-tile-Liste (in C ++ würde ich eine verwenden std :: vector dafür, etwas mit zusammenhängender Speicher, kein Link Liste)
• Das Beenden eines Effekts wird durch Iteration behandelt die interessierten Kacheln und entfernen Referenzen darauf, bevor Sie es zerstören
• das Verschieben oder Ändern der Form wird durch Entfernen erledigt die Referenzen wie oben, Durchführung der Änderungsberechnungen, dann werden die Referenzen in den Kacheln, die jetzt betroffen sind, erneut angefügt
• Sie sollten auch eine Debug-only Invariant-Prüfung haben, die durchläuft Ihre gesamte Karte und überprüft, dass die Liste der Kacheln im Effekt stimmt genau mit den Kacheln in der Karte überein, die darauf verweisen.

Normalerweise BSP-Bäume (oder Quadtrees oder Octrees ).

Einige Brute-Force-Lösungen, die nicht auf ausgefallene Informatik angewiesen sind:

1000 x 1000 ist nicht zu groß - nur ein Meg. Computer haben Gigs. Sie könnten ein 2D-Array haben. Jedes Bit in den Bytes könnte ein "Typ von Bereich" sein. Der "betroffene Bereich", der größer ist, könnte ein anderes sein. Wenn Sie eine vernünftige Anzahl verschiedener Arten von Bereichen haben, können Sie immer noch eine Multi-Byte-Bitmaske verwenden. Wenn das lächerlich wird, können Sie die Array-Elemente Zeiger auf Listen von überlappenden Bereichstyp-Objekten machen. Aber dann verlierst du die Effizienz.

Sie könnten auch ein Sparse-Array implementieren - indem Sie eine Hash-Taste verwenden, die von den Coords abgesetzt wird (z. B. key = 1000 * x + y) - aber das ist um ein Vielfaches langsamer.

Wenn natürlich, wenn es Ihnen nichts ausmacht, die fancy Informatik Wege zu kodieren, arbeiten sie normalerweise viel besser!

Wenn Sie einen bekannten maximalen Bereich für jeden Flächeneffekt kennen, können Sie eine Datenstruktur Ihrer Wahl verwenden und nur die tatsächlichen Quellen speichern, die für normale 2D-Kollisionsprüfungen optimiert sind.

Wenn Sie dann nach Effekten auf einer Kachel suchen, überprüfen Sie einfach (Kollisionserkennungsstil, optimiert für Ihre Datenstruktur) für alle Effektquellen innerhalb des maximalen Bereichs und wenden Sie dann eine definierte Testfunktion an (z. B. wenn die Fläche a ist Kreis, überprüfe, ob der Abstand kleiner als eine Konstante ist, wenn es ein Quadrat ist, überprüfe, ob die x- und y-Abstände jeweils innerhalb einer Konstanten liegen.

Wenn Sie eine kleine (& lt; 10) Anzahl von Effekt- "Feld" -Formen haben, können Sie sogar eine eindeutige Kollisionserkennung für jeden Effektfeldtyp innerhalb ihrer vorberechneten maximalen Reichweite durchführen.