網路遊戲中地圖隨機位置刷新物品的演算法如何實現?

現在的實現是把地圖中所有可以放置物品的點讀到伺服器上的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
我讀完題第一反應完全沒到要優化的地步,伺服器不在乎???