XNA 中是否有一些标准功能可以在大世界中有效地实现 2D 相机 [英] Is there some standard functionality in XNA to efficiently implement a 2D Camera on a large world

查看:15
本文介绍了XNA 中是否有一些标准功能可以在大世界中有效地实现 2D 相机的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在制作一个包含许多移动物体的 2d 空间游戏.我已经实现了一个可以四处移动并在视图中绘制对象的相机.现在的问题是,在绘制之前,我必须检查每个对象是否在我的视图矩形内(O(n) 操作,其中 n 是数字我的世界中的对象).我想要一种更有效的方法来获取视图中的所有对象,所以我只需要绘制它们.

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.

我知道一堆数据结构可以实现一个 O(log n + k) 查询时间进行二维范围查询,其中 k 是范围内的对象数量.问题是所有对象都在不断移动.大多数数据结构的更新时间也是 O(log n).这很糟糕,因为几乎所有对象都在移动,因此所有对象都必须更新,从而导致 O(n log n) 操作.使用我当前的实现(所有内容都存储在列表中),更新时间需要 O(n) 次操作来更新所有内容.

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.

我想这个问题一定已经解决了,但我真的找不到一个专门考虑我的选择的解决方案.大多数 2D 相机示例只是按照我目前的方式进行操作.

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:

  1. 有没有比我目前的方法(一般)更有效的方法?
  2. 有没有比我目前的方法(在 XNA 中)更有效的方法?

一方面我在想,O(n) + O(n) 比 O(log n) + O 好(n log n),但另一方面我知道在许多游戏中他们使用所有这些数据结构,如 BSP 等.所以我觉得我错过了一些的拼图.

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:我有点困惑我是否应该在 Stack Overflow、游戏开发者堆栈交换或计算机科学理论堆栈交换上发布这个......所以如果它有点超出范围,请原谅我.

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.

推荐答案

我的第一个问题是:你真的会拥有一个拥有一百万(甚至十亿!)个物体的世界吗?

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.)

最后,如果这太慢了,我会实现一个分桶数据结构(恒定更新时间,恒定查询时间).在这种情况下,一个 2D 列表网格覆盖了您的世界空间.适用于数千个对象.

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 中是否有一些标准功能可以在大世界中有效地实现 2D 相机的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆