2D Bitmap und "Boundingboxes"

[igel457]

Hallo.

Ich habe ein kleines Problem. Ich möchte die 2D S/W Maske einer bliebigen Landschaft in meinem 2D Spiel in kleine, virtuelle Rechtecke unterteilen, mit denen ich schneller Kollisionsabfragen machen kann. Meine Frage ist nun: Wie schreibe ich einen solchen Algorythmus? Gibt es da irgendwo Anleitungen? Wie würdet ihr vorgehen?

Ich habe mal ein Beispiel, wie das aussehen soll, angehängt...

Igel457

[arbu man]

Das ähnelt etwas einen 2d octree verfahren, aber ein genauer algorithmus ist schwirig.
Wahrscheinlich würde es sehr lange dauern eine solche matrix zu stellen.
Aber man könnte so vorgehen:


Das bild in Spalten oder Zeilen einteilen. (z.B. mit 60px weite)


dann jede einzele spalte untersuchen: und ab einer gewissen anzahl von pixeln (z.b. 20px) ein rechteck beginnen und wenn dann wieder weniger pixel da sind das recheck benden.

Danach könnte man die Spalten noch optimieren.

[Der_Unwissende]

HI,
dass das einem Octree für 2D ähnelt finde ich ist eine lustige Idee. Der 2D Octree heißt (ganz logisch) Quadtree. Die Idee entspricht eigentlich genau der eines Octree oder BinTree. Fangen wir mal unten an.
Bei keiner Dimension habe ich einen Punkt, Kollision ist trivial.
Bei einer Dimension kann ich weiter nach links oder Rechts gehen. Teile ich also eine gerade in der Mitte in zwei Teile und diese Teile wieder in der Mitte... Ich hätte einen Binären Baum.
Bei zwei Dimensionen habe ich Höhe und Breite. Der Einfachheit halber können wir sogar von einem Quadrat ausgehen (macht die Sache auch schneller). Hier kann ich jetzt einfach das gesamte Quardrat in 4 Teile zerlegen, diese wieder in 4 usw.
Bei drei Dimensionen brauche ich wieviel Teile? Genau 2^{3} oder auch 8 -> Octree. Du zerlegst den Raum in 8 Quarder, diese wieder in 8...

Warum macht man das? Na ja, z.B. zur Kollisionskontrolle. Im zwei Dimensionalen Raum kann ich gucken, in welchem der 4 Quadrate sich mein betrachteter Körper befindet. Es können bis zu 3 Quadrate (75%) rausfallen aus der Betrachtung. So schränkt man einfach den Bereich ein, den man absucht. Gut, doch woher weiß man jetzt in welchen Quadraten sich ein Körper befindet? Richtig man baut eine Boundingbox rum. Die Beschreibt ungefähr die Form des Körpers, tut dies jedoch geometrisch sehr einfach durch Rechtecke, mit denen man leichter rechnen kann. Also ist es nicht eine Art von 2D Octree, sondern wird benötigt um den Quadtree sinnvoll anzuwenden.
Der Weg der hier angegeben wurde ist eine Möglichkeit. Du kannst aber wieder den Quadtree Trick anwenden. Du gehst ja rekursiv vor und die einzelnen Quadrate werden immer kleiner. Dies machst du bis sie deine Toleranzgrenze (du willst ja eine ungefähre Box) erreicht haben (also alles von deinen Körpern liegt tolerierbar von der Kante des umgebenden Quadrats entfernt). Nun kannst du einfach für alle Quadrate schauen, ob sich hierin ein Körper befindet (z.B. geg. durch die Farbe). Wenn ja, fässt du den einfach mit den Nachbarn, die auch einen Körper enthalten zu einem größeren Körper zusammen. So hast du dann ein Rechteck, dass sich aus ein paar dieser Quadrate zusammen setzt.

Gruß Der Unwissende

[igel457]

Danke für die Tipps.

Werde es nachher mal ausprobieren!

[BlackJack]

ich würde dir statt eines QuadTrees einen kdTree empfehlen. bei dem wird die Fläche nicht immer in 4 genau gleich grosse quadrate weiter unterteilt, sondern es wird immer nur in 2 bereiche unterteilt, wobei die schnittgeraden zw. den Bereichen abwechselnd waagerecht und seknrecht verlaufen. Und die Position der Schnuttgeraden kann man dabei auch variieren, z.b. so dass sich links und rechts der Schnittgeraden etwa gleich viele objekte befinden.
Das ganze kann man dann auch auf 3D ausweiten, hier findest du ein paar bilder zu 2D und 3D: http://en.wikipedia.org/wiki/Kd-tree

[Phobeus]

Das Bild sagt nicht viel aus über die tatsächliche Dimension, die letztendlich angestrebt wird. Dennoch möchte ich an dieser Stelle hinweisen, dass QuadTrees und auch BSP in vielen aktuellen Fällen sogar kontraproduktiv sein können, da mehr Einteilungen vorgenommen würde als die CPU per Bruteforce durchjagen könnte. Sollte z.B. nur der Spieler auf Kollision geprüft werden, könnte es mehr Sinn machen, wenn man um die Zielobjekte eine große Kollisionsbox legt. Befindet sich der Spieler in diesem Bereich, wird eine detaillierte Kollision vorgenommen und zwar auf gut Glück alle durch. So wird der Spieler vermutlich entweder den Boden oder gegen die Decke springen... beides gleichzeitig könnte in manchem Projekt unwahrscheinlich sein. Ggf. macht es noch einen Sinn eine Eben darüber oder darunter zu unterteilen... also zu sehen, ob der Spieler in einem Sektor ist und nur jene Objekte darinne zu prüfen, oder halt den Kollisionsbereich noch einmal in zwei Teile zu unterscheiden. Eine viel feinere Abstimmung oder gar ein komplexer Quadtree würden vermutlich unterm Strich nicht nur schwerer zu implementieren sein, sondern auch mehr Leistung kosten als es nötig wäre. (BSP bremst aktuelle Quake-Titel auf aktuellen Rechnern). Eine solche Überlegung lohnt sich nur dann, wenn Du wenige Objekte hast, die kollidieren... nimmt dessen Zahl zu (zahlreiche Gegener ohne feste Pfade, Geschosse deren Bahn nicht vorbestimmbar ist etc.), kann ein QuadTree oder vergleichbares natürlich sinnvoll sein.

[igel457]

Hallo,

Ich habe es jetzt einigermaßen hinbekommen. Im Endeffekt ist es jetzt so, wie Arbu Man vorgeschlagen hat. Mein Spiel läuft auch merklich schneller.
Ich habe die Unit, ein Beispielprojekt und einen Screenshot meines Spiels angehängt.