2D Kollisionsabfragen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: 2D Kollisionsabfragen

Beitrag von Xin » Do Jan 10, 2013 11:27 am

Laut Moderationsprotokoll hat Glocke gestern um das Thema gesperrt...

Code: Alles auswählen

Glocke	95.91.48.96	Gestern 19:48	Thema gesperrt
Daraus ergeben sich zwei Fragen:
a) Warum eigentlich?
b) Wo hat Glocke die Berechtigung her, ein Thema zu sperren? ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Glocke
Beiträge: 332
Registriert: Fr Okt 26, 2012 8:39 am

Re: 2D Kollisionsabfragen

Beitrag von Glocke » Do Jan 10, 2013 8:07 pm

Xin hat geschrieben:a) Warum eigentlich?
Ich wollte das Thema als gelöst markieren - das stand nicht da, dafür aber sperren. Ich dachte das is das gleiche in diesem Forum :D
Xin hat geschrieben:b) Wo hat Glocke die Berechtigung her, ein Thema zu sperren? ^^
Das kann ich dir nicht sagen :shock:

Glocke
Beiträge: 332
Registriert: Fr Okt 26, 2012 8:39 am

Re: 2D Kollisionsabfragen

Beitrag von Glocke » Mi Jan 16, 2013 10:53 am

Hey, ich greif die Sache mit der Polygon-Kollision mal wieder auf.
In Python habe ich jetzt erstmal ein Demo-Skript geschrieben um aus gegebenen Punkten die Punktrichtungsgleichung der Geraden aufstellt und sich die Länge merkt, weil ich ja keine Gerade sondern eine Strecke brauche.

Code: Alles auswählen

#!/usr/bin/python

import math

# Punkt mit x und y Koordinate
class Point:

    def __init__(self, x, y):
        self.x = x
        self.y = y


# Strecke mit Stützvektor (start), Richtungsvektor (dir) und Streckenlänge (length)
class LineSegment:

    def __init__(self, start, stop):
        self.start  = start
        self.dir    = Point(stop.x - start.x, stop.y - start.y)
        self.length = math.sqrt((start.x - stop.x)**2 + (start.y - stop.y)**2)
        print "(x, y) = (%i, %i) - t * (%i, %i) with len %i" % (self.start.x, self.start.y, self.dir.x, self.dir.y, self.length)

    def cut(self, line):
        # Schnittbedingung:
        # a.start + r * a.dir = b.start + t * b.dir
        # mit 0 < r <= a.length und 0 < t <= b.length
        # .... -.-' 
        return False

a = LineSegment(Point(5,0), Point(5, 10))
b = LineSegment(Point(0, 5), Point(10, 5))

print a.cut(b)

Jetzt fehlt mir nur noch der Ansatz, wie ich das Gleichungssystem löse.

/EDIT: Ich hab doch ne Idee.. wie blöd bin ich denn :oops:

LG Glocke

Glocke
Beiträge: 332
Registriert: Fr Okt 26, 2012 8:39 am

Re: 2D Kollisionsabfragen

Beitrag von Glocke » So Jan 27, 2013 11:19 am

Ich bin letztens über die Boost-Polygone gestolpert... 8-)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: 2D Kollisionsabfragen

Beitrag von Xin » Mo Jan 28, 2013 11:43 am

Glocke hat geschrieben:Ich bin letztens über die Boost-Polygone gestolpert... 8-)
Ich habe mir auf der MeetingC++ den Vortrag über boost::Geometry angesehen.

Boost::Geometry ist weiter als ich privat. Aber erstens entwickelt der seit 15 Jahren und nur spaßeshalber seit einem Jahr (bisher zweimal drangesessen...), aber es ist jetzt schon abzusehen, wo boost gegen die Wand fahren wird, denn beruflich (ich arbeite als Entwickler an einem CAD) sind wir deutlich weiter als Boost und vor allem wissen wir, warum wir anders arbeiten als Boost.

Wenn Du also nur Polygone brauchst - kein Problem. Wenn Du mit den Dingern rechnen willst... mach Dir Gedanken zum Thema Numerik.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Glocke
Beiträge: 332
Registriert: Fr Okt 26, 2012 8:39 am

Re: 2D Kollisionsabfragen

Beitrag von Glocke » Fr Feb 01, 2013 10:16 pm

So, ich habe mich bzgl. Kollisionserkennung mal etwas schlau gemacht. Auf einen Quadtree würde ich verzichten, weil imho durch viele sich bewegende Objekte quasi ständig der Tree neu generiert werden müsste.
Alternativ würde mir eine uniforme Raumaufteilung mittels Gitterung einfallen. D.h. die Map wird in gleichgroße Rechtecke unterteilt (bzw. ist das ja schon durch die Tile-Größen mit gegeben) und jeder Bereich bekommt eine Liste von Objekten, deren Hüllfläche (z.B. ein Rechteck das das Polygon des entsprechenden Objektes einschließt) den Gitterbereich schneiden/berühren.
Bewegt sich ein Objekt muss effektiv nur noch geprüft werden, welche Gitterbereich es auf der neuen Position schneidet/berührt, und dann entsprechend die Eintragung in die neuen Bereiche bzw. Austragung aus den alten Bereichen durchgeführt werden.

Quasi könnte man die Kollisionserkennung in drei Phasen durchführen:
  • Phase 1: Suche der kollisionsverdächtigen Objekte durch die Gitteraufteilung. Alle Funde werden in Phase 2 genauer untersucht.
  • Phase 2: Die Hüllflächen werden mit dem der des zu bewegenden Objektes auf Kollision überprüft (zwei Rects zu prüfen ist imho kein großer Aufwand). Alle weiterhin verdächtigen Objekte werden in Phase 3 schließlich exakt untersucht.
  • Phase 3: Basierend auf den Polygonen der verbliebenen Verdächtigen wird schließlich exakt überprüft, ob eine Kollision schließlich vorliegt
Was sagt ihr dazu?

LG Glocke :)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: 2D Kollisionsabfragen

Beitrag von Xin » So Feb 03, 2013 10:53 am

Glocke hat geschrieben:Was sagt ihr dazu?
Phase3 wird spaßig - je nach Objekt. Du müsstest die 3D Körper schneiden und gucken, ob Du eine Schnittmenge erhältst.

Deswegen machen das Spiele in der Regel auch nicht, Wenn zwei Figuren aufeinander zulaufen, stehen sie direkt voreinander, laufen sie im 45Grad Winkel zum globalen Koordinatensystem aufeinander zu, passt da eigentlich noch einer zwischen, die kommen aber nicht weiter.

Der BoundingBox-Check ist SEHR schnell. Körper zur Echtzeit zu verschneiden... davon schaffst Du ein paar wenige kleine Körper und dafür brauchst Du schon eine brauchbare CPU. Und das ganze muss ja auch noch programmiert werden...
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Glocke
Beiträge: 332
Registriert: Fr Okt 26, 2012 8:39 am

Re: 2D Kollisionsabfragen

Beitrag von Glocke » So Feb 03, 2013 11:35 am

Naja für die 3. Phase (vom Kontext her beziehe ich mich erstmal auf 2D) würde ich konvexe Boost-Polygone verwenden.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: 2D Kollisionsabfragen

Beitrag von Xin » So Feb 03, 2013 11:36 am

Glocke hat geschrieben:Naja für die 3. Phase (vom Kontext her beziehe ich mich erstmal auf 2D) würde ich konvexe Boost-Polygone verwenden.
Das ist der einfachste Weg. Das sollte zu schaffen sein.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Glocke
Beiträge: 332
Registriert: Fr Okt 26, 2012 8:39 am

Re: 2D Kollisionsabfragen

Beitrag von Glocke » Mo Feb 04, 2013 9:44 am

Für den Anfang werde ich bei Phase 2 beginnen. Wenn mir das dann auf größeren Maps zu langsam geht, implementiere ich noch Phase 1 davor 8-)

Antworten