spieleprogrammierer.de

Vielleicht könnte man ja auch einen Contest zum Thema Kollisionserkennung machen.



z.B. 1000 Objekte bewegen sich nach einem definierten Muster in einem definierten Bereich. Nun muss man die Kollisionen erkennen und zählen. Wer am schnellsten 1000 Kollisionen erkannt hat, hat gewonnen. Als Framework läuft halt die brute-force Methode (alle Objekte werden gegeneinander geprüft). Ich finde soetwas macht spass und sinn. Denn das ist ja der developer Alltag Man muss sich dann nur noch Gedanken um die Bedingungen machen und natrülich um das framework.

Keine schlechte Idee!
Um es möglichst nicht ausarten zu lassen, könnte man sagen, dass die Objekte allesamt Rechtecke sind, die sich nicht drehen können. Und ganzzahlige Werte für x, y, Breite und Höhe.
In jedem "Frame" kann sich jedes Objekt dann um eine Einheit nach links, rechts, oben oder unten bewegen.
Kollisionen zählen finde ich nicht gut, lieber eine Liste von Objektpaaren generieren, die kollidieren. Ziel ist es, diese Listen über eine gewisse Anzahl von Frames hinweg korrekt und möglichst schnell zu generieren.

Deine Idee mit den Objektpaaren in einer List ist auch nicht schlecht. Das einzige was mir dazu einfällt, was passiert wenn 3 gleichzeitig kollidieren. Wie groß ist wohl die Wahrscheinlichkeit?

Das macht doch nichts!
Wenn 1, 2 und 3 kollidieren, dann steht in der Liste halt (1, 2), (1, 3) und (2, 3).

Okay, hast mich überredet. So kann man es natürlich auch machen.

Finde ich nicht sehr sinnvoll die Aufgabe. Ist ein wenig, wie wenn man eine Sortieralgorithmus schreiben soll, der schneller ist, als die anderen.

Das Problem ist einfach bereits zu breit diskutiert, als dass da noch viel neues dazu kommen kann..

Hier wird ein Algorithmus beschrieben, welcher in O(nlog(n)+k) läuft (k ist die Grösser der Antwort)

http://books.google.ch/books?id=uXKyuK0j…epage&q&f=false

Und das ganze dann einfach noch zu optimieren stelle ich mir nicht unbedingt sehr spassig vor.. (zumindest nicht der Sinn der Sache)

Zitat von »drakon«

Hier wird ein Algorithmus beschrieben, welcher in O(nlog(n)+k) läuft (k ist die Grösser der Antwort)

http://books.google.ch/books?id=uXKyuK0j…epage&q&f=false

Die Anzeige des Buchs funktioniert zwar im Moment nicht, aber ich vermute mal, dass dieser Algorithmus davon ausgeht, dass man die Berechnung ein einziges Mal macht und danach fertig ist. Du müsstest die dabei verwendete Datenstruktur also für jedes Frame neu aufbauen. Wenn du aber weißt, dass du Objekte hast, die sich bewegen, dann kannst du versuchen, die Datenstruktur aus dem letzten Frame nicht komplett neu zu bauen, sondern anzupassen. Manchmal ist eine Anpassung vielleicht ganz einfach, wenn sich nicht viel getan hat. Manchmal könnte es sich aber auch lohnen, nochmal von vorne neu aufzubauen. Sowas macht man z.B. auch beim Raytracing für animierte Szenen. Ich denke nicht, dass es mit diesem einen Algorithmus getan ist.

Und wer weiß - vielleicht gibt es ja noch andere Algorithmen, die dieselbe Komplexitätsklasse haben, aber in der Praxis dennoch schneller sind?

Oder wie wäre es mit Kreisen statt Rechtecken? Dann könnte man den Algorithmus zumindest nicht direkt 1:1 übernehmen.

Kreise finde ich vollkommen in Ordnung. Warum nicht



Wenn man immer davon ausgeht, dass man nichts verbessern kann, wäre die Menschheit jetzt nicht da wo sie ist.





.... Ölpest .... oups ..

Dort werden Segment und Intervalbäume erklärt, wie z.B auch hier:
http://mylinux.rmz.uni-lueneburg.de/fern…Segmentbaum.htm

Natürlich kann man auch Versuchen diese Struktur hier dynamischer zu machen, indem man die Information nutzt, dass sie sich bewegen.

Der komplette Check ist in dieser Laufzeit drin und um O(n) kommst du beim der besten Ausnutzung der Informationen nicht herum und O(logn) ist dazu im Vergleich recht wenig.

Algorithmisch geht es sicher nicht besser (zumindest nicht mit dem Sweep-Line Ansatz, aber auch generell ist das denke ich eine untere Schranke, was aber zu beweisen wäre).

Auf jeden Fall denke ich, dass es eher schwer ist einen anderen Algorithmus zu finden, der bessere Konstanten hat, als der, aber ihr müsst es wissen, ob ihr es machen wollt, oder nicht.

Hmm. Kreise bringen nur eine kleine Anpassung des Algorithmus. Vielleicht vereinfacht sich das ganze aber auch extrem. Das müsste ich mir mal genau überlegen.

Ich wollts eigentlich nur mal gesagt haben, damit alle die gleichen Chancen haben, weil der Baum wahrscheinlich nicht sehr bekannt ist, aber doch eine gute Optimierung bringt.

Ich geh davon aus, dass sich nicht viel zwischen Kreisen und Rechtecken tut. Einzig die Bedingung für eine Kollisionsbedingung ändert sich von
links1 < rechts2 && links2 < rechts1 && oben1 < unten2 && oben2 < unten1
auf
(Mx1-Mx2)^2 + (My1-My2)^2 < R1+R2
was doch eine recht einfache Anpassung ist.

Wie wäre es, eine Figur (Kreis, Rechteck, Vieleck?) über eine Fläche zu bewegen und gesucht ist derjenige Punkt, der irgendwann in diesem Ablauf am längsten durchgehend nicht von der Form überdeckt/berührt wird. Gewinner ist derjenige, dessen errechneter Punkt die längte Zeitspanne liefert, in der der Punkt nicht überdeckt wird. Die Größe der Form und ihre Bewegung und die Ablaufdauer ist für alle Teilnehmer gleich aber während der Entwicklung unbekannt, lediglich die Art der Form (= Kreis, Rechteck, Vieleck) ist bekannt.
Schwierig ist nur, eine (zeitliche?) Begrenzung anzugeben, damit das Durchprobieren aller ganzzahligen Punkte und Variationen davon als Lösung ausscheiden.

Auch eine interessante Idee ...
Wäre die Fläche begrenzt?
Könnte die Figur nur an ganzzahligen Koordinaten stehen, so dass man eine Art "Bild" machen könnte?

Die Fläche muss begrenzt sein, sonst könnte der Algorithmus einfach die Figur beobachten und anschließend einen Punkt nehmen, der außerhalb des beobachteten Bewegungsbereichs liegt. Um dies auszuschließen sollte sich die Figur sogar sogar ein wenig über die Flächenränder hinaus bewegen können.
Wenn die Koordinaten Fließkommawerte sind, könnten numerische Schwierigkeiten dabei auftreten, wann genau ein Punkt die Figur berührt und wann nicht. Ich würde daher Ganzzahlen empfehlen. Dann muss die Fläche aber groß genug sein, um kein Brute Force möglich zu machen. Um ein Bild zu machen bzw. die Bewegung/lösung als Mensch optisch nachzuvollziehen muss man dann halt die Fläche/Figur skalieren.

Autsch, natürlich muss sie begrenzt sein, sonst wär's ja in der Tat sinnlos!