lua实现游戏抽奖的几种方法?
^_^内容原创,禁止转载
假设配置如下:
1 local reward_pool = { 2 {weight = 1000, item = {type = 100218, num = 12}}, 3 {weight = 1000, item = {type = 100218, num = 12}}, 4 {weight = 1000, item = {type = 100218, num = 12}}, 5 {weight = 1000, item = {type = 100218, num = 12}}, 6 {weight = 1000, item = {type = 100218, num = 12}}, 7 {weight = 1000, item = {type = 100218, num = 12}}, 8 }
1.顺序查找,预处理时间复杂度O(n),抽奖最坏情况O(n)
1 --预处理 2 local N = #reward_pool 3 local total_weight = 0 4 for _, v in ipairs(reward_pool) do 5 total_weight = total_weight + v.weight 6 end 7 8 --实现 9 local rand_weight = math.random(total_weight) 10 local reward_index 11 local _total_weight = 0 12 for k, v in ipairs(reward_pool) do 13 _total_weight = _total_weight + v.weight 14 if _total_weight >= rand_weight then 15 reward_index = k 16 break 17 end 18 end
2.按照离散思路进行分割,二分查找,预处理时间复杂度O(n),抽奖最坏情况O(logn)
1 --预处理 2 local N = #reward_pool 3 local com_weight = 0 4 for _, v in ipairs(reward_pool) do 5 com_weight = com_weight + v.weight 6 v.weight = com_weight 7 end 8 9 --实现 10 local left, right = 1, #reward_pool 11 while right >= left then 12 local mid = math.floor((left + right) / 2) 13 local mid_weight = reward_pool[mid].weight 14 if value == mid_weight then 15 right = right - 1 16 break 17 elseif value < mid_weight then 18 right = mid - 1 19 else 20 left = mid + 1 21 end 22 end 23 right = right + 1 --此时right为reward_pool中抽到的索引
这种方法在实际上是对第一种方法的优化,在大多数情况下都可以取代第一种方法,但取舍还要看实际情况,一个极端且明显的例子如下:
1 local reward_pool = { 2 {weight = 1000, item = {type = 100218, num = 12}}, {weight = 1000, item = {type = 100218, num = 12}}, 3 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}}, 4 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}}, 5 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}}, 6 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}}, 7 }
3.AliasMethod,个人实现的预处理O(3n),抽奖时间复杂度O(1),下面是实现过程,证明日后有时间再整理给出
1 queue = {} 2 3 function queue:new() 4 local res = {first = 0, last = -1} 5 self.__index = self 6 setmetatable(res, self) 7 return res 8 end 9 10 function queue:push(value) 11 self.last = self.last + 1 12 self[self.last] = value 13 end 14 15 function queue:pop() 16 local first = self.first 17 if first > self.last then 18 self.first = 0 19 self.last = -1 20 return nil 21 end 22 local value = self[first] 23 self[first] = nil 24 self.first = self.first + 1 25 return value 26 end 27 28 function queue:front() 29 return self[self.first] 30 end 31 32 --预处理 33 local N = #reward_pool 34 local total_weight = 0 35 for _, v in ipairs(reward_pool) do 36 total_weight = total_weight + v.weight 37 end 38 39 local Prob = {} 40 local Alias = {} 41 local weightN_queue_L = queue:new() 42 local weightN_queue_U = queue:new() 43 for k, v in ipairs(reward_pool) do 44 local weight_N = v.weight * N 45 if weight_N == total_weight then 46 Prob[k] = weight_N 47 else 48 local tb = {index = k, value = weight_N} 49 local qu = weight_N > total_weight and weightN_queue_U or weightN_queue_L 50 qu:push(tb) 51 end 52 end 53 54 while true do 55 local l_qu = weightN_queue_L:pop() 56 if not l_qu then 57 break 58 end 59 local u_qu = weightN_queue_U:front() --或直接pop,比total_weight大再push回去 60 Prob[l_qu.index] = l_qu.value 61 Alias[l_qu.index] = u_qu.index 62 u_qu.value = u_qu.value + l_qu.value - total_weight 63 if u_qu.value < total_weight then 64 weightN_queue_U:pop() 65 weightN_queue_L:push(u_qu) 66 elseif u_qu.value == total_weight then 67 weightN_queue_U:pop() 68 Prob[u_qu.index] = total_weight 69 end 70 end 71 weightN_queue_U = nil 72 weightN_queue_L = nil 73 74 --实现 75 local n = math.random(N) 76 local weight = math.random(total_weight) 77 local reward_index = weight > Prob[n] and Alias[n] or n