Вопрос, касающийся самоу узкой на сегодня части игрового сервера-эмулятора LineageII.
Есть игровой мир размеров 327680x655360 (в будущем может расти).
Есть ~40 тыс. объектов.
Нужно быстро получить список объектов, находящихся на расстоянии не более R от произвольного выбранного.
Сейчас используется такая методика: весь мир делится на NxM регионов (~300x400, где-то). Для каждого из них есть список находящихся в нём объектов.
Перебираем все регионы, попадающие в круг радиусом R, в них перебираем все объекты, измеряя расстояние до каждого из них. Составляем список тех, расстояние до которых подходит.
...
Выходит чудовищно неэффективно (в некоторых случаях до 60% всех затрат сервера уходит на этот механизм).
Есть ли более оптимальные методы? Нутром чую, что есть, но Кнут таких задач не рассматривал :D
...
Не очень важно, но конкретная реализация сделана на Java. Памяти под улучшение алгоритма можно отдать мегабайт до 200 (сейчас потребляет около 30, наверное).