Die richtige Antwort hängt ein wenig vom eigentlichen Spiel ab, das Sie entwerfen. Wenn Sie sich für ein anderes entscheiden, müssen Sie beide implementieren und ein Profil erstellen, um herauszufinden, welches für Ihr bestimmtes Spiel zeit- oder platzsparender ist.
Die Rastererkennung scheint nur für die Erkennung von Kollisionen zwischen sich bewegenden Objekten und einem statischen Hintergrund zu gelten. Der größte Vorteil dabei ist, dass der statische Hintergrund als zusammenhängendes Speicherarray dargestellt wird und jede Kollisionssuche O (1) mit guter Lokalität ist, wenn Sie mehrere Lesevorgänge durchführen müssen (da Entitäten mehr als eine Zelle im Raster abdecken). Der Nachteil, wenn der statische Hintergrund groß ist, ist, dass das Gitter ziemlich platzraubend sein kann.
Wenn Sie stattdessen den statischen Hintergrund als Quadtree darstellen, steigen die Kosten für einzelne Suchvorgänge. Da jedoch große Blöcke des Hintergrunds wenig Speicherplatz beanspruchen, sinkt der Speicherbedarf, sodass mehr Hintergrund im Quadtree gespeichert werden kann Zwischenspeicher. Selbst wenn in einer solchen Struktur zehnmal so viele Lesevorgänge erforderlich sind, ist die Suche im Cache zehnmal schneller als bei einer einzelnen Suche mit fehlendem Cache.
Wenn ich vor der Wahl stünde? Ich würde mit der Grid-Implementierung weitermachen, weil es einfach blöd ist, meine Zeit für andere, interessantere Probleme zu verwenden. Wenn ich bemerke, dass mein Spiel etwas langsam läuft, mache ich ein paar Profilerstellungen und finde heraus, was Hilfe gebrauchen könnte. Wenn es so aussieht, als würde das Spiel viel Zeit für die Kollisionserkennung aufwenden, würde ich eine andere Implementierung ausprobieren, wie einen Quadtree (nachdem alle einfachen Korrekturen erschöpft sind), und herausfinden, ob dies geholfen hat.
Bearbeiten: Ich habe keine Ahnung, wie sich die Erkennung von Gitterkollisionen auf die Erkennung von Kollisionen mehrerer mobiler Objekte auswirkt. Stattdessen beantworte ich, wie ein räumlicher Index (Quadtree) die Erkennungsleistung gegenüber der iterativen Lösung verbessert. Die naive (und normalerweise vollkommen feine) Lösung sieht ungefähr so aus:
foreach actor in actorList:
foreach target in actorList:
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Dies hat offensichtlich eine Leistung um O (n ^ 2) mit n der Anzahl der Akteure, die derzeit im Spiel sind, einschließlich Kugeln und Raumschiffe und Außerirdische. Es kann auch kleine statische Hindernisse enthalten.
Das funktioniert fantastisch, solange die Anzahl solcher Gegenstände einigermaßen gering ist, sieht aber ein wenig schlecht aus, wenn mehr als ein paar hundert Objekte geprüft werden müssen. 10 Objekte ergeben nur 100 Kollisionsprüfungen, 100 ergeben 10.000 Prüfungen. 1000 ergibt eine Million Schecks.
Ein räumlicher Index (wie Quadtrees) kann die erfassten Elemente effizient nach geometrischen Beziehungen auflisten. Dies würde den Kollisionsalgorithmus in etwa so ändern:
foreach actor in actorList:
foreach target in actorIndex.neighbors(actor.boundingbox):
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Die Effizienz davon (unter der Annahme einer gleichmäßigen Verteilung von Entitäten): ist normalerweise O (n ^ 1,5 log (n)), da der Index ungefähr log (n) Vergleiche zum Durchlaufen benötigt, gibt es ungefähr sqrt (n) Nachbarn zum Vergleichen , und es gibt n Schauspieler, die überprüft werden müssen. Realistisch gesehen ist die Anzahl der Nachbarn jedoch immer sehr begrenzt, da bei einer Kollision meistens eines der Objekte gelöscht oder von der Kollision entfernt wird. Sie erhalten also nur O (n log (n)). Für 10 Entitäten machen Sie (ungefähr) 10 Vergleiche, für 100 machen Sie 200, für 1000 machen Sie 3000.
Ein wirklich cleverer Index kann sogar die Nachbarsuche mit der Masseniteration kombinieren und einen Rückruf für jede sich überschneidende Entität ausführen. Dies ergibt eine Leistung von ungefähr O (n), da der Index einmal gescannt und nicht n-mal abgefragt wird.
Es tut uns leid, dass Sie den alten Thread wiederbelebt haben, aber IMHO-normale alte Gitter werden für diese Fälle nicht oft genug verwendet. Ein Gitter bietet viele Vorteile, da das Einsetzen / Entfernen von Zellen spottbillig ist. Sie müssen sich nicht darum kümmern, eine Zelle freizugeben, da das Raster nicht für spärliche Darstellungen optimiert werden soll. Ich sage, dass wir die Zeit für das Festzurren verkürzt haben, indem wir eine Reihe von Elementen in einer alten Codebasis von über 1200 ms auf 20 ms reduziert haben, indem wir einfach den Quad-Tree durch ein Gitter ersetzt haben. Der Fairness halber war dieser Quad-Tree jedoch wirklich schlecht implementiert und speicherte ein separates dynamisches Array pro Blattknoten für die Elemente.
Das andere, was ich äußerst nützlich finde , ist, dass Ihre klassischen Rasterungsalgorithmen zum Zeichnen von Formen zum Durchsuchen des Rasters verwendet werden können. Sie können beispielsweise die Bresenham-Linienrasterung verwenden, um nach Elementen zu suchen, die eine Linie schneiden, die Scanline-Rasterung, um zu ermitteln, welche Zellen ein Polygon schneiden usw. Da ich viel in der Bildverarbeitung arbeite, ist es sehr schön, dasselbe verwenden zu können optimierter Code Ich zeichne Pixel in ein Bild, um Schnittpunkte mit sich bewegenden Objekten in einem Raster zu erkennen.
Um ein Raster effizient zu gestalten, sollten Sie jedoch nicht mehr als 32 Bit pro Rasterzelle benötigen. Sie sollten in der Lage sein, eine Million Zellen in weniger als 4 Megabyte zu speichern. Jede Gitterzelle kann nur das erste Element in der Zelle indizieren, und das erste Element in der Zelle kann dann das nächste Element in der Zelle indizieren. Wenn Sie eine Art vollwertigen Container mit jeder einzelnen Zelle lagern, wird die Speichernutzung und die Zuweisung schnell explosionsartig. Stattdessen können Sie einfach Folgendes tun:
Wie so:
Okay, so weiter zu den Nachteilen. Zugegeben, ich gehe dies mit einer Vorliebe für Gitter an, aber ihr Hauptnachteil ist, dass sie nicht spärlich sind.
Der Zugriff auf eine bestimmte Gitterzelle unter Angabe einer Koordinate erfolgt in konstanter Zeit und erfordert keinen günstigeren Abstieg über einen Baum, aber das Gitter ist dicht und nicht dünn, sodass Sie möglicherweise mehr Zellen als erforderlich überprüfen müssen. In Situationen, in denen Ihre Daten sehr dünn verteilt sind, muss das Raster möglicherweise stärker überprüft werden, um die Elemente zu ermitteln, die sich schneiden, beispielsweise eine Linie oder ein gefülltes Polygon oder ein Rechteck oder ein Begrenzungskreis. Das Raster muss diese 32-Bit-Zelle speichern, auch wenn sie vollständig leer ist. Wenn Sie eine Formschnittabfrage durchführen, müssen Sie diese leeren Zellen überprüfen, ob sie Ihre Form schneiden.
Der Hauptvorteil des Viererbaums ist natürlich seine Fähigkeit, spärliche Daten zu speichern und nur so viel wie nötig zu unterteilen. Das heißt, es ist schwieriger, wirklich gut zu implementieren, besonders wenn sich die Dinge in jedem Frame bewegen. Der Baum muss die untergeordneten Knoten im laufenden Betrieb sehr effizient unterteilen und freigeben, andernfalls wird er zu einem dichten Raster, in dem der Aufwand für das Speichern von übergeordneten und untergeordneten Links verschwendet wird. Es ist sehr machbar, einen effizienten Quad-Tree mit sehr ähnlichen Techniken zu implementieren, wie ich es oben für das Grid beschrieben habe, aber im Allgemeinen wird es zeitintensiver sein. Und wenn Sie es so machen, wie ich es im Grid mache, ist das auch nicht unbedingt optimal, da es zu einem Verlust in der Fähigkeit führen würde, sicherzustellen, dass alle 4 Kinder eines Quad-Tree-Knotens zusammenhängend gespeichert werden.
Auch ein Quad-Tree und ein Grid leisten keine großartige Arbeit, wenn Sie eine Reihe großer Elemente haben, die einen Großteil der gesamten Szene umfassen, aber zumindest bleibt das Grid flach und unterteilt sich in diesen Fällen nicht bis zum n-ten Grad . Der Quad-Baum sollte Elemente in Zweigen speichern und nicht nur Blätter, um solche Fälle vernünftig zu behandeln, sonst möchte er sich wie verrückt unterteilen und die Qualität extrem schnell herabsetzen. Es gibt weitere pathologische Fälle wie diesen, die Sie mit einem Quad-Tree behandeln müssen, wenn Sie möchten, dass er die unterschiedlichsten Inhalte verarbeitet. Ein weiterer Fall, bei dem ein Quad-Tree zum Stolpern gebracht werden kann, ist beispielsweise, wenn Sie eine Schiffsladung von zusammenfallenden Elementen haben. An diesem Punkt greifen einige Leute einfach darauf zurück, eine Tiefenbegrenzung für ihren Quad-Tree festzulegen, um zu verhindern, dass er unendlich unterteilt wird. Das Gitter hat den Reiz, dass es einen anständigen Job macht,
Die Stabilität und Vorhersehbarkeit ist auch im Spielkontext von Vorteil, da Sie manchmal nicht unbedingt die schnellste Lösung für den Normalfall wünschen, wenn es in seltenen Fällen gelegentlich zu Schluckauf bei den Bildraten kommen kann, im Vergleich zu einer Lösung, die relativ schnell ist. Dies führt jedoch nie zu solchen Schluckaufen und sorgt dafür, dass die Frameraten reibungslos und vorhersehbar sind. Ein Gitter hat diese letztere Qualität.
Nach alledem denke ich wirklich, dass es an dem Programmierer liegt. Mit Dingen wie Grid vs. Quad-Tree oder Octree vs. KD-Tree vs. BVH ist meine Stimme der produktivste Entwickler mit einem Rekord an sehr effizienten Lösungen, egal welche Datenstruktur er / sie verwendet. Auch auf Mikroebene gibt es eine Menge, wie Multithreading, SIMD, Cache-freundliche Speicherlayouts und Zugriffsmuster. Einige Leute mögen diese Mikro in Betracht ziehen, aber sie haben nicht unbedingt eine Mikroauswirkung. Solche Dinge können von einer Lösung zur anderen einen 100-fachen Unterschied machen. Trotzdem, wenn ich persönlich ein paar Tage Zeit hätte und die Anweisung erhalten würde, eine Datenstruktur zu implementieren, um die Kollisionserkennung von Elementen, die sich in jedem Frame bewegen, schnell zu beschleunigen, wäre es mir in dieser kurzen Zeit besser, ein Raster als ein Quad zu implementieren -Baum.
quelle