Комментарии 21
Скажите, пожалуйста, так в итоге вы улучшили мультиплеер у вашего друга? Стала ли игра потреблять меньше ресурсов на сервере?
Спасибо за статью! А можно чуть подробнее о
создание нескольких деревьев для поиска, чтобы искать элементы в разных горутинах в нескольких деревьях
Правильно я понимаю, что несколько деревьев в данном случае нужны не для оптимизации поиска, а именно для оптимизации вставки элементов?
Кстати, в рекомендациях к вашей статье есть вот такая https://habr.com/ru/post/319096 в которой упоминается B-tree индекс на основе Z-order. Не пробовали сравнивать по производительности с ним? Есть ощущение, что для случая с постоянно изменяющимися данными, именно он должен позволить достичь в целом лучшей производительности.
Правильно я понимаю, что несколько деревьев в данном случае нужны не для оптимизации поиска, а именно для оптимизации вставки элементов?
Как для поиска, так и для вставки элементов.
Для вставки - да. Время, затрачиваемое на каждый следующий элемент растет, так что делить скорее даже нужно, чем можно.
Для поиска - тоже, так можно параллельно запускать несколько горутин (в случае языка Go), а потом через каналы соединить данные поиска, которые были получены из всех деревьев.
В итоге, буквально можно искать данные параллельно в нескольких деревьях в разных потоках и, соответственно, не терять в производительности при большом количестве данных, разделенных на равные части.
Кстати, в рекомендациях к вашей статье есть вот такая https://habr.com/ru/post/319096 в которой упоминается B-tree индекс на основе Z-order. Не пробовали сравнивать по производительности с ним? Есть ощущение, что для случая с постоянно изменяющимися данными, именно он должен позволить достичь в целом лучшей производительности.
Обязательно проверю и сравню, благодарю :)
Возможно, Вам будет интересно посмотреть на алгоритм Cell List, используемый в методе молекулярной динамики. Решается та же задача, сложность O(N). В начальной реализации пространство разбивается на ячейки, размером с видимость, проверка идёт только по объектам в своей и соседних ячейках.
Поддерживаю предыдущего оратора! Если верно предположение, что не более k игроков одновременно окажутся в зоне видимоти друг друга и M - минимальное число кругов видимости, которыми можно покрыть граф карты (кридоры, стены и другие статические непрозрачные объекты учитываются), то сложность решения задачи в первый раз есть
O( (k^2)*N*log M ) в худшем случае. Обновления имеют ту же O-большое сложность, но фактически при правильной реализации стоить должны подешевле.
И добрый совет всем работающим программистам: прочтите наконец хотя бы одну книгу по теории алгоритмов. Хорошая маленькая книга, например,: Ахо, Хопфорт, Ульман "Алгоритмы. Построение и анализ" - там не все, но прям все для дела и не надо. Главное уловить суть и набраться шаблонов мышления, тогда многие алгоритмы вы сами сможете изобрести быстрее, чем найдете их в интернете, или, по крайней мере, будете примерно представлять, что искать.
Благодарю за совет, записал себе в ближайшее чтение :)
На здоровье. А я вот ошибку нашел в своем прошлом ответе. Если области карты подгружать динамически, только когда какой-либо игрок туда входит, и отбрасывать , когда в области нет ни одного игрока, то сложность уведомления всех игроков об их соседях по зоне видимости оценивается как
O( max[(k^2)*N и N*log N] ) и (асимптотически) не зависит от размера карты.
Если у вас вдруг не получится прийти к этому ответу самостоятельно, напишите мне - я подробно объясню как его получить.
Даже вот так O( max[(k*N и Nlog N] )
Благодарю!
Также изучу этот вопрос. Я пробовал использовать этот алгоритм, но немного некорректно.
Я использовал статический размер ячейки, но при этом меняя зону видимости. При этом, если зона видимости задевала какую-то ячейку - то это ячейка так же "рассматривалась" в решении. Для меня оно показалось неэффективным, но, я понял свою ошибку.
Мне кажется более стандартное решение в виде BSP-дерева было бы лучше, и было бы интересно посмотреть сравнение результатов R*-дерева с ним
Переборы в погоне за производительностью - изначальное зло, считаю, что в играх нельзя такое использовать.
Также, предполагаю, что этот Ваш пример актуален только для 2D-карт.
Переборы в погоне за производительностью - изначальное зло, считаю, что в играх нельзя такое использовать.
Тут я с Вами абсолютно согласен. Просто у нас используется буквально разработка 2004 года, от которой очень тяжело отказаться. Сам же разработчик буквально бросил её пару лет назад, никого не слушая. А сейчас те, кто занимаются на основе этого мультиплеера, страдают и пытаются реверсить и внедрять свой код сами с большим трудом.
Также, предполагаю, что этот Ваш пример актуален только для 2D-карт.
Да, примеры актуальны для 2D карт, но как R-tree, так и R*-tree можно использовать для большего количества измерений. Причем, это явно указывается в конструкторе этой структуры. Естественно, сравнивать данных придется больше, но это всё равно будет эффективнее, чем вычислять трехмерную дистанцию между элементами что называется "в лоб". :)
Ну хорошо, а если игровая карта - куб со стороной в 1 млн делений и игроков 1 млн?
Если хотите, я мог бы сделать статью, в которой объясняю, как работать с задачами, подобно Вашей, безо всяких переборов и поисков, и что никак не затрагивает производительность системы, независимо от размерности карт.
Может Вы уже догадались, конечно, каким образом это делать, а то я достаточно скуп на афиширование своих подходов к программированию. Словно что-то отрывается от меня в эти моменты. :-)
R*-tree в Go, немного геймдева и поиска элементов в пространстве