Это может быть грубое предложение, и я уверен, что оно может быть улучшено, но вот мысль:
Во-первых, сохраняйте свои позиции таким образом, чтобы вы могли получать к ним доступ в постоянное время для определенного объекта. Например, если вы хотите получить к ним доступ напрямую через ваши сущности, вы можете сохранить структуры позиций в списке / векторе и дать каждой сущности указатель / ссылку на свою позицию.
Во-вторых, сохраните указатель / ссылку на объект или GUID в той же структуре, что и позиция объекта, чтобы можно было идентифицировать объект на основе объекта позиции. (Возможно, сейчас есть лучший способ, о котором я не думаю.)
В-третьих, используйте некоторые принципы развертки и сокращения / сортировки и развертки (распространенные в 3D-играх): сохраняйте два отсортированных списка / вектора позиций, один из которых отсортирован в направлении x, а другой - в направлении y. Один может содержать объекты фактической позиции, а другой может содержать указатели / ссылки. Эти списки могут использовать временную согласованность, поэтому затраты на их сортировку не должны быть слишком высокими, если только нет большого быстрого и хаотичного движения.
Преимущество этой настройки состоит в том, что действительно легко определить, где каждый объект находится относительно друг друга. Хотите знать, сколько объектов находятся в пределах 10 квадратов от Билли-эльфа в любом направлении? Проверяйте позицию Билли и итерируйте вперед / назад по обоим спискам, пока не достигнете сущности на расстоянии более 10 клеток в каждом направлении.
Если вам интересна эта концепция, ищите сортировку и развертку (также известную как развертка и сокращение). Вы будете использовать только первую половину алгоритма, но он используется для обнаружения столкновений в широкой фазе практически в каждом основном механике трехмерной физики, так что вы знаете, что он должен быть быстрым в целом. ;) Вокруг него много информации, так что вы наверняка найдете и более сложные идеи реализации. (Например, мне не нравится косвенность, связанная с сохранением отсортированного списка указателей / ссылок на структуры позиций; работа с фактическими структурами более эффективна с точки зрения кэширования, но тогда вам нужно обновить позицию в двух местах, если вы хотите использовать временную согласованность с постоянными массивами. Кто-то еще мог подумать о более умном дизайне, который ускользает от меня прямо сейчас.)
РЕДАКТИРОВАТЬ: Я бы прокомментировал идею Эрика Х, но мой представитель недостаточно высок. Я просто хотел сказать, что его идея звучит очень хорошо для вашей игры, особенно если у вас будет много сущностей, плотно упакованных на одной клетке или в небольшом районе. Если бы я был тобой, я бы, наверное, попробовал это до идеи подметания и обрезки. Однако это должно сопровождаться хорошо спланированной стратегией управления памятью: Если у вас есть словарь расположений листов, которые наивно сопоставляются с векторами сущностей, у вас будет много памяти, выделяемой и освобождаемой, когда сущности переходить от одной плитки к другой. Вместо этого вы захотите реализовать его идею как нечто более похожее на словарь / список связанных ссылок:
Ключи словаря будут позициями листов, а словарь будет возвращать один указатель на узел связанного списка. Этот узел будет частью связанного списка всех объектов на одной плитке. Всякий раз, когда объект перемещается из одной плитки в другую, он будет удален из своего текущего связанного списка и добавлен в новый. Если сущность перемещается в пустую плитку, она будет находиться в связанном списке самостоятельно, и ее следует добавить в словарь. Когда последний объект перемещается из тайла, запись для этого тайла должна быть удалена из словаря. Это позволит вам перемещаться по объектам без постоянного динамического выделения / освобождения, поскольку вы просто обновляете указатели (и словарь, вероятно, будет довольно эффективно использовать память).
Обратите внимание, что вам не нужно хранить полноценные объекты в связанных списках; Вы можете легко создать свой связанный список из легких объектов (содержащих указатель или идентификатор GUID для фактической сущности).