c# - 网格的最优高密度二元空间划分

Question

我正在编写一个游戏，其中角色在随机生成的 map 上实时移动(正如所显示的那样。)这给我带来了一个有趣的数据结构问题。 map 是在它进入视野时生成的，在角色周围的一个圆圈中(可能是 20-60 个图 block )，所以在有数据的地方，它非常密集，并且都在网格中。但是，在没有数据的地方，可能会有巨大的、未生成的空间。角色可以绕一个巨大的圆圈走，例如，在广阔的空白空间周围创建一个瓷砖环。

一个简单的矩阵会产生大量不必要的开销，并浪费大量空间。不过，典型的 BSP 似乎会导致性能大幅下降，因为数据具有密集的网格状特性。

你有什么建议？矩阵 - 四叉树 - 两者的某种混合体？

Answer 1

我正在考虑在我正在开发的游戏中实现类似的东西。我将创建一个可以像 2D 数组 ex 一样访问的自定义类。 map[x][y] 但底层数据类型更接近哈希表。类似于 data[x.Value.ToString() + ","+ y.Value.ToString()]

我的游戏相当基础，因为我的方 block 只会是可行走的、致命的或不可行走的。

不过我对更优雅的解决方案很感兴趣 :D