Краткая версия
Каков эффективный способ обнаружения столкновений на большой открытой карте, где объекты генерируются на лету?
Длинная версия
В настоящее время я работаю над воссозданием первой игры для Android, которую я когда-либо делал (https://play.google.com/store/apps/details?id=com.Joey_Ant.Lite&feature=search_result#?t=W251bGwsMSwyLDEsImNvbS5Kb2V5X0FudC5MaXRlIl0.
Я перестраиваю его с нуля и добавляю около сотни новых функций.
Описание игры: пользователь будет управлять колонией муравьев с подземной картой на основе сетки и надземным открытым игровым полем. У муравьев будет ИИ, и муравьев может быть большое количество. (Это означает, что мне нужно оптимизировать все дерьмо.) Карты будут очень разнообразными. (Я планирую создать средство для создания карт и позволить пользователям создавать и загружать карты онлайн.)
Итак, на карте, полной большого количества объектов и других муравьев/существ, какой оптимальный способ обнаружения столкновений? Я не могу перебирать все другие объекты для обнаружения столкновений, так как это должно было бы происходить для каждого существа и потребляло бы слишком много процессорного времени.
Что я рассмотрел
Сетка: создание произвольного объекта сетки. Объект сетки будет создавать подобласти (фактическая сетка) и каждый раз, когда существо «думает». он обновил бы объект сетки ссылкой на себя. Затем существо запросит у объекта сетки другие объекты в своей сетке. Мы надеемся, что это значительно сократит количество необходимых проверок. Но накладные расходы для этого могут быть больше. Эта сетка может быть полезна для того, чтобы позволить существам обнаруживать других существ в своей общей области, поскольку решения ИИ будут зависеть от других объектов и существ в этой области.
Занятые сетки. По сути, то же самое, что и описанный выше параметр сетки, только объект сетки создается объектами. Скажем, у меня есть 3 объекта (A, B и C). Когда я инициализирую объект A, он создает ячейку сетки с заданной шириной и высотой. Объект B инициализирован, но находится в той же области, что и объект A, поэтому он добавляет себя в эту область сетки. Объект C инициализируется за пределами области, поэтому он создает ячейку сетки для своего местоположения. Если объект C входит в ячейку, в которой находится объект A, его предыдущая ячейка уничтожается. Думаю, вы могли бы представить это как выдувание пузырей.
Любые идеи о лучшем способе сделать это?
