R*-tree в Go, немного геймдева и поиска элементов в пространстве +13


Приветствую, уважаемые читатели Habr!

Сегодня я хотел бы рассказать об интересном подвиде одного алгоритма, о котором Вы могли возможно забыть!

Начну с предыстории...

У меня довольно интересный опыт в разработке модификаций для мультиплееров (далее - МП) трехмерных игр на серверной и клиентской части для разных игровых проектов, как на языках JS, так и Lua, которые использовались на сервере и клиенте.

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

И, пока всё это происходило, я понял, что знания все же необходимо подтягивать, а сами собеседования помогут направить меня в нужное русло. И, после одного из собеседований с вопросами об индексах, я решил углубиться в них (помимо бездумного расставления btree и hash через EXPLAIN ANALYZE).Так я наткнулся на интересный для себя индекс в PostgreSQL - GiST.

Что из себя представляет индекс GiST? Вспомним, что GiST - это подвид структуры R-tree, которая позволяет быстро обращаться к данным в пространстве.

Когда я это прочитал, мне стало невероятно интересно, как в игровых модификациях, с которыми я работал, обстоят дела с пространственным поиском?

Как с этим обстоят дела в той сфере, где я работаю:

Там, где я работаю, существует один из старейших МП, разработанный ещё в 2004 году. Исходников у меня не было, поэтому мне стало интересно, как решали эту проблему тогда и, возможно, сейчас.

Объяснение для тех, кто совсем не связан с играми.
В каждом МП, где большое количество игроков (а я работал с МП, где средний онлайн на одном сервере более 300-500, а порой и 1000 человек). Представляем себе большую карту и понимаем, что игрокам не обязательно видеть друг друга на большом расстоянии.

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

Обратившись к своему хорошего другу, с кем я продолжаю работать в этой сфере, и скинув ему интересную статью, он подсказал мне, как действительно устроен стриминг в этом МП. Он смог покопаться в закрытом исходном коде и найти конкретно то место, которое меня интересовало. Ответ меня поразил и смутил. Разработчик МП буквально перебирал каждого игрока для каждого игрока.

Я был в шоке, но в то же время понимал, почему разработчик этого старого МП ограничился всего 1000 игроков в пределах одного сервера. Если бы он поставил хотя бы ограничение в 1500 игроков, то сложность поиска игроков в зоне стрима увеличилась бы уже буквально в 2.25 раз. И, судя по метрикам, даже текущее решение съедало не мало так ресурсов.

Решение уже близко

Вооружившись современным инструментов в виде языка Go я решил провести искусственное нагрузочное тестирование с алгоритмами R-tree и квадратным (каждый игрок для каждого игрока) линейным поиском.

Что я сделал в логике приложения на Go?

На сервере есть сущности с данными:

  • Координаты X и Y

  • Массив указателей на игроков, которые находятся в зоне видимости этой сущности

Данные области видимости и "поля" для поиска:

  • Размер поля в X и Y (2000x2000 у. е.)

  • Размер стороны области видимости

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

Синхронизация в логике Go обновляется раз в секунду.

У следующих сущностей будут случайно сгенерированная позиция в пределах поля.

Теперь к самим показателям, начнем с квадратичного линейного поиска:

Количество сущностей, единиц

Область видимости, у. е.

Время обновления стриминга для всех игроков, мсек

1000

200

72.5

2000

200

295

4000

100

1150

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

Как это выглядит в коде:

for i := 0; i < len(players); i++ {
  for k := 0; k < len(players); k++ {
    p1 := players[i]
    p2 := players[k]
    if(dist(p1, p2) > visibleDistance) {
      continue;
    }
    p1.playersInStream = append(p1.playersInStream, p2)
  }
}

Сложность квадратичного линейного поиска здесь буквально O(n^2), и мы можем её сократить. Например, если один игрок уже видит второго, то и второй игрок видит первого. Следовательно, нам не нужно перебирать весь список игроков внутри второго цикла. В итоге, можем представить новый код уже вот так:

for i := 0; i < len(players); i++ {
  for k := i; k < len(players); k++ {
    p1 := players[i]
    p2 := players[k]
    if(dist(p1, p2) > visibleDistance) {
      continue;
    }
    p1.playersInStream = append(p1.playersInStream, p2)
    p2.playersInStream = append(p2.playersInStream, p1)
  }
}

Довольно банальное решение, и я был крайне удивлен, что разработчик мультиплеера к этому не пришел. Показатели O(n^2)/2:

Количество сущностей, единиц

Область видимости, у. е.

Время обновления стриминга для всех игроков, мсек

1000

200

35

2000

200

150

4000

100

580

Уже лучше, но даже с учетом затрат в виде 580 из 1000 мсек чисто на синхронизацию - это невероятно много, потому что в том же потоке работает ещё и основная логика сервера. В общем, это решение так же не подходит...

И, наконец, гвоздь программы - R-tree!

К моему счастью (огромное спасибо dhconnelly) я буквально сразу нашел библиотеку rtreego, которая реализовывала структуру R-tree в языке Go.

Количество сущностей, единиц

Область видимости, у. е.

Время обновления стриминга для всех игроков, мсек

1000

200

16

2000

200

55

4000

100

110

Я был невероятно удивлен, ведь показатели времени обновления зоны стрима оказались от 4 до 10 раз меньше, чем то, что используется сейчас!

Что удивительно, в моей сфере есть более современный мультиплеер, у которого есть примерно аналогичная проблема, но утверждать я, к сожалению, ничего не могу, так как нет доступа к исходному коду от слова СОВСЕМ.

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

Причем здесь вообще R*-tree?

Я уже радовался победе, что сделал что-то полезное, как друг, которому я скидывал эту же статью обратил внимание, что там написано R*-tree, а не R-tree в некоторых местах.

Как мы поняли, R*-tree и R-tree - это две разных структуры данных, первая является подвидом второй. Параллельно я решил покопаться у себя в показателях, заведя свой код с отладкой, и понял, что 70-80% времени занимает вставка и удаление.

Я решил сравнить R-tree и R*-tree хоть в каких-нибудь бенчмарках, чтобы убедиться, что, возможно, есть алгоритм ещё эффективнее.

Поискав бенчмарки R*-tree в сравнении R-tree и наткнувшись на:

На что мне удалось наткнуться, пока я искал данные об R*-tree
  • Delphi в статье;

  • R*-tree в Boost (туда я пока не хочу);

  • Статью про нейробиологию от 2020 года научного деятеля в Швеции;

  • Имплементация на Java вместе с бенчмарками и показателями эффективности структуры.

Имплементация на Java с показателями оказалась ровно тем, что мне нужно, но...
Оказалось, что показатели вставки в R*-tree гораздо медленнее, но поиск гораздо эффективнее. Мне стало резко интересно, а есть ли R*-tree такое в Go? И такого не оказалось.

И тут мне невероятно сильно захотелось это воссоздать и сравнить на практике...

Так что же такое R-tree? И в чём разница R-tree и R*-tree?

После таких историй пора приступить к делу и понять, в чём разница между R*-tree и R-tree простыми словами

R-tree - это древовидная структура, которая разбивает пространство на области.

R*-tree - это подвид структуры дерева R-tree, которое балансирует эти данные, чтобы поиск по этому дереву был эффективнее.

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

Возьмем пример обычного R-tree:

Визуализация структуры R-Tree по Гуттману
Визуализация структуры R-Tree по Гуттману

Синими квадратами обозначаются поддеревья или ветки.

Красными квадратами обозначаются "листья" этих поддеревьев, в которых хранятся элементы.

Черные точки - те самые элементы в этом дереве.

Теперь же возьмем пример R*-tree:

Топологическое дерево R*-Tree
Топологическое дерево R*-Tree

Все данные остаются теми же самыми, но мы буквально можем заметить визуальные отличия:

  1. Поддеревья и ветки располагаются так, чтобы не накладываться друг на друга. Уменьшается перекрытие веток.

  2. Все ветки или поддеревья стараются быть минимальных размеров. Уменьшается площадь листьев и веток.

Как раз, в этом и есть главная задумка R*-tree!

При абсолютно каждой вставке элемента происходит цикл, который перебирая все возможные элементы, старается уменьшить площадь веток и перекрытие веток, таким образом, упрощая в будущем поиск по этой структуре данных!

Как мы понимаем, за счет таких манипуляций, растёт и цена (то есть, время) вставки элемента. Причем, если дерево становится больше, то и элементов нужно перебирать больше.

Ну и зачем оно вообще нужно: что одно, что второе?

Буквально, на примере разработки игровых модификаций, я пришел к таким выводам:

Где можно использовать R-tree?

  • Игровые мультиплееры с большим количеством элементов;

  • Любая реал-тайм карта с множеством элементов, которые перемещаются (например, карта автомобилей с такси)

Где можно использовать R*-tree?

  • Статические карты хоть с миллионом миллионов элементов (например, это можно использовать в игровом стриминге статических объектов);

  • Любые гео-данные, которые читаются в несколько раз чаще, чем заполняются (например, карта целого города или области)

Псевдо-бенчмарки

Я решил не использовать стандартное решение в виде бенчмарков Go и буквально на своих примерах показать время обработки запросов. Я решил взять приблизительные размеры карты той игры, в которой я работал, и актуальный размер зоны стрима.

  • Область в условных единицах: 8000x8000

  • Область видимости: 500x500, элемент находится в центре зоны видимости

  • Позиции элементов: генерируются случайно

  • Показатели: средние из 3-5 прогонов

Тип поиска

R-tree

R*-tree

Вставка 1000 элементов

18.5 мсек

330 мсек

Вставка 100 тысяч элементов

2.91 сек

37 сек

Вставка 1 млн элементов

37.8 сек

6 мин 30 сек

Поиск среди 1000 элементов (1 тыс. итераций)

1.5 мсек

0.2 мсек

Поиск среди 100 тысяч элементов (1 тыс. итераций)

140.1 мсек

8 мсек

Поиск среди 1 млн элементов (1 тыс. итераций)

1.4 сек

40 мсек

Интересная идея: невероятно эффективным (и простым в реализации, особенно в случае языка Go) решением является создание нескольких деревьев для поиска, чтобы искать элементы в разных горутинах в нескольких деревьях. Простыми словами - чтобы достичь максимальной эффективности - нужно найти для себя максимальное количество элементов в среднем на дерево и делить деревья на равные части. Буквально, как партицирование в БД :)

Самое важное (ссылка на мою реализацию R*-tree в Go):

Конец

Невероятно огромное спасибо за внимание!

Если Вы знаете более эффективные решения для игр или гео-данных на вставку или чтение, я буду очень рад почитать в комментариях!

Дополнительно

Ссылка на реализацию rtreego (обычного R-tree), которую я взял за основу и переделал её под R*-tree.




Комментарии (7):

  1. Alexrook
    /#24362830 / +1

    как на языках NodeJS

    Поправьте. Нет такого языка - Node.JS, есть JavaScript, на котором и пишут под Node.JS.

  2. Vest
    /#24363532

    Скажите, пожалуйста, так в итоге вы улучшили мультиплеер у вашего друга? Стала ли игра потреблять меньше ресурсов на сервере?

  3. amphasis
    /#24363680

    Спасибо за статью! А можно чуть подробнее о

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

    Правильно я понимаю, что несколько деревьев в данном случае нужны не для оптимизации поиска, а именно для оптимизации вставки элементов?

    Кстати, в рекомендациях к вашей статье есть вот такая https://habr.com/ru/post/319096 в которой упоминается B-tree индекс на основе Z-order. Не пробовали сравнивать по производительности с ним? Есть ощущение, что для случая с постоянно изменяющимися данными, именно он должен позволить достичь в целом лучшей производительности.

  4. azTotMD
    /#24363734 / +2

    Возможно, Вам будет интересно посмотреть на алгоритм Cell List, используемый в методе молекулярной динамики. Решается та же задача, сложность O(N). В начальной реализации пространство разбивается на ячейки, размером с видимость, проверка идёт только по объектам в своей и соседних ячейках.

    • Sergey_Kovalenko
      /#24363828

      Поддерживаю предыдущего оратора! Если верно предположение, что не более k игроков одновременно окажутся в зоне видимоти друг друга и M - минимальное число кругов видимости, которыми можно покрыть граф карты (кридоры, стены и другие статические непрозрачные объекты учитываются), то сложность решения задачи в первый раз есть
      O( (k^2)*N*log M ) в худшем случае. Обновления имеют ту же O-большое сложность, но фактически при правильной реализации стоить должны подешевле.

      И добрый совет всем работающим программистам: прочтите наконец хотя бы одну книгу по теории алгоритмов. Хорошая маленькая книга, например,: Ахо, Хопфорт, Ульман "Алгоритмы. Построение и анализ" - там не все, но прям все для дела и не надо. Главное уловить суть и набраться шаблонов мышления, тогда многие алгоритмы вы сами сможете изобрести быстрее, чем найдете их в интернете, или, по крайней мере, будете примерно представлять, что искать.

  5. DyadichenkoGA
    /#24367064

    Мне кажется более стандартное решение в виде BSP-дерева было бы лучше, и было бы интересно посмотреть сравнение результатов R*-дерева с ним