Python。用于存储地图上对象坐标的数据结构

Question

我正在开发游戏服务器。我想要用于存储地图上对象的 3d 坐标（x、y、z）的数据结构。这个对象可以动态地改变它们的位置（移动、传送、被摧毁等）。我想根据他们在地图上的视觉位置以特定顺序存储此坐标。所以，我认为为此目的使用图表是不错的选择。但我不确定。

请注意，我需要存储许多对象（大约 4-5 千）的实时坐标。是否存在实现我需要的库或算法？

Answer 1

你想要一个像 Octree (for 3D spaces) or Quadtree 的空间结构（对于二维空间）。

他们将内容划分到将相邻坐标分组在一起的桶中。这使得围绕坐标的检查变得快速，因为只需要检查一个坐标桶（或者，只需要检查紧邻坐标桶的桶以进行更大的检查）。这可以极大地限制需要检查的对象的数量。

这些结构通常用于游戏中的碰撞检测。