Я работаю над инструментом Quickfort для игры Крепость-гном. Quickfort превращает электронные таблицы в формате csv/xls в ряд команд для Крепости Гномов, чтобы выполнить "план" в игре.
В настоящее время я пытаюсь оптимально решить проблему построения области для выпуска 2.0 этого инструмента.
Рассмотрим следующий "чертеж", который определяет составление команд для двумерной сетки. Каждая ячейка в сетке должна быть выкопана ( "d" ), направляется ( "c" ) или остается незамкнутой ( "." ). В фактическом использовании может присутствовать любое количество отдельных команд построения.
. d . d c c
d d d d c c
. d d d . c
d d d d d c
. d . d d c
Чтобы свести к минимуму количество инструкций, которые нужно отправить в Крепость Гномов, я хотел бы найти набор самых больших смежных прямоугольников, которые могут быть сформированы, чтобы полностью покрыть или "заговорить" все ячейки, способные к размножению. Чтобы быть действительными, все ячейки прямоугольника должны содержать одну и ту же команду.
Это более быстрый подход, чем Quickfort 1.0: построение каждой ячейки по отдельности в виде прямоугольника 1x1. Это видео показывает разницу в производительности между двумя версиями.
В приведенном выше проекте решение выглядит следующим образом:
. 9 . 0 3 2
8 1 1 1 3 2
. 1 1 1 . 2
7 1 1 1 4 2
. 6 . 5 4 2
Каждый прямоугольник с одинаковым номером обозначает смежный прямоугольник. Самые большие прямоугольники имеют приоритет над меньшими прямоугольниками, которые также могут быть сформированы в их областях. Порядок нумерации/прямоугольников не имеет значения.
Мой текущий подход является итеративным. На каждой итерации я строю список из самых больших прямоугольников, которые могут быть сформированы из каждой из сетчатых ячеек, распространяющихся во всех четырех направлениях от ячейки. После сортировки самого большого списка сначала я начинаю с самого большого найденного прямоугольника, отмечаю его базовые ячейки как "построенные" и записывая прямоугольник в списке. Перед построением каждого прямоугольника его базовые ячейки проверяются, чтобы убедиться, что они еще не построены (перекрытие предыдущего графика). Затем мы начинаем снова, находим самые большие оставшиеся прямоугольники, которые могут быть сформированы и построены, пока все ячейки не будут отложены как часть некоторого прямоугольника.
Я считаю этот подход немного более оптимизированным, чем поиск немой грубой силы, но я трачу много циклов (пере) вычисляя наибольшие прямоугольники ячеек и проверяя состояния ячеек.
В настоящее время эта процедура обнаружения прямоугольника принимает львиную долю от общей продолжительности работы инструмента, особенно для больших чертежей. Я пожертвовал некоторой точностью ради скорости, рассматривая только прямоугольники из ячеек, которые, как представляется, образуют угол прямоугольника (определенный с использованием эвристики соседних ячеек, которые не всегда правильны). В результате этой "оптимизации" мой текущий код на самом деле не создает правильное решение выше, но оно достаточно близко.
В более широком смысле, я считаю цель самых больших прямоугольников - сначала быть "достаточно хорошим" для этого приложения. Однако я замечаю, что если цель состоит в том, чтобы найти минимальное множество (наименьшее число) прямоугольников для полного покрытия нескольких областей, решение будет выглядеть следующим образом:
. 3 . 5 6 8
1 3 4 5 6 8
. 3 4 5 . 8
2 3 4 5 7 8
. 3 . 5 7 8
Эта вторая цель фактически представляет собой более оптимальное решение проблемы, поскольку меньшее количество прямоугольников обычно означает меньшее количество команд, отправленных в Крепость Гномов. Однако этот подход мне кажется ближе к NP-Hard, основанный на моих ограниченных математических знаниях.
Посмотрите видео, если хотите лучше понять общую стратегию; Я не рассматривал другие аспекты процесса Quickfort, такие как поиск кратчайшего пути курсора, который отображает все прямоугольники. Возможно, существует решение этой проблемы, которая когерентно объединяет эти множественные стратегии.
Помощь любой формы будет оценена.
