Effizienter Algorithmus für Kollisionsermittlung gesucht
-
Hallo,
Im Rahmen meines Weltraum-Spiel-Projekts Fleet Commander (http://lars.ruoff.free.fr/fcom/) suche ich nach einem effizienten Verfahren um Kollisionen zu ermitteln.
Eckdaten sind folgende:
- 2D
- Die Objekte sind punkt- (Raumschiffe) oder kreisförmig (Wolken).
(die eingentliche Kollisionserkennung zwischen zwei Objekten ist also trivial)Bis jetzt vergleich ich jedes Objekt mit jedem, also O(n*n).
Strenggenommen ist es O(n*m), wobei n=Raumschiffe, m=Wolken.
(Raumschiffe und Wolken kollidieren nicht untereinander, jeweils nur miteinander)Wie bekomm ich die Komplexität runter?
Ich hab mir gedacht den Raum in überlappende Boxen zu partitionieren und dann halt nur innerhalb der Boxen jeden gegen jeden zu prüfen.
Es würde dann eine Map zum Einsatz kommen (O(log n)) die von der Koordinate des Objekts ausgehend die zugehörige(n) Bounding-Box(en) findet.
Klingt das vernünftig?Da gibt's sicher schon fertige Algorithmen? Wie heissen die?
(Im Netz find ich beim Stichwort Kollisionen nur haufenweise Zeug zu Kollisionsberechnung zwischen 3D Polygonen, aber darum geht's ja hier nicht).
-
Vielleicht wär das was: http://en.wikipedia.org/wiki/R-tree
-
Ich wuerde einen Quadtree nutzen.
-
fuer weltraumspiele nutzt man normalerweise einfach nur sortierte listen.
1. ist ein weltraum meistens extrem gross in relation zu den schauplaetzen, das macht grids und binary trees (z.b. oct-trees unpraktikabel).
2. die bewegung der objekte in relation zur levelgroesse ist relativ klein, bubblesort laeuft also in 99% der faelle nur einmal durch was also meist ein O(1) ist. das laeuft meist besser als dynamische hierarchische trees (besonders sparse trees wie bsp, (b)kd-tree etc. brauchen da oft eine rekonstruktion).
3. die wahrscheinlichkeit einer kollision ist meistens relativ gering, deswegen reicht eine sortierte liste, man hat nur selten ueberlappungen von benachbarten objekten, selbst wenn man einen 3d raum hat.google: sweep&prune
-
rapso schrieb:
bubblesort laeuft also in 99% der faelle nur einmal durch was also meist ein O(1) ist.
Du meinst O(n).
-
Janjan schrieb:
rapso schrieb:
bubblesort laeuft also in 99% der faelle nur einmal durch was also meist ein O(1) ist.
Du meinst O(n).
du hast recht, sorree
-
raps schrieb:
Janjan schrieb:
rapso schrieb:
bubblesort laeuft also in 99% der faelle nur einmal durch was also meist ein O(1) ist.
Du meinst O(n).
du hast recht, sorree
Ich vergebe dir.
-
Danke!
