Map value onto range

[WaterKnight]

In ORPGs for example, enemies may drop random loot and furthermore that loot may be exclusive as to exactly spawn a single item. For this purpose, they possess a table which governs the types of all possible items and their chances/weight to appear.

Now how do you roll for an item? One option would be to accumulate the weights first, determine a random int from that, then iteratively accumulate the weights again and stop if the sum becomes greater than what was rolled.

Another possibility is to directly assign the same item to multiple slots in a data structure depending on its weight. In the above scenario, you could scale the table down for optimization. For example

{itemA: 3; itemB: 6; itemC: 9} is as good as {itemA: 1; itemB: 2; itemC: 3}

in terms of chances. The relative weight for each element remains the same. However, this of course means you may have to store a lot in the container structure and it requires a heavier init.

As a third simple option I want to state you could also roll for each item individually with their respective chance, multiply the result with the weight of the item and check for the highest product.

Anyway, that's iterative too and needs more randomizations.

My question is if there is a better, efficient approach or maybe a hybrid form that neither inflates the memory too much nor has O(n).

Additionally, in contrast to the described randomization scenario, which is somewhat different, I depict a 2nd task:

You know the unit limit events, unit's mana becomes greater than 100 for example. If you were to reconstruct this event yourself, you would hook onto the unit's mana points, you acquire the change from a source value to a target value.

There may be a lot of limit events on the same unit and with different bounds: unit's mana becomes greater than 20, greater than 50, greater than 100, greater than 499 etc. Iteratively checking each event for its limit and whether the current unit's state matches it, once more is not very convenient. One would rather like to determine the corresponding events directly by the value the unit's mana has adopted. And that's why having a method to assign to a number range, this case is even special because it greater than x would mean from x to infinity, would be a bless.

Thanks for reading/replying

 

[Solu9]

I think it depends on how you would like the drops to work.
Fx. if you take a Diablo II approach. You could use item life as the chance factor combined with the item dropping monster's level.

Throw the items into an array and make a real array in which you store the life of the corresponding item array.

When the drop is to be calculated the monster's level is determined first to determine the highest level of item that can be dropped. Call the monster's level X.
Then set a temp real to (random number between 1 and (the real array[X])

Then you do the iteration of the real array and stop it when the temp real is equal to or higher than the real array[x] you spawn that item.

Anyway. That's how I would do it.

Edit:
Correct me if I got the purpose of this thread completely screwed up.

 

[Zeatherann]

Just use theitempool type and the natives to work with it. This will do exactly what you want. You can check the chosen item (return value of the drop function) to see if that is a dummy item to represent 'nothing dropped' or a dummy item to represent another pool to pick an item from.

 

[edo494]

for the second question, you may store the events in ordered list by the mana/life/whatever, and also store integer of current position in the list, and as mana increases, you run the events and increase integer. Something like this:

Unit has 10 mana, event list is:
on6, on8, on15, on17, on19, on22, on50

so your positioning integer is at 2, and when your unit recovers up to 15 mana, you run on15 and increase integer. Or lets say your unit regens up to 20 instantly, you just keep increasing integer and running events until the event requires more mana(so you would check if you have enough for on15, you have, run it and increase integer, check for on17, yup, run it and increase integer. The same for 19, but you check 22 and you see that you cant, you stop the loop).

While you may still loop, you will not loop O(n) with this approach, however this requires a ordered list

 

[Zeatherann]

A Solution.

This is my solution to your problem (it is untested and might have syntax errors). It is a simple system to recursivly drop items from tables and allows for easy assigning of item drops. This system assumes you know how to construct a single table by creating an itempool and adding item types to it. The globals used here are shown in a globals block so you can better integrate this system with your map(s). It should all be self-explainatory. There is one problem in that removing an itempool from a unit isn't shown here. I tried making it and couldn't create a workable function in the little time I have. I might add one later if you want one. Though, if you only care about assigning pools to units, than this is just fine. You can replace the instances if unitwithwidgetto extend the system more to also be workable with destructables and even items (yo dawg I heard you liked items and item drops). This solution is not the fastest method, as it uses hashtables. But it is an easy and clean solution. If you want to have the fastest then you'd have to adapt this system to use arrays instead of hashtable entries.

globals
    constant integer ItemPoolIndex=0
    constant integer ItemPoolNoItem='DROP'
    constant integer UnitItemPoolDataStart=0
    hashtable Hash=InitHashtable()
endglobals

function RegisterItemPool takes integer ItemId,itempool Pool returns nothing
    call SaveItemPoolHandle(Hash,ItemPoolIndex,ItemId,Pool)
endfunction

function UnitAddPool takes unit Unit,itempool Pool returns nothing
    local integer UnitHandleId=GetHandleId(Unit)
    local integer NumberOfPools=LoadInteger(Hash,UnitHandleId,UnitItemPoolDataStart)+1
    call SaveItemPoolHandle(Hash,UnitHandleId,UnitItemPoolDataStart+NumberOfPools,Pool)
    call SaveInteger(Hash,UnitHandleId,UnitItemPoolDataStart,NumberOfPools)
endfunction

function DropLoot takes real X,real Y,itempool Pool returns nothing
    local item Item
    local itempool MorePools=Pool
    local integer ItemId
    loop
        exitwhen MorePools==null
        set Item=PlaceRandomItem(X,Y,MorePools)
        set ItemId=GetItemTypeId(Item)
        set MorePools=null
        set MorePools=LoadItemPoolHandle(Hash,ItemPoolIndex,ItemId)
        if ItemId==ItemPoolNoItem then
            call RemoveItem(Item)
        endif
endfunction

function UnitDropLoot takes unit Unit returns nothing
    local integer UnitHandleId=GetHandleId(Unit)
    local real X=GetUnitX(Unit)
    local real Y=GetUnitY(Unit)
    local itempool Pool
    local integer NumberOfPools=LoadInteger(Hash,UnitHandleId,UnitItemPoolDataStart)
    loop
        exitwhen NumberOfPools<1
        set Pool=LoadItemPoolHandle(Hash,UnitHandleId,UnitItemPoolDataStart+NumberOfPools)
        call DropLoot(X,Y,Pool)
        set Pool=null
        set NumberOfPools=NumberOfPools-1
    endloop
endfunction

 

[Dr Super Good]

Diablo II used a loot tree.

You enter the tree at a pre-determined node (use a table to map monster type/area to a node). The entry node may not be the root and can be internal or even a leaf.

Each node then has X different children where X is any number greater than 0. A Child can be another node or an item class/type.

Each parent to child relationship has a weight attached to it governing the probability of traversing that path. Each node has an inherit weight attached to it governing the chance of failure. From these you can derive weight cut-off values for each parent to child traversal. A single roll of a random integer between 0 and maximum weight is then used as the input and applied to the cut-offs to determine where to traverse.

Determining the item to drop becomes an iterative process where you keep traversing the tree until you either hit a "failure" roll (no item) or until you hit an item class/item type (make item).

The main advantage of this approach is it allows you to inherit item drops from lower monsters or form certain drop classifications that can be merged with a single node.

Diablo II used it to inherit drops from lower level monsters. The best example being runes where killing a high end monster (World Stone Keep A5 Hell) would roll down from Zod all the way to the lowest rune if a rune drop type was determined. Gear also worked the same way, starting with the most advanced versions of items and dropping down to normal mode item types.

 

[Zeatherann]

This is indeed a good method, but with the limitations of JASS... would it not be better to use a class already built for this (itempool)? The recursive structure of the code I posted allows inheritance as well.

 

[Dr Super Good]

You posted that after I started writing my post. In any case I was explaining the logic behind a system, not giving specific implementation details.

 

[aple]

What do you mean by "Roll"?

Do you mean like how attack damage is calculated, the "Dice Roll"?

In which case, what about just in a trigger pick a random number from 1 to # and depending on what number is picked you spawn the item? If the random number "Rolls" 1, do this item and if it rolls 2 do that item.

EDIT: Or you could just use this as a seed to pick certain items. If it picks 1, then you go down one branch of seeds, pick one of the seeds randomly, and that seed has so many items to pick from.

If it rolls one then there is a list of seeds then it generates a string using characters from 0 to A, being 4 characters long. (With values from 0-9 then A) and two will result in B to K and etc. Idk, just random idea. xD

Or you could just take away the picking a random number to generate a seed and just randomly generate that 4-character long string using all characters and then each character goes down a different path. It's got 36 different paths to go down for the first character (0-9, A-Z) then 36 paths for the next and 36 for the third character and 36 for the last...Or however many characters long you want it to be.

 

[WaterKnight]

@Solu9: The items of the specific table for the unit/unit type are already known. No need to derive it from the unit's level.

@Zeatherann: I know the itempool/unitpool functions. But those are specifically for the native items/units. Using them as dummies to indicate struct instances would cause quite the extra burden. Anyway, I am asking for profound strategies, itempool/unitpool must also possess a realization.

The item loot of unit's was just a common example. The question was to effectively construct/roll from a list whose elements have different chances. Or the 2nd stated question how to map values to whole index ranges inside some container. If you can find a good solution for the 2nd one, it solves the first one as well because basically the weights would be index ranges.

@edo494: A sorted list sounds reasonable. If the unit's mana is not greater than on5, it's not becoming greater than on10 either. And checking the list should have a much higher frequency than insert/remove.

@aple: Roll as in rolling a dice, determining a random number/element from a pool. The problem and the reason why the direct indexing by a single GetRandomInt seems no good is that if you want to have different chances for the different elements, you would have to have the greatest common divisor and store the same element multiple times in the same data structure.

For example itemA shall have a chance of 35%, itemB 65% -> gcd is 5%, itemA has to be available 7 times, itemB 13 times.

The tree or graph approach sounds interesting because you could arrange it in a fashion that you gain the wanted probabilities

    /80%      \20%
  apple       redirection
             /50%          \50%
          pear              redirection
                            /20%        \80%
                         orange        strawberry

That would result in a 80% chance for apple, 10% pear, 2% orange, 8% strawberry, although you only save each one with a single percentage.

Yet is this not the same as

One option would be to accumulate the weights first, determine a random int from that, then iteratively accumulate the weights again and stop if the sum becomes greater than what was rolled.

execution effort-wise? You iterate for each element and compare until you drop out. Except that the accumulation is replaced by multiple randomizations.

What is worthwhile, however, is to place the greatest chances in the first positions to be checked, so there is a high possibility you can stop at this point.

 

[edo494]

well you know what I ended up doing for my drop system on my map that I will never release(cause I will never finish it ) is basically just storing list of [item, chance] for every unit type. And when the unit died I randomized the list so that it was shuffled to full randomness and then roll number in range [0, sum of chances inside list(stored in variable)] and then I iterated over the list and each item passed I decreased the value by the chance and if it hit 0 I would generate that item. It had some neat things(multiple drops, splitting to stacks) but it lacked things like "no drop" feature and it is not really the fully best approach, because while its average is O(log n), it will be closer to O(n/2), worst case being O(n) (n - number of items in the droplist).

For full and total description I would have to load the map up and check the HOOOOOOOORRIBLE script to see how I made it to sum to 100% and stuff like that

 

[Zeatherann]

Blizzard does something similar to this with this BJ function. It might shed light onto the 'mapping a value to a range' issue. And if you monitor the adding of items then you can save iterating over it twice by pre-calculating the max index.

function RandomDistChoose takes nothing returns integer
    local integer sum = 0
    local integer chance = 0
    local integer index
    local integer foundID = -1
    local boolean done

    // No items?
    if (bj_randDistCount == 0) then
        return -1
    endif

    // Find sum of all chances
    set index = 0
    loop
        set sum = sum + bj_randDistChance[index]

        set index = index + 1
        exitwhen index == bj_randDistCount
    endloop

    // Choose random number within the total range
    set chance = GetRandomInt(1, sum)

    // Find ID which corresponds to this chance
    set index = 0
    set sum = 0
    set done = false
    loop
        set sum = sum + bj_randDistChance[index]

        if (chance <= sum) then
            set foundID = bj_randDistID[index]
            set done = true
        endif

        set index = index + 1
        if (index == bj_randDistCount) then
            set done = true
        endif

        exitwhen done == true
    endloop

    return foundID
endfunction

 

[edo494]

thats pretty much the same thing but yea I cached the total "weigth" or chance or whatever but my code has a lot of control for like stack splitting, stack sizes and multiple drops so it has a lot of unreadable shit on top of this