Collisiondetection - Richtig gemacht?

[Network]

Hi,

- Ich möchte eine art "Radar" implementieren.
= Alle Objekte (die sich ständig bewegen) innerhalb eines Maximalradius anzeigen.
- Das Radar selbst bewegt sich auch ständig

Damit ich nicht konstant den Satz des Pythagoras an allen Objekten berechnen muss, dachte ich an die Kollisionserkennungsmethode. (Gerade eben durch einen anderen Post mit ähnlichem Thema wieder daran erinnert worden)
In einigen Artikeln im Internet liest man darüber, dass die Objekte selbst räumlich zugeteilt werden sollten. Erst wenn sich 2 Objekte im selben Raum befinden, sollte man weiter exakt berechnen, ob die Objekte kollidieren.
Bzw. in meinem Fall den Abstand zwischen zwei Punkten berechnen.

Das habe ich vor einiger Zeit auch mal versucht umzusetzen und aufgegeben.
- Mir kam nähmlich die Frage nach auf, wie man es denn eig. überhaupt Umsetzen sollt...
- Oder was passiert, wenn sich das Objekt in zwei Räumen gleichzeitig befindet?

Umgesetzt habe ich es so:
- Der Raum ist virtuell aufgeteilt in 4 "Räume", die wiederum sich in 4 "Räume" aufteilen etc... etc..., bis irgendwann eine Minimalgröße erreicht wurde. Der letzte "Raum" enthält eine ArrayList (Richtiger Container?) in der die Objekte gespeichert werden können.
- Jedesmal wenn sich ein Objekt bewegt, wird es aus der gegebenen ArrayList gelöscht und wieder geprüft in welchem Raum es sich jetzt befindet und dort hinzugefügt.
- Das bewegliche Radar bekommt einer der oberen Räume zugeteilt.
Dass heißt, jedesmal wenn sich das Radar bewegt, wird jeder Raum bzw. Unterraum solange durchgegangen, bis der minimalste Unterraum gefunden wurde, der alle Räume umfasst, die im Maximalradius liegen.
Das heißt natürlich, ragt der Maximalradius über die Kante des 2. größten Raumes um 1 Pixel nach draussen, wird dem Radar der größte Raum zugeordnet und damit werden alle Räume vom radar geprüft.
(Ein sehr blöder Umstand, aber darauf habe ich keine Antwort im Internet gefunden, was man macht wenn bei der Kollisionserkennung, ein Objekt über die Grenzen ragt)

Die Frage: Habe ich das so richtig gemacht? Dadurch dass ich im Internet keinen Bspcode gefunden habe, finde ich es schwer einzuschätzen.

Vielen Dank
Gruß
Net

PS: Den Originalcode habe ich mir erspart hereinzusetzen, da ich es nur zu gut kenne, dass man dann am Ende eh zu faul ist, den durchzugehen und unübersichtlich wird der Thread dann auch noch

 

[Marco13]

"The more you know..." : Das ist ein Thema über das man sehr lange nachdenken und reden kann. Genau dann stellen sich viele der ("Detail"?)fragen, die du jetzt aufgelistet hast.

Umgesetzt habe ich es so:
- Der Raum ist virtuell aufgeteilt in 4 "Räume", die wiederum sich in 4 "Räume" aufteilen etc... etc..., bis irgendwann eine Minimalgröße erreicht wurde. Der letzte "Raum" enthält eine ArrayList (Richtiger Container?) in der die Objekte gespeichert werden können.

Da gibt es schon verschiedene Ansätze. (Es geht erstmal nur um 2D?). Das, was du beschrieben hast, ist ein Quadtree - also eine Hierarchische Aufteilung mit gleichen Zellengrößen. Als nicht-hierarchische Alternative käme noch "Spatial Hashing" in Frage: Dort wird der Raum von vornherein fix in "kleine" Zellen eingeteilt. Dann wird jedes Objekt berechnet, welche Zellen es berührt. In jeder dieser Zellen wird eine Referenz auf das Objekt gespeichert. Bei der Kollisionserkennung muss man dann alle diese Zellen für ein Objekt durchgehen, und schauen, ob dort auch eine Referenz auf ein anderes Objekt gespeichert ist. Das ganze bietet sich (aus dem Bauch heraus) eher an, wenn man (im Vergleich zur Raum- und Gittergröße) kleine, weit verstreute Objekte hat. Für den beschriebenen Fall der Abstandsberechnung zwischen Punkten (die Prinzipbedingt immer nur EINE Zelle belegen können) würde sich das evtl. anbieten.

Aber eigentlich wäre das im Idealfall gar nicht so wichtig: Sowohl ein Spatial Hashing, als Auch Quad- oder KD-Trees oder andere Strukturen können für diese sogenannte "Broad Phase" der Collision Detection ein Interface implementieren

interface BroadPhase<T>
{
    List<T> getObjectsPotentiallyCollidingWith(T t);
}

(sehr idealisiert und vereinfacht )

Ob eine Liste die geeignetste Datenstruktur ist, ist schwer zu sagen: Das kommt eindeutig auf die Situation und den Anwendungsfall an (wie viele wie große Objekte bewegen sich wie schnell...?)

- Jedesmal wenn sich ein Objekt bewegt, wird es aus der gegebenen ArrayList gelöscht und wieder geprüft in welchem Raum es sich jetzt befindet und dort hinzugefügt.
- Das bewegliche Radar bekommt einer der oberen Räume zugeteilt.
Dass heißt, jedesmal wenn sich das Radar bewegt, wird jeder Raum bzw. Unterraum solange durchgegangen, bis der minimalste Unterraum gefunden wurde, der alle Räume umfasst, die im Maximalradius liegen.
Das heißt natürlich, ragt der Maximalradius über die Kante des 2. größten Raumes um 1 Pixel nach draussen, wird dem Radar der größte Raum zugeordnet und damit werden alle Räume vom radar geprüft.
(Ein sehr blöder Umstand, aber darauf habe ich keine Antwort im Internet gefunden, was man macht wenn bei der Kollisionserkennung, ein Objekt über die Grenzen ragt)

Daran habe ich jetzt keine direkte Frage erkannt. "Das ist halt so". Diese Broad Phase mit der Hierarchie ist ja ein konservativer Test: Sie wird viele "false positives" liefern, die dann bei genauerer Prüfung ("Narrow Phase") eben doch nicht kollidieren.
Die Aktualisierung bei bewegten Objekten, die du erwähnt hast, ist dabei ziemlich wichtig. Wenn sich ALLE Objekte bewegen, und quasi ALLES aktualisiert werden muss, muss man aufpassen, dass es nicht zu langsam wird.
Die Strukturen der Broad Phase so aufzubauen, dass sie möglichst wenige false positives liefert, und trotzdem noch schnell überprüft und aktualisiert werden kann ist eben der entscheidende Punkt.

 

[Network]

Ok vielen dank. Ja ich denke bereits seit gut über einem halben Monat darüber nach. Es könnte der wichtigste Teil sein.

Aus dein Text hab ich jetzt geschätzte, fast gezählte 9 mal durchgelesen innerhalb von 30Minuten und eine ganze Menge von Informationen herausfiltern können
Schön wenn man eine Antwort bekommt von jmd. der sich in seiner Diplomarbeit darum bemüht hat (War zufällig über den anderen Thread gestolpert, beim benutzen der Foren-Suchfunktion). Danke.
Auf jedenfall ist es zum Teil auch eine Bestätigung sowie Verwerfung meines bestehenden Codes... das hilft mir in dem Sinn auch weiter, dass ich den richtigen Gedanken habe und hier nicht gegen eine Wand programmiere...

Wobei mir jetzt nurnoch eine Sache offen bliebe... die Suche nach den richtigen Containern.
Es kennt nicht zufällig jmd. eine Liste in der alle Container von Java aufgelistet sind?
Oder einfach eine Liste bei der man schnell removen und adden kann sowie alle Elemente durchgehen(Reihenfolge ist völlig egal)?
Leider musste ich fesstellen auf sehr unangenehme eindrückliche Weise, wie ungeschickt ArrayLists in Extremfällen werden können.

Vielen Dank

 

[Marco13]

Für die Einträge in den Blättern kann man da ja sehr flexibel bleiben:

//private Container<T> container = new ArrayList<T>(); // Ach nee, war doch blöd
private Container<T> container = new HashSet<T>(); // Hier besser

Mehr als add/remove/contains/iterator braucht man ja i.a. nicht. Eine HashSet könnte hier OK sein, aber welcher Container der "beste" ist, hängt vom konkreten Anwendungsfall ab.

Ich wollte schonmal ein paar Klassen für solche Dinge erstellen: Kollisionerkennung allgemein, BVHs, und vielleicht die ganzen Primitiventests. Aber... erstens braucht man da SEHR viel Zeit dafür (wie immer: Wenn man's richtig machen will) und zweitens zieht das so einen Rattenschwanz an Anforderungen hinter sich her: Was macht eine BVH für einen Sinn, wenn man keine Meshes hat, mit denen man sie aufbauen kann? Dann bräuchte man noch Repräsentationen von Boxes, Spheres, Polytopes, Planes, K-DOPs ... Und das alles mal rendern zu können wäre auch nicht schlecht. Für die Primitiventests bräuchte man auch irgendwelche Klassen, einerseits für die Entitäten an sich, andererseits für 3D-Vektoren & Co. ... Schnittpunkt- und Abstandsbestimmung zwischen allen geometrischen Primitiven, CCD ... Ich glaube, in der Praxis ist man fast gezwungen, immer gerade das hin-zu-hacken, was man gerade braucht, weil das alles schon bei dem Versuch, einen Hauch von Allgemeingültigkeit reinzubringen, unverhältnismäßig aufwändig werden würde.

 

[Network]

Ja das ist mir leider zu oft aufgefallen...

Also vielen Dank für die Hilfe. Wusste nicht, dass ein HashSet all ihre Einträge preisgibt. Habe die immer im Doppelpack mit einer ArrayList verwendet, wenn ich relativ oft und sehr schnell wissen wollte, ob ein bestimmtes Objekt in der ArrayList gespeichert ist...

Wie dem auch sei, Thema als erledigt markiert.