spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hmm mich überzeugt der Ansatz mit "Tile weiß, welche Objekte sie berühren und Objekt weiß, welche Tiles er berührt" noch
Vielleicht könnte man - wenn sehr viele Objekte pro Tile vorhanden sind - die Anordnung der Objekte im Tile mittels Quadtree organisieren...

Wenn ich den neuen Standpunkt der Figur kenne, kann ich ein ein Rechteck drum legen und dann die Tiles, die darin liegen einzeln abfahren. Dabei wäre es dann sinnvoll nicht in 1er Schritten sondern TILE_WIDTH- / TILE_HEIGHT-er Schritten vorzugehen. Dann ist der Aufwand die neuen Kacheln - mit denen die Figur am neuen Standpunkt kollidieren könnte - nicht mehr ganz so groß.

Am Besten arbeite ich erstmal mit dem Gitter weiter. Wenn mir das nicht reicht, muss ich später den Quadtree implementieren. Da ich Daten und Darstellung eh trenne, wirft die nachträgliche Quadtree-Implementierung schonmal die Ausgabelogik nicht durcheinander

LG Glocke

Heyho,

ich habe jetzt mal ein paar Tage nicht über die Kollisionserkennung nachgedacht und mir die Vorschläge eben nochmal angesehen. Manchmal hilft es etwas Distanz zu bekommen

Ich werde die Kollision erstmal nur kreisbasiert implementieren, d.h. ohne Polygone. Die Kreise kann ich später als Approximation der Polygone betrachten und für die grobe Kollisionserkennung verwenden. Über die Sache mit den Objekt- bzw. Kachel-Listen in den Kacheln bzw. Objekten habe ich noch einmal nachgedacht; mit folgendem Ergebnis:

• Ich werde jeder Kachel eine Liste von Objekten geben, deren Kollisionsradius diese Kachel berührt oder umfasst.
• Die Kacheln ordne ich im Grid entsprechend ihrer Kachel-Position an (quasi std::map, also assoziatives Array mit entsprechendem Key).
• Dem Objekt an sich werde ich nur seine "Welt-Position" und den entsprechenden Kollisionsradius geben.
• Die Kollisionserkennung werde ich in zwei Phasen durchführen:

Phase 1: Kachel-Kollision

• Im Umkreis von MAX_RADIUS um das Objekt iteriere ich (quadratisch) durch alle Kacheln. Dazu frage ich die entsprechende Position im Grid ab und erhalte die Kachel.
• Liegt die Kachel außerhalb des Kreises (ceil(distance(worldPosOfTile, worldPosOfObject)) > radiusOfobject), überprüfe ich diese Kachel nicht weiter.
• Liegt sie innerhalb, prüfe ich ob sie begehbar ("befliegbar" usw.) ist, so dass ich eine Aussage darüber treffen kann, ob das Objekt auf diese Kachel dürfte, wenn kein anderes Objekt sie blockiert

Am Ende weiß ich, ob die Kacheln begehbar (etc.) sind. Ist eine Kachel z.B. eine Wand, bricht die Kollisionserkennung ab. Sonst geht es weiter:
Phase 2: Objekt-Kollision

• Im Umkreis von 2*MAX_RADIUS um das Objekt iteriere ich (quadratisch) durch alle Kacheln. Dazu frage ich erneut die entsprechende Position im Grid ab und erhalte die entsprechende Kachel.
• Liegt die Kachel außerhalb dieses doppeltem Umkreises (analoge Formel, nur mit 2*MAX_RADIUS), prüfe ich diese Kachel weiter.
• Dann gehe ich durch alle Objekte, die in der Kachel (in der entsprechenden Liste) hinterlegt sind.
• Wenn das andere Objekt sich von meinem Unterscheidet (effektiv Pointer-basiert - da weiß ich ja ob es != oder == ist - schaue ich, ob sich die Kollisionsradien schneiden (das lässt sich ja einfach berechnen).
• Wenn ja, bricht die Kollision ab und könnte z.B. anderesObject liefern oder einfach nur einen bool'schen Wert. Ansonsten könnte hier später auch die exakte Kollisionserkennung auf Polygonbasis durchgeführt werden. Falls keine Kollision erkannt wurde, geht es mit dem nächsten Objekt bzw. der nächsten Kachel weitergehen.

/EDIT: Hier kann ich sogar noch weiter optimieren und statt 2*MAX_RADIUS auch object.Radius + MAX_RADIUS nehmen
Und am Ende der 2. Phase weiß ich dann exakt ob (oder sogar mit wem, wenn ich das zurückgebe) mein Objekt kollidieren würde.

Die Liste von Kacheln - die das Objekt berührt - lasse ich wie gesagt weg. Ich würde sie nur in Phase 1 brauchen, allerdings macht es wahrscheinlich kaum einen Unterschied: ob ich durch die Tiles (in der Liste meines Objektes) iteriere oder (mit etwas "Ausschuss", durch die quadratische "Abtastung") direkt im Grid in einem ausgewählten Bereich durch die Tiles gehe.... imho macht es sogar einen Performance-Vorteil aus, wenn ich (beim Verschieben des Objektes) nur die Objekt-Liste der Tile ändern muss und nicht noch zusätzlich die Tile-Liste des Objektes.

LG Glocke

PS: "Deine Nachricht enthält folgende zensierte Wörter: umschlie ßt" (ohne Leerzeichen, sonst blockt er wieder). Dann sag ich halt "umfasst" Aber warum ist das Wort umschlie*t denn so evil