Fast algorithm for line of sight calculation in an RTS game
I'm making a simple RTS game. I want it to run very fast because it should work with thousands of units and 8 players.
Everything seems to work flawlessly but it seems the line of sight calculation is a bottleneck. It's simple: if an enemy unit is closer than any of my unit's LOS range it will be visible.
Currently I use a quite naive algorithm: for every enemy units I check whether any of my units is see him. It's O(n^2)
So If there are 8 players and they have 3000 units each that would mean 3000*21000=63000000 tests per player at the worst case. Which is quite slow.
More details: it's a stupid simple 2D space RTS: no grid, units are moving along a straight lines everywhere and there is no collision so they can move through each other. So even hundreds of units can be at the same spot.
I want to speed up this LOS algorithm somehow. Any ideas?
EDIT:
So additional details:
- I meant one player can have even 3000 units.
- my units have radars so they towards all directions equally.
3 ответа
Используйте структуру пространственных данных для эффективного поиска единиц по местоположению.
Кроме того, если вас интересует только то, виден ли объект, но не какой объект его заметил, вы можете сделать
for each unit
mark the regions this unit sees in your spatial data structure
и получить:
isVisible(unit) = isVisible(region(unit))
Очень простая структура пространственных данных - это сетка: вы накладываете грубую сетку поверх игровое поле. Ячейками этой сетки являются регионы. Вы выделяете массив регионов, и для каждого региона храните список юнитов, находящихся на данный момент в этом регионе.
Вы также можете найти демонстрацию пространственных индексов Муки Хаклая полезной.
Я бы сделал это с помощью сетки. Думаю, именно так решают эту проблему коммерческие RTS-игры.
- Дискретизируйте игровой мир для трекера видимости. (Квадратная сетка - самая простая. Поэкспериментируйте с крупностью, чтобы увидеть, какое значение работает лучше всего.)
- Запишите текущие юниты в каждой области. (Обновляйте каждый раз, когда юнит перемещается.)
- Запишите области, которые видит каждый игрок. (Это должно обновляться по мере перемещения юнитов. Юнит может просто провести опрос, чтобы определить свои видимые тайлы. Или вы можете проанализировать карту до начала игры...)
- Составьте список (или любую другую подходящую структуру) вражеских юнитов, видимых каждым игроком.
Теперь каждый раз, когда юнит переходит из одной области видимости в другую, выполняйте проверку:
- Перешел из невидимой области в видимую - добавьте юнит в трекер видимости игрока.
- Перешел из видимой области в невидимую - удалите единицу из трекера видимости игрока.
- В двух других случаях изменения видимости не произошло.
Это быстро, но занимает некоторое количество памяти. Однако с BitArrays и списками указателей, использование памяти не должно быть таким уж плохим.
Об этом была статья в одной из книг Game Programming Gems (кажется, в одной из первых трех)
.Одно из самых фундаментальных правил в gamedev - оптимизировать bejeebers из ваших алгоритмов, используя все возможные ограничения, которые определяет ваш игровой процесс. - это основная причина того, что вы не видите совершенно разных игр, построенных на игровом движке какой-либо конкретной компании, они так эффективно использовали свои ограничения, что не могут справиться ни с чем, что выходит за рамки этих ограничений.
Тем не менее, вы сказали, что отряды движутся по прямым линиям - и вы говорите, что игроки могут 3000 отрядов - даже если я предполагаю, что это 3000 отрядов на восемь игроков, то есть 375 отрядов на игрока, поэтому я думаю, что могу предположить, что что на каждом шаге игры (и я предполагаю, что каждый шаг включает в себя вычисление, которое вы описали выше) , что больше юнитов не изменят свое направление , чем юниты, которые изменят направление.
Итак, если это правда, тогда вы хотите разделить все свои части на две группы - те, которые действительно изменили направление на последнем шаге, и те, которые не изменились.
Для тех, кто это сделал, вам нужно немного посчитать - для единиц любых двух противостоящих сил вы хотите спросить, «когда единица A увидит единицу B, если ни единица A, ни единица B не изменят направление или скорость? (вы можете иметь дело с ускорением / замедлением, но тогда это становится более сложным) - чтобы вычислить это, вам нужно сначала определить, будут ли пересекаться векторы, по которым движутся единицы A и B (простой расчет пересечения двухмерных линий в сочетании с вычислением который сообщает вам, когда каждая единица достигает этого пересечения) - если они этого не сделают, и они не могут видеть друг друга сейчас, то они никогда не увидят друг друга, если хотя бы один из них не изменит направление.Если они действительно пересекаются, вам необходимо рассчитать разницу во времени между тем, когда первый и второй юниты проходят через точку пересечения - если это расстояние больше, чем диапазон прямой видимости, то эти юниты никогда не увидят друг друга, если один из них не изменит направление - если этот дифференциал меньше диапазона LOS, то еще несколько вычислений (энергично взмахивайте руками) расскажут вам , когда это благословенное событие произойдет.
Теперь у вас есть набор информации, раздвоенный на элементы, которые никогда не увидят друг друга, и элементы, которые увидят друг друга в какой-то момент времени t в будущем - на каждом шаге вы просто имеете дело с единицами, которые изменили направление и вычислить их взаимодействие с остальными модулями. (Да, и разберитесь с теми единицами, которые, как сказали в предыдущих расчетах, будут видны друг другу - не забудьте сохранить их во вставляемой упорядоченной структуре) То, что вы фактически сделали, - это использование линейного поведения системы, чтобы изменить ваш вопрос с 'Видит ли блок A блок B' до 'Когда будет блок A видеть блок B'
Теперь, все это сказано, это не для того, чтобы сбрасывать со счетов структуру пространственных данных ответ - это хороший ответ - однако он также способен иметь дело с объектами в случайном движении, поэтому вы хотите подумать, как оптимизировать этот процесс дальше - вам также нужно быть осторожным при работе с видимостью между областями, т. е.единицы на границах двух разных регионов могут видеть друг друга - если у вас есть части, которые имеют тенденцию слипаться, использование пространственной структуры данных с переменными размерами может быть ответом, где части, которые не находятся в одном регионе, гарантированы не видеть друг друга.