代表一个不规则形状的游戏世界

Question

我正在处理一个项目，其中游戏世界的形状是不规则的（类似于湖泊的形状）。这个形状上有一个带坐标的网格。游戏世界只存在于形状的内部。（再次，请想象一下湖泊的形状）

如何高效地表示游戏世界？我知道许多世界基本上都是正方形，在二维或三维数组中运作良好。如果我使用一个正方形的数组，那么我基本上是在浪费空间，并增加了需要遍历数组的时间。但是，我不确定在这里如何使用不规则数组。

游戏世界的形状示例：

X
XX
 XX   X XX
 XXX XXX
  XXXXXXX
XXXXXXXX
 XXXXX XX
   XX   X
  X

编辑： 游戏世界很可能需要遍历每个有效位置。因此，我需要一个简单易用的方法来实现这一点。

- Aaron M

---

我认为存储游戏世界的最佳方法取决于你需要在游戏世界中进行何种操作。 - Matti Virkkunen

当遍历每个位置时，您会做什么？您需要查看附近的单元格吗？ - Matti Virkkunen

Answer 1

稀疏表示会带来计算负荷和复杂性，因此，除非边界区域比实际世界要大得多，否则最好接受“浪费”的空间。你本质上是在将额外的内存使用换成更快速地访问世界内容。更重要的是，“浪费空间”的实现更易于理解和维护，直到需要更复杂的实现为止都是可取的。如果没有充分证据表明需要更复杂的实现，则保持简单会更好。

- Dan Bryant

---

在我的例子中，有66%的地图空间将被浪费。但是，目前我还没有足够的进展来确定是否需要稀疏表示。 - Aaron M

在这种情况下，请参考kevingessner的答案。您可以最初根据数组编写使用地图的原语。如果需要，您可以稍后使用不同的实现来节省内存，尽管您可能不需要，并且可能会获得更好的性能与简单的数组。 - Dan Bryant

我对我创建的一个对象进行了一些简单的测试。看起来循环遍历它的性能对于我的需求来说是不错的，特别是因为它不需要实时能力。 - Aaron M

Answer 2

您可以使用四叉树来最小化表示中浪费的空间。 四叉树适用于具有不同粒度的二维空间划分-在您的情况下，最细粒度是游戏方块。 如果您有一个完整的20x20区域没有任何游戏方块，则四叉树表示将允许您仅使用一个节点来表示该整个区域，而不是像数组表示中的400个节点。

- Jordan Lewis

---

四叉树的问题在于游戏世界可能会变成三维的。我希望能找到一个既适用于二维又适用于三维的解决方案。 - Aaron M

3D四叉树的版本被称为八叉树：http://en.wikipedia.org/wiki/Octree - Mark Byers

Aaron，如果你需要扩展到三维空间，可以使用八叉树。它是四叉树的扩展，可以考虑上下邻居以及左右邻居。 - Jordan Lewis

@Aaron，如果是这样的话，您可以使用八叉树，它是四叉树的三维版本。四叉树用于Google Earth和Google Maps，因此它们在处理三维数据时也不错，除非您需要将两个物体放在相同的X、Y坐标上（根据它们为何同时存在，这可能仍然不是问题）。每个位置都可以有一个Z坐标作为可视化属性。 - Rangoric

正如@Rangoric所提到的，四叉树在许多情况下都可以使用——如果您真正模拟的是湖上的游戏，则四叉树是完美的选择。如果您正在进行扭曲、交错的洞穴设计，则八叉树将更可取。但是，如果您将树的生成和遍历代码与游戏代码的其余部分分开，那么将其“升级”应该是微不足道的。 - dash-tom-bang

Answer 3

使用你已经想好的数据结构，你可以随时更改它。如果你习惯使用数组，请使用它。不要担心你将使用的数据结构，开始编码吧。

在编码过程中，从这个基础数组中构建抽象，比如将其包装在一个语义模型中；然后，如果你通过分析发现它对于你需要的操作来说浪费空间或者速度慢，你可以替换掉它而不会引起问题。在你知道自己需要什么之前不要试图优化。

- kevingessner

Answer 4

你可以将世界呈现为陆地（或水域）区域的（无向）图表，每个区域有规则的形状，整个世界由这些区域组成。每个区域都是图表中的一个节点，并与其所有邻居节点相连。

这可能也是任何一般世界最自然的表示方式（但它可能不是最有效的）。从效率的角度来看，它可能会击败数组或列表对于高度不规则的地图，但不适用于适合放入矩形（或其他规则形状）并且变化很少的地图。

一个高度不规则地图的例子：

x
 x   x
  x x    x
   x     x
    x xxx
     x
    x
   x
  x

这几乎不可能被高效地适配到常规形状中（无论是空间比例还是访问时间）。另一方面，通过应用基本的几何变换（它是一个带有小块缺失的平行四边形），以下内容非常适合常规形状：

xxxxxx  x
 xxxxxxxxx
  xxxxxxxxx
   xx   xxxx

- Konrad Rudolph

Answer 5

使用像列表或映射这样的数据结构，仅插入有效的游戏世界坐标。这样，您保存的唯一内容是有效位置，并且不会浪费内存来保存非游戏世界位置，因为您可以通过在数据结构中缺少存在来推断它们。

- Ben Burnett

Answer 6

最简单的方法就是使用数组，并用一些特殊标记标记非游戏空间位置。锯齿形数组也可能有效，但我很少使用它们。

- FrustratedWithFormsDesigner

Answer 7

另一个选项是使用哈希表，它可以让您在O(1)时间内访问游戏世界位置，并不浪费太多空间。其中键将是坐标。

- Cam

Answer 8

另一种方法是存储边缘列表 - 沿每条直线边的线向量。这种方法易于检查包含关系，并且在每个顶点上使用四叉树甚至简单的位置哈希可以加快信息查找速度。我们在每个边缘上使用高度组件来模拟棒球场的墙壁，效果非常好。

- Michael Dorgan

Answer 9

这里有一个很大的问题，没有人提到：将其存储在磁盘和存储在内存中之间存在巨大的差异。

假设你正在谈论一个游戏世界，这意味着它会非常庞大。你不会一次性将整个东西存储在内存中，而是将即时附近的内容存储在内存中，并随着玩家四处走动进行更新。

这个附近区域应该尽可能简单、易于访问和快速。它应该绝对是一个数组（或一组随着玩家移动而交换的数组）。它将经常被你的游戏引擎的许多子系统引用：图形和物理将处理加载模型、绘制它们、使玩家保持在地形上、碰撞等；声音需要知道玩家当前站在什么类型的地面上，以播放适当的脚步声；等等。如果你只是将它保留在全局数组中，它们可以随意访问并以100%的速度和效率访问它，而不必在所有子系统之间广播和复制这些数据。这可以真正简化事情（但要注意全局变量的后果！）。

然而，在磁盘上您肯定希望对其进行压缩。提供的答案中有一些很好的建议；您可以序列化数据结构，例如哈希表，或仅包含填充位置的列表。您当然也可以存储八叉树。在任何情况下，您都不希望在磁盘上存储空白位置；根据您的统计数据，这意味着 66% 的空间被浪费了。当然，有时候需要忘记优化并让它只是工作，但是您不希望将一个填充率为 66% 的文件分发给最终用户。还要记住，硬盘并不是完美的随机访问设备（除了 SSD）；机械硬盘应该至少还会持续几年，并且它们最适合顺序读取。看看能否组织您的数据结构，以使读操作是顺序的，当玩家移动时，您流式传输更多的周边地形，并且您可能会发现它是有明显差异的。不过，别轻信我的话，我实际上没有测试过这种东西，只是听起来是有道理的吧？

- Ricket