网格的最优高密度二进制空间划分
我正在写一个游戏，其中一个角色在随机生成的地图上实时移动(正如它所揭示的那样)。这就引出了一个有趣的数据结构问题。地图是在它进入视图时生成的，在角色周围的圆圈中(可能是20-60个瓦片)，所以哪里有数据，它就会非常密集，并且都在一个网格中。然而，在没有数据的地方，可能会有巨大的未生成的空间。例如，角色可以在一个巨大的圆圈中行走，在广阔的空白空间周围创建一个瓷砖环。
一个简单的矩阵会产生大量不必要的开销，并浪费大量空间。然而，由于数据的密集、网格性质，典型的BSP似乎会导致巨大的性能下降。
你有什么建议？矩阵-四叉树-两者的某种混合？
回答 2
Stack Overflow用户
发布于 2010-08-01 03:54:04
在过去的一个月里，我一直在解决这个问题，并提出了一个我认为是相当好的解决方案。它不像纯矩阵那样快，但具有无限可扩展的优点(在int的限制内)。
基本上，它是一个向上构建的二进制空间分区(而不是向下构建，就像四叉树一样)。如果您写入当前分配的矩阵空间之外的点，它将生成一个更大的节点并展开。如果一个节点的大多数子节点被分配了矩阵，它会将它们聚合到自己中，并删除它们的引用。这意味着你使用的边界越明确，你就会获得越好的性能，因为这种结构越像矩阵。
我已经发布了我的代码here，将来我会尝试写一些演示，然后转到一个更好的托管站点。
请不要犹豫，让我知道你的想法，或者如果你有任何问题。
Stack Overflow用户
发布于 2010-06-30 01:18:32
我正在考虑在我正在开发的游戏中实现类似的东西。我将创建一个可以像二维数组ex一样访问的自定义类。map[x][y]，但底层数据类型更接近于哈希表。像data[x.Value.ToString() + "," + y.Value.ToString()]这样的东西
我的游戏是相当基本的，因为我的瓷砖将永远是可行走的，致命的，或不能行走的。
我感兴趣的是一个更优雅的解决方案:D
https://stackoverflow.com/questions/3142919
复制相似问题
腾讯云开发者
