存储大型2D游戏世界

Question

我一直在尝试不同的想法来存储2D游戏世界。我感兴趣的是听听如何存储大量对象并管理可见的集合（比如说一个100,000块瓦片的正方形）。显然，技术因游戏如何呈现这个空间而异。

让我们假设我们正在描述一个滚动的2D游戏世界，而不是基于屏幕的，因为你可以从这样的设置中相当容易地进行基于屏幕的渲染，而反过来则要复杂得多。

这里寻找与语言无关的解决方案，以便对其他人更有帮助。

编辑: 我认为一个好的答案应该是对考虑这一点的思路的概括审查，就像一些回答者所尝试的那样，但也要开始解释不同的解决方案如何适用于这些情况。这是一个有些复杂的问题，所以我希望一个好的答案能够反映出这一点。

- grey

Answer 1

四叉树是一种相当高效的解决方案，用于存储关于大型二维世界及其中的对象的数据。

- Amber

---

从我所了解的四叉树，它们似乎更新代价很高。那么，如果有任何正在积极移动的物体，这可能会带来问题，对吗？ - grey

这要看世界的稀疏程度，如果世界中物体与空间的比例相对较小，则使用四叉树的优势会超过稍微复杂化的更新过程。如果比例较大（因此世界中物体相当密集），那么四叉树将不是最理想的解决方案，另一种表示方法会更加理想。 - Amber

Answer 2

你可以从一些空间数据结构（如范围树或kd树）中获取一些实现此功能的想法。

然而，这个问题的答案会因为你的游戏如何工作而有很大的不同。

我们是在讨论一个2D平台游戏吗？场景上有10个敌人，20个在屏幕外但“活跃”，还有一个未知数量的“非活跃”敌人？如果是这样，你可以将整个关卡存储为一个“屏幕”数组，在其中操作最靠近你的部分。

或者你是指真正的2D游戏，同时有很多上下运动？这里可能需要更加小心。

平台的重要性也很大。如果你正在为桌面PC实现一个简单的平台游戏，你可能不必像在嵌入式设备上那样担心性能。这并不是说你可以对它毫不在意，但你可能不必过于聪明。

我认为这是一个有趣的问题。想必比我聪明的已经有经验的平台游戏开发者已经思考过这些问题了。

- McPherrinM

Answer 3

将世界分成较小的区域并处理它们。任何解决此问题的方案都将归结为这个概念（例如四叉树，如另一个答案中所提到的）。它们的区别在于它们如何划分世界。

每个瓷砖存储多少数据？玩家在世界上移动有多快？屏幕外的NPC的行为是什么？他们只是重置当玩家回来时（像旧的塞尔达游戏）？他们只是恢复到他们之前的位置？他们会执行某种追赶脚本吗？

不同区域需要多少不同的渲染数据？

一次可以看到多少世界？

所有这些问题都会影响您的解决方案，以及您平台的能力。如果没有合理的这些参数的想法，为这些问题提供一般答案会有点困难。

- kyoryu

---

我可以提供关于我的具体情况，但那对于这里的其他人似乎没有那么有用。我会在这里进一步说明一个好答案的参数... - grey

Answer 4

假设您的游戏只会更新可见区域及其周围一定范围内的内容，那么可以将整个世界分成“屏幕”（即瓷砖地图上的矩形区域，可以填满整个屏幕）。在内存中保留可见区域周围的“屏幕”（如果要更新靠近角色的实体，则保留更多 - 但是没有必要更新远离角色的实体），其余部分则保存在磁盘上，并使用缓存以避免在移动时加载/卸载常访问的区域。设置如下：

+---+---+---+---+---+---+---+
|FFF|FFF|FFF|FFF|FFF|FFF|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|VVV|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|FFF|FFF|FFF|FFF|FFF|FFF|
+---+---+---+---+---+---+---+

在这里，“V” 部分是“屏幕”，其中心（英雄或其他）所在的位置，“N” 部分是附近并具有活动（更新）实体的部分，会被检查碰撞等，而“F” 部分则是远离的部分，可能不经常更新，并且容易被“交换”出去（存储到磁盘）。当然，您可能希望使用更多的“N”屏幕，而不仅仅是两个 :-).

顺便提一下，由于2D游戏通常不保存太多数据，因此您可能希望将远离的部分压缩后仅保留在内存中。

- Bad Sector

---

谢谢分享。我已经在做类似的事情了，并且发现它对我目前的目的来说足够高效。 - grey

Answer 5

你可能想使用一个单一的int或byte数组来链接块类型。如果你需要更多的优化，那么你就需要从数组中链接到更复杂的数据结构，比如八叉树。这里有一个关于Java游戏论坛的好讨论：http://www.javagaming.org/index.php/topic,20505.30.html text

任何带有链接的东西都会变得非常昂贵，因为指针占用了大约8个字节，具体取决于语言，所以根据你的世界有多少人口密集，它很快就会变得非常昂贵（8个指针每个8个字节，每个字节数组是1个字节）。所以除非你的世界中有1/64是空的，否则字节数组将是一个更好的选择。每当你进行碰撞查找或其他操作时，你还需要花费大量时间迭代树 - 字节数组将是即时查找。

希望这对你足够详细了。 :-)

- Eli

---

感谢您的想法！这并不普遍到足以成为被接受的答案，但感谢您分享这个想法。 - grey