Нотатки по темі розробки багатокористувацьких ігр

Нотатки після прочитання книги "Джошуа Глейзер, Санджай Мадхав - Многопользовательские игры. Разработка сетевых приложений"

  1. Таймери ходів
    В стратегіях типу "Age of Empires" використовується сихронізація "таймери ходів" -
    хід має періодичність в 200 мс,
    протягом цього часу всі команди гравця акумулюються і не надсилаються іншим гравцям
    лише після закінчення цього інтервалу команди надсилаються

також існує затримка на два ходи,
тобто команди, створені в інтервалі ходу під номером 50 не розпочнуть виконуватись,
поки не буде отримано команди ходу під номером 52

таким чином затримка реакції на хід гравця досягає 600 мс.

  1. Синхронізація за допомогою генератора псевдовипадкових чисел
    Для того щоб елементи випадковості в грі у всіх клієнтах видавали одинаковий результат
    використовується генератор псевдовипадкових чисел ( Pseudo-Random Number Generator, PRNG ),
    з одинаковим алгоритмом, встановленим початковим значенням та з одинаковою кількістю викликів на всіх клієнтах

  2. Мінімізація та стиснення даних при передачі
    Оскільки ігровий світ може містити дуже багато об'єктів з різноманітними властивостями,
    нам варто подумати над оптимізацією
    ( передавати абсолютно всі дані кожному клієнту може бути не просто недоцільним, але і неможливим )

3.1. Ми можемо передавати лише ті дані, які не збігаються зі значеннями по-замовчуванню
тобто код для моментів, які відбувається найчастіше - записуємо значенням по-замовчуванню і не надсилаємо
в пакеті з очікуваними значеннями інформації об'ємом менше, ніж в пакеті з неочікуваними

3.2. Ми можемо використовувати бітову маску
Це означатиме що ми пересилаємо біт замість байта
для прикладу, якщо ми розробляємо додаток-гру для вк,
то ми обов'язково познайомимось з бітовою маскою при заданні прав додатку/користувачу :

notify = +1, friends = +2, photos = +4, audio = +8, video = +16 і тд
запишемо в іншому вигляді = 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 11111(2) = 16 + 8 + 4 + 2 + 1 = 31(10)

крім того, що ми можемо таким чином передавати список параметрів,
ми можемо добряче зекономити у кількості даних при передачі,
і відповідно - швидкості їх передачі, без загублення ефективності -
у прикладі вище число 31 в десятковій системі числення займає 2 байти (16 біт) в uft8
( загалом, символи в utf8 можуть займати від 1 до 4 байтів, чи й більше )
і те ж число ми можемо передати як послідовність 5 біт, що є економією у порівнянні з 16

також, у травіані гравець на карті бачив дві координати - X та Y,
коли ж клікав на місто сусіда щоб відправити в атаку війська -
дві координати - X та Y перетворювались в одну - Z
якщо я не помиляюсь ( давненько уже не грався ) за наступною формулою
Z = (401 - Y) * 801 + (401 - X)
(чи може (401 - Y), чи може (Y + 401), треба сісти перевірити)
відповідно одній парі значень координат X та Y відповідає лише одне значення Z
( мапа у травіані має вигляд поверхні геометричного тіла тор -
координати X та Y можуть мати значення від -400 до +400, включаючи 0,
-400 переходить в 400 сусідньою клітинкою )

як варіант, таке можна робити для оптимізації швидкості вибірки,
якщо ми не хочемо показувати гравцям id клітинки,
та не хочемо відправляти дві (чи й більше) координат

3.3. Перетворення в формат чисел з фіксованою комою
допустимо у нас є ігрове поле 4000*4000 одиниць,
тобто з координатами X та Y від -2000 до 2000
розглянемо розрахунок кількості варіантів позицій при коефіцієнті точності 0.1 одиниці
(максимальне_значення - мінімальне_значення)/точність + 1 =
= (2000 - (-2000))/0.1 + 1 = 40001

3.4. Стиснення геометричної інформації
наприклад, з координат двох точок рівностороннього трикутника можна вичислити третю

  1. Розсинхронізації та затримки
    Зазвичай при топології клієнт-сервер вважається що сервер є уповноваженим
    ( authoritative ), і якщо клієнт виявить розходження стану ігрового світу з сервером -
    він повинен оновити стан ігрового світу зважаючи на інформацію сервера

4.1. Схема з уповноваженим сервером означає наявність затримки
до отримання зворотньої реакції на дії клієнта
одним з факторів цієї затримки є час передачі/підтвердження
( Round Trip Time, RTT ) - час, зазвичай в мілісекундах,
необхідний для передачі пакетів запиту та відповіді для певного комп'ютера в мережі
в ідеальному випадку RTT = 100 мс чи менше

розглянемо гру з сервером та двома клієнтами - А та Б
клієнт А відправляє пакет з даними до сервера,
сервер обробляє пакет і надсилає відповідь клієнтам А та Б
у цьому сценарії найгірша затримка у клієнта Б виглядає як :
"1/2 RTT клієнта А" + "час обробки сервером команд отриманого пакету" + "1/2 RTT клієнта Б"

у випадку з топологією "точка-точка" всі вузли мають з'єднання один з одним,
клієнт надсилає свої команди кожному з вузлів,
і найгірша затримка виглядає як "1/2 RTT" + не забуваємо про період ходу з п. 1

4.2. Ловимо помилки розсинхронізації
щоб спростити відлов таких помилок,
потрібно записувати в лог час виконання різних етапів з координатами ігрових об'єктів

4.3. Затримки передачі пакетів
передача ->
0 мс - пакет 1
5 мс - пакет 2
10 мс - пакет 3
-> прийом
40 мс - пакет 3
45 мс - пакет 1
65 мс - пакет 2

використання TCP або ж написання власного рівня забезпечуючого цілісність даних до UDP
( з прийомом підтверджень доставки та передачею стану доставки )

  1. Розглянемо приклад інтерполяції на стороні клієнта
    допустимо що у нас RTT ( Round Trip Time )
    між клієнтом A та сервером = 100 мс

в момент 0 ігровий персонаж клієнта A знаходиться в стані спокою
в координаті Z = 0, далі гравець натискає клавішу щоб зробити стрибок
при допущенні що затримка приблизно симетрична,
то через 50 мс, тобто 1/2 RTT пакет з командою від гравця досягне сервера,
сервер розпочне виконання стрибка, присвоїть координаті Z персонажа гравця A значення 1.
далі сервер відправить новий стан гравцю A, з отриманням ще через 50 мс, тобто 1/2 RTT.
клієнт A оновить стан персонажу згідно отриманих даних та покаже на екрані,
тобто з моменту натискання клавіщо до змін на екрані пройде повних 100 мс.

висновок з цього наступний -
результати виконання команди на сервері появляються завжди на 1/2 RTT раніше,
ніж їх побачить гравець,, іншими словами, гравець завжди спостерігає картину,
яка відстає від істинного стану мінімум на 1/2 RTT

При використанні інтерполяції на стороні клієнта ігрові персонажі не переміщуються
стрибкоподібно при отриманні нових даних від сервера, натомість клієнт плавно
інтерполює нови стан протягом певного інтервалу часу.
це називають локальним фільтром сприйняття ( local perception filter )

нехай період інтерполяції (IP), в мс -
той інтервал часу, під час якого клієнт інтерполює старий стан в новий,
період пакету (PP), в мс -
той інтервал часу, під час якого сервер очікує можливість послати новий пакет.
клієнт закінчує інтерполяцію через IP мс після отримання пакета,
відповідно якщо IP менше PP, клієнт закінчить інтерполяцію раніше ніж прийде новий пакет,
і гравець все ще спостерігатиме деякі стрибки;
щоб забезпечити плавність IP повинен бути не менше PP

клієнт "простий термінал" без інтерполяції відстає від сервера мінімум на 1/2 RTT,
клієнт з інтерполяцією відстає від сервера мінімум на 1/2 RTT + IP,
тому величина IP повинна бути мінімальною, тобто IP = PP.

для цього сервер повинен повідомити клієнту як часто він очікує отримання пакетів,
або ж клієнт самостійно вичисляє PP, вимірюючи частоту отримання пакетів.
якщо сервер посилає дані з частотою 15 пакетів в секунду, PP = 66.7 мс,
це означає затримку в 66.7 мс + 1/2 RTT = 66.7 + 50 мс
проте завдяки інтерполяції користувач сприймає гру набагато позитивніше,
таким чином проблема затримок стає не такою гострою

в даному прикладі клієнт не пробує вгадати що робить сервер,
і ніколи не покаже невірні значення,
проте останнє не завжди вірне для наступного прийому

  1. Прогноз на стороні клієнта - екстраполяція
    Щоб показати на клієнті ситуацію, максимально наближену до серверної
    ( без такого відставання як у випадку використання інтерполяції ),
    використовують екстраполяцію -- клієнт на основі отриманої раніше інформації
    може розрахувати-передбачити свіжішу ситуацію та вивести на екран.

клієнт виконує моделювання на додатковий інтервал 1/2 RTT,
під час кожного ходу;
для того щоб виконати екстраполяцію на 1/2 RTT, спочатку необхідно
визначити величину RTT.
оскільки годинники на клієнті та сервері можуть бути розсинхронізовані,
клієнт повинен визначити повний період RTT та розділити на 2
( відправлення сервером пакета з міткою часу не спрацює ).

передача клієнтом ->
0 мс - пакет з міткою часу 0 мс
50 мс - прийом пакету з міткою часу 0 мс на сервері
- відправлення сервером клієнту пакету з отриманою міткою часу від клієнта - 0 мс
100 мс - прийом клієнтом пакета з міткою часу 0 мс на сервері
(100 мс - 0 мс)/2 = 50 мс - визначення клієнтом 1/2 RTT

примітка -
затримки від клієнта до сервера, та від сервера до клієнта -
не обовязково симетричні, 1/2 RTT -- це лише середнє значення

  1. Розрахунки траекторії руху
    Більшість моментів ігрового моделювання мають детерміновану природу,
    тому клієнт може виконувати екстаполяцію користуючись копією серверного коду
    ( модель польоту кулі, відскакування мяча etc -- одинакові на сервері та клієнті ).

існує один момент, з абсолютно недетермінованою поведінкою - дії гравців,
клієнт не знає про що думають гравці по іншу сторону сервера,
які дії вони збираються зробити, як змінити свій напрямок руху та інше,
це ускладнює екстраполяцію.
у даному випадку кращим рішенням клієнта буде робити прогноз,
і далі коректувати його при отриманні даних з сервера.

Розрахунок траекторії руху в мережевій грі - це процес прогнозу поведінки
дій персонажів інших гравців на основі припущення, що вони продовжують
виконути ті ж дії, що і секунду раніше ( оптимістичний алгоритм ).

інколи результати прогнозу виявляються помилковими
нехай період RTT = 100 мс,
частота зміни кадрів = 60 кадрів/секунду
в момент 50 мс клієнт А отримує інформацію
що персонаж гравця Б знаходиться в точці (0,0)
та рухається вздовж осі +X зі швидкістю 1 одиниця в мілісекунду.

оскільки цей стан був актуальним 1/2 RTT назад, клієнт А прогнозує,
що персонаж гравця Б продовжує рухатись у тому ж напрямі з тією ж швидкістю,
і через 50 мс, тобто на момент відображення на екрані гравця А,
повинен бути в точці (50,0). Далі під час 4х кадрів,
до отримання наступного пакету з даними від сервера, клієнт А
продовжує моделювати переміщення персонажа Б в кожному кадрі.
В 4му кадрі в момент 117 мс, клієнт А прогнозує знаходження
персонажа Б в точці (117,0). і в цей час від сервера приходить пакет,
з інформацією про знаходження персонажа Б в (67,0) та його швидкість (1,0).
клієнт А знову виконує екстраполяцію на 1/2 RTT та отримує підтвердження
про співпадіння істинної та вичисленої позиції персонажа Б.

поки все було добре, клієнт А продовжує роботи прогнози,
і в 4му кадрі персонаж Б повинен опинитись в точці (184,0).
і в цей момент він отримує пакет від сервера з наступними даними -
персонаж Б знаходиться в точці (134,0) і його швидкість (0,1)
( ймовірно, гравець Б помітив суперника і вирішив його атакувати ),
моделювання на 1/2 RTT наперед дає в результаті позицію (134,50) -
зовсім не ту, яку передбачав прогноз на клієнті А.
Гравець Б виконав неочікувані, непередбачені дії,
в результаті яких на клієнті А локальна модель тепер містить похибку,
відхилення від істинного стану ігрового світу.

Способи виправити ситуацію:

7.1. Миттєве виправлення ситуації
гравець може помітити стрибкоподібні переміщення об'єктів,
хоча це й краще ніж відображати неточну модель.
Також памятаємо про відставання на 1/2 RTT від істинного стану на сервері,
тому клієнт знову повинен розраховувати позиції об'єктів.

7.2. Інтерполяція
Плавно проводимо корекцію - перемістимо об'єкт на половину відстані від
похибки до реальних значень, почекаємо поки від сервера прийде новий пакет з даними,
продовжимо корекцію ( популярний метод - інтерполяція кубічним сплайном,
зі створенням траекторії, яка відповідає обом позиціям і швидкості для плавного переміщення
з передбаченого стану в скоректований )

7.3. Корекція стану другого порядку
Навіть плавна інтерполяція може викликати неприємні відчуття через
стрімку зміну швидкості практично стаціонарного об'єкту.
Для помякшення змін гра редагує параметри другого порядку,
використовуючи складні математичні розрахунки, щоб зробити
корекцію більш незамітною.

Зазвичай в іграх використовують комбінації методів, в залежності
від типу гри - в шутерах та різних динамічних іграх,
для незначних відхилень використовують інтерполяцію,
для корекції значних - миттєве виправлення,
в менш динамічних іграх використовують корекцію стану
другого порядку, окрім особливо великих відхилень.

Загалом гравець А не може знати, коли гравець Б змінює напрям,
тому для нього імітація виглядає без протиріччя, навіть з урахуванням
прогнозування стану на 1/2 RTT вперед від моменту, отриманого від сервера.

  1. Приховування затримок
    Оскільки вистріли та деякі інші дії створюють сервером,
    а гравець очікує побачити результати на екрані одразу після
    натискання клавіші - необхідні додаткові хитрості.
    Зазвичай такі затримки маскують анімацією -
    спалах при вистрілі, помахи рук мага та інше

  2. Повернення на стороні сервера
    Існує один тип ігрових дій, який особливо важко моделювати
    на клієнті -- застосування зброї миттєвої дії на великих відстанях.
    Коли гравець А вистрілює зі снайперської гвинтівки, перед тим
    спіймавши персонаж противника в приціл - він очікує точне попадання.
    Проте через лаги-затримки-неточності в розрахунках траекторій,
    може виникнути ситуація, коли на серверному екземплярі гри
    суперник знаходився у трішки в стороні від побаченого гравцем А варіанту.

Суть вирішення даної проблеми полягає в поверненні стану гри на сервері
до того, яке спостерігав гравець А. За умови ідеального прицілювання
попадання буде 100%.

З цією метою в методи прогнозів варто внести декілька поправок:

9.1. Використання інтерполяції на стороні клієнта без розрахунку
траекторій персонажів гравців по іншу сторону сервера
Сервер повинен точно знати що спостерігали гравці в будь-який момент часу. Період інтерполяції повинен точно співпадати з періодом пакету, довжину якого визначає сервер.

9.2. Використання прогнозування і перегравання ходів для персонажу локального гравця

9.3. Додавання стану, який спостерігає клієнт в кожен пакет при відправленні на сервер

9.4. Збереження на сервері координат всіх об'єктів , зв'язаних з декількома останніми ходами(кадрами)
При отриманні пакета від клієнта, сервер повинен знайти у себе тих два кадри,
між якими клієнт виконав інтерполяцію, і використовуючи
відсоток виконання інтерполяції з пакета, отриманого від клієнта,
для перевірки-повернення всіх відповідних об'єктів в стан,
у якому вони були на момент вистрілу,
далі прокласти пряму лінію від персонажа, щоб визначити точку попадання.
Повернення на стороні сервера гарантує, що у випадку точного прицілювання
гравець попаде в ціль на сервері.

Втім, при наявності великих затримок гравець Б, у персонажа якого стріляли,
первий час може думати що він встиг втекти від гравця А
( для прикладу, сховався за кутом ), а далі сервер робить перерахунок,
і гравець Б отримує повідомлення про попадання та розчарування.

  1. Область видимості та релевантність об'єктів
    З метою оптимізації гравцю показують лише ті об'єкти, з якими він
    взаємодіє чи може розпочати взаємодіяти через хід-два (пряма видимість).

10.1. Статичні зони
В світах MMORPG релевантними будуть тільки об'єкти,
які знаходяться в одній статичній зоні з гравцем.

Для прикладу, гравець знаходиться в місті,
іншою зоною може бути ліс, печери etc
відповідно немає смислу гравцям в місті посилати
повідомлення про гравців в лісі.

Щоб не перенавантажувати певну статичну зону як окремий сервер,
має смисл після певної кількості активних гравців
телепортувати нових гравців в паралельну статичну зону

10.2. Піраміди видимості
В 3D-іграх область поля зору має вигляд усіченої піраміди
як представлення області ігрового світу, спроектованого
на двохвимірну площину для відображення на екрані.
Це використується в шутерах, гонках та ін.

Якщо використовувати тільки область поля зору,
об'єкти за спиною гравця вважають невидимими.
це може стати проблемою при допущенні бажання гравця
миттєво розвернутись на 180 градусів.
Особливо якщо за спиною в наявності персонаж суперника.

Одне з рішень -- використовувати два підходи -
і на основі піраміди видимості,
і на основі визначення відстані.

10.3. Потенціально видимий набір об'єктів (Potentially Visible Set, PVS)
Цей авгоритм використовується для змінної релевантності
в гонках, при поворотах,, в шутерах при наявності обмеженого простору.
Для подібних ігр також можна використовувати подібну методику під назвою "портали".
Кожна кімната вважається окремою областю видимості, кожне вікно чи двері -
порталом. Піраміда видимості порталу можна об'єднати з областю поля зору,
і таким чином зменшити кількість релевантних об'єктів.

Аналогічно в таких іграх можна використовувати прийоми іерархічного усічення,
такі як двійкове розбиття простору (Binary Space Partition, BSP), =
квадродерево (quadtree) чи октодерево (octree). Кожен з цих прийомів
розбиває об'єкти ігрового світу на деревовидні структури.

10.4. Релевантність невидимих об'єктів
Існують моменти, коли гравцю необхідно донести інформацію
про об'єкти, яких він не бачить, наприклад -
звук взриву гранати. Одним з рішень буде надсилати команду
про звук взриву опираючись на відстань а не видимість.

  1. Сегментування та клонування серверного середовища
    Ідея полягає у виконанні обробки ігрової моделі
    одночасно на декількох серверах, для випадків коли
    між собою взаємодіють 8 - 16 гравців.

Сегментування може полягати в розбитті ігрового світу на континенти,
континентів - на кімнати і тд.
Деякі ігри при зростанні нагрузки можуть телепортувати гравців
в інші кімнати чи континенти, Eve online просто сповільнює темп роботи
( режим розтягування часу, time dilation ), такий прийом дозволяє
серверу рівномірно працювати з усіма клієнтами.

При клонуванні екземплярів гри невеликі групи граців можуть
проходити завдання по окремих сценаріях, без взаємодії з рештою гравців.

  1. Безпека та бани
    Гравці (деяка частина) багатокористувацької гри можуть і будуть намагатись
    отримати перевагу будь-якими способами, включаючи різноманітні махінації.
    Розумним рішенням будуть гнучкі фільтри відстежування дій користувачів
    та використання хвиль банів замість одиночних банів -
    спочатку певний час збирається статистика, аналізуються параметри,
    далі - неочікуваний бан всіх махінаторів, і цикл повторюється знову.

  2. Важливою частиною успішного ігрового проекту є наявність
    цілої купи різних нагород-медалей, бонусів квестів зі щедрими винагородами,
    рейтингами та інфографікою.

  3. Також у книзі доволі детально розписано мережеву архітектуру протоколів IPv4,
    IPv6, багаторівневу модель TCP/IP, маршрутизацію та інше