Есть ли в XNA стандартные функции для эффективной реализации 2D-камеры в большом мире?

Question

Я делаю 2D игру со множеством движущихся объектов.Я уже реализовал камеру, которая может перемещаться и рисовать объекты в представлении.Теперь проблема заключается в том, что мне нужно проверить каждый объект, находится ли он в прямоугольнике моего вида, прежде чем рисовать его (O ( n ) операций, где n - количество объектовв моем Мире).Я хотел бы более эффективный способ получить все объекты в представлении, поэтому мне нужно только нарисовать их.

Я знаю несколько структур данных, которые могут достичь O (log n + k ) время запроса для двумерного запроса диапазона, где k - количество объектов в диапазоне.Проблема в том, что все объекты постоянно движутся.Время обновления большинства структур данных также равно O (log n ).Это довольно плохо, потому что почти все объекты движутся, поэтому все придется обновлять, что приводит к операциям O ( n log n ).В моей текущей реализации (все просто хранится в списке), время обновления занимает O ( n ) операций, чтобы обновить все.

Я думаю, что эта проблема уже должна быть решена, но я не мог действительно найти решение, которое конкретно рассматривает мои варианты.Большинство примеров 2D-камер просто делают это так, как я сейчас.

Так что мой вопрос в основном состоит из двух вещей:

1. Есть ли более эффективный способ сделать это, чем мойтекущий (в целом)?
2. Есть ли более эффективный способ сделать это, чем мой текущий (в XNA)?

С одной стороны, я думаю, O ( n ) + O ( n ) лучше, чем O (log n ) + O ( n log n ), но с другой стороны я знаю, что во многих играх они используют все эти структуры данных, такие как BSP и т. д. Поэтому я чувствую, что мне не хватает какой-то части головоломки.

PS: Я немного запутался, стоит ли мне публиковать это на переполнении стека, обмене стека разработчиков игр или обмене стека теории компьютерных наук ...... Так что извините, если это немного не такОбъем.

Answer 1

Мой первый вопрос: у вас действительно будет мир с миллионом (или даже миллиардом!) Объектов?

Это оптимизация производительности, так что вот чтоЯ бы сделал:

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

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

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

И, наконец, если это слишкоммедленно, я бы реализовал структуру данных с интервалами (постоянное время обновления, постоянное время запроса).В этом случае 2D сетка списков, которая покрывает ваше мировое пространство.Подходит для тысяч объектов.

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

Запомните идиому: DoСамое простое, что могло бы сработать .Реализуйте простой случай, а затем посмотрите, работает ли ваша игра медленно с реальным количеством объектов, прежде чем приступить к реализации чего-то сложного.

Answer 2

Вы хотите сказать, что вы проверяете каждый объект, который хотите поместить на экран, и принимаете меры против того, находится ли он внутри указанной области экрана ???

XNA позаботится о том, чтобы автоматически обрабатывать объекты, которые находятся за пределами экрана (не рисуя, конечно). Вы просто указываете координаты ... Или я неправильно понял вопрос?* EDIT

Почему бы не использовать контейнерный спрайт, нарисовать в нем все, что вы хотите, а затем нарисовать этот единственный основной спрайт на экране?Вызов draw на этом единственном спрайте не будет включать рисование тех частей, которые находятся снаружи.