Seite 2 von 5

Re: 2D Kollisionsabfragen

Verfasst: Do Jan 10, 2013 11:27 am
von Xin
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? ^^

Re: 2D Kollisionsabfragen

Verfasst: Do Jan 10, 2013 8:07 pm
von Glocke
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:

Re: 2D Kollisionsabfragen

Verfasst: Mi Jan 16, 2013 10:53 am
von Glocke
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

Re: 2D Kollisionsabfragen

Verfasst: So Jan 27, 2013 11:19 am
von Glocke
Ich bin letztens über die Boost-Polygone gestolpert... 8-)

Re: 2D Kollisionsabfragen

Verfasst: Mo Jan 28, 2013 11:43 am
von Xin
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.

Re: 2D Kollisionsabfragen

Verfasst: Fr Feb 01, 2013 10:16 pm
von Glocke
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 :)

Re: 2D Kollisionsabfragen

Verfasst: So Feb 03, 2013 10:53 am
von Xin
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...

Re: 2D Kollisionsabfragen

Verfasst: So Feb 03, 2013 11:35 am
von Glocke
Naja für die 3. Phase (vom Kontext her beziehe ich mich erstmal auf 2D) würde ich konvexe Boost-Polygone verwenden.

Re: 2D Kollisionsabfragen

Verfasst: So Feb 03, 2013 11:36 am
von Xin
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.

Re: 2D Kollisionsabfragen

Verfasst: Mo Feb 04, 2013 9:44 am
von Glocke
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-)