Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Bounding Box Collision bei vielen Objekten

Werbeanzeige

Dareptor

Frischling

  • »Dareptor« ist der Autor dieses Themas

Beiträge: 31

  • Private Nachricht senden

1

22.06.2015, 15:59

Bounding Box Collision bei vielen Objekten

Hallo Community,

ich habe folgenden Code um mit Hilfe von Bounding Boxes Kollision zu prüfen:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

bool checkBoundingBoxCollision(SDL_Rect* boundingBox_1, SDL_Rect* boundingBox_2)
{
    if (boundingBox_1->y + boundingBox_1->h <= boundingBox_2->y)
        return false;

    if (boundingBox_1->y >= boundingBox_2->y + boundingBox_2->h)
        return false;

    if (boundingBox_1->x + boundingBox_1->w <= boundingBox_2->x)
        return false;

    if (boundingBox_1->x >= boundingBox_2->x + boundingBox_2->w)
        return false;

    return true;
}


Und soweit funktioniert dieser auch richtig. Doch eine Frage hätte ich... bei einem Level mit vielen Objekten (also auch vielen Bounding Boxes), wie genau modifiziere ich die Funktion am besten, sodass sie überall prüft ? Ich könnte mir eine Art Liste vorstellen, wo ich alle Boundingboxes lagere und diese gebe ich dann immer für das Prüfen weiter, aber das scheint doch recht ineffizient zu sein für jedes sich bewegende Objekt einen Kollisionstest mit allem durchzuführen. Gibt es eine Alternative, welche weniger Leistung in anspruch nimmt ?

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

2

22.06.2015, 16:26

Geht es dir jetzt darum wie du die Bounding Boxen speicherst oder darum dass du nicht jedes Objekt mit jedem auf Kollision prüfen möchtest? Für letzteres kannst du deine Welt in eine geeignete Datenstruktur unterteilen. Am einfachsten wäre da eine simple Partitionierung. Stell dir vor deine Spielwelt befindet sich auf einem Schachbrett. Die Anzahl der Zellen spielt da erst mal keine Rolle. Jedes Objekt in der Welt wird nun einer Kachel auf dem Schachbrett zugeordnet. Anstatt jetzt jedes Objekt mit jedem zu prüfen reicht es aus die Objekte einer einzelnen Zelle auf dem Brett untereinander zu prüfen. Dabei müsste dann allerdings sichergestellt sein dass sich ein Objekt immer nur wirklich in genau einer Zelle befinden kann. Bei den meisten Spielen wird es aber so sein, dass deine Objekte über den Rand einer Zelle hinaus stehen können. In diesem Fall prüfst du nicht die Objekte einer einzelnen Zelle untereinander, sondern prüfst die Objekte einer benachbarten Zelle mit.
Eine andere Möglichkeit wäre ein Quadtree. Das hier zu erklären würde etwas länger dauern aber du kannst danach ja mal googeln und hier gegebenenfalls noch mal Fragen wenn du etwas nicht verstehst. So einen Quadtree kann man um eine dritte Dimension erweitern (eben für 3D Spiele) was sich dann Octree nennt.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Dareptor

Frischling

  • »Dareptor« ist der Autor dieses Themas

Beiträge: 31

  • Private Nachricht senden

3

22.06.2015, 20:57

Zitat

Geht es dir jetzt darum wie du die Bounding Boxen speicherst oder darum
dass du nicht jedes Objekt mit jedem auf Kollision prüfen möchtest?
Ich wollte beide Themen einmal ansprechen, weil ich in Sachen Kollisionserkennung absoluter Neuling bin und somit vorallem mit eben diesen beiden Hauptfragen bei Boundingboxes konfrontiert werde.

Zitat

Für letzteres kannst du deine Welt in eine geeignete Datenstruktur
unterteilen. Am einfachsten wäre da eine simple Partitionierung. Stell
dir vor deine Spielwelt befindet sich auf einem Schachbrett. Die Anzahl
der Zellen spielt da erst mal keine Rolle. Jedes Objekt in der Welt wird
nun einer Kachel auf dem Schachbrett zugeordnet. Anstatt jetzt jedes
Objekt mit jedem zu prüfen reicht es aus die Objekte einer einzelnen
Zelle auf dem Brett untereinander zu prüfen. Dabei müsste dann
allerdings sichergestellt sein dass sich ein Objekt immer nur wirklich
in genau einer Zelle befinden kann. Bei den meisten Spielen wird es aber
so sein, dass deine Objekte über den Rand einer Zelle hinaus stehen
können. In diesem Fall prüfst du nicht die Objekte einer einzelnen Zelle
untereinander, sondern prüfst die Objekte einer benachbarten Zelle mit.
Das klingt sehr vielversprechend und definitiv performanceschonender als alle dutzend Objekte durchgehend mit Objekten komplett ausser Reichweite zu vergleichen.

Zitat

Eine andere Möglichkeit wäre ein Quadtree
Ich werde mich mal in das Thema einlesen - vielen dank für die Ratschläge :thumbsup: .

Werbeanzeige

Ähnliche Themen