Создаем многопользовательскую браузерную игру. Часть первая. Клиент-серверная архитектура
Рассказывает Алвин Лин, разработчик программного обеспечения из Нью-Йорка
В 2014 году я впервые побывал на CodeDay в Нью-Йорке. И хотя CodeDay не совсем хакатон, это было моё первое знакомство с подобными мероприятиями. Там мы с моим другом Кеннетом Ли написали многопользовательскую игру в танчики. Так как несколько моих друзей спрашивали меня о том, как я её написал, я решил описать процесс её создания.
В этом посте я вкратце опишу ход своих рассуждений и покажу, как воссоздать архитектуру, а также дам некоторые советы, если вы захотите сделать игру сами. Этот пост рассчитан на тех, кто владеет основами JavaScript и Node.js. Если вы с ними не знакомы, то есть много замечательных онлайн-ресурсов, где можно их изучить.
Прим. перев. На нашем сайте есть много познавательных материалов как по JavaScript, так и по Node.js — обязательно найдёте что-нибудь подходящее.
Прим. перев. Если вы не знакомы с веб-сокетами, рекомендуем прочитать наш вводный материал.
Создание проекта
Для начала установите зависимости. Создайте папку проекта, перейдите в неё и запустите следующий код:
Для быстрой настройки сервера целесообразно использовать фреймворк Express, а для обработки веб-сокетов на сервере — пакет socket.io. В файл server.js поместите следующий код:
Теперь нужно настроить веб-сокеты на сервере. В конец файла server.js добавьте:
Пока что в игре нет никаких функций, поэтому в обработчик веб-сокетов ничего добавлять не нужно. Для тестирования допишите следующие строки в конец файла server.js :
Эта функция будет отправлять сообщение с именем message и содержимым hi всем подключенным веб-сокетам. Позже не забудьте удалить эту часть кода, так как она предназначена только для тестирования.
Запустите сервер командой node server.js и в любом браузере перейдите по ссылке http://localhost:5000. Если вы откроете окно разработчика (нажать правую кнопку мыши → Проверить (Inspect)), то увидите, как каждую секунду приходит новое сообщение:
Как правило, socket.emit(name, data) отправляет сообщение с заданным именем и данными серверу, если запрос идет от клиента, и наоборот, если запрос идет от сервера. Для получения сообщений по конкретному имени используется следующая команда:
С помощью socket.emit() вы можете отправить любое сообщение. Можно также передавать объекты JSON, что для нас очень удобно. Это позволяет мгновенно передавать информацию в игре от сервера к клиенту и обратно, что является основой многопользовательской игры.
Теперь пусть клиент отправляет некоторые состояния клавиатуры. Поместите следующий код в конец файла static/game.js :
Эта часть кода позволит отправлять на сервер информацию о состоянии клавиатуры клиента 60 раз в секунду. Теперь необходимо прописать эту ситуацию со стороны сервера. В конец файла server.js добавьте следующие строки:
Когда сервер получит сообщение о том, что присоединился новый игрок, он добавит новый вход в объект игроков при помощи id сокета, который будет в этом сообщении. Когда сервер получит сообщение о движении, то обновит информацию об игроке, который связан с этим сокетом, если он существует.
io.sockets.emit() — это запрос, который будет отправлять сообщение и данные ВСЕМ подключённым сокетам. Сервер будет отправлять это состояние всем подключённым клиентам 60 раз в секунду.
Этот код обращается к id Canvas ( #canvas ) и рисует там. Каждый раз, когда от сервера будет поступать сообщение о состоянии, данные в Canvas будут обнуляться, и на нём в виде зеленых кружков будут заново отображаться все игроки.
Вот и всё! Если у вас возникли проблемы, посмотрите архив с исходным кодом.
Некоторые тонкости
Когда будете разрабатывать более функциональную игру, целесообразно разделить код на несколько файлов.
Такие многопользовательские игры — отличный пример архитектуры MVC (модель-представление-контроллер). Вся логическая часть должна обрабатываться на сервере, а всё, что должен делать клиент — это отправлять входные пользовательские данные на сервер и отображать информацию, которую получает от сервера.
Однако в этом демо-проекте есть несколько недостатков. Обновление игры связано со слушателем сокета. Если бы я хотел повлиять на ход игры, то мог бы написать в консоли браузера следующее:
Теперь данные о движении будут отправляться на сервер в зависимости от характеристик компьютера более 60 раз в секунду. Это приведёт к тому, что игрок будет передвигаться невероятно быстро. Так мы переходим к концепции определения полномочного сервера.
Ни на каком этапе клиент не должен контролировать какие-либо данные на сервере. Например, никогда не нужно размещать на сервере код, который позволит клиенту определять своё положение/здоровье на основе данных, которые передаются через сокет, так как пользователь сможет легко подделать сообщение, исходящее из сокета, как показано выше.
Лучшая аналогия, которую я могу привести, заключается в том, что клиенты должны посылать на сервер только информацию о своих намерениях, которые затем будут обрабатываться и использоваться для изменения состояния игроков, если они валидны.
Кроме того, старайтесь избегать такого кода:
В этом отрезке кода обновление координаты х для игрока связано с частотой смены кадров в игре. SetInterval() не всегда гарантирует соблюдение интервала, вместо этого напишите нечто подобное:
Это не так изящно, зато обеспечит более плавную и последовательную работу. Усложните демо-проект и попробуйте сделать так, чтобы обновление осуществлялось согласно времени, а не частоте смены кадров. Если не захотите на этом останавливаться, попытайтесь создать на сервере физический движок, который будет управлять движениями игроков.
Также можно сделать так, чтобы из игры удалялись отключенные игроки. Когда сокет отключается, автоматически отправляется сообщение о разъединении. Это можно прописать так:
Также попытайтесь создать собственный физический движок. Это сложно, но весело. Если захотите попробовать, то рекомендую прочитать книгу «The Nature of Code», в которой есть много полезных идей.
Если хотите посмотреть на гораздо более продвинутый пример, вот игра, которую я сделал, а также исходный код, если вы хотите узнать, как это было написано. На этом всё. Спасибо, что прочитали!
Создание браузерной игры. Как заработать миллион?
К браузерным играм не привыкли относиться всерьез, но на самом деле – это неплохой бизнес для небольшой команды друзей, у которых нет денег, но есть светлые мысли. А если еще и деньги есть, то тогда все значительно упрощается.
На самом деле создать браузерную онлайн игру может любой, у кого есть желание учиться, но не думайте, что вас ждет легкая прогулка. Даже если вы мастер на все руки (программист и дизайнер в одном флаконе), то придется потратить уйму времени. Если же вы не владеете ни кодом, ни карандашом, то затраты будут финансовыми.
Как создать браузерную игру ничего не изучая?
Ответ – никак. Для начала нужно будет выучить HTML – язык разметки, который работает в связке с каскадной таблицей стилей – CSS. Эти языки располагают текст и изображения на странице, собирая картинку из множества фрагментов. Поскольку вы намерены сделать именно браузерную игру, то ей обязательно понадобится сайт, желательно красивый и функциональный. Поэтому не обойтись без JavaScript – самого простого способа визуализировать вашу игру на стороне геймера. Этот язык позволяет менять местами элементы страницы без ее перезагрузки. По сути, JavaScript управляет элементами CSS и HTML в реальном времени.
Для создания браузерной игры придется выучить HTML, CSS, PHP и JavaScript, так что бессонные ночи вам гарантированы
Язык программирования PHP нужен для создания движка игры. Он используется на сервере для обработки данных, поступающих от разных геймеров. Это – ядро, которое приводит в действие все внутренние механизмы.
Я не хочу ничего учить, но у меня есть деньги
Поздравляем, вы избежали многих проблем. И тут же получили новые. Чтобы сделать браузерную игру хорошего качества (в плохую никто играть не будет) нужно иметь хорошую команду разработчиков, а хорошие спецы стоят денег. Если брать по минимуму, то вам необходимы:
Если у вас нет личных знакомств, то придется обращаться к аутсорсингу. Обычно такие ребята трутся на биржах фрилансеров, самой популярной их которых является www.fl.ru/.
Всех необходимых работников можно найти на биржах фрилансеров
Правда, в этом случае нужно быть очень осторожным, поскольку фрилансеры привыкли регулярно срывать сроки. Как говорят опытные руководители, можно бесконечно смотреть на 3 вещи: как течет память, как горит дедлайн и как не работает фрилансер.
Во сколько обойдется разработка?
Во столько, сколько у вас есть денег. Вот здесь приведены примерные выкладки и структура расходов на создание среднестатистической браузерки. Итоговая сумма – 25 миллионов рублей. Однако не стоит пугаться этой цифры. В статье автор посчитал расходы на разработку по максимуму, так что при желании эту сумму модно уменьшить в разы и даже десятки раз. Или увеличить, если ваш папа – прокурор. Безусловно, такие проекты, как Drakensang Online или City of Steam требуют сумм как минимум с шестью нулями, но простую табличную браузерку можно сделать за пару десятков тысяч рублей.
В конце концов, вы всегда можете обратиться к краудфандингу. Пути Кикстартера неисповедимы, взлететь там может любой проект. Главное правильно подать блюдо.
Этапы разработки
Создание браузерной игры с нуля можно разделить на несколько этапов:
1. Поиск идеи
Поскольку у вас вряд ли есть 25 миллионов рублей и вы вряд ли являетесь гением в программировании и дизайне, единственное, чем вы можете зацепить пользователя, это необычный сеттинг. Даже пресловутая кампания из эльфов, орков, людей и гномов способна увлечь клиента, если погрузить их в необычную среду или заставить делать странные вещи. Например, игра Ботва Онлайн была написана «по приколу» четырьмя людьми в свободное от работы время, но благодаря своему необычному сеттингу быстро стала успешным бизнес проектом.
2. Разработка сюжета
Сюжет очень важен (если конечно, вы не делаете стратегию). Если у самого воображения не хватает, наймите кого-нибудь, у кого оно есть. В крайнем случае, обратитесь к аутсорсингу и найдите толкового копирайтера, у которого уже есть опыт создания квестов.
3. Создание игры
Даже если вы выучили вдоль и поперек JavaScript и CSS, вы все еще ничего не знаете о том, как создать браузерную игру. Это примерно то же самое, как если бы вы выучили теорию плавания, ни разу не побывав в бассейне. Лучший выход в этом случае – воспользоваться самоучителем. Вот здесь можно многое узнать о разработке игр, причем не только браузерных.
Скорее всего, ваша первая браузерка будет выглядеть так. Это – легендарный Бойцовский Клуб
4. Продвижение проекта
Последний этап, на котором дело в свои руки берут комьюнити-менеджер и специалист по маркетингу (если таковой имеется). В крупных компаниях на долю рекламы уходит примерно 60% бюджета, поэтому на эту статью денег лучше не жалеть. Если же ваши финансы поют романсы, то тогда не остается ничего другого, как самому перепахивать игровые форумы и завлекать геймеров всеми возможными способами.
Как создать браузерную игру с помощью конструктора
Оказывается, ушлые программисты уже давно создали кучу конструкторов MMO, которые могут помочь новичку создать браузерную онлайн игру бесплатно. Это не значит, что вы можете успокоиться и удалить все закладки по программированию, но с помощью конструктора можно здорово ускорить процесс.
Популярный игровой конструктор Construct 2
Большой популярностью пользуется MMO Constructor – отечественный продукт, в котором можно создать все элементы полноценной браузерной RPG. Взамен авторы требуют совсем ничего – 50% от прибыли проекта. Разобраться в конструкторе непросто, но добрые люди уже написали гайды. Также чтобы создать браузерную игру, можно воспользоваться такими программами, как Construct Classic, Eclipse, FPS Creator.
Больше информации о конструкторах можно узнать на форуме Gcup, где тусуются все: и продвинутые геймдевы, и зеленые новички.
Так что там насчет миллиона?
Любая, даже мобильная игра должна приносить прибыль. Иначе нет никакого смысла тратить свое и чужое время. Дабы сделать свой проект финансово успешным, нужно слушать, что говорят опытные разработчики и делать то же самое:
Напоследок хочется сказать – не так страшен черт, как его малюют. Даже лучшие геймдевы когда-то начинали с нуля, и кто знает, может быть именно вы станете следующим Джоном Кармаком или Ричардом Гэрриотом?
Разработка браузерной онлайн игры без фреймворков и движков
В этом посте будет описан процесс разработки онлайн игры на чистом javascript и WebGL (без фреймворков и движков). Будут рассмотрены некоторые алгоритмы, техники рендеринга, искусственный интеллект ботов и сетевая игра. Проект является полностью опенсорсным, в конце поста будет ссылка на репозиторий.
Сразу же геймплейное видео:
Тут играет бот по имени Лягуха и другие боты
Введение
Клиент написан на javascript с использованием WebGL, а сервер на node.js. В этом проекте используются следующие библиотеки:
Генерация уровня
Для генерации карты используется обычный Шум Перлина плюс некоторые преобразования и фильтрации:
Где perlinNoise() — шум Перлина, в диапазоне от 0 до 1,
abs(x) — модуль числа,
clamp(x) — если x 1, то x = 1,
norm(-0.5, 2) — нормализует шум в данный диапазон.
Именно такая последовательность преобразований на выходе даёт требуемую топологию карты: она состоит из комнат и коридоров, шириной в 2-3 пикселя.
Получившаяся текстура является маской земли (черный цвет — земля, белый — стена).
Далее в отдельном буфере генерируется река лавы. Для этого генерируется ломаная (если нужны притоки, то несколько ломаных) и каждый отрезок ломанной «рисуется» в буфер с помощью алгоритма Брезенхама. Затем этот буфер с отрезками размывается по Гауссу. Радиус размытия выбирается исходя из требуемой ширины реки. Для оптимизации размытия используется двухпроходный алгоритм. Функция размытия нам ещё не раз пригодится. Размытие буфера с лавой нужно для того, чтобы придать реке ширину, а так же в дальнейшем для рендеринга.
В маске земли, где проходит лава и в непосредственной близости от неё, удаляются стены:
Слева направо: маска земли с предыдущего этапа; маска лавы; расчищаем стены от лавы; финальный результат
Перед тем, как получить этот самый финальный результат, над маской земли проводятся несколько преобразований: фильтрация мелких деталей (стены и проходы шириной в один пиксель нежелательны); заливка изолированных областей (в процессе генерации могут образоваться зоны полностью изолированные стенами со всех сторон, их лучше залить белым, чтобы игроки там не спавнились); по краям добавляется слой стен шириной в 5 пикселей, чтобы игроки не сбежали с карты.
Ну и в конце генерируются мосты. Тут все просто: выбираются случайные точки на лаве так, чтобы мосты не были слишком близко друг к другу или слишком далеко, и ориентируются они перпендикулярно потоку лавы в данной точке (естественно мосты не запекаются в левелмапу, они хранятся просто как массив объектов).
Помимо масок земли и лавы генерируются еще две вспомогательные: маска для текстур (т.к. в игре на землю накладываются две разные текстуры, эта маска задает коэффициенты смешивания этих текстур) и маска статичных теней от стен. Маска для текстур — это всё тот же шум Перлина.
Перед тем, как маску земли запечь в левелмапу её следует размыть по Гауссу. Это нужно для создания плавных контуров.
Все вышеперечисленные маски и составляют нашу левелмапу. Вот из чего она состоит: R канал содержит маску лавы; G — маска земли; B — маска для смешивания диффузных текстур; A — тени.
Рендеринг уровня
Если прямо сейчас взять и отрендерить левелмапу, то получится примерно следующее:
Слева прямоугольник на левелмапе показывает охват камеры
Как такое получить? Допустим у нас есть матрица камеры (мы же точно знаем позицию своего игрока и угол его поворота). В вершинном шейдере эта матрица умножается на текстурные координаты полноэкранного квада, а результат передаётся во фрагментный шейдер. Эти текстурные координаты ни что иное, как координаты фрагмента внутри левелмапы. Поэтому просто делаем выборку из неё по этим координатам. На скриншоте выше выводятся только RG каналы левелмапы.
Получилось слишком размыто (фильтр Гаусса даёт о себе знать). Давайте к результату выборки из левелмапы применим клампинг:
Смысл этой формулы: level.rg у нас меняется плавно от 0 до 1 (видно на скриншоте выше). После клампинга все значения выборки меньшие 0.5 обращаются в 0, а большие 0.516 обращаются в 1, а значения на отрезке [0.5, 0.516] «растягиваются» в отрезок [0, 1]. Вот так это выглядит:
Пришло время для текстур: две диффузные текстуры смешиваются по маске из B-канала левелмапы, с ними смешивается текстура стены по G-каналу, а получившийся результат смешивается с текстурой лавы по R-каналу левелмапы (смешивание цветов в шейдерах GLSL производится функцией mix — это обычная линейная интерполяция двух значений по коэффициенту смешивания). Для выборки из текстур используется всё те же текстурные координаты домноженные на некий коэффициент, который влияет на количество повторений этой текстуры по всей карте:
Всё выглядит слишком плоским. Чтобы это исправить в наш шейдер нужно передать ещё одну текстуру с шумом Перлина. Выборку из этой текстуры прибавляем к значению R-канала левелмапы (маска лавы). Получившийся коэффициент используется не только для смешивания лавы и земли, но и для затенения береговой линии. Также добавим статические тени, которые хранятся в A-канале левелмапы:
Выглядит уже лучше, обратите внимание как преобразилась береговая линия, теперь она не такая ровная и плоская.
Осталось решить последнюю проблему: мы можем видеть через стену (то есть видим области, которые отгорожены стеной от нашего персонажа). Для решения этой проблемы используется трассировка фрагмента: из исследуемого фрагмента выпускается луч в сторону персонажа и делаются выборки из левелмапы (нас интересует только G-канал с маской стены), в данном проекте используется 12 выборок. По результатам выборок можно определить, виден ли фрагмент из позиции персонажа или нет. Для полноэкранного прохода такая трассировка слишком дорогая операция, поэтому она выполняется в отдельном фреймбуфере малого размера (64х64). Эта текстура называется картой видимости:
До применения карты видимости и после
Карта видимости используется не только в полноэкранном проходе для рендеринга карты, но и для рендера всех игровых объектов (мосты, пушки, персонажи).
Рендеринг лавы
Теперь давайте анимируем лаву. Для этого нужно создать карту смещений. В этой текстуре в RG-каналах хранится 2D вектор, который складывается с текстурными координатами для выборки из текстуры лавы. Причем нужна не просто карта смещений, а карта смещений меняющаяся со временем. В данной игре для создания карты смещений используется фреймбуфер размером 512х512. В шейдер этого прохода передаётся текстура с шумом Перлина и время, измеряемое от 0 до 1.
Кусок фрагментного шейдера (упрощено):
где noise — шумовая текстура (она статичная).
Смысл этого шейдера в том, что делаются 4 выборки из одной и той же шумовой текстуры, но с разным масштабом текстурных координат. Да ещё и смещаются они со временем в перпендикулярных направлениях (обратите внимание на вторую выборку, там используется смещение time.yx, а в первой — time.xy). Время зашито только в x-компоненту переменной time, а y-компонента содержит 0.
Теперь эту анимированную текстуру можно передать в шейдер лавы. В этом шейдере делаем выборку из карты смещений и прибавляем полученный 2D вектор к текстурным координатам лавы.
Упрощенный кусок шейдера:
где tex_wave — карта смещений (ну или карта волн).
С коэффициентом 0.1 можно поиграться, влияет он на «возмущение» лавы.
В принципе, на этом можно было бы и остановиться, выглядит довольно неплохо. Но можно сделать ещё лучше — заставить лаву течь. Для создания течения нам понадобится сгенерировать ещё одну текстуру: карту скоростей. Когда генерировалась лава, мы создали ломаную и нарисовали отрезки этой ломаной в буфер лавы. Теперь заведем ещё один буфер для карты скоростей. Нарисуем в него отрезки ломаной, но при этом каждый отрезок будет заносить в этот буфер вектор направления отрезка. Затем размоем этот буфер по Гауссу, тем самым мы не только «размешаем» скорости на изломах реки и на пересечениях с притоками, но и получим эффект «вязкой лавы», то есть скорость потока лавы в середине реки выше, чем у берегов.
Карта скоростей используется для смещения текстурных координат лавы. Чтобы появился эффект течения, смещать нужно с учетом времени.
Итак, обновленный шейдер лавы (упрощено):
Тут делается две выборки из текстуры лавы на расстоянии друг от друга в точности равное vel.xy и смешиваются по значению времени.
Всё вместе выглядит так:
Декали в данной игре — это лужи крови, следы от взрывов ракет и других пуль.
Декали, как объекты, сами по себе нигде не хранятся и не процессятся. Каждая декалька, в момент своего появления, рендерится в огромную текстуру, которая покрывает всю карту. Эта текстура потом «натягивается» на левелмапу. То есть, она содержит в себе все когда либо появлявшиеся декали (естественно она не чистится).
Теперь давайте выясним, какое разрешение должно быть у этой текстуры с декалями. Экспериментальным путём было выяснено, что 16х16 текселей текстуры, приходящиеся на один тайл карты выглядит оптимально (если брать 32х32, то это уже больше, чем размер самой декальки, например следа от взрыва, а по памяти 4-кратный проигрыш). Самая большая карта имеет размер 256х256, тогда разрешение текстуры с декалями равно 16 * 256 = 4096х4096.
На самом деле текстура 4К*4К не создаётся, вместо этого всю карту «распиливаем» на зоны 32х32. На каждую такую зону приходится собственная текстура с декалями 512х512. Всего таких текстур для большой карты 64. Чтобы не передавать пачку этих текстур в главный проход рендеринга карты (и не процессить из какой именно делать выборки) был создан ещё один фреймбуфер. Для него настраивается ровно та же матрица камеры, что и для рендеринга карты. И все текстуры с декалями по-очереди рендерятся в неё с учётом своих позиций на карте (естественно большая часть из них отсекается до вызова drawcall). Теперь в главный проход рендеринга карты передаём только этот готовый фреймбуфер.
Физика
Чтобы определить факт столкновения некой точки со стеной или попадание точки в лаву, нужно прочитать значение из массива с размытой левелмапой по целочисленным координатам этой точки, а так же по соседним координатам. Вручную произвести линейную интерполяцию этих значений и сравнить с неким пороговым значением.
Для определения нормали к стене в точке (X, Y) нужно произвести такую операцию трижды: для точек (X, Y), (X + 0.25, Y), (X, Y + 0.25):
Нормали используются не только для вычисления рикошетов, но и для столкновения персонажа со стеной. Когда персонаж пересекает корпусом стену, то в этом же кадре его как бы выпихивает по направлении нормали.
Преимущества и недостатки использования левелмапы по сравнению с тайловым рендером.
Искусственный интеллект ботов
Первая и самая главная задача ИИ ботов — это научить их просто бегать по карте, не обращая внимание на врагов и предметы. То есть адекватное перемещений по коридорам и комнатам, а так же по мостам через лаву. Для этого используется специальный граф, узлы которого назовём вейпоинтами. Такой граф должен покрывать всю карту, проходить через все коридоры и комнаты. Бот просто имеет ссылку на текущий вейпоинт, и, когда достигает его, выбирает случайным образом следующий вейпоинт из тех, на которые ссылается его текущий. Выглядит вроде просто. Но сначала нужно построить этот граф вейпоинтов.
Итак, у нас есть маска земли и маска лавы. Сложим эти две маски, чтобы получить карту проходимости (далее именно с ней и будем иметь дело при построении графа).
Наверняка для того, чтобы построить граф вейпоинтов существует много способов. В данном проекте алгоритм построения графа основан на методе Distance Field (карта расстояний). Вот в этом посте описывается алгоритм построения Distance Field. Смысл карты расстояний — в каждой точке записано расстояние до ближайшей непроходимой точки.
Тут на картинке в цвете закодировано расстояние, чем темнее, тем дальше
В принципе, тут уже угадываются очертания будущего графа. Следующий подготовительный этап — это вычисление градиента карты расстояний. Где градиент близок к нулю, там и будет вейпоинт.
Градиент карты расстояний в точке (i, j) вычисляется примерно так:
Т.о. для всех пикселей карты выполняем этот код (на самом деле только для проходимых пикселей).
Градиент карты расстояний:
Тут, по традиции, RG-каналы кодируют вектор
Зелёные точки — это вейпоинты
Вейпоинты расположились слишком густо. Некоторые из них нужно удалить. В данном проекте минимально допустимое расстояние между вейпоинтами равно 4 пикселя. Поэтому перебираем все пары вейпоинтов и если расстояние меньше допустимого, то удаляем один из них. Естественно пропускаем мостовые вейпоинты, т.к. они никогда не должны быть удалены.
Теперь необходимо соединить эти вейпоинты рёбрами. Перебираем все пары вейпоинтов и соединяем пару ребром тогда, когда оба вейпоинта видимы друг из друга. Для определения видимости используется трассировка: делаем n выборок из карты проходимости вдоль отрезка, соединяющего эти вейпоинты; где n — длина отрезка. Если все выборки дали проходимый пиксель, то соединяем эти два вейпоинта ребром:
Красные линии — это рёбра графа
Получилось слишком много лишних рёбер. Для решения этой проблемы нужно избавиться от треугольников. Как это работает? Возьмём любое ребро с двумя вейпоинтами A и B. Допустим среди соседей A есть вейпоинт C, который в свою очередь является и соседом B. Т.е. образуется треугольник ABC. Самое длинное ребро этого треугольника нужно удалить. То же самое проделываем для всех рёбер:
Некоторые вейпоинты не связаны ребрами с другими — они отфильтровались. Также на картинке видно, что одно ребро прошло по мосту через лаву
Это окончательный граф. Теперь каждый бот может по нему навигироваться.
ИИ бота состоит из стейтмашин, всего их три. Одна стейтмашина задаёт общее состояние бота, а две другие управляют двумя степенями свободы: ноги (перемещение) и корпус. На выходе ИИ бота выдаёт угол поворота и нажатость его клавиш, т.о. единственное отличие бота от реального игрока — персонаж игрока получает ввод от клавиатуры и мыши, а персонаж бота получает ввод от ИИ. Помимо беготни по графу вейпоинтов бот также умеет реагировать на объекты: валяющиеся пушки и пауэрапы, других ботов и некоторые пули. Причем бот реагирует на эти объекты тогда и только тогда, когда они находятся в зоне его видимости: в пределах его «камеры» (как у игрока) и не отгороженные стенами.
В следующем видео демонстрируется ИИ бота по имени Лягуха в поединке с другими ботами на большой карте:
| Алгоритм | Время, мс |
|---|---|
| Генерация текстур частиц | 280 |
| Генерация текстур крови | 190 |
| Генерация реки лавы | 700 |
| Генерация остальной карты | 630 |
| Создание графа | 210 (720) |
| Всего: | 2010 (2520) |
В скобках указано время без использования хеша для вейпоинтов. Этот хеш служит для быстрого поиска вейпоинтов рядом с данным в некоторых алгоритмах построения графа. Без этого хеша в этих алгоритмах перебираются вейпоинты со сложностью O(n 2 ).
Сетевая часть
Сервер написан на node.js с использованием WebSocket. Весь сервер состоит из трёх частей: master-server — http-сервер, раздаёт статику; game-server — соединяется с мастер-сервером и невидим для пользователя, владеет игровыми комнатами; игровая комната — именно к ней коннектится пользователь по веб-сокету, там бегают другие игроки и боты.
При разработке серверной части был применён подход с использованием фейксокетов. Что это такое? Фейксокеты — это два объекта в клиентской части с интерфесами настоящего клиентского и серверного сокета. Они эмулирует работу реальных сокетов. «Клиентский» и «серверный» фейксокет (в кавычках, потому что они оба клиентские, т.е. браузерные) обмениваются данными друг с другом по средством setTimeout (в целях отладки был выбран интервал он же пинг в 30 миллисекунд). Идея в том, что настоящий серверный код можно отдать браузеру, сказать ему, чтобы он работал в режиме фейксокетов. При этом настоящий клиентский код даже не подозревает, что и сервер работает рядом с ним в браузере, он просто посылает данные в сокет (которым является фейксокет) и получает данные с него. Фейксокеты использовались при разработке и отладки серверного кода. Но настоящий online работает через реальные сокеты.
Даже после окончания разработки серверного кода фейксокеты не пропали зря, они остались в проекте и служат в качестве подстраховки, в случае, если игровая комната по каким-либо причинам недоступна. Как это работает? Когда пользователь заходит в игру, то может случиться два варианта: комната свободна и готова принять нового игрока, тогда ему просто отдаётся ip адрес и порт комнаты и он играет онлайн. Второй вариант: если нет мест в комнатах или все комнаты покрешались, тогда мастер-сервер говорит браузеру переходить в режим фейксокетов, также посылает ему весь серверный код (ну не весь, а только код игровой комнаты). И пользователь играет в игру с ботами исключительно локально (ну не повезло ему), при этом пользователь даже не будет знать, что он играет локально (ну это в идиале).
Фейксокеты сыграли огромную роль при разработке серверной части. Т.к. и клиент и сервер запущены в браузере — их очень легко отлаживать, также можно выводить на экран debug-render, т.е. схемотично рендерить объекты именно в тех позициях, где они реально находятся на сервере в данный момент времени. Можно играться с пингом: менять интервал в функции setTimeout, чтобы реализовать всякие предсказания и посмотреть, как они работают на разных пингах (в данном проекте, правда, не было реализовано никаких предсказаний).
Заключение
Помимо всего вышеперечисленного в игре также есть своя консоль, которая вызывается клавишей тильда (с командами, переменными, автодополнением и историей). Ещё есть довольно неплохой генератор ников и система событий.
Полный исходный код игры выложен на github.
Руководство по запуску (у вас должен быть установлен node.js).
Если у вас уже установлен bower, то этот шаг пропускаем, иначе:
В корне проекта выполняем две команды:
Если 80 порт у вас занят, то можно так:
В принципе, этого уже достаточно, можно зайти на localhost (ну или localhost:8800, если сменили порт) и там уже будет игра, правда локальная через фейксокеты. Если нужен честный онлайн, то в другой консольке выполняем:
Теперь можно зайти в игру не только с этого компьютера, но и с любого другого, просто указав в адресной строке ip мастер-сервера. Чтобы узнать локальная ли игра, нужно вызвать консоль игры и выполнить команду status. Ещё одна интересная команда spectator nick, где nick — имя игрока, тогда камера переместится на этого игрока. По умолчанию будет сгенерирована большая карта на 110 игроков. Чтобы генерировать другие карты, нужно выполнить:
Здесь не опечатка, количество дефисов именно такое.
Эта команда сгенерирует маленькую карту, которая описывалась в этом посте. Поддерживаются следующие size: 0 — маленькая карта, 1 — средняя и 2 — большая карта (по умолчанию).
Запускать лучше всего в браузере chrome, в других браузерах не гарантируется корректная работа.