Match-3. Match-3. Создание стартового поля без матчей.

Это первая из статей об алгоритмах match-3 игр.

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

Проблема

Если вы разрабатывали или разрабатываете match-3 игру, то наверняка столкнулись с проблемой исключения готовых матчей на стартовом поле, до того как игрок совершит первое действие.

Основной проблемой является то, что поле генерируется на основе значений генератора случайного числа (как базового так и псевдо-генератора с использованием зерна(seed)). Следовательно у вас нет абсолютно никакой гарантии, что на поле не образуются комбинации 3+ в ряд.

Псевдо-генератор случайных чисел

Хоть это и не принципиально для данной статьи, но я хотел бы уточнить один момент. Я использую для генерации поля псевдо-генератор случайных чисел с начальным зерном, так как его использование позволяет повторить весь алгоритм генерации, и получить то же самое состояние поля, что было у конкретного игрока.

Такой подход помогает в тестировании и отладке, и позволяет получить более предсказуемые результаты, по сравнению с использованием Math.random().

Оба предложенных решения базируются на возможности повторить достигнутый результат.

Решение

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

Вариант №1. Тестирование во время генерации

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

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

Пример проверки образования комбинации 3 в ряд по соседним элементам во время генерации.

Пример проверки образования комбинации 3 в ряд по соседним элементам во время генерации.

Стоить учесть: нет необходимости проверять элементы слева, если элемент находится в первых двух колонках, и сверху, если в первых двух строках.

Алгоритм:

Алгоритм достаточно простой и позволяет всегда(!) получить одинаковый результат с одним и тем же зерном псевдо-генератора.

Вариант №2. Перестановка элементов

Второй алгоритм сложнее в реализации и более ресурсоёмкий, но также имеет право на жизнь. Он заключается в перестановке элементов на поле, таким образом, чтобы “разбить” уже имеющиеся матчи.

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

Алгоритм:
После генерации поля, мы определяем матчи на поле и разбиваем их.

Представим что поиск матчей возвращает нам массивы с позициями элементов соединённых в один матч.

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

Все матчи разбиваются на мелкие матчи по три элемента, и из этих трёх выбирается начиная с первого элемент, который может быть переставлен с любым из соседних элементов, имеющим иной цвет.

Пример: матч из 4-х элементов будет разбит на два: 3 элемента в первом и 1 во втором. В каждом из этих матчей будет проводиться проверка начиная с первого элемента, на возможность перестановки его с соседями. Если такой элемент будет найден, то последующие элементы не проверяются и происходит перестановка.

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

В следующей статье я расскажу о поиске матчей, их приоритетах, и объединении пересекающихся матчей.


Comments are closed.