Лать на дерево сфер или искать где-нибудь еще?

Question

Сценарий: большое количество игроков, играющих в игру в реальном времени в трехмерном пространстве, должно быть организовано таким образом, чтобы сервер мог эффективно обновлять других игроков и любого другого наблюдателя за ходом и действиями игрока.То, что объекты «общаются» друг с другом, необходимо отбирать в зависимости от их расстояния друг от друга при моделировании;Это необходимо для сохранения работоспособности сети, работоспособности программиста, а также для того, чтобы сервер позволял обрабатывать небольшие фрагменты всего игрового пространства в мире.

Однако, если у вас 3000 игроков, это приводит к тому, что нужно запустить 3000!Расчеты, чтобы узнать диапазоны между всем.(Google говорит мне, что в конечном итоге это число с более чем 9000 цифрами; это безумие, и его не стоит рассматривать в условиях, близких к реальному.)проблема с их массовой онлайн-игрой от первого лица Planetside 2;он позволил 3000 игрокам играть в общем пространстве и оперативно реагировать в реальном времени.Они, очевидно, сделали это через структуру данных «Sphere Tree».

Тем не менее, я не положительный , это решение, которое они используют, и я все еще задаюсь вопросом, как применить концепцию "Sphere Trees", чтобы уменьшить вычисления дальности для отбраковкив разумных пределах.

Если сферические деревья - не то дерево, на которое нужно лаять, на что еще я должен обратить свое внимание для решения этой проблемы?

(я ac # программист (в основном), но я ищу логичный ответ, а не кодовый)

Ссылки, которые я нашел о сферических деревьях;

http://isg.cs.tcd.ie/spheretree/#algorithms

https://books.google.com/books?id=1-NfBElV97IC&pg=PA385&lpg=PA385#v=onepage&q&f=false

Answer 1

Если объектам нужно взаимодействовать только с объектами, например, на расстоянии <= 100 м, вы можете разделить мир на плитки размером 100 х 100 м (или вокселями) и отслеживать, какие объекты находятся в каждом непустом поле.плитка. </p>

Затем, когда одному объекту нужно «поговорить», вам нужно только проверить объекты максимум в 9 плитках, чтобы убедиться, что они достаточно близко, чтобы их услышать.

Answer 2

Вот несколько моих мыслей: пусть n обозначает общее количество игроков.

1. Думаю, ваша оценка 3000!неправильно.Если вы хотите вычислить все пары расстояний с учетом матрицы фиксированного расстояния, вы запускаете 3000, выбирая 2 операции, в порядке O (n ^ 2 * t), где t - это количество операций, которые вы проводите, вычисляя расстояние между двумя игроками.Если вы строите график, лежащий в основе игроков с весами ребер, равными евклидову расстоянию, вы можете свести это к задаче кратчайших путей для всех пар, что выполнимо с помощью алгоритма Флойда-Варшалла в O (n ^ 3).

2. То, что вы описываете, звучит очень похоже на выполнение запроса диапазона: https://en.wikipedia.org/wiki/Range_searching. Существует множество структур данных, которые могут вам помочь, например деревья диапазонов и деревья kd.