Pull to refresh

Comments 21

UFO just landed and posted this here

Благодарю, исправил!

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

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

С R-tree для синхронизации между игроками мы ещё будем разбираться, так как возможно Cell List, указанный ниже, может быть эффективнее.

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

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

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

Кстати, в рекомендациях к вашей статье есть вот такая 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] ) и (асимптотически) не зависит от размера карты.
Если у вас вдруг не получится прийти к этому ответу самостоятельно, напишите мне - я подробно объясню как его получить.

Благодарю!

Также изучу этот вопрос. Я пробовал использовать этот алгоритм, но немного некорректно.
Я использовал статический размер ячейки, но при этом меняя зону видимости. При этом, если зона видимости задевала какую-то ячейку - то это ячейка так же "рассматривалась" в решении. Для меня оно показалось неэффективным, но, я понял свою ошибку.

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

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

Переборы в погоне за производительностью - изначальное зло, считаю, что в играх нельзя такое использовать.

Также, предполагаю, что этот Ваш пример актуален только для 2D-карт.

Переборы в погоне за производительностью - изначальное зло, считаю, что в играх нельзя такое использовать.

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

Также, предполагаю, что этот Ваш пример актуален только для 2D-карт.

Да, примеры актуальны для 2D карт, но как R-tree, так и R*-tree можно использовать для большего количества измерений. Причем, это явно указывается в конструкторе этой структуры. Естественно, сравнивать данных придется больше, но это всё равно будет эффективнее, чем вычислять трехмерную дистанцию между элементами что называется "в лоб". :)

Ну хорошо, а если игровая карта - куб со стороной в 1 млн делений и игроков 1 млн?

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

Может Вы уже догадались, конечно, каким образом это делать, а то я достаточно скуп на афиширование своих подходов к программированию. Словно что-то отрывается от меня в эти моменты. :-)

Вы не спрашивайте, вы пишите :)

Так и не дождался публикации в Песочнице, разместился в другом месте.

Кроме этого, один коммент в день максимум.

Стимула здесь ноль.

Ну, вы хоть ссылку в личку киньте. А то как-то уж совсем слились. 🤗

Sign up to leave a comment.

Articles