Efficient way of distributing items

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Efficient way of distributing items

Post 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

...
Last edited by Gunroar:Cannon() on Tue Aug 02, 2022 7:33 pm, edited 1 time in total.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
GVovkiv
Party member
Posts: 668
Joined: Fri Jan 15, 2021 7:29 am

Re: Effecient way of distributing items

Post 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()
Last edited by GVovkiv on Tue Aug 02, 2022 3:48 pm, edited 1 time in total.
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Effecient way of distributing items

Post 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
...
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: Effecient way of distributing items

Post 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.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Effecient way of distributing items

Post 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.
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Efficient way of distributing items

Post 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
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Efficient way of distributing items

Post 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.
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Efficient way of distributing items

Post 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
Weighted Random.png (346 Bytes) Viewed 2037 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?
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
Andlac028
Party member
Posts: 174
Joined: Fri Dec 14, 2018 2:27 pm
Location: Slovakia

Re: Efficient way of distributing items

Post 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
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Efficient way of distributing items

Post 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.)
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
Post Reply

Who is online

Users browsing this forum: No registered users and 53 guests