Задача:
1. Есть около 40 тыс. объектов.
2. Иногда в плотном взаимодействии до сотен из них
3. Нужно чтобы это всё быстро знало всё, что нужно о соседях
Чтобы не оперировать абстрактными оценками, конкретные цифры:
1. Размер мира 327680 x 655360 условных единиц.
2. Средний размер игрока - около 10 единиц, NPC (персонаж, управляемый компьютером) - от единиц до сотен.
3. Дальность видимости игроком окружающих объектов - до 6000. NPC видят на меньших расстояниях, чаще - 300..600
Сейчас мир разбит на квадраты стороной в 8192 единицы (coord>>13), каждому из которых приписан массив активных объектов.
Оригинальный алгоритм, который сейчас используется в основной ветке проекта:
- Каждый персонаж содержит полный список всех известных ему объектов.
- Периодически (например, при его перемещении) он получает список всех активных объектов квадрата, где находится + список всех таких объектов в соседних квадратах, измеряет дистанцию для них по обычной hypot-формуле, если в поле его зрения появились новые объекты, вызываются соответствующие новые методы addKnownObject, если объекты вышли за преедлы зоны наблюдения, то - removeKnownObject.
- Аналогично считаются игроки.
- NPC, в поле зрения которых нет игроков, переходят в статус IDLE, у них сбрасываются все "ненужные" данные (например, удаляется объект их ИИ и т.п.)
Минусы:
- У каждого активного объекта требуются большие затраты на хранение данных обо всех других объектах. При разряженном состоянии объектов метод работает хорошо, но в "плотном строю" начинает тормозить - постоянные пересчёты взаимной видимости десятков, а то и сотен объектов почти что кладут тот тред, который этим занимается.
- Хранятся ссылки на объекты. Достаточно забыть удалить объект из памяти одного из NPC, как этот объект становится недоступен для удаления сборщико…
Дальше »»»