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

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

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

Меня зовут

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

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

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

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

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

Какие цели ставил

1. Сделать нечто, прыгнуть выше своей головы
2. Заняться чем-то интересным
3. Перестать играть в героев :)

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

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

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

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

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

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

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

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

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

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

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

h3m-map-convertor

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

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

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

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

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

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

					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)
		

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

Чтобы достичь одинаковой скорости...

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

			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
			])
		

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

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

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

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

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

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

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

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

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

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

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

			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)
			})
		

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

			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

#3 UI на Canvas

В начале я создавал UI-элементы так

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

Кол-во параметров росло и росло...

			const okButton = new Buttton({
			    left: 0,
			    top: 10,
			    onClick: () => { ... }
			})
			const cancellButton = new Buttton({...})
		

Их становилоь все больше, появился JSON...

			[
			    {
			         id: 'okButton',
			         options: {
			             left: 0,
			             top: 10,
			             onClick: () => { ... }
			         },
			    },
			...
			]
		

Но далее я вспомнил, что есть XML

			<button id="okButton"
			        left="0"
			        top="10"
			        onClick="{doSomething()}"
			/>
		

При сборке он собирается в JSON с предыдущего слайда

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

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

#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. это красиво

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

Вопросы