XNA 中是否有一些标准功能可以在大世界上有效地实现 2D 相机
我正在制作一个带有许多移动物体的二维空间游戏。我已经实现了一个可以在视图中移动并绘制对象的相机。现在的问题是，在绘制每个对象之前，我必须检查它是否在视图的矩形内（O(n) 次操作，其中 n 是数字我的世界中的物体）。我想要一种更有效的方法来获取视图中的所有对象，所以我只需要绘制它们。
我知道一堆数据结构可以实现二维范围查询的 O(log n + k) 查询时间，其中 k是范围内物体的数量。问题是所有物体都在不断移动。大多数数据结构的更新时间也是 O(log n)。这是非常糟糕的，因为几乎所有对象都在移动，因此所有对象都必须更新，从而导致 O(n log n) 操作。使用我当前的实现（所有内容都存储在列表中），更新时间需要 O(n) 次操作来更新所有内容。
我想这个问题一定已经解决了，但我找不到一个专门考虑我的选择的解决方案。大多数 2D 相机示例都按照我目前的方式进行。
所以我的问题基本上由两件事组成：
- 有没有比我目前的方法（一般来说）更有效的方法来做到这一点？
- 有没有比我当前的方法（在 XNA 中）更有效的方法？
一方面我在想， O(n) + O(n) 比 O(log n) + O(n) >n log n），但另一方面，我知道在许多游戏中他们使用所有这些数据结构，如 BSP 等。所以我觉得我错过了拼图的一些部分。
PS：我有点困惑是否应该将其发布在 Stack Overflow、游戏开发人员堆栈交换或计算机科学理论堆栈交换上……所以如果有点超出范围，请原谅。
I am making a 2d space game with many moving objects. I have already implemented a camera that can move around and draw the objects within the view. The problem now is that I have to check for every object wether it is within the rectangle of my view before I draw it (O(n) operations where n is the number of objects in my world). I would like a more efficient way to acquire all the objects within the view so I only have to draw them.
I know a bunch of data structures that can achieve a O(log n + k) query time for a two dimensional range query, where k is the amount of objects within the range. The problem is that all the objects are constantly moving. The update time on most of the data structures is O(log n) as well. This is pretty bad because almost all objects are moving so all will have to be updated resulting in O(n log n) operations. With my current implementation (everything is just stored in a list), the update time takes O(n) operations to update everything.
I am thinking that this problem must have been solved already, but I couldn't really find a solution that specifically considers my options. Most 2D camera examples just do it the way I am currently doing.
So my question basically consists out of two things:
- Is there a more efficient way to do this than my current one (in general)?
- Is there a more efficient way to do this than my current one (in XNA)?
On one hand I am thinking, O(n) + O(n) is better than O(log n) + O(n log n), but on the other hand I know that in many games they use all these data structures like BSPs etc. So I feel like I am missing some piece of the puzzle.
PS: I am a bit confused whether I should post this on Stack Overflow, the Game Developers stack exchange or the Computer Science Theory stack exchange...... So please excuse me if it's a bit out of scope.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我的第一个问题是：你真的会拥有一个拥有一百万（甚至十亿！）物体的世界吗？
这是性能优化，所以我会这样做：
首先：什么也不做。只需使用一个大列表绘制所有内容并每帧更新所有内容即可。适用于数十个物体。
如果这太慢，我会在迭代列表时进行一些基本的剔除。因此，对于每个对象 - 如果它在屏幕外，则不要绘制它。如果它“不重要”（例如：粒子系统、其他类型的动画等），也不要在屏幕外更新它。适用于数百种物体。
（您需要能够获取对象的位置和边界框，并检查将其与屏幕的矩形进行比较。）
最后，如果这太慢，我将实现一个分桶数据结构（恒定更新时间，恒定查询时间） 。在本例中，列表的二维网格覆盖了您的世界空间。适用于数千种物体。
如果这最终占用了太多的内存——如果你的世界非常大而且稀疏——我也许会开始研究四叉树。请记住，您不必每次更新对象时都更新空间分区结构 - 仅当对象的位置发生显着变化时！
记住这句习语：做可能有效的最简单的事情。实现简单的案例，然后在实现复杂的事情之前，实际看看您的游戏是否在现实世界中的对象数量上运行缓慢。
My first question would be: are you really going to have a world with a million (or even a billion!) objects?
This is a performance optimisation, so here's what I would do:
First of all: nothing. Just draw everything and update everything every frame, using a big list. Suitable for tens of objects.
If that is too slow, I would do some basic culling as I iterated the list. So for each object - if it is off-screen, don't draw it. If it is "unimportant" (eg: a particle system, other kinds of animation, etc) don't update it while off-screen either. Suitable for hundreds of objects.
(You need to be able to get an object's position and bounding box, and check compare it with the screen's rectangle.)
And finally, if that is too slow, I would implement a bucketed data structure (constant update time, constant query time). In this case a 2D grid of lists that covers your world space. Suitable for thousands of objects.
If that ends up taking up too much memory - if your world is crazy-large and sparse - I would start looking into quadtrees, perhaps. And remember that you don't have to update the space-partitioning structure every time you update an object - only when an object's position changes significantly!
Remember the idiom: Do The Simplest Thing That Could Possibly Work. Implement the simple case, and then actually see if your game is running slowly with a real-world number of objects, before you go implementing something complicated.
你的意思是说，你检查了你想要放在屏幕上的每个对象并显示在屏幕上。判断是否在指定的屏幕区域内进行处理？？？
XNA 负责自动处理屏幕外的对象（当然不是绘图），您只需指定坐标...或者我是否误解了您的问题？
编辑
为什么不使用容器精灵，在其中绘制您想要的所有内容并在其中绘制所有内容？然后将单个主精灵绘制到屏幕上？在该单个精灵上调用绘制实际上并不涉及绘制外部的那些部分。
You mean to say, you check every object that you wish to put on to screen & take action against whether or not it is inside the specified screen area???
XNA takes care of handling objects which are out of screen (by not drawing of course) automatically, You simply specify the coordinates... Or did I misunderstand you question??
EDIT
Why not use a container sprite, draw everything you want inside it & then draw that single main sprite onto the screen? Calling draw on that single sprite won't really involve drawing of those parts which are outside.