Как реализовать в браузере игру, на которой годы назад залипал без всякого браузера? С какими сложностями столкнёшься в процессе, и как их можно решить? И, наконец, зачем вообще это делать?

В декабре на конференции HolyJS Александр Коротаев (Tinkoff.ru) рассказал, как он сделал браузерную версию «Героев». Ранее уже появилась видеозапись доклада, а теперь для Хабра мы сделали ещё и текстовую версию. Кому удобнее видео — запускайте ролик, а кому текст — читайте его под катом:


Я хотел бы рассказать вам о том, как делал в браузере тех самых третьих «Героев», в которых многие из вас, я думаю, играли в детстве.

Перед тем, как браться за любое интересное длинное путешествие, следует посмотреть маршрут. Я зашел на GitHub и увидел, что каждые два месяца появляется новый клон Героев. Это репозитории с двумя-тремя коммитами, где добавляется буквально несколько функций, и человек бросает, потому что это сложно делать. Он понимает весь груз ответственности, который на него ляжет, если это доделывать. Здесь я представил ссылки на самые успешные репозитории, которые можно найти:

1. sfia-andreidaniel/heroes3
2. mwardrop/HOMM3Clone
3. potmdehex/homm3tools
4. openhomm/openhomm
5. vcmi/vcmi

Последний из них я особо выделил, чтобы отметить его значимость для сообщества, потому что это единственный полностью написанный клон «Героев» на языке C, использующий дистрибутив оригинальных ресурсов, которые можно к нему подложить. И это единственный способ запустить третьих «Героев» на Android-устройствах. Они запускаются через эмулятор, проблема в том, что они сильно тормозят, тач-интерфейс там недоступен, приходится двигать мышку — в общем, это только для очень больших фанатов.

Какие цели я ставил для себя, когда брался за это?

• Я очень хотел сделать нечто, мне хотелось прыгнуть выше своей головы. Естественно, мне хотелось показать себя. Вообще, изначально это планировалось как собственный сайт.
• Еще я хотел перестать играть в игры вообще, и в «Героев» в частности. Как известно, лучшая защита — это нападение. Вы начинаете разрабатывать игры, начинаете играть в них по-другому и сильно меньше.
• А еще я хотел сделать что-то очень красиво, потому что всегда стремился к красоте интерфейсов, а игрушка сама по себе очень красивая.

Сперва я пытался повторить оригинальную картинку:



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

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

Для начала, для тех, кто не в курсе про gamedev в JavaScript, я расскажу, из чего состоит обычная игра:

• Модель данных. То есть, это какая-нибудь карта, персонажи, сцена, попросту то, где у нас хранятся объекты.
• Игровой цикл или game loop, который обсчитывает каждую секунду, делая какие-то действия с объектами и изменяя модель.
• Еще есть обработка пользовательского ввода. Это реакции на ввод с клавиатуры, джойстика, мышки, чего угодно.
• И, самая красивая часть — рендер, который должен отрисовывать модель. По факту, модель изменяется, а отрисовка работает независимо.

Если представить это в виде кода, тут все просто:

01. const me = {name: 'Alex', left: 0}
02. ...
03. setInterval(() => update(), 1000)
04. ...
05. window.addEventListener('keyup', () => me.left++)
06. ...
07. requestAnimationFrame(() => draw())

Что за этим скрывается:

• Строка 01: модель. Она банально что-то хранит.
• Строка 03: игровой цикл. Это setInterval, который вызывает функцию update().
• Строка 05: обработка ввода. Обычный EventListener на события пользователя, который, например, сдвигает персонажа вправо.
• Строка 07: отрисовка. Это requestAnimationFrame, который позволяет нам вызывать callback, стремясь к 60 кадрам в секунду. Когда браузер скрыт, он не вызывается, в противном случае он рисуется вместе с окном браузера, очень удобно.

Подробнее про геймдев на JS вы можете почитать в книге «Сюрреализм на JavaScript», откройте ее хотя бы ради таких замечательных картинок:

---

Краткая история разработки игры

Если вы хотите начать делать своих «Героев», у вас есть:

1. Оригинальная игра
2. Редактор карт. Разработчики сначала думали, что он позволит игре прожить ещё максимум два года, как же сильно они ошибались!
3. FizMig — большой справочник по всем игровым механикам. Примечательность его в том, что люди эмпирически вычислили все вероятности выпадения навыков, заклинаний, любого урона, и представили это в формулах и таблицах с процентным соотношением. Люди вели работу на протяжении десяти лет, то есть это очень большие фанатики, даже я не могу с ними сравниться.
4. Много форумов с ребятами, которые много лет копались в «Героях». Кстати, форумы русскоязычные: англоязычные ребята почти не копались.
5. Распаковщик ресурсов, благодаря которому вы можете получить картинки, данные, что угодно.

Начинал я с рендеринга обычного зеленого поля, как на первой картинке:



Тут можно увидеть, как я нарисовал на зеленом поле объекты и дебажил их важные точки. Красные точки — это непроходимость, желтые — какое-то действие в этой точке. У замка action только там, где можно зайти, у героя же — на всей модели.

Далее я работал с данными. Данные — это списки всех навыков, монстров, персонажи, карты, всё, что касается текстовых и бинарных файлов, которые нужно было прочитать и как-то аккумулировать.



Затем я работал с алгоритмами. Алгоритмы получались у меня не сразу. Здесь я пытался сделать алгоритм поиска пути:



Но не все работало гладко, это, пожалуй, один из лучших его прогонов.

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

---

Парсинг карт

В начале был очень важный этап, он был относительно скучный, сложный, и это — парсинг карт. Дело в том, что если бы не было его, не было бы ничего. Так как мне было неинтересно рисовать просто поле с объектами, которые я накладывал друг на друга при помощи какого-то оффсета, я захотел прочитать оригинальные карты, чтобы иметь удобный редактор, при помощи которого можно сразу смотреть изменения в игре:



Когда вы открываете карту в этом редакторе, вы видите отличный визуальный интерфейс для редактирования любых построек, объектов, и так далее. Это удобно, понятно и интуитивно. Сделано уже много тысяч или десятков тысяч карт для «Героев», они до сих пор есть в очень большом количестве.

Но если вы захотите прочитать ее как разработчик, вы увидите, что это просто бинарный код, который сложно читать:



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

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



Для карт уже написаны шаблоны, которые позволяют парсить их в редакторе 010 Editor. В нем они открываются как в браузере. Вы видите что-то похожее на dev-tools, можете наводить курсор на какую-то секцию кода, и будет показываться, что там внутри находится. Это куда удобнее того, с чем я пытался работать раньше.

Допустим, скрипты есть, осталось написать код. В начале я пытался делать это на PHP, потому что я не знал другого языка, который мог бы с этим справиться, но со временем я наткнулся на homm3tools. Это набор библиотек для работы с разными данными «Героев». В основном это парсер разных форматов карт, генератор карт, рендер надписей из деревьев, и даже игра «Змейка» из игровых объектов. Когда я увидел эту поделку, я понял, что при помощи homm3tools можно делать что угодно, и фанатизм этого человека меня зажег. Я начал с ним общаться, и он убедил меня, что я должен выучить C и написать свой конвертер, что я, в общем, и сделал:



Фактически, мой конвертер позволяет взять обычный файл карт для «Героев» и превратить его в удобочитаемый JSON. Удобочитаемый как для JavaScript, так и для человека. То есть я могу посмотреть, что в этой карте есть, какие там есть данные и быстро понять, как с этим работать.

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

---

Все тормозит!

Что мне с этим делать? Я никогда с этим не сталкивался, и сначала пошел смотреть на отрисовку карт. Карта же большая, наверное, тормозит она.

Но для начала немного теории. Так как все рисуется на Canvas, я хотел бы объяснить, чем он отличается от DOM. В DOM вы просто берете элемент, можете передвинуть его, и не задумываетесь, как он рисуется, просто двигаете, и все. Чтобы передвинуть и нарисовать что-то на Canvas, вам нужно каждый раз его стирать:

01. const ctx = canvas.getContext('2d') 
02. 
03. ctx.drawImage(hero, 0, 0) 
04. ctx.clearRect(0, 0, 100, 100) 
05. ctx.drawImage(hero, 100, 0) 
06. ctx.clearRect(0, 0, 100, 100) 
07. ctx.drawImage(hero, 200, 0)

Если под героем, которого вы анимируете таким образом, находится трава, вам приходится рисовать траву:

01. const ctx = canvas.getContext('2d') 
02. 
03. ctx.drawImage(hero, 0, 0) 
04. ctx.drawImage(grass, 0, 0) 
05. ctx.drawImage(hero, 100, 0) 
06. ctx.drawImage(grass, 100, 0) 
07. ctx.drawImage(hero, 200, 0)

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

Поэтому я предлагаю рисовать слоями:



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

Я просто использую три Canvas, которые наложены друг на друга:

<canvas id=”terrain”>
<canvas id=”objects”>
<canvas id=”ui”>

Их названия говорят сами за себя. Terrain — трава, дороги и реки.

Если посмотреть на алгоритм рисования terrain, он может показаться довольно нагруженным с точки зрения ресурсов:

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

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

Как плавно передвигать карту? У меня были проблемы и с этим, но я наткнулся на решение от Яндекс.Карт:



Дело в том, что при перемещении карты, у нее меняется трансформация. Эта операция, как многие знают, выполняется только на видеокарте, без вызывания Repaint. Довольно дешевая операция для перемещения довольно большой картинки. Но каждые 32 пикселя я компенсирую left этой карты обратно, по факту я ее просто перерисовываю, но у пользователя создается впечатление непрерывного движения карты. Чего я и хотел добиться, так реализовали в Яндекс.Картах, и так реализовал я.

Дальше я занялся отрисовкой объектов, потому что оптимизации одной карты мне не хватило. Но для начала, немного теории. Дело в том что ось рисования объектов в «Героях» инвертирована. По факту, объекты рисуются с правого нижнего угла. Зачем это сделано? Дело в том, что на карту мы смотрим как бы сверху, но чтобы создать у игрока впечатление, что он смотрит в три четверти сбоку, объекты рисуются снизу вверх, перекрывая друг друга.



Алгоритм рисования объектов:

1. Сортируем массив по Y нижней границы каждого объекта (текстуры разной высоты, нужно это учитывать)
2. Фильтруем те, которые не попадают в окно (рисовать то, что не видит человек, дороговато)
3. Проводится масса различных проверок
4. Рисуем текстуру объекта
5. При необходимости рисуем флаг игрока
   И это все при том, что количество объектов может достигать over 9000! Что делать, как рисовать это в рантайме? Я думаю, что лучше не рисовать это в рантайме, и сейчас расскажу, как.
   
   
   
   Для начала, я нашел такой алгоритм рисования, как renderTree. Он используется, например, в браузере чтобы отрисовать DOM-элементы, которые висят друг над другом с Z-индексом. И каждая ветвь, которая есть в этом дереве — это ось Y, по которой объекты отсортированы. В свою очередь, на каждой ветви все объекты отсортированы по оси X.
   
   Что мы с этого получаем? Мы получаем более дешевую итерацию, потому что мы сразу можем отсекать ветви, не попадающие на экран. А при каждой итерации на ветви, мы будем смотреть на X объекта, и как только мы натолкнемся на объект, который точно не поместится в карту, перестаем итерироваться по этому объекту. Таким образом затрагивается меньше объектов, чем если бы мы просто пробегались по массиву. Также нам сразу дается корректное перекрытие объектов, потому что они уже отсортированы. Таким образом получается грамотное хранение данных.
   
   Далее я пошел в функцию рисования:
   
   

   01. const object = getObject(id)
   02. const {x, y} = getAnimationFrame(object)
   03. const offsetleft = getMapLeft()
   04. const offsetTop = getMapTop()
   05. 
   06. context.drawImage(object.texture, x - offsetleft, …
   

   
   Видим, что каждая функция состоит из того, что я определяю конечное смещение объекта, его фрейм для анимации, и, самое главное — функция drawImage. Все сводилось к этой функции, и нужно было как-то это оптимизировать.
   
   Я понял, что я просто могу создать эту функцию через bind с нужными параметрами и сохранить прямо в renderTree. То есть я перестал хранить там объекты, и стал хранить только функции рисования. Больше там не нужно ничего, поэтому я получил отличный прирост производительности.
   
   
   
   Но дело не только в объектах, дело еще в том, что игра не должна тормозить с точки зрения анимации. Коняшка должна бегать по экрану идеально, иначе у вас создастся впечатление, что с игрой что-то не так.
   
   Давайте немножко окунемся в геометрию, чтобы понять, через что пришлось пройти. Там, когда вы прокладываете отрезок на определенное расстояние в любую сторону — хоть по горизонтали, хоть по диагонали — они равны.
   
   
   
   Но это геометрия. А у нас «героеметрия». Там проблема в том, что это игра на сетке, где диагональное и горизонтальное перемещение по факту не равны, но игра считает, что это равно, и все нормально.
   
   
   
   Как с этим жить? Если посчитать, то для горизонтального движения мы делаем четыре шага анимации, для диагонального — примерно шесть. Я начал искать решение, как сделать эту анимацию действительно плавной.
   
   Проблема с JavaScript в том, что он однопоточный и оперирует задачами. Каждый setTimeout, который мы ставим, создает отдельную задачу, она конкурирует с другими задачами, которые у нас есть, например, с другими setTimeout. И в этом плане нас не спасет ничто.
   
   Я пытался делать через setTimeout, через setInterval, через requestAnimationFrame — все создает задачи, которые друг с другом конкурируют.
   
   
   
   И при большом количестве обсчетов при движении игрока, конкурирующие задачи портили мне всю анимацию.
   
   Я пошел искать дальше и нашел, что в JavaScript, оказывается, есть микрозадачи, которые являются частью задач. Они нужны в тех случаях, когда callback, который вы передаете, допустим, в Promise, единственный объект, который делает микрозадачу, может совершиться сразу, либо асинхронно. Поэтому, на всякий случай, реализовали микрозадачу, которая имеет приоритет выше, чем у задачи.
   
   
   
   По факту, мы получаем неблокирующий цикл, который можно использовать для анимации. Подробнее об этом можно почитать в статье Джейка Арчибальда.
   
   Для начала я взял все и обернул в Promise:
   
   

   01. new Promise(resolve => {
   02. setTimeout(() => {
   03. // расчеты для анимации
   04. requestAnimationFrame(() => /* рисование */) 
   05. resolve()
   06. })
   07. })
   

   
   Мне все равно нужен был setTimeout, чтобы делать анимацию, но он был уже в Promise. Я делал расчеты для анимации и скармливал в функцию requestAnimationFrame то, что мне нужно было рисовать по итогу этих расчетов, чтобы расчеты не блокировали рисование, и оно шло тогда, когда это действительно нужно.
   
   Таким образом, я смог построить целую последовательность из шагов анимации:
   
   

   01. startAnimation()
   02. .then(step)
   03. .then(step)
   04. .then(step)
   05. .then(step)
   06. .then(doAction) 
   07. .then(endAnimation)
   

   
   Но я понял, что этот объект не очень сильно конфигурируем и не сильно отражает то, что я хочу. И я придумал хранить анимации в объекте, который назвал AsyncSequence:
   
   

   01. AsyncSequence([
   02.    startAnimation, [
   03.        step
   04.        step
   05.        ...],
   06.    doAction,
   07.    endAnimation
   08. ])
   

   
   По сути, это некий reduce, который проходится по Promise и вызывает их последовательно. Но он не так прост, как кажется, дело в том, что в нем есть еще и вложенные циклы анимации. То есть я мог после startAnimation засунуть массив из одних step. Допустим, их тут семь или восемь штук, сколько нужно максимально для диагональной анимации героя.
   
   Как только герой доходит до определенной точки, в этой анимации выходит reject, анимация прекращается, и AsyncSequence понимает, что нужно перейти на родительскую ветвь, а там уже вызывается doAction и endAnimation. Очень удобно делать сложную анимацию декларативно, как мне показалось.
   
   

   ---

   
   

   Хранение данных

   
   Но не только благодаря рендеру мы сможем увеличить нашу производительность. Оказалось, что больше всего тормозит хранение данных, что явилось для меня наибольшим сюрпризом в JavaScript.
   
   Для начала найдем данные, которые больше всего тормозят, а это карта. Вся карта — это сетка, она состоит из тайлов. Тайлы — это какие-то условные квадратики в сетке, которые имеют свою текстуру, свой набор данных, и позволяют нам строить карту из ограниченного количества текстур, как делали все старые игры.
   
   Этот набор данных содержит в себе:
   
   
   1. Тип тайла (вода, земля, дерево)
   2. Проходимость/стоимость перемещения по тайлу
   3. Наличие события
   4. Флаг «Кем занят»
   5. Другие поля, зависящие от реализации вашего движка
   
   В коде это можно представить в виде сетки:
   
   

   01.const map = [
   02. [{...}, {...}, {...}, {...}, {...}, {...}], 
   03. [{...}, {...}, {...}, {...}, {...}, {...}], 
   04. [{...}, {...}, {...}, {...}, {...}, {...}], 
   05. ...
   06. ]
   07.const tile = map[1][3]
   

   
   Такая же визуальная конструкция, как тайловая сетка. Массив массивов, в каждом массиве у нас объекты, которые содержат что-то для тайла. Получить конкретный тайл мы можем по смещению X и Y. Этот код работает, и он, вроде, норм.
   
   Но. У нас есть алгоритм поиска пути, который сам по себе довольно дорогой, ему приходится учитывать массу деталей, которые есть не только в тайлах, но и в объектах. А когда мы перемещаем мышку, курсор меняется в зависимости от того, можем ли мы дойти до этой точки, находится ли в этой точке противник или какое-то действие.
   
   
   
   Например, навели на дерево — появился обычный курсор, потому что на эту точку нельзя пройти. А еще нам нужно показывать количество дней, которое требуется чтобы дойти до точки. То есть по факту мы гоняем алгоритм поиска пути постоянно, и та самая сетка работает очень медленно.
   
   Чтобы получить свойство тайла, мне нужно было:
   
   
   1. Запросить массив тайлов
   2. Запросить массив массива для строки
   3. Запросить объект тайла
   4. Запросить свойство объекта
   
   Четыре вызова кучи, как оказалось — это очень медленно, когда нам нужно очень много раз запросить карту для алгоритма поиска пути.
   
   И что можно с этим сделать? Вначале я глянул данные:
   
   

   01. const tile = {
   02. // данные для отрисовки
   03. render: {...},
   04. // данные для поиска пути
   05. passability: {...},
   06. // данные которые нужны значительно реже
   07. otherStuff: {...},
   08. }
   

   
   Я увидел, что каждый объект тайла состоит из того, что нужно для рендера, из того, что нужно для алгоритма поиска пути, и других данных, которые нужны значительно реже. Они каждый раз вызывались, при том, что были не нужны. Надо было откинуть эти данные и придумать, каким образом их хранить.
   
   И я обнаружил, что быстрее всего читать эти данные из массива.
   
   
   
   Ведь объект тайла можно разделить на массивы. Конечно, если вы будете писать так бизнес-код на работе, к вам будут вопросы. Но мы говорим о производительности, и тут все средства хороши. Мы просто берем отдельный массив, где храним тип объекта в тайле, или что тайл пустой, а вместе с ним массив цифр для алгоритма поиска пути, который простое единицей/нулем «проходима клетка или нет».
   
   Но для алгоритма поиска пути нужно не просто узнать, есть объект или нет, и поставить единичку или нолик. Разные типы почвы имеют разную проходимость, разные герои по-разному ходят, все это нужно считать.
   
   
   
   Этот простой массив считается по сложным алгоритмам из двух больших массивов: с тайлами и с объектами. Таким образом, мы получаем уже посчитанные цифры, которые можно быстро использовать в алгоритме поиска пути. Считаем заранее, когда объект обновляется, обновляем и значения.
   
   В итоге у нас есть много массивов, которые что-то кэшируют и что-то связывают:
   
   
   • Массив функций отрисовки для цикла отрисовки
   • Массив чисел для поиска пути
   • Массив строк для ассоциации объектов к тайлам
   • Массив чисел для дополнительных свойств тайлов
   • Map объектов с их ID для игровой логики
   
   Остается только своевременное обновление данных из медленных хранилищ в более быстрые.
   
   Конечно, назрел вопрос, каким образом можно уйти от массива массивов, который работает куда медленнее обычного массива.
   
   По факту, я перешел к обычному массиву, просто развернув массив массивов, это работает на 50% быстрее:
   
   
   
   Получать смещение данных в массиве просто. Нам всего лишь надо знать Y, ширину этого квадрата, который мы храним в этом массиве, и X.
   
   Дальше — больше. Я смотрел и понимал, что при каждой итерации мне нужно из индекса в массиве высчитывать X и Y объекта. Каждую итерацию нужно было что-то делать, и, в зависимости от X и Y, принимать какое-то решение:
   
   

   01. const map = [{...}, {...}, {...}, {...}, ...] 
   02. 
   03. const tile = map[y * width + x] 
   04. map.forEach((value, index) => {
   05. const y = Math.floor(index / width)
   06. const x = index - (y * width)
   07. })
   

   
   Тут есть дорогие операции, такие как умножение, округление и деление. Пожалуй, самым дорогим здесь было деление, и я начал искать, что же с этим делать.
   
   Тут я познакомился с силой двойки:
   
   
   
   Я не зря назвал этот слайд «Power of 2», потому что это переводится одновременно как «сила двойки» и «степень двойки», то есть, сила двойки в ее степени. И если вы научитесь работать с битовыми сдвигами, которые я выделил желтым, то вы можете увеличить производительность.
   
   Проблема в том, что если это встретится в вашем бизнес-коде, вас, скорее всего, тоже будут ругать, потому что это непонятный код. А найти применение этой силе двойки можно только если вы сможете понять, каким образом с этими формулами работать.
   
   Хотя сдвиг влево, который равен умножению, не даст вам особого роста производительности, зато сдвиг вправо, который сравним с делением, дает довольно большой рост, а в сочетании с тем, что мы делим только на двойку, и числа у нас предсказуемые, без дробей, производительность увеличивается еще сильнее.
   
   Таким образом, я дошел до того, что мы можем посчитать ближайшую степень двойки большую, чем нам нужно, чтобы заранее сделать больший массив, но квадратный, со стороной-степенью двойки, который покрывает все наши нужды по хранению.
   
   

   01. const map = [{...}, {...}, {...}, {...}, ...] 
   02. const powerOfTwo = Math.ceil(Math.log2(width)) 
   03. 
   04. const tile = map[y << powerOfTwo + x] 
   05. map.forEach((value, index) => {
   06. const y = index >> powerOfTwo
   07. const x = index - (y << powerOfTwo)
   08. })
   

   
   Допустим, карта 50x50, мы находим ближайшую степень двойки больше 50 и используем ее для дальнейших расчетов (при получении X и Y, а также сдвига в массиве для получения тайла).
   
   Как ни странно, такие же оптимизации присутствуют в видеокарте:
   
   
   
   Видеокарта раскладывает каждую текстуру, для которой предусмотрен так называемый MIP-маппинг, на квадраты-степени двойки, которые рисуются в зависимости от удаленности объекта. Это дает нам очень дешевое сглаживание и очень быструю отрисовку, потому что все, что является степенью двойки, очень быстро считается процессорами.
   
   Так у меня получился Grid. Grid — это очень удобный для меня тип хранения данных, который позволяет итерироваться, получая сразу X и Y каждого объекта, и, наоборот, получать объект по X и Y.
   
   

   01. const grid = new Grid(32)
   02. 
   03. const tile = grid.get(x, y) 
   04. grid.forEach((value, x, y) => {})
   

   
   Проблема в том, что таким образом можно хранить только квадратные сетки, но я там храню и прямоугольные, просто потому что это быстро. И минус грида в том, что он неэффективен для сеток со стороной больше, чем 256: если это перемножить, становится понятно, насколько много в массиве данных. А такие массивы тормозят всегда и везде, и ничего для них не придумано. Но мне это не нужно, потому что нет карт больше 256x256, везде все довольно красиво.
   
   

   ---

   
   

   UI на Canvas

   
   Дальше я начал разрабатывать UI на Canvas. Я посмотрел разные игрушки, и, в основном, в игрушках UI делался на HTML. Он накладывался сверху, таким образом его было проще разрабатывать, проще делать адаптивным. Но я хотел упороться по полной и сделать рисование.
   
   Сначала я стала создавать обычные объекты, передавая в них какие-то данные, вешая на них eventListener. И это работало, пока я имел две-три кнопки.
   
   

   01. const okButton = new Buttton(0, 10, 'Ok') 
   02. okButton.addEventListener('click', () => { ... }) 
   03. const cancellButton = new Buttton(0, 10, 'Cancel')
   04.cancellButton.addEventListener('click', () => { ... })
   

   
   Потом я понял, что количество данных у меня растет и растет, и начал передавать там объекты. Там же и «биндил» события, потому что это было удобно.
   
   

   01. const okButton = new Buttton({
   02. left: 0,
   03. top: 10,
   04. onClick: () => { ... }
   05. })
   06. const cancellButton = new Buttton({...})
   

   
   Потом выросло количество объектов, и я вспомнил, что есть JSON.
   
   

   01. [
   02.    {
   03.        id: 'okButton',
   04.        options: {
   05.            left: 0,
   06.            top: 10,
   07.            onClick: () => { ... }
   08.        },
   09.    },
   

   
   Далее я начал грустить, потому что не мог представить, как он будет выглядеть. Когда вы пишете код, вы немного предвыполняете его у себя в голове. Когда вы верстаете, вы немного визуализируете. И я, пытаясь верстать, пытался и визуализировать, и это было очень сложно.
   
   Тут я вспомнил, что есть XML. XML — это то же самое, что и HTML, это для меня понятно и просто, а при сборке он генерирует тот самый JSON, который понятен машине, но плохо понятен мне.
   
   

   01. <button id="okButton"
   02. left="0"
   03. top="10"
   04. onClick="{doSomething()}"
   05. />
   

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

   01. <group id="main" ... >
   02.    <group id="header" ... >
   03.       <text-block ... />
   04.       <button ... />
   05.   </group>
   06.   <group id="footer" ... >
   07.       <any-component ... />
   08.       <button ... />
   09.   </group>
   10. </group>
   

   
   Как оказалось, не я первый, кто это придумал — делать из XML что-то на Canvas. Есть такая библиотека — react-canvas, и я был очень рад, когда узнал, что мои мысли тоже кому-то знакомы, и я додумался до чего-то полезного, что может пригодиться и в других отраслях.
   
   

   ---

   
   

   Как это все работает

   
   Мы рассмотрели по отдельности рендер, производительность, чтение данных, их хранение… Пожалуй, у вас возник вопрос: а как все это вместе работает? А вот как-то так:
   
   
   
   Я нарисовал схему, по которой видно, что у меня есть зона быстрого доступа к данным, которая, получая какой-то ивент от пользователя, может быстро изменить что-то в рендере, а есть зона долгого доступа — это модель для хранения большого количества объектов. То есть всё хранится в долгом доступе, где-то в моделях, и асинхронно приходит в рендер.
   
   Пунктирные стрелочки представляют собой асинхронное взаимодействие. Ресурсы — это то, что мы загружаем с сервера. Когда нам нужно подгрузить картинку, она, естественно, придет к нам асинхронно. Мы не загружаем все картинки, потому что, переходя по экрану, стараемся грузить только необходимое. Надеюсь, вы на сайтах делаете так же.
   
   Я бы хотел рассмотреть, как это все работает, на примере сбора ресурсов. Мы видим какой-то ресурс, бежим к нему и собираем. Как в этом случае работает игра?
   
   Сначала включается поиск пути:
   
   
   
   Я использую алгоритм A*. Этот алгоритм позволяет искать пути по графам. Граф — это то, что можно представить в виде сетки, либо квадратной, либо гексагональной, как в боевке. По факту, на экране боя и экране карты используется одинаковый алгоритм поиска пути — алгоритм переиспользуемый, и это большой плюс. Он учитывает «вес» перемещения по каждой клетке (на картинке слева можно заметить, что герой пойдет не прямо, а по дороге, потому что это банально дешевле, потратит меньше шагов хода).
   
   Далее, во время движения персонажа, выполняется его анимация. Во время анимации мне нужно обновлять героя в дереве отрисовки. Зачем это нужно? Дело в том, что, так как объекты рисуются друг над другом, когда герой находится за мельницей, она его перекрывает, и наоборот:
   
   
   
   Чтобы достичь такого эффекта в нужный момент времени, мне надо делать перенос героя по ветвям дерева отрисовки каждый раз, когда он проходит тайл.
   
   Затем мне нужно сделать проверки в конечной точке, то есть, когда герою остался буквально один шаг, начинаются проверки:
   
   
   • Делаем запрос к карте и получаем ID объектов в этой точке
   • Они отсортированы как: действия, проходимые и непроходимые
   • Берем первый объект по ID
   • Проверяем, можно ли заходить на объект для активации действия
   
   Для того, чтобы совершить действие с объектом, у меня в каждом из них реализован PubSub в объекте events:
   
   

   01. const objectInAction = Objects.get(ID) 
   02.const hero = Player.activeHero 
   03. objectInAction.events.dispatch('action', hero) 
   04. ...
   05. this.events.on('action', hero => {
   06. hero.owner.resources.set('gems', this.value) 
   07. this.remove()
   08. })
   

   
   Так я могу диспатчить события и уже внутри объекта, начиная с пятой строки, я могу повесить callback на это действие (в данном случае я кидаю действие «action» и единственный атрибут, который его вызвал — это герой. В объекте я получаю этого героя, перечисляю ему нужные ресурсы и самоудаляюсь).
   
   Кстати, с удалением объекта не все так просто, пожалуй, тут это самая сложная операция, потому что мне нужно обновлять много связанных массивов:
   
   
   • Удаляем отрисовку из рендера
   • Удаляем из массивов поиска пути
   • Удаляем из ассоциативного массива с координатами
   • Удаляем обработчики событий
   • Удаляем из массива объектов
   • Обновляем мини-карту, уже без этого объекта
   • Рассылаем событие об удалении этого объекта из текущего стейта (для того, чтобы делать save/load, я храню данные в стейте, это отдельный интересный челлендж)
   
   Со временем я задумался, как обновлять все эти массивы быстрее. Оказалось, что доля динамических объектов, которые могут удаляться или перемещаться — всего около 10%, и это, пожалуй, максимум. Таким образом, у нас есть балласт из 90% объектов, которые мы каждый раз итерируем, когда нам нужно что-то обновить в этих массивах. И я сильно сэкономил на расчетах, делая две сетки, которые потом мерджу, когда мне это действительно нужно.
   
   У меня есть базовая сетка со статичными объектами и сетка с динамическими объектами, потому что чаще всего мне приходится обновлять и проверять только динамические объекты. Если же я не нахожу объект в динамической сетке, я лезу в более большую и дорогую статическую сетку, которая содержит больше, и там уже точно будет найдено то, что мне нужно. Таким образом я увеличиваю производительность при чтении данных. Советую вам всегда смотреть на данные, действительно ли они все нужны сейчас? Можно ли разделить их так, чтобы читать их побыстрее, а какие-то долгие, большие данные хранить отдельно и читать только при необходимости?
   
   Как устроены объекты? Так как это игра, на нее отлично ложится ООП:
   
   

   01. // Объект содержит гарнизон и может быть атакован
   02. @Mixin(Attacable)
   03. class TownObject extends OwnershipObject {...}
   04. // Содержит все для отрисовки флажка, его смены и т.п. 
   05. class OwnershipObject extends MapObject {...}
   06. // Содержит все базовые поля для объекта карты 07.class MapObject {...}
   

   
   Одни объекты экстендят другие, таким образом получая какие-то свойства от своих родителей. Также я очень люблю миксины, которые позволяют мне добавлять какое-то поведение. Например, TownObject, который является объектом города, также является Attacable, потому что его можно атаковать. Это значит, что у него есть свой гарнизон, там находятся функции для работы с этим гарнизоном, там же есть функции коллбэков, которые говорят, что делать, если на город напали (если есть гарнизон, то вступать в бой, если нет, то просто сдаваться).
   
   Сам по себе TownObject наследуется от OwnershipObject, который содержит все, что нужно объектам, которые можно захватить и поставить флажок. Там есть все функции для постановки флажка, для его отрисовки, для событий, которые нужны, когда объект захватывает какой-то другой герой. И все это, в свою очередь, наследуется от базового MapObject, где хранятся все данные для базовых объектов, имеющихся у нас.
   
   

   ---

   
   

   Выводы

   
   Какие выводы я могу из всего этого сделать? Это была очень большая борьба с нечистью. Нечисть была в том, что было много багов, я много раз унывал, я бросал проект (бывало, на месяцы). Это, кстати, полезно делать в рамках вашего домашнего проекта. Конечно, в рамках рабочего проекта вы вряд ли сможете так сделать, но домашний проект позволяет вам быть немножко ленивым и отдохнуть, чтобы придумать что-то красивее, чем у вас есть сейчас.
   
   Многие спрашивают: а зачем ты это делал? Я делал это на протяжении двух лет. Спрашивается, зачем ты делаешь что-то большое и никому не показываешь? Я показываю это на большом экране, пожалуй, второй раз, и были разные советы, вроде: «почему ты не сделаешь плагин для webpack или какую-нибудь маленькую библиотеку и не нахватаешь звезд, и все у тебя в шоколаде». Но я продолжал это делать, я продолжал никому ничего не показывать, кроме нескольких друзей, которым иногда кидал ссылки. Спасибо моей жене, которая долго это терпела!
   
   Что мне это дало:
   
   
   • Я очень сильно саморазвился
   • Я выходил за рамки привычных рабочих задач. Дело в том, что, когда я начинал делать эту игру, я работал в обычной web-студии, делал сайты, рамки рабочих задач были строго ограничены тем, что нужно для сайта, а это, обычно, повторяющиеся задачи.
   • Я сильно расширил кругозор, занимаясь игровыми задачами, занимаясь игровой логикой.
   • Также я узнал много фанатиков, которые тоже что-то делают для «Героев». Многие из них делали это далеко не два года, а пять-десять лет. Кто-то делает свой конвертер, кто-то за пять лет делает крутую карту. То есть, фанатиков много, они не очень себя пиарят, они вдохновляли меня на то, чтобы двигаться дальше и не останавливаться. Знакомство с фанатиками очень окрыляет.
   
   Зачем делать игры:
   
   
   • На мой взгляд, это куда интереснее, чем делать сайтики, потому что вы решаете такие задачи, которые обычно не решаете
   • Это большое количество новых для вас алгоритмов, с которыми вы не сталкиваетесь. Например, я изобретал новые способы хранения данных, или, допустим, написал алгоритм поиска пути, который банально был в составе, но для того, чтобы сделать его быстрее, мне пришлось в нем разобраться и немножко дописать.
   • Это очень красиво. Советую вам наполнять мир красотой, потому что я всегда к ней стремился, и мне нравилось делать интерфейсы.
   
   На мой взгляд, степень мастерства прямо пропорциональна времени, которое можно потратить на работу вглубь. Когда я учился рисовать, нам рассказывали, что, когда вы рисуете голову, вы должны поступать как скульптор. Скульптор сначала берет параллелепипед камня и отсекает от него грани, делая его отдаленно похожим на голову. Потом он начинает искать все новые и новые грани, он находит форму носа, находит форму брови и под конец он находит 50, или даже больше, граней в веке.
   
   И работа вглубь заключается в том, насколько долго можно углублять свое детище, насколько долго над ним можно работать. И если вы видите свое детище, и не представляется никаких вариантов, что еще можно сделать, то что-то не так со степенью мастерства. Советую почитать и расширить свой кругозор, отдохнуть и вернуться снова. Таким образом вы будете только улучшаться и делать себя бо?льшим мастером.
   
   Тут я оставил полезные ссылки, которые отчасти мне помогли:
   
   
   • Про побитовые операторы на JS
   • Книга «Game Programming Patterns»
   • Интерактивная визуализация алгоритмов поиска пути в сетке
   • FizMig (та самая спецификация по всем игровым механикам «Героев»)
   
   И, конечно же, демка, куда ж без нее. Работает и на телефонах.
   

   Минутка рекламы. Если вам понравился этот доклад с предыдущей HolyJS, обратите внимание: уже 19-20 мая пройдёт HolyJS 2018 Piter. И на сайте конференции уже опубликована её программа, так что смотрите, что из её докладов будет интересным для вас!