Продолжаю писать о разработке онлайн-версии игры Color Lines 2025. Предыдущая часть:
На прокси-сервере осталось реализовать механизмы поиска кратчайшего пути и непрерывных линий.
Кратчайший путь
Алгоритм подробно описан здесь:
Образно говоря, делаем стартовую клетку "мокрой", далее вокруг каждой "мокрой" клетки помечаем новые "мокрые" клетки, и так до тех пор, пока всё игровое поле не "намокнет". Если финишная клетка тоже "намокла", значит, "вода дырочку нашла" и между двумя клетками есть путь.
Сделаем класс компонента PathFinder:
Для конструктора нужны ширина и высота поля. Кроме того, он хранит атрибуты начальной и конечной клеток srcPos и dstPos, а атрибут pos отвечает за текущую позицию в пути, когда мы по нему движемся.
Я немного модифицировал алгоритм из вышеуказанной статьи. Он прекращает работу, когда дойдёт до конечной клетки, а большего ему и не надо. В качестве максимального значения клетки используется 255.
Функция checkTile(), проверяющая соседнюю клетку:
Серверу не требуется находить кратчайший путь, ему достаточно только его наличия. Но это требуется клиенту, чтобы визуализировать перемещение шарика.
Алгоритм работает таким образом, что в каждой клетке сохраняется расстояние до "источника". Поэтому, находясь в какой-то точке пути, достаточно выбрать из её соседей ту, у которой расстояние меньше. Это приблизит нас к "источнику".
Но делать это надо задом наперёд. Если мы построили путь из точки А в точку Б, то двигаться по нему можно только из точки Б в точку А. Поэтому, чтобы двигаться из А в Б, путь надо построить из Б в А.
После заполнения поля компонент PathFinder присвоит атрибуту pos значение srcPos, это будет позиция начала пути. Далее мы можем пошагово двигаться по пути, вызывая функцию next(), которая будет сдвигать pos ближе к финальной точке:
И чтобы понимать, остались ли ещё шаги, нужна функция hasNext():
Поиск линий
Поиск линий должен удовлетворять следующим требованиям: горизонтальные, вертикальные и диагональные линии могут пересекаться друг с другом. Если один и тот же шарик находится одновременно в нескольких линиях, повторно его считать не надо.
Поэтому в компоненте для поиска линий LineScanner я добавляю ещё одно поле, равное по размерам игровому, где будут храниться пометки шариков.
Рассмотрим простой пример с обычным массивом, где нужно найти последовательность одинаковых элементов. Мы берём первый элемент массива и делаем его текущим. Далее перебираем следующие элементы, и если они равны текущему, увеличиваем счётчик. Если встречаем другой элемент, то просто заканчиваем поиск.
Здесь pos это позиция, с которой начинать поиск, step это изменение позиции (так как мы можем двигаться не только по одному элементу вправо, но и вверх и вниз и по диагонали), maxLength это сколько вообще осталось элементов.
Теперь, имея этот примитив, мы можем считать последовательности в нужном направлении до конца строки:
Найдя последовательность, проверяем, чтобы она не состояла из пустых клеток, и чтобы её длина была не меньше requiredCnt. Если таковая нашлась, то ставим пометки в marks. Далее увеличиваем стартовую позицию поиска pos на длину найденной последовательности, уменьшаем оставшуюся длину строки maxLength также на длину последовательности, и ищем следующую последовательность.
Далее, имея инструмент поиска всех подпоследовательностей, перебираем строки в определённом направлении. Вот поиск по строкам в направлении слева направо:
Здесь мы движемся по координате y, перебирая горизонтальные строки от верхней до нижней.
Аналогично перебираем вертикальные строки (столбцы):
Диагонали перебираются чуть сложнее. Перебор состоит из двух частей: по координате y и по координате x. Для наглядности нарисую cхему:
Кроме того, у каждой диагонали своя длина. И также видно, что начинать поиск с самых первых клеток, а также заканчивать ими бессмысленно, так как заведомо не будет набрана необходимая длина.
Осталось объединить все поиски вместе:
Добавим в сервер компоненты поиска:
Обработка хода на сервере
В предыдущей части у сервера уже был сделан метод init(), который возвращал объект класса InitResponse с начальными данными игры. Теперь можно сделать обработку хода методом moveBallAsync():
Метод асинхронный, но об этом позже. Итак, сервер получает ход игрока: начальная и конечная позиция. Он использует pathFinder.findPath(), чтобы убедиться в валидности хода. Затем перемещает шарик в массиве tiles, и пытается удалить шарики методом removeBalls(). Если шарики не удалились, значит линии не собрались, и значит надо добавить на поле новые шарики. Сервер добавляет шарик на поле и в массив addedBalls, который будет передан в ответе.
После добавления шариков ещё раз вызывается removeBalls(), чтобы удалить те линии, которые могли получиться после добавления.
Если опять ничего не удалилось, и оставшихся пустых клеток больше нет (!this.emptyTilesCache.hasMore()), значит игра закончена, и признак canContinuе устанавливается в false.
Это практически вся логика сервера, которая требуется.
Теперь почему метод moveBallAsync() асинхронный. Клиент после совершения хода игроком должен отрисовать анимацию хода. Если он отрисует анимацию, а затем пошлёт запрос на сервер, или сначала пошлёт запрос, а потом отрисует анимацию, отклик сервера может быть не мгновенным, и тогда игрок после хода заметит некоторую задержку. Поэтому клиент будет отправлять запрос на сервер сразу же после совершения хода, но не ждать ответ, а рисовать анимацию. За ответом он обратится после отрисовки анимации, и есть шанс, что он уже будет получен.
В связи с этом сервер не делает return new MoveResponse(...), а просто сохраняет его у себя в атрибуте asyncResponse:
А клиент затем обратится к методу getAsyncResponse():
Обращу внимание, что на данный момент это всего лишь эмуляция, так как ответ сервера всегда готов мгновенно. Этот механизм понадобится в дальнейшем, когда сервер станет по-настоящему удалённым.
Также надо отметить, что сервер возвращает объект класса MoveResponse,
в котором возвращается текущее игровое поле (атрибут tiles). Это поле сервер возвращает в виде копии массива Array.from(tiles):
Если этого не сделать, то вместо копии будет передан указатель непосредственно на массив tiles сервера, который получит клиент и сможет в него вмешаться. Это опять же лишь потому, что сейчас клиент и сервер тесно связаны и фактически являются одной и той же программой с доступом к одним и тем же данным. И конечно, у меня нет цели написать зловредный клиент, который будет что-то портить на сервере, но передача копии может помочь избежать ошибок и странных глюков.
Сервер уже готов к работе, и в следующей части приступим к реализации клиента.
Читайте дальше: