[2d/games] efficient collision detection.

[Alarmnummer]

Ik heb in een wereld kogels en vliegtuigen, en mijn vraag is of ik het detecteren van een collision sneller kan laten verlopen. Op dit moment gaan alle kogels alle vliegtuigen bij langs om te kijken of de kogel met het vliegtuig botst. Kogels zijn in dat opzicht dus extreem dure objecten. Mijn vraag is of er niet een efficientere manier is.

[André]

Je kunt eerst kijken of de afstand tussen de objecten niet dusdanig groot is dat er sowieso geen collision kan plaatsvinden, die kun je alvast overslaan. Je kunt in sommige situaties berekenen hoe lang het minimaal duurt voordat er uberhaupt een collision kan plaatsvinden, die tijd hoef je ook niet te collision checken.

[Macros]

Je moet je scherm opdelen in vakken. Objecten moeten alleen collision detecteren met alle andere objecten in hun eigen vak en de vakken daaromheen. Dit verlaagt de orde van de operatie van N*N naar NlogN in theorie.

[.oisyn]

Spatial partitioning is het antwoord

De truc is natuurlijk alleen de vliegtuigen te controleren die dicht bij een kogel liggen. Je zou je wereld bijvoorbeeld kunnen opdelen in een 2d grid. Een object bevindt zich dan in 1 tot 4 cells in de grid (1 als ie volledig binnen een cell ligt, 4 als ie precies op het punt ligt dat aan 4 cells grenst). Vervolgens controleer je per kogel alleen de objecten die ook in de cellen liggen waarin de kogel zelf ligt.

Een andere methode is een simpele overlap-test in een enkele dimensie. Als je al je objecten projecteert op de x-as, krijg je dus een set intervallen, die je kunt sorteren. Je hoeft dan alleen de objecten te checken waarvan de intervallen met elkaar overlappen. Je zou dit nog kunnen uitbreiden door al die overlappen op de x-as te groeperen, en voor elke groep ook nog eens de overlappen op de y-as te bekijken.

Daarnaast heb je nog een concept dat spatial en temporal coherence genoemd wordt. Het is gebaseerd op de afhankelijkheden tussen objecten op verschillende momenten in ruimte-tijd. Als 2 objecten op een bepaald tijdsstip vlak bij elkaar liggen, dan zullen die 2 objecten op het volgende tijdsstip waarschijnlijk ook nog wel vlak bij elkaar liggen.

[Macros]

André schreef op 22 oktober 2004 @ 12:53:
Je kunt eerst kijken of de afstand tussen de objecten niet dusdanig groot is dat er sowieso geen collision kan plaatsvinden, die kun je alvast overslaan. Je kunt in sommige situaties berekenen hoe lang het minimaal duurt voordat er uberhaupt een collision kan plaatsvinden, die tijd hoef je ook niet te collision checken.

Dat werkt niet, omdat de collsion detection in het simpele geval al gewoon een afstands bereking is.

[Alarmnummer]

Ik zal dit weekend eens gaan spelen met spatial partitioning. thanx.