Efficient way of distributing items

[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

...

[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()

[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
...

[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.

[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.

[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.

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.

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.

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

[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.

[milon]

... 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 2216 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?

[Andlac028]

... 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:

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

[milon]

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.

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.)