用于在游戏中存储实体的数据结构

Question

我有一个由块组成的平铺地图，每个块都是一个矩形的块。现在我想为此添加实体（每个实体都放在特定的图块上），并且每个循环都应该调用它们的update()函数，所以我想问一个建议：我应该使用什么数据结构来保存它们的位置？

我还不知道我将有什么样的方法，但我可能会需要的是会从一个特定的区域（可能是点）的所有实体，例如绘制方法。这是一个批评性问题，因为可能有一个像100x100大块的巨大地图，其中每个块都是30x20块，所以它将是3000x2000块，并且有很多实体，例如1000，所以如果我将它保存在列表中，它会非常缓慢搜索实体O(n)，如果每个实体进行搜索，它将采取O(n^2)。

现在我有一对夫妇的解决方案，但他们都是有问题的：

kd树（二维） - 因为每个循环中的所有实体可以改变他们的位置，更新他们的将是复杂与每个循环O(nlogn)重建整个树相同。

每个块都会保存属于它的实体 - 迄今为止我的最佳解决方案，易于更新，但复杂度高于kd-tree。

那么有没有人有这个问题的建议？

Answer 1

将瓦片（位置）映射到该瓦片上所有实体的列表的字典。所有实体都应该有一个位置属性和一个事件通知它的更改时间，以便字典可以在每次移动时更新。

（应该是没有实体没有列表的瓷砖。要当一个entitiy移动到该位置创建的列表，并在最后一个实体离开的位置被删除。）

Answer 2

这可能是粗的建议，我敢肯定，这可以改善，但这里有一个想法：

首先，存储，这样你可以访问它们在固定时间给特定对象的方式你的位置。例如，如果你想通过你的实体直接访问它们，你可以将位置结构存储在一个列表/向量中，并给每个实体一个指向它的位置的指针/引用。

第二，存储的实体的指针/参考或在相同的结构作为该实体位置GUID，这样就可以识别基于位置对象的实体。 （有可能是我现在没有想到的更好的方法。）

第三，利用扫除和修剪/排序和扫描（在3D游戏中常见）的一些原则：保留两个排序的位置列表/矢量，一个按x方向排序，另一个按y方向排序。一个可以容纳实际的位置对象，另一个可以容纳指针/引用。这些列表可以利用时间上的一致性，所以保持排序的成本不应该太高，除非有很多快速和混乱的运动。

这种设置的一个优点是很容易找出每个对象相对于彼此的位置。想知道在精灵比利的10个方格内有多少个物体在任何方向上？检查Billy的位置并向前/向后遍历这两个列表，直到您到达距离每个方向10多个方格的实体。

如果你有兴趣的概念，查找和排序扫描（也被称为扫描和删节）。你只会使用算法的前半部分，但它几乎用于每个主要的3D物理引擎的广泛相位碰撞检测，所以你知道它一般要快。 ;）关于它的信息很多，所以你可能会发现更多复杂的实现思想。 （例如，我不喜欢涉及将位置结构的指针/引用的排序列表存储的间接方式;使用实际的结构更加缓存高效，但是如果你想要在两个位置更新位置利用与持久阵列的时间相关性，其他人可能会想到一个更聪明的设计，现在正在逃避我）

编辑：我会评论Erik H的想法，但我的代表不够高。我只是想说，他的想法听起来非常适合你的游戏，尤其是如果你将很多实体紧紧包装在同一个瓷砖或小的社区。如果我是你，我可能会在扫除和修剪想法之前尝试。然而，应该伴随着一个精心策划的内存管理策略：如果你有瓷砖的位置是天真地映射到实体的载体的字典，你将有被分配了大量的内存和释放实体时，从移动一个瓷砖到另一个。相反，你会想实现他的想法的东西更像是一个字典/链表组合：

的字典键是瓷砖的位置，和字典将一个指针返回到链表节点。该节点将成为同一图块上所有实体的链表的一部分。每当一个实体从一个tile移动到另一个时，它将从当前链表中移除并添加到新的链表中。如果一个实体移动到一个空的磁贴，它将全部在链接列表中，并且它应该被添加到字典中。当最后一个实体从一个图块移出时，该图块的条目应该从字典中移除。这将允许你在没有持续动态分配/释放的情况下移动实体，因为你只是更新指针（并且字典可能会非常有效）。

注意，您不必存储全面的实体的链表，要么;您可以轻松地使用轻量级对象（包含指向实际实体的指针或GUID）创建链接列表。