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

Question

我正在做一个游戏世界不规则形状的项目(想一想湖的形状)。此形状有一个坐标放置在其上的网格。游戏世界只在形状的内部。(再说一次，想想Lake)

我如何有效地表示游戏世界？我知道许多世界基本上是正方形的，在2或3维数组中工作得很好。我觉得如果我使用一个正方形的数组，那么我基本上是在浪费空间，并且增加了我迭代数组所需的时间。但是，我也不确定锯齿数组在这里是如何工作的。

游戏世界的形状示例

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

编辑:游戏世界将很可能需要每个有效的位置步入。所以我想要一个方法，让它更容易做到这一点。

Answer 1

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

Answer 2

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

Answer 3

使用你想出的任何结构-你可以随时改变它。如果你习惯于使用数组，那就使用它。不要担心你将要使用的数据结构，开始编码吧。

在编写代码时，从底层数组中构建抽象，比如将其包装在语义模型中；然后，如果您意识到(通过分析)它对于所需的操作来说是浪费空间或缓慢的，那么您可以在不引起问题的情况下将其交换出去。不要试图优化，直到你知道你需要什么。