网络游戏中地图随机位置刷新物品的算法如何实现?

现在的实现是把地图中所有可以放置物品的点读到服务器上的list中,然后随机。

现在list中一共要存储几十万个点,想问下有什么更好的实现方式吗,谢谢。

Milo   (游戏程序员、《游戏引擎架构》译者)     752018-09-02 15:15:58

假设可放置物品的位置为 n \times n 的二值图像,当中像素为1表示可放置,而需求是要均匀地采样像素为 1 的坐标。

现时题主的方法是把可放置的坐标存储为列表,然后均匀采样。每个坐标需用 \lceil \log_2 n^2 \rceil=\lceil2\log_2 n\rceil 个比特存储,所以最坏的空间复杂度应为 O(n^2\log n) ,而采样的时间复杂度为 O(1) 。例如 4096 \times 4096 的地图,用 32 位整数存储坐标,那么最坏情况需要 64MB 存储空间。

那么问题是,能否降低空间复杂度的同时,不会增加太多时间复杂度?

我想到一个方法是,先统计每行中像素为 1 的出现次数,然后做成直方图,再离散采样这个分布。常用的离散采样方法是别名方法(alias method),它采用 O(n) 的空间存储预计算的数据,然后可用 O(1) 时间采样。

选择到某一行之后,可以即时从二值图像生成列表,这需 O(n) 时间和 O(n) 空间。那么,在空间上,这个方法只需用 O(n^2) 存储二值图像、 O(n) 的别名方法预计算表及 O(n) 的时列表,整体空间为 O(n^2) ,而运行时时间复杂度为 O(n) 。同样对于 4096 \times 4096 地图,最大的存储空间是二值图像,只需 2MB 空间。

如果可放置物品的位置都是比较连续的,那么我们可以把每行的表示方法改为区间列表,在每行再用别名方法去抽取区间。如果每列最多有 m 个区间,那么空间复杂度为 O(nm) ,时间复杂度为 O(1) 。假设 4096\times 4096 地图中每行平均有 16 个区间,而别名方法每项需用 16 字节,那么大约只需 1MB 空间,又能达到 O(1) 时间。

酱紫君     12018-09-02 15:45:42
我读完题第一反应完全没到要优化的地步,服务器不在乎???