• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

lua实现游戏抽奖的几种方法

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

^_^内容原创,禁止转载


 假设配置如下:

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

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
lua学习之逻辑运算符not,and,or发布时间:2022-07-22
下一篇:
redis lua发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap