Jump to content
  • Advertisement
Sign in to follow this  
freeworld

how to randomly select an item from a list with each item having a different chance..

This topic is 3612 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

OK here's my dilema. I've got a list of items all of wich have a different percentage chance of being able to show up. ie item1 = 40% item2 = 20% item3 = 80% Now I want to generate a list of say 20 items, looping through the list, I need to randomly pick one of the above items, then go onto the next element in the list.ie

std::vector<int> items;

for (int index=0; index<max_index; ++index)
{
    int item = // ?? random item
    items.push_back(item);
}


whats an easy way to generate the random item using std::rand(). I was thinking of sorting the list by it's percentage, the highest being first, and go through the list of items. for each one I'd pick a random number between zero and 100. if the number was higher than the percentage chance then that number would be pick. keep looping till one is picked? This just seems like the low percentage ones would rarely if never show up?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by freeworld
OK here's my dilema.

I've got a list of items all of wich have a different percentage chance of being able to show up. ie

item1 = 40%
item2 = 20%
item3 = 80%

Now I want to generate a list of say 20 items, looping through the list, I need to randomly pick one of the above items, then go onto the next element in the list.ie

*** Source Snippet Removed ***

whats an easy way to generate the random item using std::rand().

I was thinking of sorting the list by it's percentage, the highest being first, and go through the list of items. for each one I'd pick a random number between zero and 100. if the number was higher than the percentage chance then that number would be pick. keep looping till one is picked? This just seems like the low percentage ones would rarely if never show up?


1) get the sum of the "chance" for each item (we can call this variable "sum")
2) generate a random number between 0 and sum (lets call this value "r"
3) For each item in the list do:
if (r<chance) select this item
else r-=chance;

(The list does not need to be sorted but it would find the right item faster most of the time if it was sorted with the most likely item first in the list)

Share this post


Link to post
Share on other sites
Quote:
Original post by Megahertz
Quote:
This just seems like the low percentage ones would rarely if never show up?


I think thats the point =P


The problem with his original post is that he allows the sum of the chances to exceed 100% while only selecting a single item, thus if he has 3 items with the chances 90,80,70 using his algorithm the chance of getting the second item in the list would be 0.1*0.8 , or 8%, the chance of the last item being selected would be 0.02*0.7 , or 1.4% (And there would also be a chance that no item gets selected)

Share this post


Link to post
Share on other sites
let me try to walk through your example to clarify it for myself.

item1 = 40%
item2 = 20%
item3 = 80%

total_chance = 140%

random number = 30
item1 !less_than
random_number - item1 = -10

This would mean any item that comes next would be selected no matter what. Even if the list was sorted, this method seems bias towards the first items in the list.

I need a method that isn't biased, the percentages I put for the items should actually matter and not invariably scale so dramatically as the percentage gets lower.

Share this post


Link to post
Share on other sites
The first problem is that all your % don't add up to 100%. This means that no item in your list will show up with the correct percentage no matter what you do.

This is first off usually offset in a game by having each entity have drop rate tables. So creature X has 95% chance to drop gold. 4% chance to drop a knife. .9% chance to drop a sword. .1% chance to drop an amulet.
Secondly, for ease of organization go one table deeper, and say "droped a knife?" has a 90% chance of a broken knife. 5% chance of a shiny knife. 4% chance of a glistening knife. 1% chance of a vorpal knife.

OR

What you described rolls more like 80%, 8%, 2.4%. Since it each item becomes "% chance assuming nothing dropped before me".

OR

You could turn each % into points 40,20,80. And roll out of 100xItemCount. where 0-40 is the first item, 41-60 is the second, 61-140 is the third and the remaining 160 rolls mean no drop(or default amount of gold) (or forgo the rolling out of 100xItemcount. and just roll from the sum of the points so you don't have to worry about the "no drop" case explicitly)

freewood. in edit to your post above mine. it is not biased, but the numbers you give as drop rates are no longer the real % drop rate. But this is unavoidable due to your % not adding up to 100%

Share this post


Link to post
Share on other sites
whould it make since to do sort of like i said before, but eliminating items as I go along the list like a tournament design.

for each item, choose random number 0-100, if number is lower then the items chance, it stays in the list, if its above I remove it from the list. I then keep going through the list removing items till there's only one item left??

Share this post


Link to post
Share on other sites
Quote:
Original post by freeworld
let me try to walk through your example to clarify it for myself.

item1 = 40%
item2 = 20%
item3 = 80%

total_chance = 140%

random number = 30
item1 !less_than
random_number - item1 = -10

This would mean any item that comes next would be selected no matter what. Even if the list was sorted, this method seems bias towards the first items in the list.

I need a method that isn't biased, the percentages I put for the items should actually matter and not invariably scale so dramatically as the percentage gets lower.


The method i posted isn't biased, if your random number is 30 it selects the first item in your case, if its between 40 and 60 it selects the second item, and if its between 60 and 140 it selects the last item. (The actual chance for each item to be selected is your listed value divided by 1.4 which means that their probability relative to eachother remains the same, item3 is twice as likely to get selected as item1 which in turn is twice as likely to get selected than item2)

Share this post


Link to post
Share on other sites
Quote:
Original post by SimonForsman...



Then you meant if (random_number < item_chance), that makes alot more sense. I actually like that one I might run with it and see what happens.

Share this post


Link to post
Share on other sites
Quote:
Original post by SimonForsman
3) For each item in the list do:
if (r<chance) select this item
else r-=chance;
Both should be the individual item's "chance" instead of the total sum. I'm sure that's what you meant to post though. :)

BTW, I believe this is called roulette selection. You might want to look in to that. I know boost has a very complete random number library, they may even have what you're looking for.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!