Unterteilen von Karten in Rechtecke

[veers]

Ich entwickle derzeit ein kleines 2D Spiel. Für dieses Spiel möchte ich die nicht passierbaren Felder auf der Karte durch möglichst grosse Rechtecke zusammenfassen (u.a. für die Kollisionserkennung und Pfadsuche).

Etwas konkreter:
Eine Karte ist eine Liste mit Feldern. Jedes Feld ist gleich gross, quadratisch und entweder begehbar oder nicht. Derzeit werden diese Felder als PNG Grafiken gespeichert (spart mir vorerst den Map Editor). Zusätzlich gegeben ist die Breite (und somit auch die Höhe) der Karte. Die Karten könnten relativ gross werden (128x128, vielleicht bis zu 1024x1024).

Nun möchte ich diese Felder durch möglichst wenige Rechtecke darstellen.

Gibt es dazu einen Algorithmus mit einer brauchbaren Effizienz welcher mir ein optimales Resultat (minimale Anzahl Rechtecke) liefert? Wenn ja, welcher? Wenn nicht, was für Approximationen gibt es?

Wäre es vielleicht besser einfach einen Quadtree zu verwenden (würde sich einfach generieren lassen, und wäre vermutlich auch effizient genug)? Das Problem beim Quadtree sehe ich dabei das die Karten oft nicht aus grossen unbegehbaren Flächen bestehen sondern aus vielen Wänden:

Code: Alles auswählen

X___
X___
XXX

Was sich in einem Quadtree natürlich alles andere als ideal darstellen lässt.

Gruss,
Jonas

[sma]

In einer Zeit vor dem Internet hatte ich mal eine GUI-Bibliothek geschrieben und musste dort das Problem lösen, die richtigen Clipping-Rectangles für sich überlappende Fenster zu berechnen. Auch dort ging es darum, eine minimale Anzahl von Rechtecken zu finden, die den sichtbaren Bereich darstellten.

Mir viel damals nur ein (und Recherchieren ging nur in Büchern oder Fachartikeln in echten Bibliotheken ;), erst mal alle möglichen Rechtecke zu berechnen, indem man an allen Kanten schneidet und dann in einer Schleife solange Rechtecke mit gleicher Kantenlänge zu größeren zusammenzufassen, bis es nicht mehr weniger Rechtecke werden. Da es hier IIRC kein Optimum gibt, habe ich eher horizontal denn vertikal zusammengefasst, wissend das ein Prozessor schneller horizontale Linien denn vertikale Linien zeichnen konnte und ich wusste, dass Quickdraw vom Mac, das zu einer Zeit, als andere Computer nur von GUIs träumen konnten, bereits abgerundete Fensterecken hatte, dort Cliprects der Höhe 1 benutzte.

Aber reicht es bei dir nicht, einfach unter Koordinate X,Y nachzuschauen, ob man mit etwas zusammengestoßen ist? Die 1024x1024 würden mich heutzutage nicht schrecken, selbst bei 4 Bytes pro Zelle reden wir da nur von 4 MB RAM. Da ist mancher Welcome-Screen größer.

Stefan