Kollisionsabfrage - Bounding Box

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Sonntag 16. November 2008, 16:44

Hallo,
ich wollte mal fragen wie man eine Kollisionsabfrage mit einer Boundingbox
macht, d.h. wie berechnet man den Umriss der Bounding Box?

Beispiel:
Ich habe ein Object: width = 10, height = 10
Wie komme ich jetzt nur an die Koordinaten, die den Umriss verdeutlichen?
Also in dem Fall (0|0),(0|1),(0,2) für den "Deckel"
(0|0),(1|0),(2|0) für die linke Seitenwand und so weiter...
Ich habe keine Ahnung...
Hoffe auf Hilfe.

MfG Jonas
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Sonntag 16. November 2008, 17:00

Für den Fall, dass es um Tkinter geht, hier ein Auszug aus der Doku:
bbox(item=None)

Returns the bounding box for all matching items. Note that the bounding box is approximate and may differ a few pixels from the real value.
Returns: The bounding box, as a 4-tuple.
Dieses 4-Tupel ist so aufgebaut (x0,y0,x1,y1), wobei die ersten beiden Koordinaten den linken oberen Eckpunkt und die letzten beiden den unteren rechten Eckpunkt des umgebenden Rechtecks angeben.
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Sonntag 16. November 2008, 17:07

Hi Numerix!
Vielen Dank für die schnelle Antwort!
Eigentlich geht es hier nicht um Tkinter sondern eher
allgemein um eine Bounding Box K. Abfrage.
Aber ich bin mir immer nocht im Klaren darüber ob
es reicht wenn man die Eckpunkte nimmt und z.B. prüft
ob diese den Koordinaten eines anderen Objekts gleich sind
ob zu testen ob diese kollidiert sind oder ob man sozusagen den
ganzen Rahmen benötigt und die Koordinaten des Rahmens immer wieder
überprüft...
Hoffe ich habe jetzt nicht all zu viel Verwirrung gesät.
MfG (der ahnungslose) Jonas
DasIch
User
Beiträge: 2464
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Sonntag 16. November 2008, 17:19

Du hast also eine 2 Dimensionale bounding box in einem karthesischem Koordinatensystem und du kennst nur Höhe und Breite.
Der Punkt (0|0) ist immer der untere linke Punkt und die Box ist immer ein Rechteck?

Nehmen wir mal an du willst abfragen ob es bei einem Punkt P mit den Koordinaten (x|y) eine Kollision gibt, dann musst du doch nur prüfen ob 0 <= x <= width und 0 <= y <= height wahr sind.

EDIT:"rechte untere linke" was hab ich geraucht :lol:
Zuletzt geändert von DasIch am Sonntag 16. November 2008, 17:34, insgesamt 1-mal geändert.
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Sonntag 16. November 2008, 17:31

Hi DasIch!
Ich meinte eine Box wie die hier:

Code: Alles auswählen

---------------------------
|                         |
|                         |
|                         |
---------------------------
DasIch hat geschrieben: Der Punkt (0|0) ist immer der rechte untere linke Punkt ...
Das versteh ich nicht...
Aber ja jetzt wo du es sagst, ich glaub du hast recht...
Ich werde mal test ob das meinen Zwecken genügt.
Ich meld mich.

MfG Jonas
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Sonntag 16. November 2008, 17:43

jonas hat geschrieben:Aber ich bin mir immer nocht im Klaren darüber ob
es reicht wenn man die Eckpunkte nimmt und z.B. prüft
ob diese den Koordinaten eines anderen Objekts gleich sind
ob zu testen ob diese kollidiert sind
Ergänzend zu dem, was andere schon gepostet haben:

Ob es "reicht" hängt u.a. von den Objekten ab bzw. deren Form. Wenn diese Form nicht rechteckig ist, dann ergibt der Vergleich der bbox möglicherweise eine Kollision, die in Wahrheit aber gar nicht stattfindet.

Und: Die Prüfung auf Gleichheit kann ggf. auch in die Hose gehen. Das hängt einmal davon ab, ob du mit int- oder float-Werten operierst und wie sich die möglichen Koordinaten der Objekte zu einander verhalten können, d.h. ob es durch eine Bewegung eines Objekts möglich ist, dass gar keine Identität der Koordinaten entsteht, sondern gleich eine Überschneidung.
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Sonntag 16. November 2008, 17:51

Hi numerix !
Du hast natürlich Recht, wenn die Objekte nicht rechteckig sind könnte es zu Fehlern führen. Danke für die Antwort.
Doch ich habe noch nicht raus wie, wenn ich ein Feld habe mit z.B. :
Breite = 10
Höhe = 10
Wie berechne ich den Rahmen? siehe mein erster Post
Mit der Liste der Koordinaten des Rahmens, will ich dann wieder Kolli. Abfragen mit meinen Objekten machen, die darin rumschwirren.

MfG Jonas
DasIch
User
Beiträge: 2464
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Sonntag 16. November 2008, 17:59

jonas hat geschrieben:Wie berechne ich den Rahmen?
Das ist unmöglich, da zwischen 2 Zahlen unendlich viele andere Zahlen liegen. Es sei den man nimmt nur Punkte deren Koordinaten Ganzzahlen sind, dann ist deine Kollisionsabfrage nicht zu gebrauchen.

Code: Alles auswählen

In [1]: class BoundingBox(object):
   ...:     def __init__(self, width, height):
   ...:         self.width, self.height = width, height
   ...:     def collides(self, *coordinate):
   ...:         return 0 <= coordinate[0] <= self.width and \
   ...:                 0 <= coordinate[1] <= self.height
   ...:

In [2]: bbox = BoundingBox(10, 10)

In [3]: bbox.collides(0, 1)
Out[3]: True

In [4]: bbox.collides(0, 11)
Out[4]: False
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Sonntag 16. November 2008, 18:15

Hi DasIch!
Danke für die Antwort.
Aber was willst du mir mit dem Code sagen, dass eine Kollisionsabfrage nur mit Ganzzahlen Mist ist oder was, ich verstehs leider nicht bin auch ganz offen für eine andere Möglichkeit...
Ich möchte halt eine Kollisionsabfrage haben.
Wie z.B. ein Rechteck in einem größeren Rechteck, wobei das kleinere Rechteck immer wieder von den Wänden abprallt. Halt eine Kollisionsabfrage zwischen 2 Objekten (Ich weiß jetzt nicht wie viel sich eine Kollisionsabfrage mit einem Rahmen von der mit einem Objekt unterscheidet...)

MfG Jonas
PS: Danke für die vielen Antworten :)
DasIch
User
Beiträge: 2464
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Sonntag 16. November 2008, 18:36

Das ist eine Implementation einer Kollisionsabfrage wie sie sein sollte. BoundingBox.collides gibt True zurück wenn der gegebene Punkt innerhalb der Box oder auf dem Rand ist.
BlackJack

Sonntag 16. November 2008, 18:54

@jonas: Vielleicht solltest Du das Problem mal ganz konkret und genau beschreiben. Denn eine Kollisionsabfrage zwischen zwei Rechtecken sollte ja `True` ergeben, wenn sie sich auch nur *teilweise* überlappen. Bei Rechtecken, die sich innerhalb eines Rahmens bewegen sollen, ist die Fragestellung ja aber ob das Rechteck und der Rahmen sich *komplett* überdecken.

Also welche Daten hast Du und welche Fragestellung möchtest Du beantworten?
Benutzeravatar
wuf
User
Beiträge: 1483
Registriert: Sonntag 8. Juni 2003, 09:50

Sonntag 16. November 2008, 18:57

Hallo jonas

BlackJack hat in Zusammenhang eines Spiels (Auffälliger Tread im Sub-Forum Tkinter) ein Code-Snippet für die Logik gepostet. Ich platziere es hier einmal. Das Code-Snippet wie ich es präsentiere enthält noch einige redundante Zeilen. Wichtig für dein Problem ist nur einmal die Methode:

Code: Alles auswählen

def neighbour_coordinates(self, coordinates):
Der Code erzeugt einen zweidimensionalen Array. Der Output des folgenden Skript gibt die Nachbarseiten für ein Rechteck auf Koordinate [0,0] und Koordinate [1,1] in Form einer Liste aus. Interessant ist das Rechteck auf Koordinate [0,0]. Hier werden die den Rand berührenden Rechteckseiten als 'None' in der Liste sichtbar.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

class Tile(object):
    """Klasse:Spielfeld"""

    def __init__(self, name):
        """Konstruktor für die Klasse"""
        self.name = name

DESERT = Tile('Desert')
WOODS = Tile('Woods')

class Map(object):
    """Klasse:Spielkarte"""

    #~~ Konstante für die Abfrage der Nachbarfelder
    DIRECTION_DELTAS = [(0, -1), (1, 0), (0, 1), (-1, 0)]

    #~~ Gibt die Anzahl x-Felder (Spalten) zurück
    @property
    def width(self):
        return len(self.tiles[0])

    #~~ Gibt die Anzahl y-Felder (Reihen) zurück
    @property
    def height(self):
        return len(self.tiles)

    def __init__(self, width, height, tile=DESERT):
        """Konstruktor für die Klasse"""

        #~~ Erzeugt eine Feldobjekt-Liste mit der
        #   Anzahl 'width' * 'height' Feldobjekten
        self.tiles = [[tile] * width for dummy in xrange(height)]

#        print 'Tiles',self.tiles, len(self.tiles)

#         for index,obj in enumerate(self.tiles):
#             print 'Tiles',index,obj

    def __getitem__(self, coordinates):
        """Adressiert das Feldobjekt"""
        x, y = coordinates
        return self.tiles[y][x]

    def __setitem__(self, coordinates, tile):
        """Setzt den Feldtyp"""
        x, y = coordinates
        self.tiles[y][x] = tile

    def neighbour_coordinates(self, coordinates):
        """Ermittelt die Koordinaten der Nachbarfelder"""
        x, y = coordinates
        for delta_x, delta_y in self.DIRECTION_DELTAS:
            new_x = x + delta_x
            new_y = y + delta_y
            if 0 <= new_x < self.width and 0 <= new_y < self.height:
                #~~ Der Nachbar existiert
                yield new_x, new_y
            else:
                #~~ Der Nachbar existiert nicht
                yield None


def main():
    #~~ Erstellt ein Spielfeld mit 10 * 10 Feldobjekten (default-Feldyp = 'Desert'

    SPALTEN = COLUMNS = 10
    REIHEN = ROWS = 10

    #~~Erstellt eine Instanz der Spielfeld-Klasse (Map)
    game_map = Map(SPALTEN, REIHEN)

    print 'Anzahl Spalten',game_map.width
    print 'Anzahl Reihen',game_map.height

    #~~ Ändert den Feldtyp des Feld auf Koordinate x=2,y=4
    #   in ein Feldtyp 'Wood' um
    game_map[2, 4] = WOODS

    #~~ Test: Abfrage des Feldtyp-Namens der Felder auf Koordinate:
    #         a) x=2,y=4 ('Wood')
    #         b) x=3,y=2 ('Desert')
    for x, y in [(2, 4), (3, 2)]:
        print game_map[x, y].name
    #~~ Keine Seiten des Rechtecks auf Koordinate [1,1] berühren den Rand
    print 'Nachbar-Koordinate',list(game_map.neighbour_coordinates((1, 1)))
    #~~ Zwei Seiten des Rechtecks auf Koordinate [0,0] berühren den Rand
    print 'Nachbar-Koordinate',list(game_map.neighbour_coordinates((0, 0)))
    #~~ Gibt die Koordinaten der Nachbarfelder des
    #   Testfeldes auf Koordinate x=1,y=1 zurück.
    #
    #   Testfeld     X  x=1,y=1
    #   Nachbarfeld  a  x=1,y=0
    #   Nachbarfeld  b  x=0,y=1
    #   Nachbarfeld  c  x=1,y=2
    #   Nachbarfeld  d  x=2,y=1
    #
    #         0   1   2   3 - x
    #         ------------------
    #     0 |   | a |   |   |
    #         ------------------
    #     1 | b | X | d |   |
    #         ------------------
    #     2 |   | c |   |   |
    #         ------------------
    #     3 |   |   |   |   |
    #         ------------------
    #     x |   |   |   |   |


main()
Output:
Nachbar-Koordinate [(1, 0), (2, 1), (1, 2), (0, 1)]
Nachbar-Koordinate [None, (1, 0), (0, 1), None]
Vielleich hilft dir das auf deiner Suche.

Gruss wuf :wink:
Take it easy Mates!
Poisos
User
Beiträge: 6
Registriert: Freitag 24. Oktober 2008, 08:41

Montag 17. November 2008, 00:59

Wie z.B. ein Rechteck in einem größeren Rechteck, wobei das kleinere Rechteck immer wieder von den Wänden abprallt. Halt eine Kollisionsabfrage zwischen 2 Objekten (Ich weiß jetzt nicht wie viel sich eine Kollisionsabfrage mit einem Rahmen von der mit einem Objekt unterscheidet...)
Tja, Deine Fragen sind ja eher mathematischer Natur, als auf Python bezogen.

Mit deinem oben zitierten Beispielt, definierst Du eigentlich einen speziellen Fall. Normalerweise würden Kollisionen zwischen zwei Rechtecken (R1, R2) dann festzustellen sein, wenn mindestens einer der Punkte von R1 innerhalb der Punktwolke R2 liegt. Das sollte für Dich ja nicht so schwer festzustellen sein, weil die x-Koordinate des Punktes aus R1 >= des x Werts des Punktes oben-links in R2 und <= des x Werts des Punktes oben-rechts in R2 sein muss. Bei dem y Wert ist es entsprechend. (aufzeichen hilft ;) )

Dein Fall beschreibt eher so etwas wie einen "Teich" in dem deine Rechtecke "schwimmen". D.h. so gesehen käme es ständig zu einer Kollision zwischen den kleinen herumschwimmenden Rechtecken und dem Rechteck des "Teichs".
D.h. Du hast jetzt zwei Möglichkeiten:
1. Du beschreibst den "Teich" in seiner speziellen Funktion, das die Objekte in ihm nicht herauskommen.
2. Du "mauerst" einen Teich aus "großen" Rechtecken um die "Wasserfläche" herum.

Im Fall 1 dürfte kein Punkt eines der kleinen Rechtecke (die wir jetzt mal Fische nennen :) ) einen x-Wert < x-min-Teich oder > x-max-Teich haben; entsprechend keinen y-Wer < y-min-Teich oder > y-max-Teich.
Im Fall 2 gilt die obige Beschreibung von der Kollision bzw. - um das genauer auszudrücken - der Überlappung von zwei Rechecken. ... Das würde die Art der Kollisions-/Überlappungsberechnung also vereinheitlichen, was ja bei der Entwicklung immer gern gesehen ist :).

Ich könnte mir vorstellen, dass Dein "Teich", der Bildschirm ist und Du willst nicht, dass die "Fische" aus dem Bild schwimmen :) !?

Übrigens bietet pygame (http://www.pygame.org) auf dieser Grundlage bereits ein fertiges System zur "Überlappungsabfrage" der in diesem Package verwendeten Sprites auf Basis von "Rect" Objekten.

Es gibt naütlich bei diese Art von Kollisionsbestimmung noch ein weiteres Problem ... abhängig von dem Detailgrad den Du benötigst. (Das Problem wird auch nicht von pygame beseitigt.)
Wenn Du eine Überlappung feststellst, kann es vielleicht schon zu spät sein, da Du ein "Eindringen" eines Rechtecks (sprich die Überlappung) in ein anderes verhindern willst.
Ich bin mir selbst noch nicht ganz sicher, wie man damit am besten umgeht, aber es läuft wohl darauf hinaus, dass man dann eine Analyse der Kollision des Bewegungsvektors des Rechtecks vornimmt ... und das wohl auch von jedem Punkt der Bounding Box aus gesehen. Einige Infos dazu kannst Du hier finden: http://java.sys-con.com/node/46663
Such in dem Artikel mal nach "processCollisions()". Die Bilder dazu erläutern das ebenfalls.

Kleiner Tipp noch: Um die Auflösung der Kollisions zwischen zwei Objekten, die durch ein Rechteck repräsentiert werden, zu erhöhen, verwendet man statt des einen Rechtecks zur Repräsentation einfach mehrere :).
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Dienstag 18. November 2008, 16:06

Wohoo!
Hey Leute vielen Dank für die raschen Antworten voll nützlicher Denkanstöße und Ideen! :D
Ich denke daraus kann ich mir nun was basteln, wenn es klappt werde ich
es posten!
@Blackjack: Zur genaueren Beschreibung meines Problems siehe Poisos Beitrag unter "1."
Dein Beispiel Code zum "Game of Life" werde ich mir noch mal genau
ansehen.
Danke an wuf für das hier posten.
@Poisos: Der Beitrag mit den Fischen und dem Teich hat mir gut gefallen, sehr kreativ! :D
Du hast wahrscheinlich Recht damit, dass die Fragen eher mathematischer Natur sind.

Vielen herzlichen Dank.
MfG Jonas
Antworten