Ellipsen überfordern mich - bitte um Hilfe

[Rolf B]

Hallo Felix,

SPIEL

ah, heiliger Alan und John, wieso fallen wir immer wieder auf Fragen mit A-B Problemen herein.

Dein B-Problem, mit dem Du uns bespaßt hast, ist die Ellipsenüberlappung. Dein A-Problem, das Du mit deinen Ellipsen lösen wolltest, ist ein Kollisionstest von Sprites.

Lösen wir lieber A statt B. Du willst keine Ellipsen. Du willst eine Partitionierung deiner Sprites

Beispielsweise so:

Beachte die orangen Linien erstmal nicht - die sieht man eh nur wenn man reinzoomt, glaube ich 😀

Zerlege jedes Objekt, für das Du Kollisionstests machen willst, in eine Liste von Rechtecken. Bei dem Space-Invader hier könnten das 6 Stück sein: 2 Ohren, zwei Fußspitzen, das Gesicht und der „Hut“. Die beiden Ohren könntest Du auch zu einem Rechteck zusammenfassen; niemand verlangt, dass Partialrechtecke überlappungsfrei sind. Hinzu kommt das rote Hüllenrechteck.

Echte Ellipsen kannst Du so auch annähern, brauchst dann nur ein paar Rechtecke mehr...

Auf den ersten Blick hast Du nun dein Problem „Teste die Überlappung von 17 Sprites“ zum Problem „Teste die Überlappung von hunderten von Partitionen“ aufgeblasen. Überlappungstests haben bei naiver Programmierung quadratische Komplexität (bzw. linear, wenn Du genau ein Objekt gegen alle anderen testen willst), aber wir haben ja auch noch die Hüllrechtecke. D.h. deine Kollisionsprüfung machst Du zweistufig. Im ersten Schritt testest Du ob die Hüllrechtecke sich überlagern. Und nur, wenn das zutrifft, vergleichst Du die Partitionen. Auch da wieder zweistufig: Wenn sich SpriteA und SpriteB mit den Hüllrechtecken überlappen, fragst Du für jede Partition von A erstmal, ob sie im Hüllrechteck von B liegt, und nur wenn das zutrifft, prüfst Du gegen alle Partialrechtecke.

Das kann man bei komplexen Sprites mit vielen Partitionen auch mehrstufig gestalten, siehe die orangen Linien. Da wäre das Sprite in 3 Regionen mit je 2 Rechtecken aufgeteilt.

Wenn Du viele Sprites hast, die durcheinander wuseln und wo Du pro Sprite testen musst, ob es mit irgendeinem anderen kollidiert, kann es sinnvoll sein, vor einem generellen Kollisionstest erstmal eine nach der „Left“ Koordinate sortierte Liste der Sprites zu erstellen. Das erlaubt eine binäre Suche in der Sprite-Liste und kann bei vielen Sprites den Aufwand von O(n²) auf O(n log(n)) reduzieren (sofern Du einen Sort-Algorithmus mit O(n log(n)) verwendest und nicht Bubble-Sort). Hier muss man aber auch testen. Laufzeitkomplexität (also O(n²) vs O(n log(n)) und echte Laufzeit sind zwei paar Schuhe. Ein Algorithmus mit höherer Komplexität wird ab einem bestimmten N definitiv langsamer sein, dieses N kann aber im Bereich von 10000 oder mehr liegen.

Rolf