Пазл «узор-наполнение плитки»

Question

Я столкнулся с интересной проблемой при программировании генератора случайного уровня для игры на основе плитки. Я реализовал для нее решатель грубой силы, но он экспоненциально медленный и определенно непригоден для моего использования. Я не обязательно ищу идеальное решение, я буду удовлетворен «хорошим» решением, которое хорошо работает.

Постановка задачи:

Скажем, у вас есть все или подмножество доступных следующих плитки (это комбинация всех возможных моделей 4-битных сопоставляются вправо, вверх, влево и вниз):

alt text http://img189.imageshack.us/img189/3713/basetileset.png

Вам предоставляется сетку, где отмечены некоторые клетки (истина), а другие нет (ложные). Например, это может быть вызвано алгоритмом perlin noise. Цель состоит в том, чтобы заполнить это пространство плиточками, чтобы было возможно как можно больше сложной плитки. В идеале все плитки должны быть подключены. Не может быть решения для некоторых входных значений (доступные плитки + узор). Всегда существует хотя бы одно решение, если доступна верхняя левая, несвязанная плитка (т. Е. Все ячейки шаблонов могут быть заполнены этой плиткой).

Пример:

Изображения слева направо: Наличие плитки (зеленые плитки могут быть использованы, красный не может), шаблон для заполнения и раствор

alt text http://img806.imageshack.us/img806/2391/sampletileset.png + alt text http://img841.imageshack.us/img841/7/samplepattern.png = alt text http://img690.imageshack.us/img690/2585/samplesolution.png

То, что я пробовал:

Моя попытка перебора всех попыток и отслеживать найденные решения. Наконец, он выбирает решение, которое максимизирует общее количество соединений, исходящих от каждого из плит. Время, которое требуется, является экспоненциальным в отношении количества плиток в шаблоне. Образец из 12 плиток занимает несколько секунд, чтобы решить.

Примечания:

Как я уже говорил, производительность является более важным, чем совершенство. Однако окончательное решение должно быть правильно подключено (нет плитки, указывающей на плитку, которая не указывает на исходную плитку). Чтобы дать представление о сфере охвата, я бы хотел обработать шаблон из 100 фрагментов менее чем за 2 секунды.

Answer 1

В качестве базы взгляните на an earlier answer I gave on searching. Программы поиска по скалолазанию - это инструмент, который каждый программист должен иметь в своем арсенале, поскольку они работают намного лучше, чем простые решатели грубой силы.

Здесь даже относительно плохой алгоритм поиска имеет преимущество в том, что он не будет генерировать незаконные доски, что значительно сократит ожидаемое время выполнения.

Answer 2

Для экземпляров с 100 элементами, я считаю, что динамическая программа, основанная на разметке на вставке графического ввода, может соответствовать счету.

Carving разложения

В теории графов, резьба разложение графа является рекурсивным бинарным разбиением его вершин.Например, здесь представлен график

1--2--3 
| | 
| | 
4--5 

и один из его резьбовых разбиений

 {1,2,3,4,5} 
    /  \ 
    {1,4}  {2,3,5} 
/ \  / \ 
{1} {4} {2,5}  {3} 
     / \ 
     {2} {5}. 

Ширина резьбы разложения максимальное число ребер, выходящих один из его разделов. В этом случае {2,5} имеет исходящие ребра 2--1, 2--3 и 5--4, так что ширина 3. Ширина перегородки кД-дерево-стиль 10 х 10 сетки 13.

Резьба-ширина График - минимальная ширина разложения. Известно, что плоские графы (в частности, подграфы сетчатых графов) с n вершинами имеют ширину резки O (√n), а константа big-O относительно мала.

Динамическая программа

Учитывая, п-вершинный граф ввода и резьба разложение шириной W, есть O (2 ^ж п) -time алгоритм для вычисления оптимального выбора плитки. Это время работы быстро растет в w, поэтому вы должны попытаться разложить некоторые примеры ввода вручную, чтобы получить представление о том, какую производительность ожидать.

Алгоритм работы над деревом разложения снизу вверх. Пусть X - разбиение, F - множество ребер, оставляющих X. Мы делаем таблицу, отображающую каждую из 2 ^{| F |} возможности наличия или отсутствия ребер в F до оптимальной суммы на X при указанных ограничениях (-Infinity, если нет решения). Например, с разбиением {1,4}, мы имеем запись

{} -> ?? 
{1--2} -> ?? 
{4--5} -> ?? 
{1--2,4--5} -> ?? 

Для разделов листа только с одной вершиной, подмножество F полностью определяет плитку, так легко заполнить число соединений (если плитка действительно) или -Infinity в противном случае. Для других разделов при вычислении записи таблицы попробуйте использовать различные шаблоны связей для ребер, которые идут между двумя дочерними элементами.

Например, предположим, что у нас есть куски

     | 
. .- .- -. . 
    |     

Стол для {1} является

{} -> 0 
{1--2} -> 1 
{1--4} -> -Infinity 
{1--2,1--4} -> 2 

Стол для {4} является

{} -> 0 
{1--4} -> 1 
{4--5} -> 1 
{1--4,4--5} -> -Infinity 

Теперь давайте вычислим таблицу для {1,4}. Для {} без края 1--4 у нас есть оценка 0 для {1} (запись {}) плюс оценка 0 для {4} (запись {}). С краем 1--4 у нас есть оценка -Infinity + 1 = -Infinity (записи {1--4}).

{} -> 0 

Для {1--2}, баллы являются 1 + 0 = 1 без 1--4 и 2 + 1 = 3 с.

{1--2} -> 3 

Постоянно.

{4--5} -> 0 + 1 = 1 (> -Infinity = -Infinity + (-Infinity)) 
{1--2,4--5} -> 1 + 1 = 2 (> -Infinity = 2 + (-Infinity)) 

В конце мы можем использовать таблицы для определения оптимального решения.

найти разложение Carving

Существуют сложные алгоритмы для нахождения хороших высекая разложения, но вы не можете им нужно. Попробуйте простую схему разбиения двоичных пространств.

Answer 3

Думаю, у меня может быть лучшая идея. Я не тестировал его, но я уверен, что он будет быстрее, чем чисто грубое силовое решение для больших зон.

Сначала создайте пустой набор («набор», являющийся коллекцией, которая содержит только уникальные объекты) узлов. Эта коллекция будет использоваться для определения того, какие плитки имеют поврежденные соединения, которые необходимо устранить.

Заполните структуры данных, чтобы представить плату с доступными деталями, используя те, которые вы видите наиболее подходящими, исходя из ваших личных критериев без учета правильности решения. Это почти наверняка приведет вас к недействительному состоянию, но пока все в порядке. Итерируйте через доску и найдите все плитки, у которых есть соединения, ведущие в никуда. Добавьте их в набор сломанных плит.

Теперь итерации через множество. Измените плитки, которые он ссылается на , уменьшив их количество соединений (иначе вы могли бы попасть в бесконечный цикл), чтобы у них не было сломанного соединения, учитывая имеющиеся в данный момент фрагменты. Проверьте их соседей снова, и если вы сломали соединения с другими плитами, добавьте их в набор сломанных тоже.

Как только набор сломанных соединений будет пустым, у вас должен быть прекрасный вид. Обратите внимание, однако, что он имеет важное предостережение: он может склоняться к упрощению шаблонов, поскольку фаза «фиксации» всегда будет пытаться уменьшить количество соединений. Возможно, вам повезет, что вы получите интересные шаблоны, поскольку на это может повлиять первая часть, которую вы надели на каждый плитку.