Контейнер для доступа к содержимому по 2d / 3d координатам

Question

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

Теперь есть несколько способов хранения объектов, которые позволяют эффективно выбирать подобласть. Самый простой способ - это, вероятно, разделить карту на сетку; выбор единиц в области будет включать в себя выбор только тех частей сетки, которые затронуты, и выполнение мелкозернистых плиток сетки координат, которые не находятся на 100% внутри области.

Что мне не нравится в этом подходе, так это ответ "Насколько большими должны быть плитки сетки?" Слишком большой, и эффективность может стать реальной проблемой. Слишком маленький, и сетка занимает тонны памяти, если игровой мир достаточно велик (и может стать нелепым, если игра 3D). Может даже не быть подходящей золотой середины.

Очевидное решение вышеизложенного состоит в том, чтобы создать большую сетку с неким интеллектуальным подразделением, таким как псевдо-древовидная структура. И именно в этот момент я точно знаю, что я далеко в преждевременной оптимизации. (Тогда есть правильные динамические квадраты / октре, но это еще сложнее для кода, и я даже не уверен, что он будет работать лучше.)

Итак, мой вопрос : существует ли стандартное решение для вышеуказанной проблемы? Что-то в строках контейнера STL, которое может просто хранить любой объект с координатой и получать список объектов в определенной области? Это не должно отличаться от того, что я описал выше, если это что-то, что было продумано и признано «достаточно хорошим» для начала.

Бонусные баллы, если в Python есть реализация алгоритма, но C тоже подойдет.

Answer 1

Первым шагом к написанию практической программы является признание того, что выбор некоторых констант основывается на реальных соображениях, а не на трансцендентных математических истинах. Это особенно относится к игровому дизайну / кодированию типов симуляторов мира, где вы никогда не получите ничего, если будете настойчиво пытаться оптимально моделировать реальный мир. : -)

Если все ваши объекты будут иметь достаточно однородный размер, я бы просто выбрал размер сетки, пропорциональный среднему размеру объекта, и согласился бы с этим. Это самое простое - и имейте в виду, что простота принесет вам некоторую скорость, даже если вы в конечном итоге будете искать в нескольких объектах больше, чем это абсолютно необходимо!

Все становится намного сложнее, если ваши объекты сильно различаются по размеру - например, если вы пытаетесь использовать один и тот же двигатель для борьбы с пулями, мышами, людьми, гигантскими монстрами, транспортными средствами, астероидами, планетами и т. Д. Если это так В этом случае общепринятый (но некрасивый) подход состоит в том, чтобы использовать разные «режимы» игры в зависимости от типа ситуации, в которой вы находитесь. Если не считать этого, одной из идей может быть использование большой сетки с подразделением двоичного дерева. ячеек сетки после того, как они накапливают слишком много мелких объектов.

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

Answer 2

Я ничего не знаю о программировании игр, но я бы предположил (основываясь на интуиции и том, что я читал в прошлом), что полная сетка станет очень неэффективной для больших пространств;вы потеряете как в хранилище, так и во времени, потому что вы расплавите кеш.

Контейнеры STL по сути одномерны.Да, такие вещи, как set и map позволяют вам определять произвольные отношения сортировки, но они по-прежнему упорядочены только в одном измерении.Если вы хотите добиться большего успеха, вам, вероятно, нужно использовать квад-дерево, kd-дерево или что-то в этом роде.

Answer 3

Вот бесплатная онлайн-книга , которая ответит на ваш вопрос. В частности, ознакомьтесь с главой 18, посвященной обнаружению и пересечению столкновений.