Добавляем размещение ключей в roguelike на JavaScript

В большинстве видеоигр любой уровень должен позволять игроку достичь цели. Хотя это может показаться очевидным, это легче сказать, чем сделать в roguelike, где уровни генерируются процедурно. Хотя сделать каждый уровень разрешимым никогда не было проблемой на ранних стадиях создания Rogue of Rhonda, это стало проблемой после добавления дверей и ключей. В этой статье обсуждается серия тестов и усовершенствований, которые в конечном итоге привели к текущему алгоритму размещения ключей.

Получение ориентировки

Приведем краткий скриншот текущей игры.

В данном примере каждый уровень в этой игре генерируется процедурно и состоит из следующего:

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

Ключи в игре называются «маленькими ключами», потому что любой ключ может отпереть любую дверь, и каждый ключ может быть использован только один раз. Ниже приведен краткий ролик, в котором игрок использует два ключа для отпирания дверей.

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

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

Генератор карт

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

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

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

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

Модульные тесты

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

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

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

Испытание с двумя комнатами

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

Размещение ключа операцией заполнение потоком

Чтобы разместить этот ключ, начнем с простого алгоритма, обычно известного как заливка потоком. Эта операция заполнения потоком является рекурсивной, поскольку она включает функцию, которая вызывает саму себя. Ниже рассмотрим, как это работает:

1. Начните с позиции игрока.
2. Выберите плитки прямо сверху, снизу, слева и справа.
   
3. Осмотрите каждую плитку. Если данная плитка является напольной плиткой, добавьте ее координаты в наш список возможных плиток, где может быть размещен ключ. Если нет, остановитесь.
   
4. Для каждой найденной плитки пола повторите шаг 2, используя координаты плитки пола в качестве отправной точки.
   

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

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

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

Сортировка дверей по положению

Вот так будет скорректирована логика, чтобы пройти вышеуказанный тест.

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

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

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

Работа за пределами

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

1. Используйте позицию игрока в качестве отправной точки.
2. Запустите заливку, в которой вы соберете (1) список всех доступных плиток пола и (2) список всех доступных запертых дверей в этой области.
   
3. Для каждой найденной запертой двери проверьте, был ли к ней прикреплен ключ.
   
4. Если для двери нужен ключ, выберите доступную плитку пола из списка для размещения ключа.
   
5. Установите для переменной hasKey этой двери значение true.
   
6. Установите отправную точку по другую сторону этой двери.
   
7. Повторите процесс, ища доступные плитки и близлежащие двери.
   
8. Продолжайте до тех пор, пока для каждой двери не будет установлен ключ.
   

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

Уточнения

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

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

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

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

Следующие шаги

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

• Отдайте ключ вражескому или неигровому персонажу (NPC) в этой комнате. В любом случае, игроку придется немного больше потрудиться, чтобы получить его.
• Спрячьте ключ в контейнер, например, в сундук или горшок.
  
• Сделайте так, чтобы ключ появлялся, когда все враги в комнате будут побеждены или когда головоломка в комнате будет решена.
  
• Ограничьте количество ключей в данном подземелье, чтобы их можно было последовательно распределять от уровня к уровню.
  

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