Обзор сетевых и многопользовательских компьютерных игр, часть первая

15.10.2012

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

Введение

За последние двадцать лет, последовательно появились три различных класса распределенных интерактивных приложений реального времени:

  1. Военные симуляции
  2. Сетевые виртуальные среды (СВС)
  3. Многопользовательские компьютерные игры (МКИ)

Центр внимания научных исследований сместился с военных симуляций (1980), через СВС (1990) к МКИ в настоящее время (см. рис.1).  Кроме того индустрия развлечений сделала серьезные инвестиции в МКИ, мобильные и онлайн-игры в целом.

Рисунок 1. История распределенных интерактивных приложений.

В литературе встречается различная терминология. Например, до недавнего времени сетевые виртуальные среды называлась, как правило, Распределенной Виртуальной Средой (РВС), которая потом была заменена на Совместную Виртуальную Среду (СВС). Мы приняли термин СВС, так как он включает в себя как РВС, так и СВС. Для военных разработок предпочитается слово «симуляция», потому как оно означает нечто большее, чем СВС (например, логистическая симуляция). Отношения между играми и симуляциями не такие однозначные, как кажется на первый взгляд. Конечно, есть игры являющееся симуляциями (например, такие игры как Football Manager) и есть игры, действия которых происходят в виртуальных средах (например, авиационные тренажеры и шутеры от первого лица). Тем не менее, чем более абстрактными становятся игры, тем меньше и меньше они становятся симуляциями (см. рис.2).

Рисунок 2. Связь между симуляциями, виртуальными средами (ВС) и компьютерными играми. В то время как ВС, моделируют (возможно реальные) среды,  компьютерные игры на обязательно являются симуляциями или виртуальными средами.

Сеть является главным понятием, когда мы рассматриваем играбельность МКИ. Физическая платформа налагает ограничения по ресурсам (например, пропускная способность и задержки), отражающие базовую инфраструктуру (например, кабели и «железо»). Как правило, существует не так много возможностей повлиять на физическую платформу, за исключением, возможно, инвестировать средства в новое оборудование. Логическая платформа основывается на физической, и ее выбор, играет ключевую роль в дизайне МКИ. Она обеспечивает архитектуру коммуникаций, обмена данными и контроля. Архитектура коммуникаций определяет логические связи между узлами сети. К примеру, в архитектуре P2P (peer-to-peer,  одноранговая сеть) в сети объединены множество равных узлов, тогда как в архитектуре клиент/сервер – один узел работает как сервер и вся связь между узлами осуществляется через него. Архитектура контроля и данных определяет, как именно информация хранится и обновляется в узлах. Например в централизованной архитектуре, только один узел содержит данные, в то время как в реплицируемой архитектуре каждый узел имеет свои копии.
В этой статье рассматриваются особенности логической платформы. Мы оглянемся назад и представим обзор научно-исследовательских работ проведенных в последние двадцать лет.

Методы

Давайте для начала вспомним наиболее распространенные методы по уменьшению требований к пропускной способности для интерактивных приложений реального времени.

Объединение и сжатие пакетов

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

Потому как мы сжимаем сетевые пакеты, стоить, так же, обратить внимание на различные методы сжатия, соотносящиеся к данным в пакете. Внутреннее сжатие применяется к информации, содержащейся в одном пакете без ссылок на другие, ранее переданные. Таким образом, оно подходит при использовании не очень надежных протоколов, таких как UDP (User Datagram Protocol). С другой стороны, внешнее сжатие может использовать информацию, которая уже была передана и, следовательно, принята и доступна в приемнике. К примеру, мы можем передавать разницу или информацию о переходе, которая, вероятно, потребует меньше бит чем, собственно, полная информация.  Мы можем так же передать ссылочные указатели на ранее переданные данные, если эти данные возникнут снова. Внешнее сжатие рассматривает большее количество данных в каждый момент времени, таким образом, оно может лучше учитывать избыточность потока информации. Следовательно, оно может дать лучшую степень сжатия, нежели внутреннее сжатие. Однако из-за ссылок на предыдущие пакеты, внешнее сжатие требует более надежного протокола передачи.

Объединение пакетов, снижает требование к пропускной способности, путем слияния и передачи нескольких пакетов в одном большом. Таким образом, накладные расходы на заголовки пакетов уменьшаются. Экономия пропускной способности может быть значительной и зависит от размеров данных в исходных пакетах, размеров заголовков пакетов и количества объединенных пакетов. Например, размеры заголовков UDP/IP и TCP/IP, соответственно – 28 и 40 байт.

Существуют два основных подхода для настройки количества объединенных пакетов: по тайм-ауту и по заполнению. При первом подходе, все пакеты проинициированные  до определенного времени, будут объединены. Этот подход гарантирует верхнюю границу задержки, вызванной объединением. В этом случае экономия полосы пропускания зависит от скорости инициации пакетов и в худшем случае не будет никакой экономии в случае отсутствия пакетов, или же инициации только одного в установленный период времени. Во втором подходе всегда объединяются фиксированное количество пакетов. Поскольку передача объединенного пакета откладывается до прихода определенного количества пакетов, нельзя гарантировать что отправка не будет задержана. При этом, хоть и есть определенная экономия полосы пропускания, но длинные задержки могут помещать работе пользователей. Ограничения обоих подходов могут быть нивелированы при их объединении. При этом гибридном подходе, пакеты будут объединяться всякий раз при выполнении одного из условий – либо срок передачи истекает, либо набралось достаточно пакетов для слияния.

Управление интересами

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

Аура может быть точно выражена с помощью формул, как круг вокруг парусника показывающий  наблюдаемую область.Однако с реализацией могут возникнуть сложности — необходимы сложные вычисления.

Пространство может быть разделено так же на статические, дискретные клетки. Для парусника будет представлять «интерес» клетки которые пересекаются его аурой. Фильтрация на основе клеток проще в реализации, но менее точна чем на основе формул. Клетки могут быть также и шестиугольными.

Аппроксимация ауры — фактически прямоугольная рамка. Вычисление проще чем с применением формул, и фильтрация лучше чем при использовании клеток.

Проще говоря, аура, это подпространство где происходит взаимодействие. Таким образом, когда ауры двух игроков пересекаются, они могут быть в курсе действий друг друга.

Управление интересами с аурой всегда симметричны: если ауры пересекаются, обе стороны получают сообщения друг о друге. Тем не менее аура может разделятся на фокус и нимб, которые являются представлением наблюдателя об объекте и его перспективе. Таким образом осведомленность требует чтобы внимание игрока пересекалась с нимбом другого игрока. При использовании фокусов и нимбов возможно построить более тонкий класс фильтрации сообщений, при этом можно дать возможность не быть симметричным (см. рис. 4). Ауры, фокусы и нимбы могут быть модифицированы адаптерами, для настройки взаимодействия игроков. Например в ВС могут быть введены инфракрасные бинокли и инструменты камуфляжа.

Рисунок 4. Игра в прятки. Нимб прячущегося человека меньше чем у ищущего. Ищущий человек не знает о прячущемся. Вместо этого ищущий видит убежище прячущегося так как нимб ищущего не пересекается с фокусом прячущегося.

В фильтрационной схеме области интересов, узлы передают изменения своего состояния менеджеру рассылок. Менеджер рассылок также получает информацию об экспресс-состоянии области интересов (или фокусов) узлов. После чего менеджер передает узлу только необходимую информацию (то есть согласованную с узлами рассылку). Фильтры площади интересов можно назвать внутренними фильтрами, потому что в них используются конкретное содержание пактов обновления для определенного узла, которые им необходимо получить. Эта фильтрация обеспечивает детальную информацию, но обработка пактов может потребовать значительных затрат времени. Внешние фильтры определяют получателей пакетов только на основе его сетевых атрибутов (например, по адресу). Внешние фильтры обрабатываются быстрее внутренних, и это можно сделать в самой сети.

При выборе стратегии группового размещения объектов, каждый объект имеет свою собственную группу многоадресной рассылки, которым и передает все свои обновления. Выделенные серверы хранят записи групповых адресов, так что узлы могут подписываться в соответствующие группы. С помощью нескольких групп многоадресной рассылки один объект может обеспечить детализированное распространение обновлений, а их абоненты могут лучше вычислять их фокусы.

В стратегии регионального размещения групп, виртуальная среда делится на регионы, которые имеют свои группы многоадресной рассылки. Все объекты в регионе передают обновления в соответствующий групповой адрес. Как правило, объекты при этом приписаны к группам соответствующим их собственному и соседним регионам. При пересечении объектом границы области он должен получать информацию о текущем состоянии многоадресной группы, от каталог-серверов. Кроме классификации объектов основанной на их расположении в Виртуальной Среде, возможны и другие их атрибуты (например, тип объекта или команды).

Счисление координат

Один их подходов к снижению использования сети для отправки пакетов обновления. Для обеспечения согласованности (или, по крайней мере, некого его разумного подобия) мы должны как-то компенсировать отсутствие обмена информации между пакетами обновления. Особенно в случае информации о местоположении, методы счисления координат оказались весьма успешными. В счислении координат отсутствующая информация вычисляется с применением апроксимационных методов (методов приближения). На основе ранее полученной информации узел предсказывает движение конкретного объекта. Вычисленное состояние объекта используется в приложении до тех пор, пока от исходного узла не будет получена новая информация. В зависимости от точности вычислительных методов, приближенное местоположение может находиться на некотором расстоянии от фактического. Чтобы избежать рывков при движении, при получении новой информации о местоположении применяются сходимость алгоритма для сглаживания передачи. Таким образом счисление координат состоит из двух частей: метода прогнозирования и метода сходимости.

Наиболее распространенным методом прогнозирования является использование производных многочленов. В случае с позиционированием они более естественно интерпретируют скорость, ускорение и толчок (рывок). Если мы используем нулевую производную полиномов, мы получаем информацию только о позиции и, следовательно, не получаем никакой выгоды. В случае использования первой производной многочленов, в дополнении к позиции объекта передается и скорость. Скорость – заметно повышает точность предсказаний. Для дальнейшего повышения точности, мы можем добавить в передаваемые условия значение ускорения. Этот прогнозирование с помощью многочлена второго порядка является наиболее популярной методикой. Тем не менее, высшие производные повышают риск появления неточных прогнозов, так как погрешность прогнозирования повышается с повышением порядка: небольшая неточность в вычислениях может привести к существенным ошибкам. Кроме того производные многочленов высшего порядка приводят к увеличению вычислительных нагрузок при прогнозировании. Передаваемые при этом дополнительные условия, так же потребляют наши ограниченные ресурсы полосы пропускания.

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

Вместо передачи высших степеней производных многочлена, они могут быть аппроксимированы в приемном узле. При вычислении позиции на основе истории счисления координат, протокол передает только абсолютные значения координат, а мгновенные скорости и ускорения аппроксимируются с использованием последних обновлений. Кроме того в узле источника, можно применить ту же методику прогноза что и в узле назначения. Когда узел источника определяет что расстояние между реальным и прогнозируемым состояниями превышает заданный порог, источник передает обновления пакетов. Порог может быть динамически изменен в соответствии с расстояниями между объектами. Идея состоит в том, что чем дальше находится объект, тем меньше обновлений он требует. Кроме того количество обновлений во время «жизненного цикла» могут быть рассчитано (т.е. временный интервал между двумя последовательными обновленными состояниями). Объясняется это тем, что может быть установлен указанный уровень обновлений во время «жизненного цикла», который лимитирует скорость передачи сообщений.

Когда узел получает сообщение об обновлении, предсказанная позиция объекта, скорее всего будет отличаться от позиции основанной на последней информации. Объект при этом, должен быть перемещен на новую позицию и метод приближения определяет как эта коррекция будет произведена. Хороший метод сходимости корректирует ошибки быстро и незаметно (см. рис.5). Простейшим методом является метод нулевой конвергенции, когда объект переводится на новую, предсказанную позицию. Тем не менее это может привести к раздражающим рывкам движения. Лучшим методом является использование линейной сходимости, где будущие точки сходимости определяются предсказанием нового пути. В этом случае объект перемещается вдоль прямого пути от текущей точки схождения, в течении периода конвергенции.

Рисунок 5. Иллюстрация счисления координат. Закрашенные кружки, это полученная информация о положении объекта p и скорости V, при заданном времени t. Не закрашенные кружки это предсказанное положение объекта на данный момент времени. В момент времени T=2, когда прогнозируемое положение объекта будет (4, 4), поступает новая информация, что в момент времени T=1 (из-за задержки) фактическое положение объекта было (3, 1) и скорость была (4, 2). Вместо того чтобы перемещать объект в новую предсказанную позицию (7, 3), сразу, точка схождения рассчитывается исходя из нового предсказанного пути на 0,5 секунд позже. В течении этого периода конвергенции объект движется вдоль гладкого линейного сходящегося пути, к новому, следующему далее, предсказанному пути.

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

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

Заполнен: NetworkingОбщееТуториалы
Присвоен тэг:

avatar

Об Авторе ()

Обычная... *)

Комментирование закрыто.

Наверх