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

稀疏表示存在计算开销和复杂性,因此除非边界区域比实际世界大得多,否则简单地接受“浪费”的空间可能是最有效的。基本上,您是在权衡额外的内存使用,以便更快地访问世界内容。更重要的是,“浪费的空间”实现更易于理解和维护,这在需要更复杂的实现之前始终是可取的。如果你没有很好的证据证明这是必要的,那么最好保持简单。

你需要一个 quadtree 以最小化表示中浪费的空间量。四叉树很适合用不同的粒度划分二维空间-在您的例子中,最细的粒度是一个游戏方块。如果你有一个完整的20x20区域没有任何游戏方块,四叉树表示法将允许你只使用一个节点来表示整个区域,而不是像数组表示法那样使用400。

在编写代码时,从这个底层数组构建抽象,就像将它包装在语义模型中一样;然后,如果您意识到(通过分析)这是浪费空间或慢的操作,您需要的,您可以交换出来,而不会造成问题。在你知道你需要什么之前不要尝试优化。

使用数据结构,如列表或地图,只插入有效的游戏世界坐标。这样,您唯一要保存的就是有效的位置,而且您不必浪费内存来保存非游戏世界的位置,因为您可以从数据结构中缺少位置来推断这些位置。

您可以将世界呈现为陆地(或水域)斑块的(无向)图形。每个补丁都有一个规则的形式,世界就是这些补丁的组合。每个面片都是图中的一个节点,它的邻域都有图的边。

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

实际上,这是不可能被有效地(在空间比例和访问时间上)装配成一个规则形状的。另一方面,通过应用基本的几何变换(它是一个缺少少量位的平行四边形),以下内容非常适合于规则形状:

xxxxxx  x
 xxxxxxxxx
  xxxxxxxxx
   xx   xxxx

另一个可以让你在O(1)时间内仍然访问游戏世界的位置并且不浪费太多空间的选项是hashtable,其中的键是坐标。

另一种方法是存储一个边列表-沿每条直边的线向量。通过这种方式很容易检查是否包含,并且每个vertice上的四叉树甚至一个简单的位置哈希都可以加快信息的查找。我们用每边的高度分量来模拟棒球场的墙壁,效果很好。

这里有一个没有人解决的大问题:存储在磁盘和存储在内存之间的巨大区别。

假设你在谈论一个游戏 世界 就像你说的,这意味着它会很大。你不会一次就把所有的东西都存储在内存中,相反,你会把紧邻的东西存储在内存中,并在玩家走动时更新它。

该附近区域应尽可能简单、方便、快捷。它肯定应该是一个数组(或者一组随着玩家移动而交换的数组)。游戏引擎的许多子系统会经常引用它:图形和物理将处理加载模型、绘制模型、使玩家保持在地形顶部、碰撞等。;声音将需要知道什么地面类型的球员目前站在,发挥适当的脚步声;等等。与其在所有子系统之间广播和复制这些数据,不如将其保存在全局数组中,这样他们就可以随意地以100%的速度和效率访问这些数据。这确实可以简化事情(但要注意全局变量的后果!)。