Wie kann man kontinuierlich alle Objekte innerhalb eines Radius effizient finden?

14

Ich habe eine sehr große Anzahl von Einheiten. Auf jeder Stufe muss jede Einheit , die die Positionen von allen Einheiten in der Nähe davon wissen (Abstand kleiner dann konstant gegebene R ). Alle Einheiten bewegen sich kontinuierlich. Dies ist in 3D.

Im Durchschnitt gibt es 1% der Gesamtzahl der Einheiten in der Nähe einer anderen gegebenen Einheit mit den gegebenen Einschränkungen.

Wie kann ich das effizient tun, ohne bruteforcing?

OCyril
quelle
7
Sie werden eine Art räumliches Partitionierungssystem wollen: en.wikipedia.org/wiki/Space_partitioning
Tetrad

Antworten:

15

Verwenden Sie einen der gängigen Raumpartitionierungsalgorithmen, z. B. einen Quadtree-, Octree-, BSP-Baum oder sogar ein einfaches Grid-System. Jeder hat seine eigenen Vor- und Nachteile für jedes spezifische Szenario. Sie können mehr über sie in diesen Büchern lesen .

Im Allgemeinen (oder wie ich gehört habe, bin ich mit der Begründung dahinter nicht allzu vertraut) ist ein Quadtree oder Octree besser für Außenumgebungen geeignet, während der BSP-Baum besser für Innenaufnahmen geeignet ist. Und die Wahl zwischen einem Quadtree oder einem Octree hängt davon ab, wie flach Ihre Welt ist. Wenn die Y-Achse mit einem Octree nur geringfügig variiert, wäre dies eine Verschwendung. Ein Octree ist im Grunde ein Quadtree mit einer zusätzlichen Dimension.

Schließlich sollten Sie die Einfachheit der Grid-Lösung nicht außer Acht lassen. Viele Leute ignorieren, dass ein einfaches Raster manchmal genug (und sogar effizienter) für ihre Probleme sein kann, und springen stattdessen direkt zu einer komplexeren Lösung.

Die Verwendung eines Rasters besteht einfach darin, die Welt in gleichmäßig verteilte Regionen zu unterteilen und die Entitäten in der entsprechenden Region der Welt zu speichern. Wenn Sie dann eine Position angeben, müssen Sie die Regionen, die Ihren Suchradius überschneiden, durchlaufen, um die benachbarten Objekte zu finden.

Angenommen, Ihre Welt reichte von (-1000, -1000) bis (1000, 1000) in der XZ-Ebene. Sie können es zum Beispiel in ein 10x10-Raster aufteilen, wie folgt:

var grid = new List<Entity>[10, 10];

Dann platzieren Sie die Objekte in den entsprechenden Zellen des Rasters. Beispielsweise würde eine Entität mit XZ (-1000, -1000) auf Zelle (0,0) fallen, während eine Entität mit XZ (1000, 1000) auf Zelle (9, 9) fallen würde. Wenn Sie dann eine Position und einen Radius in der Welt angeben, können Sie bestimmen, welche Zellen von diesem "Kreis" geschnitten werden, und nur über diese iterieren, mit einem einfachen Doppel für.

Wie auch immer, recherchieren Sie alle Alternativen und wählen Sie die aus, die zu Ihrem Spiel besser zu passen scheint. Ich gebe zu, ich bin immer noch nicht gut genug informiert, um zu entscheiden, welcher der Algorithmen für Sie am besten geeignet ist.

Edit Fand dies in einem anderen Forum und es könnte dir bei der Entscheidung helfen:

Raster funktionieren am besten, wenn die meisten Objekte in ein Rasterfeld passen und die Verteilung ziemlich homogen ist. Umgekehrt funktionieren Quadtrees, wenn die Objekte variable Größen haben oder in kleinen Bereichen gruppiert sind.

Angesichts Ihrer vagen Beschreibung des Problems lehne ich mich auch an die Rasterlösung (vorausgesetzt, die Einheiten sind klein und ziemlich homogen verteilt).

David Gouveia
quelle
Danke für die ausführliche Antwort. Ja, es scheint so, als ob eine einfache Grid-Lösung für mich gut genug ist.
OCyril,
0

Ich habe das vor einiger Zeit geschrieben. Es ist jetzt auf einer kommerziellen Website, aber Sie können die Quelle für den persönlichen Gebrauch kostenlos erhalten. Es mag übertrieben sein und ist in Java geschrieben, aber es ist gut dokumentiert, so dass es nicht zu schwierig sein sollte, es in einer anderen Sprache zu schneiden und umzuschreiben. Grundsätzlich wird ein Octree mit Optimierungen verwendet, um sehr große Objekte und Multithreading zu handhaben.

Ich fand, dass ein Octree die beste Kombination aus Flexibilität und Effizienz bietet. Ich begann mit einem Raster, aber es war unmöglich, die Quadrate richtig zu dimensionieren, und große Flecken leerer Quadrate verbrauchten Platz und Rechenleistung für nichts. (Und das war nur in zwei Dimensionen.) Mein Code Griff Anfragen von mehreren Threads, die eine fügt Menge der Komplexität, aber die Dokumentation sollten Sie um Hilfe arbeiten, wenn Sie es nicht brauchen.

RalphChapin
quelle
0

Um Ihre Effizienz zu steigern, versuchen Sie, 99% der "Einheiten", die sich nicht in der Nähe der Zieleinheit befinden, mithilfe eines sehr kostengünstigen Kontrollkästchens trivial zurückzuweisen. Und ich hoffe, Sie könnten dies tun, ohne Ihre Daten räumlich zu strukturieren. Wenn alle Ihre Einheiten in einer flachen Datenstruktur gespeichert sind, können Sie versuchen, sie von Anfang bis Ende zu durchlaufen, und zunächst überprüfen, ob sich die aktuelle Einheit außerhalb des Begrenzungsrahmens der gewünschten Einheit befindet.

Definieren Sie einen übergroßen Begrenzungsrahmen für die Einheit von Interesse, sodass er sicher Elemente ablehnen kann, die nicht als "nahe" angesehen werden können. Die Prüfung auf Ausschluss von einem Begrenzungsrahmen könnte billiger als eine Radiusprüfung sein. Bei einigen Systemen, bei denen dies getestet wurde, wurde jedoch festgestellt, dass dies nicht der Fall ist. Die beiden sind fast gleich stark. Dies bearbeitete nach langer Diskussion weiter unten.

Erstens: 2D-Begrenzungsrahmenclip.

// returns true if the circle supplied is completely OUTSIDE the bounding box, rectClip
bool canTrivialRejectCircle(Vertex2D& vCentre, WorldUnit radius, Rect& rectClip) {
  if (vCentre.x + radius < rectClip.l ||
    vCentre.x - radius > rectClip.r ||
    vCentre.y + radius < rectClip.b ||
    vCentre.y - radius > rectClip.t)
    return true;
  else
    return false;
}

Im Vergleich zu so etwas (in 3D):

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  D3DVECTOR relPos = obj1->prPosition - obj2->prPosition;
  float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
  float minDist = obj1->fRadius + obj2->fRadius;
  return dist <= minDist * minDist;
}.

Wenn das Objekt nicht einfach zurückgewiesen wird, führen Sie einen teureren und genaueren Kollisionstest durch. Aber Sie suchen nur nach Nähe, deshalb ist der Kugeltest dafür geeignet, aber nur für 1% der Objekte, die die triviale Zurückweisung überleben.

Dieser Artikel unterstützt die Box für triviale Ablehnung. http://www.h3xed.com/programming/bounding-box-vs-bounding-circle-collision-detection-performance-as3

Wenn Sie mit diesem linearen Ansatz nicht die Leistung erhalten, die Sie benötigen, ist möglicherweise eine hierarchische Datenstruktur erforderlich, über die die anderen Poster bereits gesprochen haben. R-Bäume sind eine Überlegung wert. Sie unterstützen dynamische Änderungen. Sie sind die Bäume der räumlichen Welt.

Ich wollte nur nicht, dass Sie sich die Mühe machen, eine solche Komplexität einzuführen, wenn Sie sie vermeiden könnten. Und was ist mit den Kosten für die Aktualisierung dieser komplexen Datenstruktur, wenn sich Objekte mehrmals pro Sekunde bewegen?

Bedenken Sie, dass ein Gitter eine tiefe Geodatenstruktur mit einer Ebene ist. Dieses Limit bedeutet, dass es nicht wirklich skalierbar ist. Je größer die Welt wird, desto mehr Zellen müssen abgedeckt werden. Irgendwann wird diese Anzahl von Zellen selbst zu einem Leistungsproblem. Für eine Welt mit einer bestimmten Größe bedeutet dies jedoch eine massive Leistungssteigerung gegenüber einer räumlichen Aufteilung.

Ciaran
quelle
1
Das OP sagte ausdrücklich, er wolle einen Brute-Force-Ansatz vermeiden, genau das, was Sie in Ihrem ersten Absatz beschrieben haben. Wie ist ein Bounding-Box-Check billiger als ein Bounding-Sphere-Check ?! Das ist einfach falsch.
notlesh
Ja, ich weiß, dass er brachiale Gewalt vermeiden möchte, die vermieden werden würde, wenn eine hierarchische Datenstruktur in seine Anwendung eingefügt würde. Aber das könnte eine Menge Aufwand bedeuten. Wenn er das noch nicht will, kann er den linearen Ansatz ausprobieren, der brachial ist, aber möglicherweise nicht so schlecht abschneidet, wenn seine Liste nicht sehr groß ist. Ich werde versuchen, den obigen Code so zu bearbeiten, dass er in meine 2D-Bounding-Box-Trivial-Reject-Funktion eingefügt wird. Ich glaube nicht, dass ich mich geirrt habe.
Ciaran
Die Verbindung zu GDnet ist unterbrochen, aber der kanonische Sphäre-Test ist sehr einfach, sehr billig und verzweigt nicht:inside = (dot(p-p0, p-p0) <= r*r)
Lars Viklund
Ich habe den Code stattdessen oben eingefügt. Es sieht alles andere als billig im Vergleich zu Bounding Box aus.
Ciaran
1
@Ciaran Ganz ehrlich, dieser Artikel scheint wirklich schlecht zu sein. Zunächst werden die Tests nicht mit realistischen Daten durchgeführt, sondern immer wieder dieselben Werte verwendet. Nichts, dem Sie in einem realen Szenario begegnen werden. Und nein, laut Artikel ist der BB nur dann schneller, wenn es keine Kollision gibt (zB die Prüfung schlägt bei der ersten ifAussage fehl ). Auch nicht sehr realistisch. Aber ganz ehrlich, wenn Sie anfangen, solche Dinge zu optimieren, dann beginnen Sie definitiv am falschen Ort.
Mistzack
0

Ich muss darauf eine Antwort geben, weil ich nicht die Punkte habe, um zu kommentieren oder zu stimmen. Für 99% der Personen, die diese Frage stellen, ist ein Begrenzungsrahmen die Lösung, wie von Ciaran beschrieben. In einer kompilierten Sprache werden im Handumdrehen 100.000 irrelevante Einheiten verworfen. Mit nicht-brute-force-Lösungen ist viel Aufwand verbunden. Bei kleineren Zahlen (z. B. unter 1000) sind sie in Bezug auf die Verarbeitungszeit teurer als die Brute-Force-Prüfung. Und sie werden erheblich mehr Programmierzeit in Anspruch nehmen.

Ich bin nicht sicher, was "eine sehr große Zahl" in der Frage bedeutet oder was andere Leute, die hier nach Antworten suchen, damit meinen. Ich vermute, meine obigen Zahlen sind konservativ und könnten mit 10 multipliziert werden. Ich persönlich bin ziemlich voreingenommen gegenüber Brute-Force-Techniken und ärgere mich sehr darüber, wie gut sie funktionieren. Aber ich möchte nicht, dass jemand mit z. B. 10.000 Einheiten Zeit mit einer ausgefallenen Lösung verschwendet, wenn ein paar kurze Codezeilen den Trick machen. Sie können später immer Lust bekommen, wenn sie müssen.

Außerdem würde ich bemerken, dass eine Begrenzungskugelprüfung eine Multiplikation erfordert, bei der der Begrenzungsrahmen dies nicht tut. Die Multiplikation dauert naturgemäß ein Vielfaches der Addition und Vergleiche. Es muss eine Kombination aus Sprache, Betriebssystem und Hardware geben, bei der die Sphärenüberprüfung schneller ist als eine Boxüberprüfung. In den meisten Fällen muss die Boxüberprüfung jedoch schneller sein, auch wenn die Sphäre einige irrelevante Einheiten ablehnt Box akzeptiert. (Und wo die Kugel schneller ist, wird eine neue Version des Compilers / Interpreters / Optimierers dies sehr wahrscheinlich ändern.)

RalphChapin
quelle
Ihre Antwort ist nicht falsch, aber Sie beantworten die Frage nicht. Es wurde ausdrücklich nach einem "non bruteforce" -Ansatz gefragt. Sie scheinen auch zu wiederholen, was Ciaran bereits geschrieben hat, und wir hatten eine lange Diskussion über AABB vs. Kreistests. Der Leistungsunterschied ist einfach irrelevant. Wählen Sie besser ein Begrenzungsvolumen, das für die meisten Ihrer Kollisionskandidaten geeignet ist, da es die Anzahl der tatsächlichen Tests in engen Phasen verringert, was sich insgesamt stärker auf die Leistung auswirkt.
Mistzack