Герои в браузере

Долго, сложно и невыносимо интересно.

Герои в браузере

Долго, сложно и невыносимо интересно.

Меня зовут

Коротаев Александр

  1. Работаю в Tinkoff.ru
    Делаю внутренние сервисы и кабинет для бизнеса
  2. Хожу на митапы 🤓
  3. Делаю SPB-Frontend Drinkcast
    Подкаст o фронтенде за кружкой пива

Из чего состоит игра?

  1. Модель данных (персонажи, карта, хранение состояния)
  2. Игровой цикл (game loop)
  3. Обработка ввода (мышь, клавиатура, джойстик...)
  4. Отрисовка (renderer)

А если представить это ввиде кода, то

			const me = {name: 'Alex', left: 0}
			...
			setInterval(() => update(), 1000)
			...
			window.addEventListener('keyup', () => me.left++)
			...
			requestAnimationFrame(() => draw())
		

Модель

			const me = {name: 'Alex', left: 0}
			...
			setInterval(() => update(), 1000)
			...
			window.addEventListener('keyup', () => me.left++)
			...
			requestAnimationFrame(() => draw())
		

Game loop

			const me = {name: 'Alex', left: 0}
			...
			setInterval(() => update(), 1000)
			...
			window.addEventListener('keyup', () => me.left++)
			...
			requestAnimationFrame(() => draw())
		

Обрабтка ввода

			const me = {name: 'Alex', left: 0}
			...
			setInterval(() => update(), 1000)
			...
			window.addEventListener('keyup', () => me.left++)
			...
			requestAnimationFrame(() => draw())
		

Отрисовка

			const me = {name: 'Alex', left: 0}
			...
			setInterval(() => update(), 1000)
			...
			window.addEventListener('keyup', () => me.left++)
			...
			requestAnimationFrame(() => draw())
		

Подробнее про gamedev на JS в книге
Сюрреализм на JavaScript

Итак, вы хотите сделать своих героев...

Каждые 2 месяца, на гитхабе появляется 1 клон героев

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

Но никто из них не доделывает до конца и не стремится объединяться

И я тоже хотел

  1. Сделать нечто, прыгнуть выше своей головы

4. сделать красиво

Что мы имеем из входных данных?

  1. Оригинальная игра
  2. Редактор карт
  3. FizMig — большой справочник по всем игровым механикам
  4. Много форумов с ребятами, по многу лет копавшимися в "героях"
  5. Распаковщик ресурсов 😎

#1 Парсинг карт

Я решил использовать homm3tools...

Это набор библиотек и утилит, для работы с картами

  1. Парсер разных форматов
  2. Генератор карт
  3. Рендер надписей из деревьев
  4. И, даже, игра "змейка"

...и сделал свой конвертор

h3m-map-convertor

Данных становилось все больше, кол-во объектов росло...

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

#2 Отрисовка карты

Canvas это не DOM

			const ctx = canvas.getContext('2d')
			 
			ctx.drawImage(hero, 0, 0)
			ctx.clearRect(0, 0, 100, 100)
			ctx.drawImage(hero, 100, 0)
			ctx.clearRect(0, 0, 100, 100)
			ctx.drawImage(hero, 200, 0)
		

А если под героем трава...

			const ctx = canvas.getContext('2d')
			 
			ctx.drawImage(hero, 0, 0)
			ctx.drawImage(grass, 0, 0)
			ctx.drawImage(hero, 100, 0)
			ctx.drawImage(grass, 100, 0)
			ctx.drawImage(hero, 200, 0)
		

Я просто использую 3 <canvas>

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

Алгоритм рисования террейна

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

Рисуем все сразу и кладем в кэш

Как плавно двигать карту

  1. Сдвигаем карту при помощи
    transform: translate()
  2. Каждые 32 пикселя
    увеличиваем left на 32px
    рисуем еще одну полоску

Иллюзия непрерывного блока
спасибо Яндекс-картам за идею

#3 Отрисовка объектов

Особенности рисования объектов

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

  1. Сортируем массив объектов по Y нижней границы
  2. Фильтруем те, что не попадают в окно
  3. ...тут масса проверок...
  4. Рисуем текстуру объекта
  5. Если нужно рисуем флаг игрока

А ведь кол-во объектов на карте может достигать over 9000!

Построим дерево!

  1. Каждая ветвь - Y объекта
  2. Объекты на ветви
    отсортированы по X

+ отсечение видимых объектов
+ корректное перекрытие
+ более дешевая итерация

					const renderTree = {
					    32: [object, object, ...]
					    64: [object, object]
					    96: [object, object, ...]
					    128: [object]
					}
				

Если заглянуть в функцию рисования объекта...

			const object = getObject(id)
			const {x, y} = getAnimationFrame(object)
			const offsetleft = getMapLeft()
			const offsetTop = getMapTop()
			 
			context.drawImage(object.texture, x - offsetleft, ...
		

То, все рисование сводится к:

			context.drawImage(object.texture, x, y)
		

Поэтому мы просто возьмем и запишем их в Render tree!

			const drawer = context.drawImage.bind(context, ...)
			renderTree.add(x, y, drawer)
		

И получим отличный прирост производительности!

Минутка геометрии

Минутка героеметрии 🏇

Для однородного перемещения...


4 шага

~6 шагов

В Event Loop есть задачи

setTimeout(() => setTimeout())

vs

setInterval()

vs

requestAnimationFrame()

Задача
setTimeout()
Задача
setTimeout()

А есть — подзадачи



Promise()

Задача
Задача
Микрозадача
Подробнее об этом в статье Джейка Арчибальда

Возьмем все и сразу

			new Promise(resolve => {
			    setTimeout(() => {
			        // расчеты для анимации
			        requestAnimationFrame(() => /* рисование */)
			        resolve()
			    })
			})
		

Построим из этого последовательность

			startAnimation()
			    .then(step)
			    .then(step)
			    .then(step)
			    .then(step)
			    .then(doAction)
			    .then(endAnimation)
		

А лучше сразу декларативную абстракцию

			AsyncSequence([
			    startAnimation, [
			        step
			        step
			        ...],
			    doAction,
			    endAnimation
			])
		

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

Вся карта — это сетка

* а точнее — тайлы

Каждый тайл это

  1. Тип (вода, земля, дерево)
  2. Проходимость/стоимость перемещения
  3. Наличие события
  4. Флаг "Кем занят"
  5. ...

Представим это в коде

			const map = [
			    [{...}, {...}, {...}, {...}, {...}, {...}],
			    [{...}, {...}, {...}, {...}, {...}, {...}],
			    [{...}, {...}, {...}, {...}, {...}, {...}],
			    ...
			]
			const tile = map[1][3]
		

Чтобы получить свойство тайла

  1. Запросить массив тайлов
  2. Запросить массив массива для строки
  3. Запросить объект тайла
  4. Запросить свойство объекта

Хранить все в одном месте — это медленно

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

Быстрее всего читать данные из массива

[🌲, ,🌳,🌲, , ,🔥,🌲]
[1,0,1,1,0,0,1,1]

Если заранее делать необходимые расчеты

tiles [{...}, {...}, {...}]
+
objects [{...}, {...}, {...}]
=
[1, 0, 2]

Делаем разные массивы

Цикл отрисовки массив функций отрисовки
Поиск пути массив чисел
Ассоциация объектов к тайлам массив строк
Дополнительные свойства тайлов массив чисел
Для игровой логики Map объектов c их ID

Остается только своевременное обновление данных из медленных хранилищ в быстрые

Как можно уйти от массивов массивов

			const map = [
			    [{...}, {...}, {...}, {...}, {...}, {...}],
			    [{...}, {...}, {...}, {...}, {...}, {...}],
			    [{...}, {...}, {...}, {...}, {...}, {...}],
			    ...
			]
		

Развернем массив, получаем прирост ~50%

			const map = [{...}, {...}, {...}, {...}, ...]
			 
			const tile = map[y * width + x]
		

Пробуем ускорить и дальше

			const map = [{...}, {...}, {...}, {...}, ...]
			 
			const tile = map[y * width + x]
			map.forEach((value, index) => {
			    const y = Math.floor(index / width)
			    const x = index - (y * width)
			})
		

Power of 2!

2n === 2 << n

Math.floor(X / 2n) === X >> n

Погружаемся в побитовые сдвиги

			const map = [{...}, {...}, {...}, {...}, ...]
			const powerOfTwo = Math.ceil(Math.log2(width))
			 
			const tile = map[y << powerOfTwo + x]
			map.forEach((value, index) => {
			    const y = index >> powerOfTwo
			    const x = index - (y << powerOfTwo)
			})
		

Степень двойки в видеокарте

Так получился Grid

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

- только квадратные сетки
- неэффективен для сеток стороной более чем 256

#5PubSub

В начале, с ним вроде бы все ОК

Сначала мы просто вешаем обработчики

			object.on('ownerChanged', () => ...)
			object.on('objectRemoved', () => ...)
			object.on('heroGoesToHellWithHisHorse', () => ...)
			object.on('someStrangeEventThatYouWantToDescribe', () => ...)
		

Их все больше — заводим константы

			const OWNER_CHANGED = 'ownerChanged';
			const OBJECTS_REMOVED = 'objectsRemoved';
			 
			dwelling.on(OWNER_CHANGED, () => ...)
			dwelling.on(OBJECTS_REMOVED, () => ...)
			 
			hero.on(OWNER_CHANGED, () => ...)
			hero.on(OBJECTS_REMOVED, () => ...)
		

Если через пару месяцев вернуться к этому

PubSub вышел из под контроля!

Имена событий — случайны

Итак, я пришел к хранению стейта

			const state = new StateStore()
			 
			state.set('objects.234.owner', hero.owner.id)
			const object = state.get('objects.234')
		

Под капотом просто хранится объект

			state.set('objects.234.owner', hero.owner.id)
			 
			{
			  objects: {
			    234: {owner: 1}
			  }
			}
		

И туда прикручивается PubSub

			// 'objects.234', 'objects.234.*'
			state.on('objects.234', object => ...)
			 
			// 'objects.234.owner', 'objects.{N}.owner' ...
			state.on('*.owner', object => ...)
		

Мы добавили жесткие правила в события

  1. Более гибкая система подписок на изменения
  2. Почти ничего не надо писать руками
  3. Нужно только подписаться
  4. Игровое состояние можно восстанавливать из JSON

#6 UI на Canvas

Верстка UI в XML

			<group id="main" ... >
			    <group id="header" ... >
			        <text-block ... />
			        <button ... />
			    </group>
			    <group id="footer" ... >
			        <any-component ... />
			        <button ... />
			    </group>
			</group>
		

В начале, я сделал некое подобие SVG

  1. Позиция элементов всегда была абсолютной
  2. Они никак не зависели друг от друга
  3. Высота была постоянной

Но ведь в моде mobile-first

И тaк я переизобрел DOM

			<group width="{windowWidth}" ... >
			    <group width="100%" ... >
			    </group>
			    <group bottom="0" ... >
			    </group>
			</group>
		

Сперва я разобрался с перерисовками

  1. Кол-во событий для обновления — конечно
  2. Обновляем усеченное дерево компонентов
  3. Если можно считать заранее, — считаем

Далее — вычисляемые свойства

			<group width="{expression}">
		

Фреймворки либо компилировали это в JS, либо имели собственный интерпретатор JS на JS

И тут я вспомнил про with...

Use of the with statement is not recommended, as it may be the source of confusing bugs and compatibility issues. See the "Ambiguity Contra" paragraph in the "Description" section below for details.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/with

Ну ладно, мы знаем, что делаем!

			...
			window.$w = function(o, e){with (o) {return eval(e)}};
		

Use strict!

			'use strict'
			window.$w = function(o, e){with (o) {return eval(e)}};
		

Challenge accepted!

			window.$w = function(o, e){with (o) {return eval(e)}};
			'use strict'
			// code in strict mode
			$w(context, 'some code here')
		

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

Например, сбор ресурсов

#1 Поиск пути — алгоритм A*

И если бы A* подошел без проблем

Это была бы история не про "Герои"

  1. Каждый объект имеет определенне точки "входа"
  2. Есть непроходимые точки, на которых можно заканчивать путь

#2 Анимация движения

После каждого шага нужно обновлять позицию героя в дереве отрисовки

#3 Проверка в конечной точке

  1. Делаем запрос к карте и получаем ID объектов в этой точке
  2. Они отсортированы как: действия, непроходимые и проходимые
  3. Берем первый объект по ID
  4. Проверяем можно ли заходить на объект для активации действия

#4 Действие с объектом

			const objectInAction = Objects.get(ID)
			const hero = Player.activeHero
			objectInAction.events.dispatch('action', hero)
			...
			this.events.on('action', hero => {
			    hero.owner.resources.set('gems', this.value)
			    this.remove()
			})
		

#5 Удаление объекта

  1. Удаляем отрисовку из рендера
  2. Удаляем из массивов для поиска пути
  3. Удаляем из ассоциативного массива с коодинатами
  4. Удаляем обработчики событий
  5. Удаляем из массива объектов
  6. Обновляем мини-карту, уже без этого объекта
  7. Рассылаем событие об удалении этого объекта из текущего стейта

Как обновлять все эти массивы быстрее?

Доля динамических объектов около 10% от всех.
Так почему бы не сэкономить на расчетах:

			// только при загрузке карты, содержит много данных
			const baseGrid = new Grid(mapSize)
			// обновляется намного чаще, потому содержит мало данных
			const dynamicGrid = new Grid(mapSize)
		

Как устроены объекты

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

Выводы

Что мне это дало

  1. саморазвитие
  2. выходы за рамки привычных рабочих задач
  3. расширение кругозора
  4. знакомство с фанатиками

Зачем делать игры

  1. куда интереснее чем сайтики
  2. это алгоритмы
  3. это красиво


Степень мастерства прямо пропорциональна времени, которое можно потратить на работу вглубь

Полезные ссылки

Про побитовые операторы на JS
Книга Game Programming Patterns из которой я многое вынес
Интерактивная визуализация алгоритмов поиска пути в сетке
FizMig. Та самая спецификация по всем игровым механикам Героев

Демка Героев 3 в браузере

http://homm.lekzd.ru/

Вопросы