Хеширование 2D/3D пространства для быстрого поиска объектов
Часто бывает нужно обрабатывать достаточно много объектов, разнесенных в пространстве, причем нужно иметь возможность искать самый близкий объект (или даже несколько) к конкретной точке. Например, любая игра в стиле Tower Defense, где нужно для каждой башни находить ближайшего врага из сотен или даже тысяч бегущих мимо. Как это можно сделать?
Полный перебор
Самый простой способ - это полный перебор всех объектов в определенном радиусе от указанной точки и нахождение ближайшего. Это рабочий вариант, пока количество объектов не перевалит за несколько сотен и полный перебор станет занимать значительную часть времени. Вторая проблема - что, если нам нужно для следования игромеханикам получать не один, а два или даже три ближайших объекта (например, для башни, бьющей отдельными лучами по трем ближайшим врагам)? Придется делать выборку из всех объектов полным перебором, потом сортировать - это дополнительный удар по производительности. Если вспомнить, что у нас могут быть десятки башен, для которых надо выполнять такой поиск - нагрузка возрастает кратно.
Деревья
Можно разбивать пространство на иерархические 2д/3д-деревья (quadtree/octtree), где каждый вышестоящий (родительский) блок содержит 4 или 8 (в случае 3д-пространства) вложенных блока. Глубина вложенности подбирается под каждый конкретный случай, чтобы в каждом блоке было не более N-объектов. В процессе заполнения принимается решение - не слишком ли много в текущем блоке объектов и не стоит ли его разбить на 4/8 более мелких с перераспределением уже содержащихся объектов.
Этот подход имеет проблемы как при сборке дерева (перебалансировка), так и при поиске нескольких ближайших объектов
к точке (нахождение соседних блоков по всей иерархии).
Хеширование пространства
Можно разбить все доступное пространство на равные блоки (в 2д это будут клетки, в 3д - кубы) и добавлять в каждый объекты, если их координаты попадают внутрь блока. Отличие от дерева - все блоки лежат на одном уровне иерархии, а каждый блок имеет свой адрес-“хеш”, вычисляющийся по определенным правилам. Регулярность сетки и равные размеры каждого блока дают возможность быстрого доступа к его соседям через расчет их адресов-хешей без перебора иерархии от корня в случае деревьев.
Возникает проблема потребления памяти, ведь мы должны обеспечивать возможность добавления объектов внутрь любого блока, а значит каждый блок должен иметь внутренний список добавленных объектов. Эту проблему можно решить через пул списков - изначально все блоки пустые и не содержат списков объектов, а при попытке добавления объекта в блок выполняется проверка - есть ли в нем список для объектов, и если нет - запрашиваем его из пула. В итоге мы сильно экономим память в случае разреженного размещения объектов в пространстве, не тратя ее на заведомо пустые области.
К этому моменту мы можем определить список блоков, находящихся в нужном радиусе поиска, а значит - можем простым перебором проверить дистанции до объектов, которые содержатся в этих блоках. Если нам нужен только самый ближний объект - пробегаем по полученным спискам и ищем ближний. Если нужно несколько - сохраняем их в коллекцию и сортируем потом по дистанции.
Пример
Пакет Leopotam.SpaceHash реализует поддержку хеширования конечного 2д и 3д пространства для float-координат. “Конечное пространство” означает, что мы должны явно указать его габариты (минимальные и максимальные), все объекты вне этого пространства будут попадать в пограничные блоки и ухудшать время поиска в них (не рекомендуется так делать, но допускается).
Создадим хеш для 2д пространства (для 3д есть точно такой же класс с таким же апи):
1 | SpaceHash2<string> spaceHash = new SpaceHash2<string> ( |
В этом случае у нас все указанное пространство будет автоматически разбито на 10х10=100 блоков.
Тип string в обобщении определяет тип идентификатора объекта и может быть любым - это может быть какой-то числовой индекс в массиве, номер ECS-сущности или даже ссылочный тип с описанием данных. В примере для простоты используется строка в качестве имени объекта.
Добавляем объекты:
1 | // Добавляем "объект1" по координатам (1f, 1f). |
А теперь давайте поищем добавленные объекты. Например, найдем все объекты в радиусе 5f от точки (0f, 0f):
1 | List<SpaceHashHit<string>> res = spaceHash.Get (0f, 0f, 5f); |
На выходе получим список из одного элемента, у которого поле Id будет равно объект1.
Точно так же можно проверить заведомо пустой результат:
1 | res = spaceHash.Get (20f, 0f, 1f); |
Или результат с несколькими точками:
1 | res = spaceHash.Get (18f, 18f, 10f); |
На выходе получим список из двух элементов, отсортированных по дистанции от ближнего к дальнему: поле Id будет равно объект3 у первого и объект2 у второго соответственно (объект3 ближе к запрашиваемой точке, чем объект2).
Пакет расчитан на работу без дополнительных аллокаций при регулярном поиске путем переиспользования списков. Так же поиск потокобезопасен и при желании возможен из нескольких потоков.
Актуальные версии пакетов доступны в закрытом telegram-сервере для vk/boosty-подписчиков.
