网格的最优高密度二元空间划分
我正在编写一个游戏，其中一个角色在一个随机生成的地图上实时移动（因为它被揭示。）这引出了一个有趣的数据结构问题。 地图在进入视图时生成，围绕角色的圆圈（可能是20-60个图块），因此在有数据的地方，它非常密集，并且全部在网格中。 但是，如果没有数据，可能会有巨大的，未经生成的空间。 例如，角色可以走在一个巨大的圆圈中，在巨大的空白空间周围创造一圈瓷砖。
简单的矩阵会产生大量不必要的开销，并浪费大量空间。 但是，典型的BSP似乎会因为数据的密集网格特性而导致性能下降。
你有什么建议？ 矩阵 – 四叉树 – 两者的混合？
我正在考虑在我正在制作的游戏中实现类似的东西。 我将创建一个可以像2D数组ex一样访问的自定义类。 map[x][y]但基础数据类型更接近哈希表。 像data[x.Value.ToString() + "," + y.Value.ToString()]
我的游戏非常基本，因为我的瓷砖只能行走，致命或不可行走。
我对更优雅的解决方案感兴趣：D
我在过去的一个月里一直在处理这个问题，并提出了我认为相当不错的解决方案。 它不像纯矩阵那么快，但具有无限可扩展的优势（在int的限制范围内）。
基本上，它是一个向上构建的二进制空间分区（而不是向下构建，如四叉树。）如果写入当前分配的矩阵空间之外的点，它将生成更大的节点并进行扩展。 如果节点的子节点的大部分都是分配矩阵，它会将它们聚合到自身并删除它们的引用。 这意味着您使用的边界越明确，您获得的性能就越好，因为这种结构就像矩阵一样。
我已经在这里发布了我的代码，并将在未来尝试编写某种演示，并转移到更好的托管网站。
不要犹豫，让我知道您的想法，或者如果您对此有任何疑问。