03-16-2003, 02:49 PM
This has nothing to do with Diablo 2 really but about random pick. So it is in part Off Topic.
One thing that always intrigue me, is how programmers end up solving a situation of picking a random "thing" out of a list of possible picks. Especially if that list is of variable size and as in the case here, each entry should have a varying probability. There are good and there are bad solutions of course. For a bad one, look at how the Diablo 1 game picked a random spell for a book for example (check my guide, I have it there). here, when picking an item to lose a durability, I would claim they have a semi good solution.
Just to recap. The game picks an item slot at random (looping until the slot actuall has an item that can lose durabilty). Then make a random number (Rnd [x] where x is the number Isolde posted), if the random value is not 0, it loops and pick a new item slot.
Now, we don't have THAT many item slots and the x value is small so practically we should not have to roll THAT many random values and not loop THAT many times. Still, theoretically, the game could get stuck for a noticable length of time.
One solution that is used (at least last time I checked) for picking affixes, which is a similar situation, is to built a table holding only the available choises (if applied to the durability loss, holding each slot that has an item that CAN lose durability). One sum up each of those entries in the table x value and then make a random call that generate a value in the 0 to sum_x -1 range and then start from the start of the tabel subtracting each entries probability value until one get to the picked random value. The current slot is the one picked.
As I mentioned in my other, old, post. The actual probability of being picked would differ some but that is just a matter of picking the probability values to match the final result one want.
So, is there another solution? Yes, there is. It works in all the above situations and even in a situation were you don't really know how many available entries there is.
Basically this is how it works. I will first giev an example were each possible entry has an equal chance of getting picked.
You start with the first item, it has a 1 in 1 chance of getting picked as the current "winner". next, we get the second item, it has a 1 in 2 chance of replacing the current winner as a new winner. The third item has a 1 in 3 chance to replace the current winner (which ever it happens to be out of the two first items) and so on were each item has a 1 in item_number chance to be replace the current winner. When we reach the final item, whatever happens to be the current winner is the item to be picked.
Feel free to verify this yourself and see that it actually create an equal chance for each item to be picked.
For a situation were we have a variable chance to be picked, we will make a slight adjustment. Instead of a 1 in item_number chance to replace the winner we make it a 1 in sum_of_probabilites_so_far chance. That is, for the third item we sum up the relative probability of an item to be picked for the items number 1, 2 and 3 and make a 1 in that value chance. That is the actual probability for an item to be picked is its own probability value divided by the sum of all items probability.
Again, feel free to verify this works.
So, what is the drawbacks and advantages. Well, some that I can think of is that a good thing is that you will have a predetermined number of "loops" and calls for rando number to pick your item. That is, you don't "loop until we get a result we are happy with). It also does not need to build a table which in itself also means you need to loop through all items at least once, possibly in part twice (see above). However, you DO need to llop through all items, that is, there is no "1 random call to pick it". If your random number generator's code is long and time consuming, it might time wise be worse than building a table for example, however with a good random number generator it is not really much code each time and you can even inline it.
Oh well. Just though I should mention it. I have seen several places were such a method would actually have been good in D2 (and also several places were it would not have been a good choice). However, I have not seen anywere were it (or something similar) have actually been used. I have seen several "not so good" other solutions though.
Comments? Flames? Complains? Just had some time to kill making a post :)
One thing that always intrigue me, is how programmers end up solving a situation of picking a random "thing" out of a list of possible picks. Especially if that list is of variable size and as in the case here, each entry should have a varying probability. There are good and there are bad solutions of course. For a bad one, look at how the Diablo 1 game picked a random spell for a book for example (check my guide, I have it there). here, when picking an item to lose a durability, I would claim they have a semi good solution.
Just to recap. The game picks an item slot at random (looping until the slot actuall has an item that can lose durabilty). Then make a random number (Rnd [x] where x is the number Isolde posted), if the random value is not 0, it loops and pick a new item slot.
Now, we don't have THAT many item slots and the x value is small so practically we should not have to roll THAT many random values and not loop THAT many times. Still, theoretically, the game could get stuck for a noticable length of time.
One solution that is used (at least last time I checked) for picking affixes, which is a similar situation, is to built a table holding only the available choises (if applied to the durability loss, holding each slot that has an item that CAN lose durability). One sum up each of those entries in the table x value and then make a random call that generate a value in the 0 to sum_x -1 range and then start from the start of the tabel subtracting each entries probability value until one get to the picked random value. The current slot is the one picked.
As I mentioned in my other, old, post. The actual probability of being picked would differ some but that is just a matter of picking the probability values to match the final result one want.
So, is there another solution? Yes, there is. It works in all the above situations and even in a situation were you don't really know how many available entries there is.
Basically this is how it works. I will first giev an example were each possible entry has an equal chance of getting picked.
You start with the first item, it has a 1 in 1 chance of getting picked as the current "winner". next, we get the second item, it has a 1 in 2 chance of replacing the current winner as a new winner. The third item has a 1 in 3 chance to replace the current winner (which ever it happens to be out of the two first items) and so on were each item has a 1 in item_number chance to be replace the current winner. When we reach the final item, whatever happens to be the current winner is the item to be picked.
Feel free to verify this yourself and see that it actually create an equal chance for each item to be picked.
For a situation were we have a variable chance to be picked, we will make a slight adjustment. Instead of a 1 in item_number chance to replace the winner we make it a 1 in sum_of_probabilites_so_far chance. That is, for the third item we sum up the relative probability of an item to be picked for the items number 1, 2 and 3 and make a 1 in that value chance. That is the actual probability for an item to be picked is its own probability value divided by the sum of all items probability.
Again, feel free to verify this works.
So, what is the drawbacks and advantages. Well, some that I can think of is that a good thing is that you will have a predetermined number of "loops" and calls for rando number to pick your item. That is, you don't "loop until we get a result we are happy with). It also does not need to build a table which in itself also means you need to loop through all items at least once, possibly in part twice (see above). However, you DO need to llop through all items, that is, there is no "1 random call to pick it". If your random number generator's code is long and time consuming, it might time wise be worse than building a table for example, however with a good random number generator it is not really much code each time and you can even inline it.
Oh well. Just though I should mention it. I have seen several places were such a method would actually have been good in D2 (and also several places were it would not have been a good choice). However, I have not seen anywere were it (or something similar) have actually been used. I have seen several "not so good" other solutions though.
Comments? Flames? Complains? Just had some time to kill making a post :)
There are three types of people in the world. Those who can count and those who can't.