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

Question

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

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

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

Так что, если есть 8 игроков и у них по 3000 юнитов, это будет означать 3000 * 21000 = 63000000 тестов на игрока в худшем случае.Что довольно медленно.

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

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

РЕДАКТИРОВАТЬ:

Итак, дополнительные сведения:

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

Answer 1

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

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

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

и иметь:

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

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

Вы также можете найти демонстрацию пространственных индексов Муки Хаклая полезной.

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

Теперь у вас есть набор информации, раздвоенной на элементы, которые никогда не увидят друг друга, и элементы, которые увидят друг друга в какое-то время в будущем - на каждом этапе вы просто имеете дело с единицами, которые изменили направление и рассчитать их взаимодействие с остальными подразделениями. (Да, и разберитесь с теми единицами, которые, как говорили предыдущие расчеты, вам приходилось видеть друг друга - не забывайте держать их в упорядоченной упорядоченной структуре). То, что вы эффективно сделали, - это использовало линейное поведение системы, чтобы изменить свой вопрос 'Имеет ли единицу А см. Единицу В' до 'Когда будет единицей А, см. Единицу В'

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