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!
Werbeanzeige
Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von »Glocke« (09.02.2013, 12:45)
Community-Fossil
Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer
Administrator
Joa, das wäre sinnvoller! Zum Beispiel würde sich als regelmäßiges Gitter das Gitter anbiete, mit dem ich die Tiles kachele.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.
Administrator
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<Tile> tilesContainingAtLeastOneObject = new Set<Tile>(); List<Tile> tilesContainingAtLeastTwoObjects = new List<Tile>(); Set<Pair<Object, Object>> objectPairsTested = new Set<Pair<Object, Object>>(); // 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<Object, Object> pair = new Pair<Object, Object>(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(); |
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
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).
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
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.
Du machst dir zu viel Arbeit Aber danke dirAlso 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();
Administrator
Absolut richtig, auch wenn 1.000 Objekte auf einer Tile unwahrscheinlich ist - selbst wenn wir mal von riesigen Iso-Tiles mit 512x256 oder so ausgehenAnzumerken 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
Werbeanzeige