我有一个由 block 组成的瓦片 map ，每个 block 都是一个矩形瓦片。现在我想添加实体到这个(每个实体站在一个特定的瓷砖上)，并且每个循环所有实体都应该调用他们的 update() 函数，所以我想征求一个建议:什么数据我应该使用结构来保存他们的位置吗？
我还不知道我将拥有什么样的方法，但我可能需要一种从特定区域(可能是一个点)获取所有实体的方法，例如用于绘图。这是一个批评性的问题，因为可能有一个像 100x100 block 这样的巨大 map ，其中每个 block 是 30x20 block ，所以它将是 3000x2000 block ，还有很多实体，例如 1000，所以如果我将它保存在列表中，它将非常慢搜索实体 O(n)，如果每个实体都进行搜索，则需要 O(n^2)。
现在我有几个解决方案，但它们都有问题:
kd-tree(for 2d) - 由于每次循环所有实体都可以更改它们的位置，因此更新它们的复杂性与每次循环重建整棵树相同 O( nlogn).
每个 block 都会保存属于它的实体 - 迄今为止我最好的解决方案，易于更新，但复杂性高于 kd 树。
那么有人对这个问题有什么建议吗？
最佳答案
将图 block (位置)映射到该图 block 上所有实体的列表的字典。所有实体都应该有一个位置属性和一个事件通知何时发生变化，以便字典可以在每次移动时更新。
(没有实体的图 block 不应该有列表。当一个实体移动到该位置时应该创建该列表，并在最后一个实体离开该位置时删除该列表。)
关于algorithm - 游戏中存储实体的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7214291/