Finde den Satz der größten zusammenhängenden Rechtecke, um mehrere Bereiche abzudecken

Ich arbeite an einem Tool namens Quickfort für das Spiel Dwarf Fortress . Quickfort verwandelt Spreadsheets im CSV / XLS-Format in eine Reihe von Befehlen, die Dwarf Fortress ausführen muss, um einen “Blueprint” innerhalb des Spiels zu erstellen.

Ich versuche gerade, ein Flächenplotting-Problem für die Version 2.0 dieses Tools optimal zu lösen.

Betrachten Sie den folgenden “Blueprint”, der Zeichenbefehle für ein 2-dimensionales Gitter definiert. Jede Zelle im Gitter sollte entweder ausgegraben (“d”), kanalisiert (“c”) oder nicht plottiert (“.”) Sein. Bei der tatsächlichen Verwendung kann eine beliebige Anzahl von unterschiedlichen Zeichenbefehlen vorhanden sein.

. d . dcc ddddcc . ddd . c dddddc . d . ddc 

Um die Anzahl der statementen zu minimieren, die an Dwarf Fortress gesendet werden müssen, würde ich gerne die Menge der größten zusammenhängenden Rechtecke finden, die gebildet werden können, um alle plotbaren Zellen vollständig zu bedecken oder zu “plotten”. Um gültig zu sein, müssen alle Zellen eines bestimmten Rechtecks ​​denselben Befehl enthalten.

Dies ist ein schnellerer Ansatz als Quickfort 1.0: Jede Zelle wird einzeln als 1×1-Rechteck gezeichnet. Dieses Video zeigt den performancesunterschied zwischen den beiden Versionen.

Für den obigen Entwurf sieht die Lösung folgendermaßen aus:

 . 9 . 0 3 2 8 1 1 1 3 2 . 1 1 1 . 2 7 1 1 1 4 2 . 6 . 5 4 2 

Jedes rechteckige Rechteck oben bezeichnet ein zusammenhängendes Rechteck. Die größten Rechtecke haben Vorrang vor kleineren Rechtecken, die auch in ihren Bereichen gebildet werden können. Die Reihenfolge der Nummerierung / Rechtecke ist unwichtig.

Mein aktueller Ansatz ist iterativ. In jeder Iteration baue ich eine Liste der größten Rechtecke auf, die aus jeder der plotbaren Zellen des Gitters gebildet werden können, indem sie sich in alle 4 Richtungen von der Zelle aus erstrecken. Nachdem ich die Liste zuerst sortiert habe, beginne ich mit dem größten gefundenen Rechteck, markiere die darunterliegenden Zellen als “geplottet” und zeichne das Rechteck in einer Liste auf. Vor dem Plotten jedes Rechtecks ​​werden die darunter liegenden Zellen überprüft, um sicherzustellen, dass sie noch nicht geplottet sind (überlappend mit einem vorherigen Plot). Wir beginnen dann erneut und finden die größten verbleibenden Rechtecke, die gebildet werden können, und zeichnen sie, bis alle Zellen als Teil eines Rechtecks ​​geplottet wurden.

Ich halte diesen Ansatz für etwas optimaler als eine dumme Brute-Force-Suche, aber ich verschwende viele Zyklen, um die größten Rechtecke der Zellen zu berechnen und die Zustände der darunterliegenden Zellen zu überprüfen.

Gegenwärtig beansprucht diese Rechteck-Erkennungsroutine den Löwenanteil der Gesamtlaufzeit des Werkzeugs, insbesondere für große Blaupausen. Aus Gründen der Geschwindigkeit habe ich etwas Genauigkeit geopfert, indem ich nur Rechtecke aus Zellen betrachtet habe, die die Ecke eines Rechtecks ​​zu bilden scheinen (bestimmt mit Hilfe einiger Nachbarzellenheuristiken, die nicht immer korrekt sind). Als Ergebnis dieser “Optimierung” erzeugt mein aktueller Code die obige Lösung nicht korrekt, aber sie ist nahe genug.

Im weiteren Sinne betrachte ich das Ziel der größten Rechtecke als “gut genug” für diese Anwendung. Ich beobachte jedoch, dass, wenn das Ziel stattdessen darin besteht, die Mindestmenge (die kleinste Anzahl) von Rechtecken zu finden, um mehrere Bereiche vollständig abzudecken, würde die Lösung stattdessen so aussehen:

 . 3 . 5 6 8 1 3 4 5 6 8 . 3 4 5 . 8 2 3 4 5 7 8 . 3 . 5 7 8 

Dieses zweite Ziel stellt tatsächlich eine optimalere Lösung für das Problem dar, da weniger Rechtecke normalerweise weniger Befehle an Dwarf Fortress senden. Dieser Ansatz erscheint mir jedoch aufgrund meiner begrenzten mathematischen Kenntnisse näher an NP-Hard.

Sehen Sie sich das Video an, wenn Sie die Gesamtstrategie besser verstehen möchten. Ich habe andere Aspekte von Quickforts process nicht angesprochen, wie zum Beispiel den kürzesten Cursorpfad zu finden, der alle Rechtecke plottet. Möglicherweise gibt es eine Lösung für dieses Problem, die diese verschiedenen Strategien kohärent kombiniert.

Hilfe jeglicher Form wäre willkommen.

    Ich habe das Papier Fast Algorithms to Partition Simple Rectilinear Polygons von San-Yuan Wu und Sartaj Sahni gefunden, das für Sie von Interesse sein könnte. In Ihrem Beispiel bildet die Region mit dem Zeichen ‘d’ ein geradliniges Polygon, ebenso die Regionen mit ‘c’ und ‘.’. Dieses Papier enthält Algorithmen für lochfreie einfache geradlinige Polygone .

    Wenn ein Polygon Löcher enthält, gibt es Algorithmen, die mit der Zeit O (n ^ 3/2 log n) laufen, wie JM Keil in der Veröffentlichung Polygon Decomposition auf Seite 11 angibt.

    Wenn die Minimierung der Gesamtlänge der im Partitionierungsprozess eingefügten Liniensegmente das andere Optimierungskriterium ist , wird das Problem NP-vollständig, wenn das Polygon Löcher enthält (Seite 12). Für diese Probleme existieren Approximationsalgorithmen (das Papier bezieht sich auf Papiere mit solchen Algorithmen). Wenn das Polygon keine Löcher enthält, gibt es einen O (n ^ 4) -Zeitalgorithmus.

    Dies ist nicht wirklich eine Antwort, aber mit einer naiven Suche können Sie bekommen

     . 1 . 2 3 3 4 1 5 2 3 3 . 1 5 2 . 6 7 1 5 2 8 6 . 1 . 2 8 6 

    Grundsätzlich beginnen Sie von der oberen linken Ecke und verwenden Sie es als die obere linke Ecke des nächsten Rechtecks, dann überprüfen Sie, wie weit Sie es nach rechts und unten erweitern können, dann finden Sie die oberste und ganz linke Zelle der verbleibenden Bits und so weiter .

    Dies ist wahrscheinlich in einigen Fällen sehr ineffektiv, aber es ist schnell, da Sie nichts neu berechnen müssen.

    Sie können versuchen, die Menge der größten Rechtecke zu vereinfachen, die der Algorithmus auf http://www.montefiore.ulg.ac.be/~pierard/rectangles/ angibt.

    Aus meiner Sicht sind alle Lösungen, die eine Reihe von Rechtecken finden, die den ursprünglichen Bereich abdecken, korrekt. Das Finden eines kleineren Satzes von Rechtecken ist besser, weil es besser komprimiert / leistungsfähiger ist.

    Daher würde ich nicht empfehlen, die optimale Lösung zu finden. (Ich denke, es ist auch NP-schwer).

    Für eine schneller laufende Lösung können Sie die Matrix zunächst in Gruppen von 4 Zellen einteilen und versuchen, sie zusammenzuführen, wenn sie identisch sind. Danach können Sie Gruppen von 4 Gruppen zusammenführen, wenn sie identisch sind. Und tun Sie das rekursiv, wenn Sie fertig sind.

    Dies wird nicht die optimale Lösung finden, wird aber sehr schnell sein. Wenn Ihre Matrizen groß sind und große zusammenhängende Bereiche haben, wird der Unterschied zum Optimalen nicht so groß sein.