Kollisionserkennung mit Zeitdifferenzmessung
-
danke, schonmal guter verbesserungsvorschlag!
Weiß vll noch wer ne alternative zu dem instanceof zeugs, oder einfach paar allgemeine tipps?
-
rapso schrieb:
versuch sowas wie
for(a0=start to end-1) for(a1=a0+1 to end) if(collides(a0,a1)) ...mit steigender anzahl der objekte steigt es mit Anzahl*log(Anzahl) statt Anzahl*Anzahl, bei 100 objekten also 10x schneller.
Nö. Nur 2-mal so schnell wie zuvor. Mit steigender Anzahl noch genauer 2-mal.
-
Die formel müsste doch (n*(n-1))/2 sein, oder?
Aber ist ja auch nicht so wichtig^^
Mir gehts eher um konzeptionelle sachen und das war schon nen guter tipp...
-
Dazu unterteilst du die Welt in kleinere Einheiten und checkst nur noch Objekte die sich in der selben "Gegend" befinden
-
Jo, das ist sicherlich ne gute idee, die welt in so kacheln einzuteilen und dann immer nur per kachel nach kollisionen zu prüfen und auch den hintergrund kann man ja so gut einteilen.
Ich stelle mir das dann so vor, dass ich zu jeder kachel eine liste von elementen habe, die sich in der kachel befinden und dann innerhalb der kachel auf kollisionen prüfe.
Ich sehe da allerdings noch ein problem, was mache ich, wenn ein element genau auf der grenze zwischen zwei (oder sogar mehr) kacheln ist, also z.B. zur hälfte links und zur hälfte rechts drin... ?
Muss das element dann in beiden listen drin sein, oder wie würde man das umsetzen?Gut wäre auch noch, wenn ihr noch was zu der sache mit instanceof (siehe seite 1) sagen könnt
Vielen Dank schonmal für weitere Antworten!
-
Jo, du musst das Objekt abhängig von seiner Größe ggf. bei mehreren Bereichen "anmelden" und wenn es sich bewegt evtl wieder "abmelden". Je grösser die Bereiche sind desto weniger An/Abmelde-Aufwand hast du, aber desto zeitintesiver wird die Prüfung (da die Anzahl der Objekte im selben Bereich steigt). Am besten alles schön dynamisch aufbauen, so das du die Bereichsgrösse variieren kannst um das perfekte Verhältnis zu finden. Wenn man einen Quadtree/Octree oder sowas verwendet, bieten sich diese Strukturen natürlich als Speicherort an.
-
Gast1337 schrieb:
Ich sehe da allerdings noch ein problem, was mache ich, wenn ein element genau auf der grenze zwischen zwei (oder sogar mehr) kacheln ist, also z.B. zur hälfte links und zur hälfte rechts drin... ?
Muss das element dann in beiden listen drin sein, oder wie würde man das umsetzen?Das wird unterschiedlich gemacht.
Entweder so wie du schreibst, also jedes Objekt in jede Kachel eintragen mit der es sich überschneidet.Die zweite Variante ist, das Objekt nur in die Kachel einzutragen die unter dem Mittelpunkt des Objekts liegt. Beim Prüfen auf Kollisionen nimmt man dann alle Objekte die einer Kachel liegen, und prüft sie dann gegen sich selbst sowie die Objekte die in den umliegenden 8 Kacheln liegen. Die Grösse der Objekte darf dabei allerdings 2x2 Kacheln nicht übersteigen.
-
Das mit den Kacheln (Grid) hört sich gut an, nur leider legt es eine obere Grenze für die Größe von Objekten fest, kann man das irgendwie in guter Weise modifizieren, so das das nicht der Fall ist?
Was mir einfällt ist man testtet, ob es in 9 kacheln reinpasst (die wos reinkommt und die umliegenden) und wenn nicht, dann kommt es in eine seperate liste, in der alles gespeichert wird, was nicht in die kacheln reinpasst.Ansonsten hab ich nochmal nen bischen was übern quadtree gelesen, klingt interessant und vermutlich auch effizient, aber ich vermute, dass es sehr aufwändig wird und bei wiki stand was von das die fläche auf die das angewendet wird rechteckig sein sollte/muss (warum auch immer)?
Falls wer nen gutes Tutorial in die Richtung kennt - für einen Link wäre ich dankbar.
-
Gast1337 schrieb:
Das mit den Kacheln (Grid) hört sich gut an, nur leider legt es eine obere Grenze für die Größe von Objekten fest, kann man das irgendwie in guter Weise modifizieren, so das das nicht der Fall ist?
Mach dir eine quadratische Bounding Box für jedes Objekt. Das Ding muss sich darin noch drehen können, falls du das willst - Falls nicht, brauch die Box nicht unbedingt quadratisch sein. Dann nimmst du dir den Punkt oben Links und den Punkt unten Rechts und berechnest, welche Tiles dazwischenliegen. Dort machst du das Objekt dann bekannt, oder eben auch nicht.
Ansonsten hab ich nochmal nen bischen was übern quadtree gelesen, klingt interessant und vermutlich auch effizient, aber ich vermute, dass es sehr aufwändig wird und bei wiki stand was von das die fläche auf die das angewendet wird rechteckig sein sollte/muss (warum auch immer)?
Für was willst du den Quadtree denn verwenden? Grundsätzlich ist es egal, welche Abmessungen das Ding hat. Man nimmt aber gerne z.B. eine 2er Potenz, weil dann jeder Teilbereich eine glatte Zahl ist (64,32,16,8 usw) und sich vielleicht irgenwelche Rechentricks anwenden lassen.
-
Gast1337 schrieb:
Das mit den Kacheln (Grid) hört sich gut an, nur leider legt es eine obere Grenze für die Größe von Objekten fest, kann man das irgendwie in guter Weise modifizieren, so das das nicht der Fall ist?
Nein, tut es nicht. Wenn du die Objekte in alle Kacheln einträgst mit denen sie sich überschneiden dann gibt es keine Obergrenze für die Grösse.
Was mir einfällt ist man testtet, ob es in 9 kacheln reinpasst (die wos reinkommt und die umliegenden) und wenn nicht, dann kommt es in eine seperate liste, in der alles gespeichert wird, was nicht in die kacheln reinpasst.
Ja, auch eine Möglichkeit - vermutlich sogar eine gute.
