Как вы знаете, разработчики игр делятся на два типа: те, кто делает ААА, и те, кто делает крайне простые матч-3. Здесь я расскажу в хронологической последовательности, как оптимизировал самый простой в мире жанр. Постараюсь далее уменьшить количество иронии. Заинтересованных приглашаю ознакомиться с моим путем
Предыстория
На предыдущей работе мы разрабатывали матч-3 баттлер на unity (empires and puzzles в референсах), мне поставили задачу сделать для него движок. Так как каждый матч должен был проверяться на сервере, у меня в требованиях были детерминизм и 5 миллисекунд на симуляцию матча. К сожалению, компания не пережила потерю инвестора, а я перед закрытием спросил разрешения показать код и рассказать о своей работе, чтобы мой труд не канул в лету
Игровой цикл
Игра происходит следующим образом:
Игрок может передвинуть фишку, если после этого образовался ряд из 3 и более фишек (в дальнейшем - мэтч), они начинают лететь вверх по полю, задевая первого попавшегося на пути врага, если он есть. В этот момент игровое поле досыпает новых фишек, которые тоже могут образовать мэтч и полетать наверх. Это происходит до тех пор, пока новые фишки перестанут образовывать мэтч.
У игрока есть герои с маной. При ее заполнении они могут использовать умения перед перетаскиванием фишек.
Далее у врагов обновляется счетчик хода, и, если наступает их очередь, они атакуют героев игрока. После этого все повторяется.
Так как я не геймдизайнер, навыка описывать механики у меня нет, но, надеюсь, общий смысл я передал.
Начало разработки
Я несколько дней проводил RnD имеющихся в открытом доступе работ по матч-3, там попадались даже весьма приятные варианты на async, но, увы, все они мало подходили для симуляции на сервере, потому что делались для unity, а уж о серьезной оптимизации никто и не думал. Я бы тоже не думал, если бы речь шла только о клиенте.
Первым делом я решил начать с проблемы создания поля и проверки возможности хода, так как глупо будет создать поле без ходов, а также поле с готовой комбинацией. Для этого я завел перечисление с направлениями и клетки, в которых был словарь с ключом — перечислением, и значением — соседней клеткой, а еще приступил к генерации этих клеток и проверке существования возможных ходов. Насмотревшись лекций от MY.GAMES про матч-3 на графах, я решил сделать что-то похожее.
Увы, у меня не осталось точного кода моих первых тестов, поэтому я просто нарисую, что происходило при проверке. Здесь я вообще собираюсь много рисовать.
Если был найден хотя бы один мэтч — возвращается true, в противном случае совершаются те же действия в остальные стороны, потом этот же процесс повторяется со всеми клетками пока не будет найден мэтч или не кончатся непроверенные клетки.
Здесь я совершил ужасную ошибку — взял вместо бенчмарка Stopwatch, решив, что он сможет с достаточной точностью показать результат. Результат вышел около 0.6 миллисекунд, что крайне много. Здесь, вероятно, ошибка в самом Stopwatch, а бенчмарк показал бы результат куда лучше, но в тот момент я не пользовался им. Еще можно сразу заметить, что такая проверка и словарь в каждой клетке — не самое быстрое решение, а еще в таком варианте много аллокаций.
Первые оптимизации
Я начал с того, что выкинул словарик, оставив только перечисление для определения соседей, и положил все это в двумерный массив, по которому уже совершались проверки. Стало быстрее. Примерно в этот момент я выкинул Stopwatch, заменив его на BenchmarkDotNet, потому что начал подозревать, что результат Stopwatch на маленьких значениях далек от точности. Результат оказался около 8 микросекунд, что уже радовало, но возникли идеи, как сделать еще быстрее.
Сначала я развернул двумерный массив в одномерный. Это сильно прибавило скорости. Потом мне захотелось вообще обойтись без массива, расположив весь список клеток на стэке. Для этого я взял Span и попробовал создавать stackalloc массив. Тогда же я выяснил, что для stackalloc нужен фиксированный размер объектов, поэтому string Id у клеток уже не подходит, пришлось заменить его на int (можно было бы и на byte, учитывая, что цветов в исходной игре всего пять).
Потом заменил метод определения существования ходов с движения клетки в стороны на движение соседа в позицию клетки.
Таким образом получилось ускорить создание и проверку наличия ходов до 1 микросекунды.
Ход игрока, мэтч после него и передача данных дальше
С ходом игрока все довольно тривиально — временно меняются местами 2 клетки, каждая проверяется в 3 направлениях, исключая направления, обратные направлению смены клеток. Если есть мэтч, то клетки меняются местами уже на «постоянку», а все клетки, задействованные в мэтче, как-то помечаются. На этот случай хотелось иметь какие-то фиксированные по размеру данные, в которых будет помечаться результат. Добавлять эту информацию в клетку мне показалось неудобным. Для этого я взял массив байтов. Можно было бы просто взять массив (span), равный по размеру массиву клеток, но мне хотелось сделать поинтереснее. Поэтому для своего поля 7 на 5 я взял массив размером 7, где каждый байт являтся вертикальной линией на поле. И в нем я уже отмечал нужные биты единичками.
Сдвиг и заполнение
Так как имелась готовая система для обозначения происходящего на поле, эти две функциональности были довольно тривиальные. На места единичек сдвигались верхние клетки, а единички переносились наверх, чтобы на их местах потом появлялись новые.
После генерации клеток нужно было еще раз проверить наличие мэтча, а также пометить клетки, участвующие в мэтче. Чтобы не проверять все поле целиком, я решил проверять область, в которой происходило движение клеток, увеличенную на две клетки в каждую сторону.
Механики врагов
Враги стоят на трех горизонтальных линиях: ближняя, средняя, дальняя.
Враги могут занимать от двух до пяти клеток, при этом моделька врага может не занимать клетку целиком, а количество врагов варьируется от одного до пяти.
В одном матче может быть несколько волн врагов со своим расположением и размером.
Враг получает урон, если его задевают летящие вверх клетки, с которыми произошел мэтч.
Если на один ряд фишек попадает два врага, то урон делится между ними
У врагов есть цвет, как и у фишек. У цветов есть система множителей урона по принципу камень-ножницы-бумага.За один мэтч фишки могут атаковать врага только в одном ряду.
Враги атакуют игрока раз в n ходов.У некоторых врагов есть мана, которая наполняется при получении этим юнитом урона. Заполненная мана позволяет провести специальную атаку вне зависимости от счетчика ходов.
Игровое поле с врагами
От игрового поля для врагов я заранее предвидел много боли. Во-первых, врагов может быть разное количество, во-вторых, они могут быть разного размера, в-третьих, враг одного и того же размера (если судить по скриншотам) может получать урон как с двух линий фишек, так и с трех. При этом все еще хотелось обойтись без аллокаций. Меня, конечно, довольно сильно в этот момент запутал визуал, надо было сразу про него забыть.
Первое, что пришло в голову — увеличить поле по горизонтали в два раза относительно поля клеток (модельки врагов могут быть центром как на клетке, так и между клеток), а во враге хранить дельту в обе стороны. Идея, надо признаться, оказалась такой себе.
После этого я брал крайний левый ряд, который мог наносить урон врагу, и ширину врага. Благодаря этому получилось выкинуть положения между клеток, так как они оказались ненужными.
Чтобы не создавать каждый раз Span с нужным для конкретной волны количеством врагов (так как он лежит на стэке, я не мог просто перезаписать старый с новым размером, а клал бы новый обязательно поверх), я сразу взял максимальное их количество — пять. От этого появилась проблема — мне надо было знать, какие враги существуют и где они стоят.
Для решения проблемы я опять взял массив байтов. На этот раз я взял три байта, а в каждом байте отмечал биты, равные индексу врагов в Span. Надеюсь, картинка объяснит это лучше.
После этого можно было как наносить урон единичным врагам, так и проверять, нет ли двух врагов на одной линии. Так как генерация юнитов всегда происходит слева направо, то для проверки коллизий надо было взять следующий ненулевой бит в ряду (если он есть). Если стартовая позиция этого юнита совпадает с крайней правой клеткой текущего, то урон между ними делится.
В завершение
Я плохо помню промежуточные цифры бенчмарков, но в финальной версии симуляция 1000 ходов занимала около 0.7 миллисекунд на моем не самом быстром ноутбуке. Результат довольно сильно обгоняет требования. При добавлении механик результат, конечно, будет похуже, но запас все равно остается довольно большим.
Баффы/дебаффы писал коллега, а так как в этот момент разработки мы потеряли издателя, полноценно внедрить их я не успел. Но идеи на этот счет у меня остались. Поскольку баффы и дебаффы являлись классами (коллега не хотел продолжать мое безумие), я предложил просто создать пулл этих эффектов, чтобы можно было хотя бы не дергать GC и не создавать их каждый раз, когда возникнет необходимость. Еще я обошел стороной генерацию специальных фишек и формулы расчета урона врагов/по врагам, но часть из этого функционала можно посмотреть на гите.
Так как я получил разрешение показывать только свою работу, а не всей команды, в гит не будет включена версия из unity, которой я занимался в конце и в которой были исправлены многие баги, существующие в выложенной версии (под конец я перестал переносить актуальные изменения в консольный вариант). А также не будет включена часть со скиллами. Еще я хочу попросить прощения у тех, кто полезет в гит, за свой нейминг и довольно большие методы, нуждающиеся в рефакторинге.