spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi,

ich arbeite an einem kleinen isometrischen 2D-Spiel unter Verwendung von SDL und C++. Dabei trenne die grafische Ausgabe von den Daten und der zugehörigen Logik. In der Datendarstellung verfügen die Objekte über ein Polygon, das zur Kollisionserkennung genutzt werden soll. Der Algorithmus dafür steht, ist aber verständlicherweise langsam, so dass ich ein paar approximative Tests vorher durchführen will. Dazu wollte ich das Polygon mit einem Kreis oder achsenparallelen Quadrat umschließen, da für diese Arten der Objekte die Kollisionserkennung wesentlich schneller ist. Zur Zeit suche ich einen Weg, an kollisionsverdächtige Objekte möglichst schnell heranzukommen. Dabei bin ich über die Thematik Quadtree gestolpert.

In einer ersten Implementierung habe ich die Datenstruktur so umgesetzt, dass hinzugefügt Punkte im richtigen Quad landen und die Struktur entsprechend erweitert wird. Allerdings sehe ich noch ein Problem, im Bezug auf die Kollisionserkennung. Nehmen wir mal an, der Quadtree hat eine Größe von 40x40 und wurde in 4 Quads unterteilt:

• Links oben (#0) von <0,0> bis <20,20>
• Rechts oben (#1) von <20,0> bis <40,20>
• Links unten (#2) von <0,20> bis <20,40>
• Rechts unten (#3) von <20,20> bis <40,40>

Des Weiteren enthält er u.A. folgende Objekte:

• Kreis A mit Mittelpunkt <18,5> und Radius 5.
• Kreis B mit Mittelpunkt <26,5> und Radius 10.

Wegen ihrer Mittelpunkte, fügt der Quadtree Kreis A in den Quad #0 und Kreis B in den Quad #1. Zur Veranschaulichung habe ich hier mit GeoGebra mal eine kleine Grafik erstellt:

Prinzipiell kann ich im Quadtree nur nach Objekten suchen, die im gleichen Quad wie ein gegebenes Objekt liegen. Suche ich nach allen Nachbarn von Kreis A, erhalte ich lediglich Kreis A (oder gar nichts - je nach Implementierung) und ein analoges Ergebnis für Kreis B. Nun kollidieren aber beide, da ihr Abstand 8 ist und 8 < 10 (10 wegen max(5, 10) der Radien) gilt.

Kann ich das, was ich vom Quadtree will, mit einer entsprechenden Modifikation erreichen? Ich habe überlegt, beim Einfügen in alle Quads einen Zeiger auf den Kreis zu legen, die mit dem Kreis kollidieren. Demnach würden die Quads #0 und #1 jeweils einen Zeiger auf Kreis A und auf Kreis B bekommen, da beide Kreis (oder man approximiert: beide Quadrate um die Kreise) jeweils beide Quads schneiden. Allerdings sorgt das bei größeren Objekten automatisch zu mehr Aufwand, wenn diese sich bewegen (also remove + insert).
Btw könnte auch Kreis A prinzipiell so liegen, dass er komplett in Quad #0 liegt - dann würde Quad #0 wegen Kreis B trotzdem den Zeiger auf Kreis B haben und als "Nachbar" von Kreis A liefern. Sicherlich könnte man auch prinzipiell die Elemente des Quads und der 3 übrigen Quads zurückliefern. Allerdings habe ich dann auch wieder ein Problem, wenn sich ein Objekt über 9 Quads erstreckt usw.

Habt ihr eine Idee für mich? Oder steckt irgendwo ein Denkfehler

LG Glocke

Hi,

ich möchte jeder Tile jedem beweglichen Objekt eine polygonbasierte Kollisionsfläche geben. Gehen wir von einer Karte 50x50 Kacheln mit ~1.000 Objekten (nicht nur Spielfiguren sondern auch Geschosse usw.) aus, sind wir bei ~3.500 kollidierbaren Objekten.

LG Glocke

Zitat von »David Scherfgen«

Wenn du sowieso schon mit Kacheln arbeitest, wäre es dann nicht sinnvoller, ein regelmäßiges Gitter anstelle eines Quadtrees zu benutzen?
Tiles untereinander können sowieso schonmal nicht kollidieren, also nur Objekte mit Tiles und Objekte mit Objekten. Dann musst du eigentlich für jedes Objekt nur die benachbarten Tiles untersuchen und die darin enthaltenen Objekte.

Joa, das wäre sinnvoller! Zum Beispiel würde sich als regelmäßiges Gitter das Gitter anbiete, mit dem ich die Tiles kachele.
Also würde ich dann folgendermaßen vorgehen bei der Suche nach Kollisionen: Ich schnappe mir das Tile, auf dem die Figur steht. Im Umkreis von x Tiles schnappe ich mir alles was kollidieren kann und prüfe weiter? Dazu müsste ich dem Tile nur ein std::vector geben und dort bei der Bewegung die Objekte hinzufügen / entfernen... Life seems less complex than I thought

Dann müsste ich einzigst einen "maximalen Kollisionsradius" festlegen. Sonst würde ich zu so einem Problem kommen wie oben in der Grafik beschrieben (wenn ich die Objekte anhand ihres Mittelpunktes identifiziere): In meinem Kollisionsradius liegt kein Mittelpunkt eines anderes Objekt, mein Mittelpunkt liegt aber im Kollisionsradius eines anderen Objektes.

Lege ich den Kollisionsradius mit r fest, muss ich dann nur noch die x Tiles um mich herum abgrasen, die maximal 2*r von mir entfernt sind. Meinst du das so?

LG Glocke

Zitat

Ordne ein Objekt nicht nur in 1 Tile ein, sondern in alle, die sein Kollisionspolygon schneidet (oder meinetwegen auch nur basierend auf dem umschreibenden Kreis/Rechteck).

Naja da wollte ich eh, indem ich jeder Tile ein Array von Objekt-Zeigern gebe, vobei jedes Objekt entweder auf der Tile liegt oder sie schneidet (genauer: ihr Bounding-Rechteck).

Zitat

Mach dir dann noch eine Liste von Tiles, die mindestens zwei Objekte enthalten (die musst du natürlich auch aktuell halten).
Nun gehst du all diese Tiles durch und prüfst die jeweils enthaltenen Objekte "naiv" auf Kollision.
Außerdem könntest du dir merken, für welche Objektpaare du schon eine Kollision getestet hast, damit du für dasselbe Objektpaar nicht mehrere Kollisionen meldest.

Das ist natürlich noch schöner Nicht nur um die kollisionsverdächtigen Objekte zu bekommen, sondern auch, um das Objekt von den Tiles zu entfernen wenn ich es bewege.

Zitat von »David Scherfgen«

Also zusammengefasst stelle ich mir das etwa so vor:

C#-Quelltext

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

Set tilesContainingAtLeastOneObject = new Set(); List tilesContainingAtLeastTwoObjects = new List(); Set> objectPairsTested = new Set>(); // In jedem Frame: // Objekte den Tiles zuordnen und dabei auch bestimmen: // - Die Menge aller Tiles, die mindestens ein Objekt enthalten. // - Die Liste aller Tiles, die mindestens zwei Objekte enthalten. tilesContainingAtLeastOneObject.Clear(); tilesContainingAtLeastTwoObjects.Clear(); foreach (Object obj in objects) { // Erzeuge Liste von Tiles, die dieses Objekt überlappt. foreach (Tile t in obj.GetOverlappingTiles()) { // Dem Tile sagen, dass jetzt hier ein Objekt ist. t.Objects.Add(obj); // Merken, dass dieses Tile mindestens ein Objekt enthält. tilesContainingAtLeastOneObject.Add(t); // Wenn dies das zweite Objekt in diesem Tile ist, // dann kommt das Tile auch auf die "Mindestens 2 Objekte"-Liste. if (t.Objects.Count == 2) tilesContainingAtLeastTwoObjects.Add(t); } } // Nun testen wir auf Kollisionen der Objekte untereinander. // Dabei müssen wir nur die Tiles durchgehen, die mindestens zwei Objekte enthalten: objectPairsTested.Clear(); foreach (Tile t in tilesContainingAtLeastTwoObjects) { // Objekte in diesem Tile paarweise durchgehen. for (int o1 = 0; o1 < t.Objects.Count; ++o1) { for (int o2 = 0; o2 < o1; ++o2) { // Wurde dieses Pair schon getestet? Wenn ja, überspringen. Pair pair = new Pair(t.Objects[o1], t.Objects[o2]); if (objectPairsTested.Contains(pair)) continue; // Merken, dass dieses Paar getestet wurde/wird. objectPairsTested.Add(pair); if (CollisionTest(t.Objects[o1], t.Objects[o2])) { // Kollision! // Entweder sofort behandeln oder in einer Liste merken. } } } } // Objekte wieder aus den Tiles entfernen. foreach (Tile t in tilesContainingAtLeastOneObject) t.Objects.Clear();

Du machst dir zu viel Arbeit Aber danke dir

LG Glocke

Zitat von »David Scherfgen«

Anzumerken ist natürlich, dass das Ganze nur so lange gut geht, wie pro Tile nur überschaubar viele Objekte vorhanden sind.
Hast du z.B. 1000 Objekte in einem einzigen Tile, dann fliegt dir der O(n²)-Check um die Ohren

Absolut richtig, auch wenn 1.000 Objekte auf einer Tile unwahrscheinlich ist - selbst wenn wir mal von riesigen Iso-Tiles mit 512x256 oder so ausgehen

Ich arbeite den Wiki-Artikel mal durch