如何高效地表示游戏世界?我知道许多世界基本上都是正方形,在二维或三维数组中运作良好。如果我使用一个正方形的数组,那么我基本上是在浪费空间,并增加了需要遍历数组的时间。但是,我不确定在这里如何使用不规则数组。
游戏世界的形状示例:
X
XX
XX X XX
XXX XXX
XXXXXXX
XXXXXXXX
XXXXX XX
XX X
X
编辑: 游戏世界很可能需要遍历每个有效位置。因此,我需要一个简单易用的方法来实现这一点。
X
XX
XX X XX
XXX XXX
XXXXXXX
XXXXXXXX
XXXXX XX
XX X
X
编辑: 游戏世界很可能需要遍历每个有效位置。因此,我需要一个简单易用的方法来实现这一点。
稀疏表示会带来计算负荷和复杂性,因此,除非边界区域比实际世界要大得多,否则最好接受“浪费”的空间。你本质上是在将额外的内存使用换成更快速地访问世界内容。更重要的是,“浪费空间”的实现更易于理解和维护,直到需要更复杂的实现为止都是可取的。如果没有充分证据表明需要更复杂的实现,则保持简单会更好。
你可以将世界呈现为陆地(或水域)区域的(无向)图表,每个区域有规则的形状,整个世界由这些区域组成。每个区域都是图表中的一个节点,并与其所有邻居节点相连。
这可能也是任何一般世界最自然的表示方式(但它可能不是最有效的)。从效率的角度来看,它可能会击败数组或列表对于高度不规则的地图,但不适用于适合放入矩形(或其他规则形状)并且变化很少的地图。
一个高度不规则地图的例子:
x
x x
x x x
x x
x xxx
x
x
x
x
这几乎不可能被高效地适配到常规形状中(无论是空间比例还是访问时间)。另一方面,通过应用基本的几何变换(它是一个带有小块缺失的平行四边形),以下内容非常适合常规形状:
xxxxxx x
xxxxxxxxx
xxxxxxxxx
xx xxxx
最简单的方法就是使用数组,并用一些特殊标记标记非游戏空间位置。锯齿形数组也可能有效,但我很少使用它们。
另一个选项是使用哈希表,它可以让您在O(1)时间内访问游戏世界位置,并不浪费太多空间。其中键将是坐标。
另一种方法是存储边缘列表 - 沿每条直线边的线向量。这种方法易于检查包含关系,并且在每个顶点上使用四叉树甚至简单的位置哈希可以加快信息查找速度。我们在每个边缘上使用高度组件来模拟棒球场的墙壁,效果非常好。
这里有一个很大的问题,没有人提到:将其存储在磁盘和存储在内存中之间存在巨大的差异。
假设你正在谈论一个游戏世界,这意味着它会非常庞大。你不会一次性将整个东西存储在内存中,而是将即时附近的内容存储在内存中,并随着玩家四处走动进行更新。
这个附近区域应该尽可能简单、易于访问和快速。它应该绝对是一个数组(或一组随着玩家移动而交换的数组)。它将经常被你的游戏引擎的许多子系统引用:图形和物理将处理加载模型、绘制它们、使玩家保持在地形上、碰撞等;声音需要知道玩家当前站在什么类型的地面上,以播放适当的脚步声;等等。如果你只是将它保留在全局数组中,它们可以随意访问并以100%的速度和效率访问它,而不必在所有子系统之间广播和复制这些数据。这可以真正简化事情(但要注意全局变量的后果!)。
然而,在磁盘上您肯定希望对其进行压缩。提供的答案中有一些很好的建议;您可以序列化数据结构,例如哈希表,或仅包含填充位置的列表。您当然也可以存储八叉树。在任何情况下,您都不希望在磁盘上存储空白位置;根据您的统计数据,这意味着 66% 的空间被浪费了。当然,有时候需要忘记优化并让它只是工作,但是您不希望将一个填充率为 66% 的文件分发给最终用户。还要记住,硬盘并不是完美的随机访问设备(除了 SSD);机械硬盘应该至少还会持续几年,并且它们最适合顺序读取。看看能否组织您的数据结构,以使读操作是顺序的,当玩家移动时,您流式传输更多的周边地形,并且您可能会发现它是有明显差异的。不过,别轻信我的话,我实际上没有测试过这种东西,只是听起来是有道理的吧?