Dezentrale Stöße vieler Kugeln (de facto Kreise)

[ichbinsisyphos]

Ich nehme an, sowas haben schon viele gemacht.

Ich hab ein bisschen Probleme mit der CPU-Auslastung.

Als ich noch jedes Objekt mit jedem anderen in Beziehung gesetzt hab (genauer gesagt, das i-te Element mit allen [i+1:]) war die eine core bei ca. 30 Kugeln ausgereizt.

Ich unterteil die Fläche jetzt in Sektoren, deren Anzahl abhängig von der Anzahl der Kugeln und der Gesamtfläche ist. Kollisionen kommen damit nur zwischen Kugeln in den selben Sektoren in Frage. Blöd ist, dass die Grenzkurve der Objekte in mehreren Sektoren gleichzeitig sein kann.
Damit komm ich auf ca. 60 Objekte zur gleichen Zeit.

Es wird aber ganz schön kompliziert, ich muss Kollisionen zwischen 2 Partnern in den Objekten selbst vermerken, sonst kommts zu mehreren Stößen an den Grenzen zweier Sektoren und so weiter ...


Ich hab aber mal ein java-Applet im Browser gesehen, das die Simulation von Stößen hunderter Objekte ermöglicht hat. Was haben die besser gemacht?

Wie kann man sowas am effizientesten angehen?

[Martin Kalbfuß]

Was du brauchst ist ein Quadtree falls du im 2D raum arbeitest. Für 3D ist Ein Octree das richtige Werkzeug.

Dies ist eine Verbesserung deines jetzigen Verfahrens.

http://de.wikipedia.org/wiki/Quadtree

[ichbinsisyphos]

Ich hab leider keine tiefgehende Ahnung von den Konzepten der Informatik.

Wie stellst du dir das im Detail vor? Also ich kann damit also die Bereiche immer feiner unterteilen, aber nur dann wenn sich auch Objekte darin befinden? Und weiter?

Gibts da Implementationen für Quadtrees in python, oder müsst ich das sowieso selbst machen?

[Martin Kalbfuß]

Hier eine ein wenig tiefergehende Beschreibung mit Pseudocode.

http://www.informatik.uni-trier.de/~nae ... ithmus.htm

[ichbinsisyphos]

Ok, danke. kannst du trotzdem nochwas dazu sagen? Es geht also darum, zusammenhängende Bereiche zu finden, zu überprüfen ob sie mehr als eine Kugel enthalten, und die dann für jeden Bereich getrennt stossen zu lassen.

Ich hab im Moment keine Ahnung wie ich das implementieren soll. Ausserdem frag ich mich, ob die Rechenarbeit wirklich weniger ist. Die Objekte den leaves zuordnen ist ja auch nicht gerade billig.

[Martin Kalbfuß]

Hier ein schönes Besipiel das die Effektivität eines Quadtrees im Vergleich zur Brute-Force methode aufzeigt.

http://lab.polygonal.de/2007/09/09/quad ... nstration/

Jetzt hast du schonmal zwei Schöne Kuntwerke . Nein, Spaß bei Seite. Ich bin hier nicht der Profi. Habe selbst noch keinen erstellt. Aber ich hoffe das obige Beispiel hält dich am Ball. Ist auf jeden Fall ein tolles Thema.

Einen hab ich aber noch. Benutze keine Quadratwurzel in deinem Kollisionsalgoritmus. Ist langsam. Statt dessen die Addierten Radi ins Quadrat nehmen und dann vergleichen.
Falls ich was interresantes finde Schreib ich's hier rein.
Viel Erfolg.

[ichbinsisyphos]

Du hast die Bilder also noch gesehen, bevor ich den post gelöscht hab?

Ja, Kunstwerke vielleicht, aber sinnlos. Ich hab dann die Größe der Felder erhöht, nur so machts Sinn. Bringt aber bisher immer noch keinen performance-Vorteil, vor allem, weil bei vielen Objekten ja trotzdem wieder die ganze Fläche belegt ist.

Vielleicht hab ich ja noch was übersehen.

[ichbinsisyphos]

Schön langsam schaut was raus. Felder wieder verkleinert und solche Felder, die nicht mehr als 1 Objekt enthalten können verworfen und müssen auch nicht weiter unterteilt werden.

[Martin Kalbfuß]

Sieht gut aus. Gratulation. Was sagt der Timer? Ist schon ein Geschwindikeitsvorteil festzustellen? Ist ja vor allem interessant zu wissen ob es ein einfaches Gitter abhängt. Einer Billiard- oder Minigolfsimulation steht nicht mehr viel im Wege.

[EyDu]

Mal zwei Gegenfragen: Wie viele Kugeln betrachtest du und wie groß ist das betrachtete Gebiet? Unter Umständen reicht dir ein einfaches Gitter. Dort kannst du dann auch ohne Probleme auf die Nachbarn zugreifen und sehr einfach eingrenzen, welche benachbarten Zellen noch zu testen sind.

[ichbinsisyphos]

... Ist schon ein Geschwindikeitsvorteil festzustellen? ...

Ja und Nein. Die Anzeige ist immer noch langsam, wenn ich sehr viele Objekte nehme, die CPU-Auslastung für python geht aber nicht mehr über 70% hinaus. Ich nehme an, die Darstellung über PyQt4 ist jetzt der Flaschenhals.

Von der CPU-Auslastung hängt die Variante jetzt alle anderen Methoden die ich benutzt habe ab, also auch das einfache Gitter.

[ichbinsisyphos]

Mal zwei Gegenfragen: Wie viele Kugeln betrachtest du und wie groß ist das betrachtete Gebiet? Unter Umständen reicht dir ein einfaches Gitter. Dort kannst du dann auch ohne Probleme auf die Nachbarn zugreifen und sehr einfach eingrenzen, welche benachbarten Zellen noch zu testen sind.

Ja, das ist was ich mit "in Sektoren einteilen" vorher gemeint hab. Die Quadtree-Methode hat aber anscheinend schon große Vorteile.

Ich kann mich bezüglich der Anzahl an Kugeln nicht einschränken, das Programm ist für mich nur eine Spielerei. Ich würd aber gern soviele Objekte wie möglich darstellen können, so dass ich näherungsweise ein Gas unter Einfluß der Schwerkraft simulieren kann. Also mit ~10^24 geb ich mich auf alle Fälle zufrieden

[EyDu]

10^24, das wären in Molekülen gerechnet immerhin schon fast 30g Wasser ^^
Du könntest es auch noch mit einer Extension in C versuchen. Ist auch eine nette Spielerei und bringt sicher noch ein bis zwei Größenordnungen. Wenn du dann noch nicht genug hast, kannst du es noch auf die GPU auslagern...

[Martin Kalbfuß]

Soweit ich mich erinnere gibt es da Pyrex. Damit lässt sich C code direkt in den Python code einbetten.

Was mir jetzt noch so spontan einfällt. Grafische Systeme benutzen in der Regel ja einen Puffer. Ich weiß nicht wie Qt das regelt und ob du das vielleicht ja auch schon machst oder ob du nur Kollisionen testest. Du kannst ja nur die Teile des Puffers auf die Ausgabe kopieren in denen sich auch Objekte befinden.

[Leonidas]

Soweit ich mich erinnere gibt es da Pyrex.

Ich denke es gibt kaum einen Fall wo man noch Pyrax Cython vorziehen würde. Aber wenn es wirklich um Performance geht, würde ich glaube ich direkt auf C gehen, denn Cython generiert schon ziemlich viel Code, der dann von irgendwem ausgeführt werden muss.

[ichbinsisyphos]

Ich will sowieso dieses Semester noch einen C++-Kurs belegen. Ich glaub ich hab mein Abschlussprojekt schon gefunden.