Быстрый алгоритм расчета линии видимости в игре RTS

Question

Я делаю простую игру RTS. Я хочу, чтобы он работал очень быстро, потому что он должен работать с тысячами единиц и 8 игроками.

Все, кажется, работает безупречно, но кажется, что линия визирования является узким местом. Это просто: если вражеский юнит ближе, чем любой диапазон LOS моего устройства, он будет виден.

В настоящее время я использую довольно наивный алгоритм: для каждого вражеского юнита я проверяю, видит ли кто-нибудь из моих юнитов его. Это O (n^2)

Итак, если есть 8 игроков, и у них есть 3000 единиц каждый, что означало бы 3000 * 21000 = 63000000 тестов на игрока в худшем случае. Это довольно медленно.

Подробнее: это глупое простое 2D-пространство RTS: нет сетки, юниты движутся по прямым линиям везде, и нет столкновения, чтобы они могли перемещаться друг с другом. Таким образом, даже сотни единиц могут находиться на одном и том же месте.

Я хочу как-то ускорить этот алгоритм LOS. Есть идеи?

EDIT:

Так дополнительные детали:

• Я имел в виду один игрок может иметь даже 3000 единиц.
• мои юниты имеют радары, чтобы они по направлению ко всем направлениям одинаково.

Answer 1

Используйте spatial data structure для эффективного поиска единиц по местоположению.

Кроме того, если вы только заботиться, является ли устройство видимым, но не какой прибор углядел, вы можете сделать

for each unit 
    mark the regions this unit sees in your spatial data structure 

и есть:

isVisible(unit) = isVisible(region(unit)) 

Очень простая пространственная структура данных сетка: вы накладываете грубую сетку поверх игрового поля. Области - это ячейки этой сетки. Вы выделяете массив областей и для каждого региона сохраняете список единиц в настоящее время в этой области.

Вы также можете найти Muki Haklay's demonstration of spatial indexes полезно.

Answer 2

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

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

Итак, если это правда, то вы хотите разделить все свои части на две группы - те, которые изменили направление на последнем шаге, а те, которые этого не сделали.

Для тех, кто это сделал, вам нужно выполнить небольшую калибровку - для единиц любых двух противоборствующих сил вы хотите спросить: «Когда блок A увидит блок B, если ни один из блоков A или блок B не изменит направление или скорость ? (вы можете иметь дело с accelleration/decelleration, но тогда это становится более сложным). Чтобы вычислить это, вам нужно сначала определить, будут ли пересекаться векторы, на которых перемещаются блок A и блок B (простой расчет пересечения 2D-линии в сочетании с расчет, который сообщает вам, когда каждый блок попадает на этот перекресток) - если они этого не делают, и теперь они не могут видеть друг друга, то они никогда не увидят друг друга, если хотя бы одно из них не изменит направление. Если они пересекаются, то вам нужно рассчитать разницу во времени между тем, когда первый и второй единицы пройдут через точку пересечения - если это расстояние больше, чем диапазон LOS, то эти единицы никогда не будут видеть друг друга, если не изменить направление - если этот дифференциал меньше, чем диапазон LOS, то еще несколько (волновые руки энергично) подсчеты скажут вам , когда это благословенное событие.

Теперь у вас есть коллекция информации, раздвоенная в элементы, которые никогда не увидят друг друга и элементы, которые будут видеть друг друга в какое-то время t в будущем - каждый шаг, вы просто имеете дело с единицами, которые изменились направления и вычислить их взаимодействие с остальными подразделениями. (О, и иметь дело с теми единицами, которые в предыдущих расчетах сказали, что вы поймете друг друга - не забудьте сохранить их в вставляемой упорядоченной структуре). Фактически вы использовали линейное поведение системы для изменения вашего вопроса с «есть ли блока A см блока B», чтобы «Когда будет блок A см блока B»

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

Answer 3

Я бы сделал это с сеткой. Я думаю, именно так решают проблему коммерческие игры RTS.

• Дискретировать мир игры для отслеживания видимости. (Квадратная сетка проще всего. Экспериментируйте с грубостью, чтобы увидеть, какое значение лучше всего работает.)
• Запишите настоящие единицы в каждой области. (Обновление при каждом движении устройства.)
• Записывайте области, которые видит каждый игрок. (Это нужно обновлять по мере того, как единицы перемещаются. Блок может просто опросить, чтобы определить его видимые плитки. Или вы могли бы проанализировать карту до начала игры.)
• Составьте список (или какая-либо структура) для врага единиц, наблюдаемых каждым игроком.

Теперь всякий раз, когда устройство переходит из одной области видимости на другой, выполнить проверку:

• пошел от невидимого к видимой области - добавить модуль для видимости трекера игрока.
• Пошел из видимого в невидимую область - удалите устройство из трекера видимости игрока.
• В двух других случаях не произошло изменения видимости.

Это быстро, но требует некоторой памяти. Однако с BitArrays и списками указателей использование памяти не должно быть так уж плохо.

Была статья об этом в одном из Game Programming Gems книг (одна из первых трех, я думаю.)