При игре в локальной вычислительной сети с задержками можно иногда примириться.
Для интернета характерна задержка от 0.15 сек до 1 сек. Задержки локальной сети находятся в пределах 0.04 сек, что тоже может быть много. Есть еще задержка из-за неготовности принимающей стороны начать немедленную обработку, она может быть занята, к примеру, рендером.
В данной статье дается обзор архитектур и алгоритмов синхронизации в рамках сетевых игр, приводятся их достоинства и недостатки.
Предполагается, что читать статью будет программист, уже почти написавший однопользовательскую игру и желающий узнать, как туда добавить сетевые возможности. Требуется также общее представление о сети вне игростроительной тематики.
Архитектуры передачи данных
Существует две основные архитектуры передачи данных — клиент-сервер и одноранговая (рис. 1а, б).
Рис. 1 Архитектуры передачи данных
В одноранговой архитектуре все узлы сети равноправны и обмениваются сообщениями непосредственно друг с другом [1].
Достоинствами одноранговой архитектуры являются низкое время задержки, отсутствие одной точки сбоя, масштабируемость (при использовании адекватной наложенной сети [2][3][4][5][6]). Недостатками одноранговой архитектуры являются больше возможностей для жульничества [7] (по сравнению с клиент-серверной архитектурой), необходимость в точке встречи (rendezvous point) и механизме позднего присоединения (late-join mechanism).
Одноранговую архитектуру часто упрекают в повышенном использовании пропускной способности канала, однако бывают условия, когда она меньше нагружает канал, чем клиент-серверная. Одноранговая сеть с широковещательной доставкой – одна из таких схем, она широко применялась в старых играх и может быть единственно знакомой читателю. Будет вредно, если он опровергнет частность, возгордится и станет считать себя более подготовленным, чем есть на самом деле.
В клиент-серверной архитектуре один из узлов сети становится сервером, через который происходит обмен сообщениями. Остальные узлы являются клиентами. Для каждого клиента обмен сообщениями с сервером становится наиболее важным элементом [1].
Сервер в целях повышения масштабируемости может быть представлен сетью серверов (server network) [1] (рис. 1в), также называемый кластером.
Достоинствами клиент-серверной архитектуры являются возможность агрегации сообщений, затрудненность жульничества, простота реализации. Недостатками являются наличие одной точки сбоя (сервер), более медленная (по-сравнению с одноранговой архитектурой) доставка сообщений, трудно достигаемая масштабируемость.
Кроме вышеупомянутых архитектур, предлагаются разнообразные гибридные подходы, совмещающие одноранговую и клиент-серверную архитектуру, такие как [8][9][10].
Архитектуры хранения и управления данными
Архитектура хранения и управления данными определяет, где хранятся данные и каким образом они могут быть обновлены.
Рис. 2 Архитектуры хранения и управления данными
В централизованной архитектуре (рис. 1а) один узел управляет всеми объектами. Централиованная архитектура представляет собой базу данных, которая поддерживает игру целостной все время выполнения. [1]
В распределенной архитектуре, напротив, каждый узел управляет своей частью объектов (рис. 2б), из-за этого появляется необходимость поддерживания целостности. Узел содержит копии объектов узлов, в которых он заинтересован.
Собственный объект узла называется первичной копией (primary), копия объекта другого узла — вторичной копией (replica) или прокси (proxy). Эти термины можно отнести и к распределенной, и к централизованной архитектурам.
Алгоритмы синхронизации
Алгоритмы синхронизации (consistency maintenance algorithms) оперируют над событиями. Событие изменяет состояние какого-либо объекта (объектов), вследствие чего могут удалятся одни объекты и возникать другие объекты и события. Событие может быть создано локально (например, игрок использовал предмет), либо получено от другого узла. Узлом (node) называется исполняемый файл игры, работающий на компьютере пользователя.
Состояние игры — это состояние объектов, составляющих игровой мир, на определенный момент времени.
Алгоритмы синхронизации производят упорядочивание событий, т. е. «следят», чтобы все события выполнялись в порядке их возникновения на всех узлах [11]. Исходя из этого, алгоритмы синхронизации можно разделить на консервативные (conservative) и оптимистические (optimistic).
Консервативные алгоритмы не позволяют нарушить целостность состояния игры с самого начала — события не выполняются до тех пор, пока не будет гарантирована целостность.
Оптимистические алгоритмы выполняют взаимодействие сразу при возникновении, не гарантируя целостность, а при нарушении таковой (которое, к тому же, следует обнаружить) используется откат (rollback) до момента возникновения события. Затем выполняется само событие и все следующие за ним [11].
Таким образом, при использовании оптимистических алгоритмов взаимодействия между объектами происходят с наименьшей задержкой, но процесс отката может вызвать раздражение и неприемлемое замешательство у игроков [12]. Очевидно, что с увеличением задержки сигнала, вероятность нарушения целостности растет, так же растет и вероятность необходимости отката.
Консервативные алгоритмы
Lockstep Synchronization
Алгоритм синхронизации Lockstep (LS) [13] работает по протоколу «остановись-и-жди»: узел ждет сообщений от других узлов, потом просчитывает следующий кадр, шлет сообщения и снова ждет [12].
Недостаток этого алгоритма заключается в том, что он может вызвать замедление геймплея, если задержка сигнала больше частоты кадров.
Pairwise Rapid Agreement
В случае взаимодействия между первичной и вторичной копиями производится асинхронный вызов удаленной процедуры (Remote Procedure Call, RPC) [14]. Удаленный узел, являющийся владельцем вторичной копии, «применяет» изменение на своей первичной копии объекта и рассылает изменившееся состояние другим узлам. Этот алгоритм называется Pairwise Rapid Agreement.
Например, если один игрок стреляет в другого игрока, то узел первого шлет RPC второму. По получении вызова второй узел вычитает значение нанесенного урона из поля «здоровье» объекта игрока, затем рассылает другим узлам обновленное состояние изменившегося объекта.
Оптимистические алгоритмы
Dead Reckoning
Передвижение непрерывно, но его возможно обновлять только дискретно. К тому же, всегда существует задержка, и получаемые данные являются устаревшими. Следовательно, необходим способ построения непрерывной траектории из дискретных обновлений и предсказывания будущей траектории.
Таким способом является Dead Reckoning (DR). Он заключается в вычислении траектории объекта (в виде скорости и положения в пространстве), основываясь на известной ранее траектории, скорости и времени, когда известная траектория была актуальной [15].
DR позволяет предсказывать траектории объектов, таким образом скрывая задержку сигнала (из-за чего его также называют предсказыванием (prediction)). Конечно, существует предел предсказывания, зависящий от требуемой отзывчивости игры [16].
Как алгоритм синхронизации, DR — это сочетание передачи и предсказывания состояния [11]. Иными словами, каждый узел обменивается с другими узлами данными о траекториях первичных копий и предсказывает траектории вторичных. В централизованной архитектуре сервер производит передачу состояния, а клиенты — предсказывание.
Данные о траектории могут передаваться либо в каждом сообщении, либо по превышении порога ошибки, в зависимости от предсказуемости траектории. Первый способ лучше всего подходит для индетерминированной траектории вроде передвижения игрока, а второй — для детерминированной траектории, например, полета ракеты или пули.
Предсказывание может быть основано на интерполяции или экстраполяции [17], в зависимости от требуемой точности. Экстраполяция может включать в себя применение физической модели игры [17][18] (например, одного и того же кода как на стороне клиента, так и на стороне сервера). Под точностью понимается точность воспроизведения траектории. К примеру, линейная интерполяция обеспечивает сглаженную, но неточную, траекторию. Это особенно заметно, когда траектория изменяется хаотически.
Было предложено множество способов улучшения точности предсказывания, например, алгоритмы [19][20][21]. Они основываются на планировании посылки обновлений траектории (message scheduling) и проставлении временных меток (timestamping). Для установки временных меток необходима синхронизация часов между узлами, что является трудной задачей ввиду неточности внутренних часов ПК и разнородных задержек в Интернете.
Другие оптимистические алгоритмы
В целом, оптимистические алгоритмы довольно сложны и все еще находятся в «незрелом» состоянии, несмотря на активное изучение многими научными группами. Одной из целей этой статьи было охватить наиболее практичные алгоритмы, но необязательно часто использующиеся на практике. Тем не менее, интересующиеся могут посмотреть [22][23][24].
Заключение
В данной статье были рассмотрены архитектуры передачи данных, архитектуры хранения и управления данными. Также было дано определение алгоритмов синхронизации и приведена соответсвующая терминология. Были кратко описаны некоторые из алгоритмов синхронизации.
Автор надеется, что информация, изложенная в статье, даст читателю общий взгляд на проблемы сетевых игр и их решения.
Благодарности
Автор выражает благодарность Дмитрию Заботину (zabotin_dima@mail.ru) за точные замечания, без которых статья была бы менее полной.
Также автор хочет поблагодарить Nicu Buculei (http://clipart.nicubunu.ro/), John Olsen (http://web.mac.com/johnny_automatic/Photos/About_Me.html), sagar_ns (http://openclipart.org/media/people/sagar_ns) за предоставление изображений, использованных для оформления иллюстраций.
Ссылки
J. Smed et al, 'Aspects of Networking in Multiplayer Computer Games ', http://staff.cs.utu.fi/~jounsmed/papers/AspectsOfMCGs.pdf
K. Moon et al, 'Efficiently Maintaining Consistency Using Tree-Based P2P Network System in Distributed Network Games ', http://www.springerlink.com/index/h1k248602r456v87.pdf
N. Matsumoto et al, 'A Scalable and Low Delay Communication Scheme for Networked Virtual Environments '
K. S. Malik, 'Proximity: A Scalable P2P Architecture for Latency Sensitive Massively Multiplayer Online Games', http://www.cs.ubc.ca/grads/resources/thesis/Nov05/Kamran_Malik.pdf
B. Knutsson et al, 'Peer-to-Peer Support for Massively Multiplayer Games', http://www.ieee-infocom.org/2004/Papers/03_2.PDF
N. Baughman et al, 'Cheat-Proof Playout for Centralized and Serverless Online Games', http://www.cs.duke.edu/courses/fall05/cps296.1/papers/cheat.journal.pdf
S. Aggarwal et al, 'Authority Assignment in Distributed Multi-Player Proxy-based Games', http://ww2.cs.fsu.edu/~christof/CS%20Site/About%20Me_files/aggarwal06.pdf
M. Assiotis, V. Tzanov, 'A Distributed Architecture for Massive Multiplayer Online Role-Playing Games' http://pdos.csail.mit.edu/6.824-2005/reports/assiotis.pdf
A. Bharambe, 'Scalable and Secure Architectures for Online Multiplayer Games', http://www.cs.cmu.edu/~ashu/thesis/proposal.ps
M. Mauve, 'Consistency in Replicated Continuous Interactive Media', http://www.cn.uni-duesseldorf.de/publications/library/Mauve2000b.pdf
K. Moon et al, 'Reducing Bandwidth Requirements of Consistency Maintenance Algorithms in Distributed Network Games', http://www98.griffith.edu.au/dspace/handle/10072/11492
N. Baughman, B. Levine, 'Cheat-Proof Playout for Centralized and Distributed Online Games', http://prisms.cs.umass.edu/brian/pubs/baughman.infocom01.pdf
J. Pang, F. Uyeda, J. Lorch, 'Scaling Peer-to-Peer Games in Low-Bandwidth Environments', http://research.microsoft.com/workshops/IPTPS2007/papers/PangUyedaLorch.pdf
H. Zhang , 'The effect of delay on network games', http://www.cs.umu.se/education/examina/Rapporter/HaishuZhang.pdf
F. Bernier, 'Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization', http://www.resourcecode.de/stuff/clientsideprediction.pdf
T. Sweeny, 'Unreal Networking Architecture', http://unreal.epicgames.com/Network.htm
S. Aggarwal et al, 'Fairness in Dead-Reckoning based Distributed Multi-Player Games'
S. Aggarwal et al, 'Accuracy in Dead-Reckoning Based Distributed Multi-Player Games', http://www.sigcomm.org/sigcomm2004/workshop_papers/net610-aggarwal.pdf
S. Singhal, 'Effective Remote Modeling in Large-scale Distributed Simulation and Visualization Environments'
E. Cronin et al, 'An Efficient Synchronization Mechanism for Mirrored Game Architectures ', http://warriors.eecs.umich.edu/games/papers/netgames02-tss.pdf
S. Burgess, M. Katchabaw, 'Design and Implementation of Optimistic Constructs for Latency Masking in Online Video Games', http://www.csd.uwo.ca/~katchab/pubs/gameonna2006_optimism.pdf
S. Ferretti et al, 'An Optimistic Obsolescence-based Approach to Event Synchronization for Massively Multiplayer Online Games'
Комментариев нет:
Отправить комментарий