Kollision - Jeder gegen Jeden

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
B.G.Michi
Establishment
Beiträge: 163
Registriert: 07.03.2006, 20:38
Alter Benutzername: B.G.Michi
Kontaktdaten:

Kollision - Jeder gegen Jeden

Beitrag von B.G.Michi »

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
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Kollision - Jeder gegen Jeden

Beitrag von Chromanoid »

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.
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: Kollision - Jeder gegen Jeden

Beitrag von antisteo »

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.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Kollision - Jeder gegen Jeden

Beitrag von Schrompf »

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.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Kollision - Jeder gegen Jeden

Beitrag von Krishty »

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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Kollision - Jeder gegen Jeden

Beitrag von Schrompf »

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.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Kollision - Jeder gegen Jeden

Beitrag von Chromanoid »

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.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Kollision - Jeder gegen Jeden

Beitrag von Schrompf »

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.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
B.G.Michi
Establishment
Beiträge: 163
Registriert: 07.03.2006, 20:38
Alter Benutzername: B.G.Michi
Kontaktdaten:

Re: Kollision - Jeder gegen Jeden

Beitrag von B.G.Michi »

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.
Thargan
Beiträge: 14
Registriert: 06.12.2014, 19:08

Re: Kollision - Jeder gegen Jeden

Beitrag von Thargan »

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.
Antworten