Kollisionsabfrage - Geeignete Methode

1. offizieller Beitrag

    Servus, ich habe mir gerade einige Gedanken zu Kollisionsabfragen gemacht. Nehmen wir einmal an, wir hätten ein Spielfeld mit 1000 beweglichen Objekten. Jedes Objekt prallt von einem anderen Objekt ab. Wie kann man da die Kollisionsabfrage realisieren? Es ist ziemlich zeitaufwendig jedes einzelne Objekt mit jedem zu vergleichen. Das wären immerhin 999! -1 Schleifendurchläufe.

    999! -1

    402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753471999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

    Gibt es da geeignetere Methoden? Selbst wenn es nur 20 Objekte wären sind immerhin 121645100408831999 Schleifendurchläufe notwendig um jedes Objekt auf Kollision mit jedem Objekt zu prüfen.

    Einmal editiert, zuletzt von Yjuq (15. März 2015 um 21:32)

    In Bereiche aufteilen und die untereinander vergleichen. Spielfeld in 16x16 z.B. trennen.

    Das ist ein sehr guter Tipp zur Optimierung. Bleiben wir mal bei den 20 Objekten bei einem Spielfeld von 10x10. Teile ich also nun das Spielfeld in 4 Bereiche auf und gehe davon aus dass sich in jedem Feld 5 Objekte befinden beträgt die Anzahl der Durchläufe immerhin noch 4 * (4! -1) = 92 Durchläufe. Aber nur wenn keiner der Objekte an einer der Stellen zwischen den Spielbegrenzungen liegt. Gibt es noch weitere Optimierungsmöglichkeiten?

    Kannst ja überlappende Felder nehmen.

    Weißt du was ein Quad(für 2D)/Octree(für 3D) oder (noch besser) ein kd-Tree ist?
    Das sind Datenstrukturen mit welchem man Elemente mit Koordinaten so abspeichert, dass die jeweiligen Nachbarn direkt ermittelt werden können (da es Nachbarn im Baum sind).
    Damit ist das Nearest-Neighbour-Problem für jedes Element furchtbar schnell gelöst. Somit kann man jedes Element immer nur mit seinem Nachbarn vergleichen anstatt mit allen.

    Probleme wären allerdings den Baum nach jeder Koordinatenänderung anzupassen und überhaupt eine derartige Struktur mit Autoit aufzubauen.
    Aber prinzipiell wäre dies ein Ansatz den ich mir vorstellen könnte.

    Speichere in jedem Feld die Nummer des jeweiligen Objektes.
    Bei einer "Kollision" befinden sich mehrere Objekte in diesem Feld. Du brauchst also nur die Anzahl der Objekte (in diesem Fall 20) Abfragen!

    @AspirinJunkie
    Ich schaue mir das mal an, danke für den Hinweis! Die Begriffe habe ich zuvor noch nie gehört. ^^

    @Andy
    Diese Idee mag nur für Objekte funktionieren, die ein einzelnes Feld besetzen. Aber was ist mit den Objekten die mehrere Felder belegen? Bleiben wir mal bei der Einheit Pixel. Bei 20x20px Quadrate sind somit 400 Einträge notwendig. Selbst wenn man die Felder von 1x1px auf 20x20px vergrößern würde, kann es immer noch vorkommen dass ein Objekt 2 oder gar 4 Felder in irgend einer Weise anschneidet. Dann kommt aber noch die Überprüfung hinzu in welchen Feld sich jetzt das Objekt befindet. Bei einfachen Geometrischen Formen mag das vielleicht einfach gehen, aber bei Polygone sieht alles anders aus. Es kann aber auch sein dass ich deine Idee falsch interpretiert habe bei der Uhrzeit oder ich bei meiner Milchmädchenrechnung was falsch mache. :)

    Deshalb nimmt man bei Polygonen als BoundingBox auch Würfel oder Kugeln.

    Zitat von ShitDown

    Selbst wenn man die Felder von 1x1px auf 20x20px vergrößern würde, kann es immer noch vorkommen dass ein Objekt 2 oder gar 4 Felder in irgend einer Weise anschneidet.

    Stichwort Intersection.
    Es ist völlig unerheblich, wie viele "Ecken" das Objekt hat.
    Du kannst einen Umkreis bzw einen Innenkreis schlagen, welcher alle "Ecken" eines Polygons beinhaltet. Wichtig ist zu unterscheiden, ob überhaupt die Möglichkeit einer Kollision besteht.
    Mal angenommen, du hast Objekte der Größe x*x und y*y Pixel (egal mit wievielen Ecken! ) .
    Dann können sich diese Objekte niemals berühren,wenn der Abstand der Mittelpunkte diese Objekte mehr als (x+y)/2 beträgt.
    Somit könnte man die schon von AspirinJunkie angesprochene Nearest Neighbour-Tabelle aufspannen....mit Abständen der Objekte.
    Und erst wenn die Abstände innerhalb des kritischen Bereichs sind, brauchst du diese beiden Objekte per Intersect-Algorithmus auf Überschneidungen vergleichen.

    Du musst dir je nach Anwendung einfallen lassen, was du genau willst.
    Bei deinem Beispiel in Post#3 reicht eine "einfache" Abfrage auf doppelt vorhandene Positionen.

    Zitat

    Du musst dir je nach Anwendung einfallen lassen, was du genau willst.
    Bei deinem Beispiel in Post#3 reicht eine "einfache" Abfrage auf doppelt vorhandene Positionen.

    Das stimmt wohl, habe ja auch sehr allgemein gefragt.

    Danke für eure Antworten, ich nehme mal die Erkenntnisse die ich aus dem Thread gewonnen habe mit. Jedoch verwirrt mich noch dieser k-d-Baum etwas, da finde ich kein für mich verständliches Material im Netz. :D

    Zitat von ShitDown

    Jedoch verwirrt mich noch dieser k-d-Baum etwas, da finde ich kein für mich verständliches Material im Netz.

    Es wäre blödsinnig das alles selbst zu implementieren.
    Dafür gibt es schon genügend sinnvolle Bibliotheken.
    Die wohl meistgenutzte zur Lösung des k-Nearest-Neighbour-Problems ist die FLANN-Bibliothek.

    Ich habe mal ein Grundgerüst für einen AutoIt-Wrapper hierfür erstellt um mal zu zeigen wie man diese in AutoIt verwenden kann.
    Einfach die Zip aus dem Anhang in einen Ordner entpacken und mal die FLANN Example.au3 ausführen.
    Dann sollte schnell klar werden was man damit machen kann und was es bringt.

    Es ist aber noch keine ausgewachsene UDF. Momentan ist nur die flann_find_nearest_neighbors-Funktion umgesetzt.
    Auch ein Error-Handling existiert noch nicht.
    Falls größeres Interesse besteht, kann ich die UDF vielleicht noch vervollständigen.
    Für dich wäre sicherlich noch die flann_radius_search-Funktion interessant.

    Was nuetzt es mir Bibliotheken zu nutzen wenn ich das Prinzip dahinter noch nicht verstanden habe? Ich hab ja nicht vor das unbedingt selber zu implantieren, jedoch sollte ich doch zumindest theoretisch verstehen was da vor sich geht. Aber danke, ich schau es mir spaeter mal an.

    Gute Einstellung.

    Lies dich am besten zuerst in die >>Quadtrees<< ein, dann die Octrees (nichts weiter als eine Dimension mehr) und dann die k-d-Bäume.
    So wird das Prinzip am ehesten klar, da die Prinzipiel aufeinander aufbauen.

    Btw.:

    Zitat von ShitDown

    Das wären immerhin 999! -1 Schleifendurchläufe.

    Dann machst du mehrfache Vergleiche.
    Du brauchst in der inneren Schleife nicht wieder bei 0 anzufangen, sondern beim letzten äußeren Index, da du diese Paare ja schon bearbeitet hast.
    Um alle Werte mit allen jeweils einmal zu vergleichen sind demnach 999 über 2 Vergleiche notwendig - also 498501.

    Einmal editiert, zuletzt von AspirinJunkie (16. März 2015 um 12:26)

    Spoiler anzeigen
    Zitat

    Dann machst du mehrfache Vergleiche.

    Eben nicht, du verrechnest dich da irgendwo. Wenn ich jedes Objekt miteinander vergleiche sind (n-1)! -1 Schleifendurchgänge nötig. Ich erläutere dir das mal anhand eines Beispieles.


    Wir haben 5 Objekte, jedes Objekt soll mit jedem verglichen werden. Dabei sind folgende Variationen möglich:

    Code
    5-45-35-25-14-34-24-13-23-12-1


    Es ist ein eindeutiges Muster zu erkennen was uns an Fakultät erinnert. Der Rest dürfte erkennbar sein. Habe keine Lust das weiter auszuschmücken. Man könnte das selbe Prinzip nun für 1000 Objekte durchführen und erkennen, dass die Rechnung 999! -1 zutrifft. Das Minimalbeispiel sollte aber zur Veranschaulichung ausreichen.


    Wie du auf dein Ergebnis kommst ist mir dabei ein Rätsel.


    €dit: Ach komm,... ich habe da doch ein Rechenfehler drin. Danke für den Hinweis, ich berechne das mal neu (der Interesse wegen). ^^
    Viel mir aber erst auf als ich das nochmal durchgelesen habe.

    Einmal editiert, zuletzt von Yjuq (16. März 2015 um 13:45)

    Danke, ja das ist schlimm... Da verwechselt man schnell was. ^^
    Solch eine Übersicht habe ich auch in meinen Mathe Duden.

    Dadurch reduziert sich natürlich die Schleifendurchläufe extrem, da ich bei meinen Berechnungen mit falschen Werten gerechnet habe, kommt alles von der Zeitabschätzung kreuz und quer durcheinander. Das Thema war mir sowieso immer ein Dorn im Auge obwohl ich ja eigentlich sehr gut in Mathematik bin. :S

    Kann man sich ja nochmal anschauen, ich bedanke mich für das ganze Material was ich jetzt bekommen habe.

    Eine ganz einfache Methode (wenn auch weniger Effizient, da Rechenaufwändiger als die Baum-Methode) für 2D wäre eine einfache Bitmap.
    1. Man weist jedem Objekt eine ausreichend große Primzahl zu (sodass später eine Primfaktorzerlegung nur kombinationen aus 2 Primzahlen zulässt)*
    2. Man Füllt die komplette Bitmap mit dem Wert 1 (Multiplikationsneutral)
    3. Man "zeichnet" die Objekte mit der Primzahl als Farbe auf die Bitmap. Dabei Multipliziert man für die einzelnen Pixel die Farbe mit dem Hintergrund.
    4. Man führt bei Werten die Größer sind als die kleinste Primzahl^2 eine Primfaktorzerlegung durch. Die beiden sich ergebenden Primzahlen sind die Nummern der kollidierten Objekte.

    Klingt auf den Ersten Blick extrem umständlich. Die Zeichenmethode lässt sich via ASM ziemlich flott gestalten (am besten alle Objekte in einem Rutsch), die Primzahlen sowie die möglichen Zerlegungen kann man beim Skriptstart puffern und somit ohne Rechenaufwand abrufen. Wenn man alles richtig macht hat man eine Lineare Laufzeit (in Bezug auf die Anzahl Objekte), eine pixelgenaue Kollision und einen Rechenaufwand beim Start von O(n^2).
    Sollte man aber lieber nur zum Üben machen, die komplett mathematische Methode ist wesentlich besser ;)

    *Der Punkt hier ist ggf falsch. Habe das selbst immer so gehandhabt, kann aber auch gut sein dass man bei 2 anfangen darf bei den Primzahlen. Kollisionen mit mehr als 2 Objekten müssten auch gehen.