ZFX + Developia

Guten Tag

nicht zum ersten mal fehlt es mir an sinnvollem Input für Big Google und ich bin mir ziemlich sicher ihr könnt da aushelfen. Folgendes Problem:

Ein vector von Objekten die auf Kollision überprüft werden sollen. Selbstverständlich jede Kombination nur 1x, also z.B. für 10 Objekte jedes Objekt i in [0; 9] mit jedem Objekt j in [i+1; 9]. Dies soll nun mit einer beliebigen Anzahl an Threads geschehen und zwar so, dass niemals ein Objekt gleichzeitig mehrfach bearbeitet wird.

Das scheint mir ein Problem zu sein, das bestimmt hier und da mal auftaucht. Gibt es da evtl. eine geschickte Zählweise? Ein paar Begriffe zum googeln würden mir vermutlich schon weiter helfen.

Vielen Dank
JFF_B.G.Michi

Mich würden da auch Lösungen interessieren. Ich bin vor einiger Zeit mal ein ähnliches Problem angegangen, allerdings nicht unter der Bedingung, dass die Objekte nicht gleichzeitig bearbeitet werden.
Siehe hier: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen Evt. kann man die "Kombinations-Sektoren" so aufteilen, dass bei der entsprechenden Anzahl an Threads keine Überschneidungen auftreten.

Wieso willst du jeden mit jedem prüfen? Das wird bei einer großen Anzahl von Objekten sehr rechenaufwendig. Baue dir lieber eine Beschleunigungsdatenstruktur, um im Vorhinein schon gewisse Kollisionen ausschließen zu können.

Wenn die Objekte irgendwie gegeneinander zu ordnen sind, könnte man doch ganz einfach nur gegen "hintere" Objekte testen.

Also: Objekt 0 testet gegen 1 bis 9
Objekt 1 testet gegen 2 bis 9, weil 0 bereits gegen 1 getestet hat
Objekt 2 testet gegen 3 bis 9, weil 0 bereits gegen 1 und 2 und 1 gegen 2 getestet hat

Doppeltests ausgeschlossen, jedes Objekt kann parallel getestet werden.

Ansonsten: was antisteo sagt. Bevor Du an Parallelisierung denkst, schau erstmal nach Beschleunigungsstrukturen. Die bringen nämlich deutlich mehr, weil sie die Komplexität der Aufgabe senken können.

Schrompf hat geschrieben:Wenn die Objekte irgendwie gegeneinander zu ordnen sind, könnte man doch ganz einfach nur gegen "hintere" Objekte testen.

Das ist immernoch O(n²).

————

Meine Spielwelt ist begrenzt, und ich unterteile sie in ein Raster von Kacheln. (Meist reicht 2D aus.)

Jedes Objekt wird, sobald es sich in eine Kachel bewegt, dort eingetragen. Die Physiksimulation berechnet Interaktionen zwischen allen Objekten in einer Kachel (jedes mit jedem). Objekte, die während eines Frames die Grenze zu einer anderen Kachel überqueren (das sind immer sehr wenige), kommen in eine spezielle Liste und werden gegen Objekte in allen umliegenden Kacheln getestet.

Viele alte Spiele (vor allem auf begrenzten Systemen wie PSX) haben es so gemacht, und die Vorteile liegen auf der Hand: Je nach Raster kriegt man das n in O(n²) sehr klein. Das Einsortieren hat bei einem regelmäßigen Raster konstante Laufzeit, oder bei einer Baumstruktur Logarithmische – verschwindet also fast ganz, zumal man nur Objekte aus der „Überqueren“-Liste einsortieren muss.

Problematisch wird es nur bei sehr schnellen Objekten: Keines darf mehr als eine Kachel pro Iteration durchqueren. Die Kachel- und Randgröße sollte also groß genug sein, dass irgendeine obere Geschwindigkeitsgrenze (sechsfache Schallgeschwindigkeit in meinem Fall) keine Sprünge erlaubt.

Krishty hat geschrieben:

Schrompf hat geschrieben:Wenn die Objekte irgendwie gegeneinander zu ordnen sind, könnte man doch ganz einfach nur gegen "hintere" Objekte testen.

Das ist immernoch O(n²).

Klar, aber darum ging's ja auch gar nicht. Soweit ich das verstanden habe, wollte der Diskussionsgründer parallelisieren und dabei vermeiden, dass verschiedene Threads das selbe Kollisionspaar testen. Und das sollte damit gehen.

Dass Parallelisierung in diesem Fall evtl. gar nicht die richtige Methode zur Beschleunigung ist, ist ein ganz anderes Thema.

So wie ich das verstanden habe, soll ein Objekt nicht von zwei Threads gleichzeitig "angeschaut" werden. Das kann beim einfachen Ablaufen, so wie Du es vorgeschlagen hast, aber noch passieren.

Stimmt, ich hatte das anders gelesen. Tja... knifflig. Ich würde dann vorschlagen, die Objekte nicht gleich zu ändern, sondern die sich aus den Kombinationen ergebenden Änderungen erstmal zu sammeln. Nach dem Testen kann man dann die gesammelten Änderungen anwenden.

So, nach dem ganzen Halloweengedöns jetzt wieder zu den wichtigen Dingen des Lebens :D Und das hier wird wohl doch ein größeres Unterfangen als erhofft. Da Objekte nur über Kollisionen oder Constraints miteinander wechselwirken ist unter der Annahme, dass es "wenig" Constraints gibt, der restliche Teil der Physikberechnung relativ trivialparallelisierbar (edit: und Kräfte aber die sind recht wenig rechenaufwändig). Aber ihr habt schon Recht: die Objekte sollten für die Kollisionserkennung wohl räumlich angeordnet werden, ich tendiere zu einer einfachen Kachel-/Würfelstruktur. Die einzelnen Raumbereiche können dann parallel getestet werden und ich muss mir (nur) noch Gedanken um die Ränder machen.

OK das hier ist ein Jahr alt, aber ich habe trotzdem eine Idee dazu.

Die Sache mit der Reihenfolge ist viel. schon ok.
Aber wenn es keine feste Reihenfolge gibt, würde ich ein Flag für jedes Objekt nehmen.
Wenn das Objekt sich gegen alle anderen getestet hat, ist das Flag True.

Bevor also ein Objekt getestet wird, testet man zuerst das Flag.

Sollen nun wirklich mehrere Threads zum Zuge kommen, nimmt man ein zweites Flag, das als Marker für Bearbeitung gilt.
Somit ist noch eine Prüfung erforderlich, bevor man den eigentlichen Test startet.

Ich glaube nicht, dass man auch mit mehreren Threads schneller wird, da man sich im Singlethread mehrere Tests sparen kann.