c# - 在一个非常大的矩形内保存一组坐标的最佳数据结构？

Question

我有一个地图的抽象表示，比如说，X 和 Y 坐标上有 5.000.000 个不同的整数坐标，所以它是一个非常大的二维矩形。

然后，在那个可变大小的矩形内，我有几个对象（角色、怪物、NPC）。玩家可以选择这个矩形的位置，我必须检查该位置是否有怪物或角色。

到目前为止，我用列和行创建了一个名为 GameMatrix 的自定义类，并且说列有 3000x2000 个位置（角色的区域视图）。

当我的游戏玩家点击所述坐标时，我必须对foreach()矩阵内的每个元素执行一次，而且大多数情况下它是空的。

有没有更好的方法来解决这个问题？具体来说，我在问什么是最好的方法，有一个非常大的矩形和一个坐标，以一种有效的方式检查所述坐标内是否有对象。

忘了提，但这是在服务器端每毫秒完成几次。所以我需要很多表现。

编辑：忘了提，我使用的是 C#。

score 4 · Accepted Answer

您应该使用四叉树实现，除非网格中的项目数量非常少（比如几十个项目），在这种情况下，线性搜索（同时蛮力检查所有项目）可能是最好的选择。

看这里

请注意，可以快速有效地查询四叉树，但更新成本更高，也就是说，如果您的项目在地图上移动很多，则要获得良好的性能，这将变得更加复杂。

score 2 · Accepted Answer

我建议先尝试最简单的解决方案，然后再考虑优化。

尝试使用数组。随时改进您的解决方案。根据您的设置，列表或哈希映射也可能很有趣。

2 回答 2