Encuentra el conjunto de rectangularjs contiguos más grandes para cubrir áreas múltiples

Estoy trabajando en una herramienta llamada Quickfort para el juego Dwarf Fortress . Quickfort convierte las hojas de cálculo en formato csv / xls en una serie de comandos para que Dwarf Fortress los lleve a cabo para trazar un “plano” dentro del juego.

Actualmente estoy tratando de resolver de manera óptima un problema de trazado de áreas para la versión 2.0 de esta herramienta.

Considere el siguiente “blueprint” que define el trazado de comandos para una grilla bidimensional. Cada celda en la grilla debe ser excavada (“d”), canalizada (“c”) o dejada sin trazar (“.”). Cualquier número de comandos de trazado distintos podría estar presente en el uso real.

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

Para minimizar el número de instrucciones que deben enviarse a Dwarf Fortress, me gustaría encontrar el conjunto de rectangularjs contiguos más grandes que se pueden formar para cubrir completamente, o “trazar”, todas las celdas trazables. Para que sea válido, todas las celdas de un rectángulo determinado deben contener el mismo comando.

Este es un enfoque más rápido que el que tomó Quickfort 1.0: trazar cada celda individualmente como un rectángulo de 1×1. Este video muestra la diferencia de rendimiento entre las dos versiones.

Para el anteproyecto anterior, la solución se ve así:

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

Cada rectángulo con el mismo número anterior denota un rectángulo contiguo. Los rectangularjs más grandes tienen prioridad sobre los rectangularjs más pequeños que también podrían formarse en sus áreas. El orden de la numeración / rectangularjs no es importante.

Mi enfoque actual es iterativo. En cada iteración, construyo una lista de los rectangularjs más grandes que podrían formarse a partir de cada una de las celdas trazables de la cuadrícula al extenderse en las 4 direcciones desde la celda. Después de ordenar primero la lista más grande, comienzo con el rectángulo más grande encontrado, marco las celdas subyacentes como “trazadas” y grabo el rectángulo en una lista. Antes de trazar cada rectángulo, se verifican las celdas subyacentes para asegurarse de que aún no se hayan trazado (superposición de un trazado anterior). Luego comenzamos de nuevo, encontrando los rectangularjs restantes más grandes que se pueden formar y trazándolos hasta que todas las celdas hayan sido trazadas como parte de algún rectángulo.

Considero que este enfoque es un poco más optimizado que una simple búsqueda de fuerza bruta, pero estoy desperdiciando muchos ciclos (re) calculando los rectangularjs más grandes de las células y comprobando los estados de las células subyacentes.

Actualmente, esta rutina de descubrimiento de rectángulo ocupa la mayor parte del tiempo de ejecución total de la herramienta, especialmente para grandes planos. He sacrificado algo de precisión por el bien de la velocidad al solo considerar rectangularjs de las celdas que parecen formar la esquina de un rectángulo (determinado usando heurísticas de células vecinas que no siempre son correctas). Como resultado de esta ‘optimización’, mi código actual en realidad no genera la solución anterior correctamente, pero está lo suficientemente cerca.

En términos más generales, considero que el objective de los primeros rectangularjs primero es ser un enfoque “suficientemente bueno” para esta aplicación. Sin embargo, observo que si el objective es encontrar el conjunto mínimo (el número más bajo) de rectangularjs para cubrir completamente áreas múltiples, la solución sería así:

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

Este segundo objective en realidad representa una solución más óptima para el problema, ya que por lo general, menos rectangularjs significan menos comandos enviados a Fortaleza enana. Sin embargo, este enfoque me parece más cercano a NP-Hard, basado en mis conocimientos limitados de matemáticas.

Mira el video si quieres entender mejor la estrategia general; No me he ocupado de otros aspectos del proceso de Quickfort, como encontrar la ruta de cursor más corta que traza todos los rectangularjs. Posiblemente haya una solución a este problema que combine de forma coherente estas múltiples estrategias.

Ayuda de cualquier forma sería apreciada.

Encontré el papel Fast Algorithms To Partition Simple Rectilinear Polygons de San-Yuan Wu y Sartaj Sahni, que podría ser de su interés. En su ejemplo, la región con el carácter ‘d’ forma un polígono rectilíneo, también las regiones con ‘c’ y ‘.’. Este artículo incluye algoritmos para polígonos rectilíneos simples sin orificios .

Si un polígono incluye agujeros, existen algoritmos que se ejecutan con el tiempo O (n ^ 3/2 log n), como JM Keil en el papel Descomposición de polígonos en la página 11.

Si se minimiza la longitud total de los segmentos de línea introducidos en el proceso de partición es el otro criterio de optimización , el problema se convierte en NP-completo si el polígono contiene agujeros (página 12). Para estos problemas existen algoritmos de aproximación (el documento se refiere a trabajos con tales algoritmos). Si el polígono no contiene agujeros, hay un algoritmo de tiempo O (n ^ 4).

Esto no es realmente una respuesta, pero usando una búsqueda ingenua puede obtener

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

Básicamente, empiezas desde la esquina superior izquierda y la utilizas como la esquina superior izquierda de tu siguiente rectángulo, luego verificas cuánto puedes extender hacia la derecha y hacia abajo, luego encuentras la celda más alta y más a la izquierda de los bits restantes, etc. .

Esto es probablemente muy ineficaz en algunos casos, pero es rápido ya que no tiene que volver a calcular nada …

Puede tratar de simplificar el conjunto de rectangularjs más grandes dados por el algoritmo apuntado en http://www.montefiore.ulg.ac.be/~pierard/rectangles/

En mi opinión, todas las soluciones que encuentran un conjunto de rectangularjs que cubren el área original son correctas. Encontrar un conjunto más pequeño de rectangularjs es mejor porque se comprime / se comporta mejor.

Así que no aconsejaría intentar encontrar la solución óptima. (Supongo que también es NP-hard).

Para una solución de ejecución más rápida, puede colocar inicialmente la matriz en grupos de 4 celdas e intentar fusionarlas si son las mismas. Después de eso, puedes unir grupos de 4 grupos, si son iguales. Y hazlo recursivamente si terminaste.

Esto no encontrará la solución óptima, pero será muy rápido. Si sus matrices son grandes, con grandes áreas contiguas, la diferencia con la óptima no será tan grande.