Генерация тайловой карты

Попробуем сгенерировать тайловую карту для стратегии, на примере известной игры Warcraft II.

Для этого возьмем готовый тайлсет из игры (можно скачать отсюда https://www.spriters-resource.com/ms_dos/warcraftii/asset/29501/)

Тайлсет выглядит следующим образом:

Размер тайлов 32х32 пикселя, между каждым тайлом есть зазор в 1 пиксель. 

Давайте нарежем тайлы и попробуем сгенерировать карту случайным образом посмотрим что получится

Как вы можете видеть полученная карта не пригодна для игры. Тайлы не могу быть сгенерированы случайным образом, потому что есть определенные правила сочетания тайлов друг с другом. Каждый тайл может быть располежен только с определенными тайлами рядом. Для того чтобф научиться генерировать красивые карты нужно извлечь правила по которым тайлы могут быть расположены рядом друг с другом (как это можно сделать читай подробнее здесь). Возьмем готовые правила в виде файла xml отсюда

Если открыть файл правил тестовым редактором, то можно увидеть следующую стркутуру файла

Набор правил в тегах rule содержит индекс тайла tileIdx, а также два вложенных эелемента right и down, которые в свою очередь содержат список индексов тайлов через разделитель (точка с запятой в данной случае). Right описывает индексы тайлов которые могут быть расположены справа от тайла с индексом tileIdx, а down - для тех которые могут быть расположены снизу. 

Данных правил будет достаточно для генерации карты сверху вниз справо налево. 

Добавляем правила

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

В каждом состоянии будет сохранять карту целиком, а также индекс где мы сейчас находимся. На каждом шаге коэффициент ветвления будет зависит от набор разрешеннных для расположения тайлов. Чтобы понять какие тайлы можно расположитб в текущую ячейку карты будем брать соседний тайл сверху и слева и смотреть в правилах какие тайлы они позволяет распологать рядом с собой. Найдя пересечение этих двух множеств получим допустим индексы тайлов для расположения на данном шаге поиска в глубину. Если допустимых тайлов нет, значит мы попали в тупик генерации карты и нужно откатиться назад. Также для рандомизации сделаем перемешку (shuffle) тайлов доступных для размещения на каждом шаге. Опишем сказанное в коде.

Сгенерируем карту и посмотрим что получилось теперь

Как вы видите карта стала выглядет красиво и правильно. Стандартные размеры карт 32х32, 48х48, 96х96. 

Попробуем запусть программу и загрузим туда правила (нажмем O на клавиатуре и укажем путь до файла правил rules.xml, после этого будем нажимать кнопку перегенерации карты R)

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

Полный код примера смотри здесь

Как вы видите карта может не влазить целиком на экран, в следующем уроке мы рассмотрим как сделать скроллинг карты.