Взрывной рост расчёта видимости (AOI, N²) Area-of-interest explosion

ID причины sp-aoi · Основной ответственный Команда разработки · Разработка сервера

Открыть карточку в основной версии с иллюстрациями и экспериментами →

Если выяснять, кто кого видит, сравнивая всех со всеми, то при росте числа игроков в 10 раз расчёты растут в 100 раз.

Почему Расстояние сравнивается между всеми персонажами, или карта разбита на сетку, но вокруг одной ячейки собираются сотни игроков → Следствие Для 100 игроков около 10 000 сравнений, для 1 000 около 1 000 000 → На экране Там, где все собрались вместе (мировой босс, осада), время тика взлетает: слоумо, микрофризы

Симптомы: Слоумо, Микрофризы
Факторы: Остановка
У кого: Одна локация или канал, Весь сервер
Когда: При наплыве игроков
Ответственные: Основной ответственный Команда разработки · Разработка сервера
Команда разработки: задачи: Разбить мир на сетку или области и сравнивать только соседей, реже обновлять дальние объекты, ограничить число игроков, которых видит один игрок.
Цифры для ориентира: Если на каждую пару игроков с учётом сравнения расстояния и обновления списков видимости заложить 0,1 µs (одна десятимиллионная секунды), то для 1 000 игроков (около 1 000 000 пар) это 100 ms на тик. Вдвое больше бюджета 20-тикового сервера (50 ms).
На графике: Растёт вслед за онлайном и нагрузкой · время тика сервера, число игроков в одном месте
Где смотреть: Вывести на один график число игроков по зонам и каналам и время тика, а также отдельно измеренное время расчёта видимости внутри тика. Если отдельного замера нет, смотреть долю CPU по функциям игрового процесса через perf top -p
Подтверждает: Когда игроков в одном месте становится вдвое больше, время тика растёт почти в 4 раза, а большую часть процессорного времени занимают функции расчёта видимости и расстояний
Опровергает: Если время тика растёт пропорционально числу игроков или велика доля функций отправки и сериализации, дело во взрывном росте рассылки или в затратах на сериализацию и сжатие
Чем проверить: Нужны логи и метрики игрового сервера или клиента

Источники

Comparing Interest Management Algorithms for Massively Multiplayer Games ACM
Статья NetGames 2006 (авторская версия). Подход с измерением расстояний между всеми парами не справляется с ростом числа игроков, а при разбиении на квадратную сетку проверяются только 9 соседних ячеек
Replication Graph in Unreal Engine Epic Games
Стандартный подход, при котором для каждого актора перебираются все подключения, при большом числе игроков и акторов упирается в CPU сервера. В MMORPG и подобных играх мир делят на сетку и переиспользуют списки по ячейкам
perf-top(1) — Linux manual page perf
В реальном времени показывает долю CPU работающего процесса (-p) или потока (-t) по функциям (символам)

Смотрите также

Тот же слой: L9 Процесс игрового сервера

Причины с тем же симптомом (Слоумо) на других слоях

Лавина догоняющих шагов при фиксированном таймстепе L1 Процесс игрового клиента
Перекос балансировки и ошибки health check L5 Сетевое оборудование ЦОД
Избыток потоков и переключение контекста L7 ОС сервера (ядро)
Троттлинг CPU в контейнере (квота CFS) L7 ОС сервера (ядро)
Всплески задержки из-за управления питанием сервера (C-state, управление частотой) L7 ОС сервера (ядро)
Плановые задания L7 ОС сервера (ядро)
Изменение производительности после обновления ОС, ядра, драйверов или прошивки L7 ОС сервера (ядро)
Блокирующая отправка из-за медленного клиента L8 Сокеты и протоколы

Карточка в основной версии с иллюстрациями и экспериментами