Spezielle Kollisionsauflösung bei verteilter Verarbeitung

[Chromanoid]

Hallo ihr,

mich interessiert das zwecks Verteilung auf mehrere Rechner schon ziemlich lange. Folgendes Problem:
Ich verteile die Kollisionserkennung auf mehrere Rechner. Nicht jeder Rechner kennt alle Objekte, aber es ist sichergestellt, dass alle Kollisionen erkannt werden. Nun benötige ich einen Algorithmus, der bei der Kollisionsauflösung möglichst so arbeitet, dass theoretisch alle Kollisionen gleichzeitig aufgelöst werden können ohne jeden Rechner mit allen Objekten bekannt zu machen. Ich bin mir allerdings nicht sicher ob das überhaupt möglich ist bzw. zu einigermaßen stabilen Ergebnissen führt. Ein Beispiel:
Objekte: A, B, C, D
A überschneidet sich mit B und B mit C und C mit D -> [A,B], [B,C], [C,D]
Zwei Prozesse: P1, P2
P1 kennt nur die Objekte A und B
P2 kennt nur die Objekte B, C und D
Nun sollen A, B, C und D von P1 und P2 so angepasst werden, dass sie sich nicht mehr überschneiden. Normalerweise verlässt man sich dann ja, soweit ich weiß, auf die Reihenfolge der Auflösung. D.h. z.B. führt [C,D] zu einer Änderung, die dann bei der Auflösung von [B,C] berücksichtigt wird, die dann wieder bei der Auflösung von [A,B] berücksichtigt wird.

Was ich jetzt gerne hätte, wäre ein Algorithmus der damit klar kommt, dass P1 A und B versetzen kann ohne die Veränderungen von C und D zu kennen. Also dass bei der Auflösung der Kollisionen immer nur die direkt durch eine Kollision betroffenen Elemente beim Prozess bekannt sein müssen. D.h. P1 wird zwar über [B,C] informiert, nicht aber über [C,D].

Gibt es einen Algorithmus dieser Art?
Ist es ein gangbarer Weg mit einem getuntem Algorithmus in einem Schritt immer nur die direkt betroffenen Pärchen zu berücksichtigen?
Das letzte mal als ich das versucht habe, sind bestimmte Kombinationen aus Objekten je nach Lokalität wesentlich schlechter aufgelöst worden (eine natürliche Folge des gewählten Algorithmus)...
Gibt es einen sinnvollen Mechanismus die Ergebnisse der einzelnen Prozesse zu verschmelzen? Momentan mache ich es so, dass die Prozesse nacheinander die Auflösung machen und sich nach jedem Schritt über die gemeinsamen bekannten Elemente austauschen. Das ist war schneller als einen Prozess alleine arbeiten zu lassen, aber durch den gesuchten Algorithmus würde es natürlich noch viel schneller werden.

Vielen Dank und viele Grüße
Christian

[kristof]

Was genau macht die Kollisionsauflösung denn? Haben die Objekte alle einen Impuls? Dann könnte ja jeder Prozess unabhängig von anderen Prozessen eine Impulsänderungen für die Objekte berechnen und du summierst die Impulsänderungen am ende auf.
Oder soll die Kollisionsauflösung direkt die Positionen anpassen? Dann wird es natürlich kompliziert.
Vielleicht kannst du auch dafür sorgen, dass echte Kollisionen im Sinne von Überschneidungen überhaupt nicht auftreten. Dazu könntest du dir "Continuous Collision Detection" ansehen. Ich habe in meiner Rigid Body Simulation (natürlich nur ein Prozess) Speculative Contacts implementiert. Das ist eine Vereinfachung von CCD.

[Chromanoid]

Dein Showroom-Post war der Anstoß für meinen Post :) Danke erst mal für die aufschlussreichen Rückfragen!

Ich habe meinen Verteilungsalgorithmus mit dem SequentialImpulseConstraintSolver von (J)Bullet vereint. Da wird soweit ich mich erinnere nur der Impuls angefasst.

Haben die Objekte alle einen Impuls? Dann könnte ja jeder Prozess unabhängig von anderen Prozessen eine Impulsänderungen für die Objekte berechnen und du summierst die Impulsänderungen am ende auf.

Die Impulsänderungen werden doch aber aufeinander bezogen. Das muss auch so sein sonst würden zwei Objekte A und B, die ein anderes Object C schieben, eine übermäßige Verschiebung auslösen. Erst verschiebt A C und dann B C, würde man die Auflösung unabhängig von einander betrachten würde doch ein viel größerer Schub heraus kommen.
Edit: Oder ist das genau der Unterschied zwischen "Sequential Solver" und nicht "Non Sequential Solver" ? :)

Bei CCD müsste ich mir also statt Impulsänderungen Punkte auf dem Zeitstrahl inkl. Rückstoß merken und pro kollidierendem Objekt den frühsten Zeitpunkt auswählen (und zwar mit "gegenseitigem Einverständnis" :))? So würde mir neben der Einverständnis-Problematik ja auch noch Zeit verloren gehen und um das auszugleichen wäre ich doch wieder beim "Summierungsproblem" von oben oder nicht müsste ich viel häufiger die Positionen der Objekte austauschen, oder?


Edit: BTW :) Wie man wahrscheinlich merkt, bin ich kein Experte auf dem Gebiet, sondern Laie und habe Kollisionserkennung letztendlich nur als Anwendungsbeispiel für einen Verteilungsalgorithmus benutzt.

[kristof]

Die Impulsänderungen werden doch aber aufeinander bezogen. Das muss auch so sein sonst würden zwei Objekte A und B, die ein anderes Object C schieben, eine übermäßige Verschiebung auslösen. Erst verschiebt A C und dann B C, würde man die Auflösung unabhängig von einander betrachten würde doch ein viel größerer Schub heraus kommen.

Hm, wenn die Objekte A und B einen Impuls auf C übertragen (das passiert ja beim Schieben), dann wird doch Cs Impuls um die Summe der beiden verändert. Impulserhaltung eben. Eine übermässige Verschiebung tritt nur auf, wenn du die Positionen der Objekte A, B und C direkt veränderst. Das ist das Problem von diskreter Kollisionsauflösung. Deswegen versucht man mit CCD Überschneidungen von vorn herein zu vermeiden.

Bei CCD müsste ich mir also statt Impulsänderungen Punkte auf dem Zeitstrahl inkl. Rückstoß merken und pro kollidierendem Objekt den frühsten Zeitpunkt auswählen (und zwar mit "gegenseitigem Einverständnis" :)). So würde mir neben der Einverständnis-Problematik ja auch noch Zeit verloren gehen und um das auszugleichen wäre ich doch wieder beim "Summierungsproblem" von oben oder nicht?

Ich vernachlässige bei mir die verloren gegangene Zeit ganz einfach. Das mag natürlich von der Grösse der Zeitschritte abhängen, wie sichtbar das am Ende ist.

Edit: Hm, jetzt hab ich es mir noch einmal genauer angesehen, wie ich das löse. Du hast recht. Wenn man den Fall mit dem Schieben hat, dann werden bei Speculative Contacts ja die Geschwindigkeiten angepasst, sodass keine Kollision statt finden wird. Wenn das A und B unabhängig voneinander machen würden, würde C zu stark verändert werden.

[Chromanoid]

Ich poste heute Abend mal meinen (recht simplen) Verteilungsalgorithmus, vielleicht fallen Dir dann ja noch mögliche Probleme ein. Ansonsten werde ich es mal mit Speculative Contacts ausprobieren.

[antisteo]

Verteilte Kollisionsberechnung? Willst du eine komplexe kompakte Welt simulieren oder eine sehr große?

Bei der großen Welt würde es Sinn machen, eine "Lichtgeschwindigkeit" festzulegen, mit der sich Information nicht schneller fortpflanzen kann. Damit ergibt sich automatisch eine Segmentierung der Welt und ein Kollisionsprüfalgorithmus, der NUR auf lokalen Daten arbeitet.

[Chromanoid]

Ich möchte eine Situation simulieren bei der räumliche Segmentierung nicht mehr viel bringt. Bei Kollisionserkennung sind das zum Beispiel viele Kollisionen in einem kleinen Raum, der nicht geteilt werden kann. Im Grunde geht's bei dem Verteilungsalgorithmus einfach nur darum N zu N Probleme auf mehrere Rechner zu verteilen, zum Beispiel als Alternative zu Eve's Time Dilation: https://wiki.eveonline.com/en/wiki/Time_Dilation / http://community.eveonline.com/news/dev-blogs/2437.

[antisteo]

Ich möchte eine Situation simulieren bei der räumliche Segmentierung nicht mehr viel bringt. Bei Kollisionserkennung sind das zum Beispiel viele Kollisionen in einem kleinen Raum, der nicht geteilt werden kann. Im Grunde geht's bei dem Verteilungsalgorithmus einfach nur darum N zu N Probleme auf mehrere Rechner zu verteilen, zum Beispiel als Alternative zu Eve's Time Dilation: https://wiki.eveonline.com/en/wiki/Time_Dilation / http://community.eveonline.com/news/dev-blogs/2437.

Da könntest du den Lokalitätseffekt gut nutzen, indem du N durch X teilst und X² Shares möglichst ideal verteilst.

[Chromanoid]

So ähnlich mache ich das auch. edit: Bedenke aber, dass einen ja eigentlich nur N über 2 Kombinationen bei der Verteilung interessieren.
Letztendlich teile ich, wie Du vorgeschlagen hast, die Elemente ideal auf die Rechner auf, so dass jeder Rechner eine minimale Anzahl der Elemente von N kennen muss und trotzdem alle Kombinationen zustande kommen. Das geht recht einfach, ich schreibe nachher mal meinen kompletten Prozess dazu auf.

edit: Habe mal einen kleinen Artikel zu meinem Lösungsansatz geschrieben: Kleiner Algorithmus zur Aufteilung von N-zu-N Problemen