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

фон

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

игровой цикл

Игра проходит так:

  • Игрок может перемещать жетон, если после этого образовался ряд из 3-х и более жетонов (далее – спичка), он начинает летать по полю, поражая первого попавшегося на пути противника, если он есть один. В это время игровое поле заполняется новыми фишками, которые также могут формировать спичку и улетать. Это продолжается до тех пор, пока не останется фишек, образующих совпадение.

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

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

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

Ссылка

Начало разработки

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

В первую очередь я решил начать с проблемы создания поля и проверки возможности попадания, ибо глупо было бы создавать поле без попаданий, как и поле с готовой комбинацией. Для этого я начал перечисление с направлениями и ячейками, в которых был словарь с ключом — перечисление, а значением — соседняя ячейка, а также приступил к генерации этих ячеек и проверил наличие возможных перемещений. Посмотрев лекции MY.GAMES по графике match-3, я решил сделать что-то подобное.

ЧИТАТЬ   Как сэкономить деньги, если у вас их нет: 6 способов эффективно сэкономить

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

Ячейка перемещается в соседнюю ячейку

Ячейка перемещается в соседнюю ячейку

После этого управление происходит во всех направлениях, кроме направления, противоположного движению.

После этого управление происходит во всех направлениях, кроме направления, противоположного движению.

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

Здесь я совершил ужасную ошибку — вместо бенчмарка взял Секундомер, решив, что он может показать результат с достаточной точностью. Результат вышел около 0,6 миллисекунды, что очень долго. Вероятно, это баг самого Секундомера, и бенчмарк показал бы результат гораздо лучше, но на тот момент я им не пользовался. Также можно сразу заметить, что такая проверка и словарь в каждой ячейке — не самое быстрое решение, да и аллокаций в этой версии очень много.

Первые оптимизации

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

Сначала я расширил двумерный массив до одномерного. Это резко увеличило скорость. Потом захотелось вообще обойтись без массива, положив весь список ячеек на стек. Для этого я взял Span и попытался создать массив stackalloc. Заодно обнаружил, что stackalloc нужен фиксированный размер объектов, поэтому строка Id для ячеек уже не работает, пришлось поменять на int (это можно было бы сделать с байтом, так как цветов всего пять в оригинальной игре).

Затем он заменил метод определения наличия движений от движения клетки в сторону к движению соседки в положение клетки.

2ba7bf32eb8c3cb23e9eee4d09672052
b81e49a8cd41e0b18e6b298a5b0aecd2

Таким образом получилось ускорить создание и проверку на наличие движений до 1 микросекунды.

Ход игрока, матч после и передача данных дальше

В ход игрока все достаточно тривиально — временно меняются местами 2 клетки, каждая проверяется в 3-х направлениях, исключая направления, противоположные направлению смены ячейки. Если есть совпадение, ячейки меняются на «постоянные», и все ячейки, участвующие в совпадении, так или иначе помечаются. В этом случае я хотел иметь данные фиксированного размера, в которых будет отмечен результат. Добавлять эту информацию в ячейку мне показалось неудобным. Для этого я взял байтовый массив. Можно было бы просто взять массив (span), равный по размеру массиву ячеек, но хотелось сделать поинтереснее. Поэтому для своего поля 7 на 5 я взял массив размером 7, где каждый байт представляет собой вертикальную черту поперек поля. И нужные биты я там уже пометил единицами.

ЧИТАТЬ   Кто самый быстрый? iPhone 14 Pro Max против Vivo X80 (видео)
9776c53bd48347cb73a62b8514feca81

Сдвиг и заливка

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

9578139476fc2e719bfed4fe08885dc6

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

1fc1d10cd21a85a0b9cd3aa15a2c5307

Вражеская механика

  • Враги стоят в три горизонтальные линии: ближняя, средняя, ​​дальняя.

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

  • В матче может быть несколько волн врагов со своим местоположением и размером.

  • Противник получает урон, если его поразили летающие клетки, с которыми был заключен матч.

  • Если два врага падают на ряд жетонов, урон делится между ними.
    У врагов есть цвет, как и у жетонов. У цветов есть система множителя урона «камень-ножницы-бумага».

  • В матче жетоны могут атаковать только противника подряд.
    Враги атакуют игрока один раз каждые n ходов.

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

056c799e65bedd0ea931f880b3b85f5a
7409d84db8d4b0a4d7dde89d4f783210

Детская площадка с врагами

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

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

c2c2952fecba0d3c89d7ed27bff53c05

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

ЧИТАТЬ   ЛУЧШИЕ ИГРЫ ДЛЯ ANDROID! 15 лучших игр для Android и iOS 2022 года
09b0028a22d02afcc3d8ff65a3fef82d

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

Для решения проблемы я снова взял байтовый массив. В этот раз я взял три байта и в каждом байте пометил биты, равные индексу противника в Span. Я надеюсь, что картина объясняет это лучше.

26ecd17f5f0eac824bb960015022aaca

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

В заключение

Я плохо помню промежуточные результаты тестов, но в окончательной версии симуляция 1000 движений заняла на моем ноутбуке около 0,7 миллисекунды, что было не самым быстрым. Результат весьма далек от ожиданий. При добавлении механизмов результат будет, конечно, хуже, но запас все же довольно большой.

Баффы/дебаффы писал коллега, и так как на этом этапе разработки мы потеряли редактор, у меня не было времени их полностью реализовать. Но у меня есть некоторые идеи на этот счет. Так как баффы и дебафы были классами (сослуживец не хотел продолжать мое безумие), я предложил просто объединить эти эффекты, чтобы хотя бы не тянуть ГК и создавать их всякий раз, когда возникнет необходимость. Я также обошел специальные формулы генерации чипов и формулы расчета урона врага/на враге, но некоторые из этих функций можно увидеть в гите.

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

Коттедж

Source

От admin