Page 1 of 2
Efficient way of distributing items
Posted: Tue Aug 02, 2022 2:06 pm
by Gunroar:Cannon()
I already have one but was wondering if anyone has more efficient ideas.
I have this, just as an example
Code: Select all
...
local n = math.random()*100
if n <= 5 then
return "super_sword_gun"
elseif n <= 30 then
return "plasma_gun"
elseif n <= 60 then
return "rifle"
elseif n <= 101 then
return "pistol"
end
...
Re: Effecient way of distributing items
Posted: Tue Aug 02, 2022 2:32 pm
by GVovkiv
Maybe something like that?
Code: Select all
-- Table with weapons
weapons = {
"coolWeapon1", -- 1
"yetAnotherWeapon", -- 2
"coolWeapon2", --3
etc,
}
-- when you need to get weapon:
weapon = weapons[love.math.random(1, 3)]
-- which may be wraped in function:
getWeapon = function()
return weapons[love.math.random(1, 3)]
weapon = getWeapon()
Re: Effecient way of distributing items
Posted: Tue Aug 02, 2022 2:46 pm
by milon
GVovkiv's method will result in a flat linear distribution, meaning all outcomes are equally likely. You don't always want that (but sometimes you do).
Gunroar's method is a little cumbersome, but it's got a non-linear distribution. You could modify it a bit to be easier to manage. Something like this, maybe:
Code: Select all
...
local weapons = {}
weapons[1] = {name = "super_sword_gun", rarity = 5, ...} -- define other weapon specs too?
weapons[2] = {name = "plasma_gun", rarity = 30, ...}
-- etc
...
local n = love.math.random(100) -- you could even specify a weapons[0] or a weapons.max instead of hardcoding '100' to make later additions easier
for i = 1, #weapons do
if n < weapons[i].rarity then return weapons[i].name end -- if you've got your weapon aspects all defined in one place, it would be better to return the table index instead of the weapon name
end
...
Re: Effecient way of distributing items
Posted: Tue Aug 02, 2022 5:25 pm
by darkfrei
Code: Select all
function weighted_random (weights)
local summ = 0
for i, weight in pairs (weights) do
summ = summ + weight
end
if summ == 0 then return end
-- local value = math.random (summ) -- for integer weights only
local value = summ*math.random ()
summ = 0
for i, weight in pairs (weights) do
summ = summ + weight
if value <= summ then
return i, weight
end
end
end
Code: Select all
local weapons = { gun = 0.1, bow = 0.2, bfg = 42 }
local weapon, weight = weighted_random (weapons) -- normally returns: "bfg" 42
It can be easily changed for weights as {name = "bfg", weight = 42} and use the ipairs for it.
Re: Effecient way of distributing items
Posted: Tue Aug 02, 2022 7:09 pm
by milon
That's even better IMO. But if you're going that route, take it one step further. Calculate the sum ahead of time once (or whenever the table changes) and store it in memory, rather than re-calculating it every time a random weapon is created.
Re: Efficient way of distributing items
Posted: Tue Aug 02, 2022 7:33 pm
by Gunroar:Cannon()
I guess Gvovkiv's method could work for quick and simple implementation though it
would be linear and milon's rarity version works though I think the list of items should be shuffled to avoid picking the same thing if there's more than one item with the same rarity.
darkfrei wrote: ↑Tue Aug 02, 2022 5:25 pm
Code: Select all
function weighted_random (weights)
...
Oh, my. weighted randoms. I guess that's one way to do it. I normally try to avoid that function because I never fully understood it but I see how it could work.
I also thought of something like this
Code: Select all
items = {
-- [percentage] = item(s)
[50] = {lame_gun, okay_gun, lamest_gun},
[20] = {power_gun, strong_gun},
[25] = {crossbow, rifle},
[5]. = {ultra_rifle, mega_cheeseburger_gun}
}
Though I think weighted stuff might be better because it may be more legible.
milon wrote: ↑Tue Aug 02, 2022 7:09 pmCalculate the sum ahead of time once (or whenever the table changes) and store it in memory, rather than re-calculating it every time a random weapon is created.
Would that really help performance? The function kind of looks like it won't take much, or maybe I'm underestimating it?
edit: dang it, spelled effeffcient effisient efficient wrongly
Re: Efficient way of distributing items
Posted: Wed Aug 03, 2022 1:11 am
by pgimeno
Well, milon's suggestion is certainly a good idea. Even more if the table is sorted.
For readability, have the weights verbatim. For efficiency, precalculate the accumulated weights.
There are two nice things about sorted accumulated weights: you can find the sum by examining the last element, and you can apply a binary search to find which element to return, which is fast.
By the way, if all the elements are integer, ffs use math.random(1, N) where N is the sum, instead of math.random()*N.
Re: Efficient way of distributing items
Posted: Thu Aug 04, 2022 6:01 pm
by milon
Gunroar:Cannon() wrote: ↑Tue Aug 02, 2022 7:33 pm
... milon's rarity version works though I think the list of items should be shuffled to avoid picking the same thing if there's more than one item with the same rarity.
I suppose you
could shuffle it, but it's really not necessary. You're picking a random number which is linearly distributed between 1 and
N. The rarity specifies the
range covered by the item - it really has nothing to do with the order it's found in. Take a look at this super crappy picture:
- Weighted Random.png (346 Bytes) Viewed 2215 times
Red is a rare outcome, black is very common, blue and green are in between. Let's say the left edge is 1 and the right edge is 100. Picking any number at random 1-100 will most likely land you in black regardless of the arrangement of the colors - just because black covers the greatest range. Similarly, you are least likely to get red because it covers the smallest range of numbers. That's the general idea behind weighted randoms. Does that help clarify?
Re: Efficient way of distributing items
Posted: Thu Aug 04, 2022 6:24 pm
by Andlac028
milon wrote: ↑Thu Aug 04, 2022 6:01 pm
Gunroar:Cannon() wrote: ↑Tue Aug 02, 2022 7:33 pm
... milon's rarity version works though I think the list of items should be shuffled to avoid picking the same thing if there's more than one item with the same rarity.
I suppose you
could shuffle it, but it's really not necessary. You're picking a random number which is linearly distributed between 1 and
N. The rarity specifies the
range covered by the item - it really has nothing to do with the order it's found in. Take a look at this super crappy picture:
Weighted Random.png
Red is a rare outcome, black is very common, blue and green are in between. Let's say the left edge is 1 and the right edge is 100. Picking any number at random 1-100 will most likely land you in black regardless of the arrangement of the colors - just because black covers the greatest range. Similarly, you are least likely to get red because it covers the smallest range of numbers. That's the general idea behind weighted randoms. Does that help clarify?
I think, there is an logical error in your code you missed:
milon wrote: ↑Tue Aug 02, 2022 2:46 pm
Code: Select all
...
local weapons = {}
weapons[1] = {name = "super_sword_gun", rarity = 5, ...} -- define other weapon specs too?
weapons[2] = {name = "plasma_gun", rarity = 30, ...}
-- etc
...
local n = love.math.random(100) -- you could even specify a weapons[0] or a weapons.max instead of hardcoding '100' to make later additions easier
for i = 1, #weapons do
if n < weapons[i].rarity then return weapons[i].name end -- if you've got your weapon aspects all defined in one place, it would be better to return the table index instead of the weapon name
end
...
Suppose you have 2 item with same rarity, like this:
Code: Select all
weapons[1] = {name = "super_sword_gun", rarity = 5, ...}
weapons[2] = {name = "super_plasma_gun", rarity = 5, ...}
If you pick random number smaller < 5, the for loop will always return "super_sword_gun" as it is checked first. You can fix it by adding up rarity to last rarity and max random as sum of rarities.
It can be then further optimized by pre-calculated prefix sums and finding items with binary search to O(log n) instead of O(n) as @pgimeno mentioned
Re: Efficient way of distributing items
Posted: Fri Aug 05, 2022 5:42 pm
by milon
Andlac028 wrote: ↑Thu Aug 04, 2022 6:24 pm
Suppose you have 2 item with same rarity, like this:
Code: Select all
weapons[1] = {name = "super_sword_gun", rarity = 5, ...}
weapons[2] = {name = "super_plasma_gun", rarity = 5, ...}
If you pick random number smaller < 5, the for loop will always return "super_sword_gun" as it is checked first. You can fix it by adding up rarity to last rarity and max random as sum of rarities.
That's actually what I was trying to say. I guess I didn't explain it very well. Ultimately, equal rarity implies equal chance of selection.
Andlac028 wrote: ↑Thu Aug 04, 2022 6:24 pm
It can be then further optimized by pre-calculated prefix sums and finding items with binary search to O(log n) instead of O(n) as @pgimeno mentioned
I agree with pgimeno's suggestion for using a binary search. I just wanted to show a basic example that would clarify the weighted random issue. (Which I apparently failed to do, lol.)