I'm making really good progress on Pish Posh Push at the moment and my enthusiasm has given me improved lucidity when solving problems I encounter whilst coding. One problem I had recently was the random selection of prizes based on their value. It's fairly easy to choose a prize randomly that chooses higher valued items more frequently. You simply total all the values then generate a number within that range and select the item that matches your randomly generated number.
It becomes trickier when you need to make the higher valued items proportionally less common than your lower valued items. That means that a plastic toy valued at "1" should appear ten times more frequently than a metal toy valued at "10". The trick is to add up the values of the items as fractions of one. So the toy valued at "1" becomes "1/1" and the toy valued at 10 becomes "1/10". Add these together and generate a number in that range and you can easily select the cheap toy proportionally more often than the expensive one.
The algorithm in java looks like this:
private int getPrize() {
int i_prize = 0;
float f_max = 0;
// loop through prizes and total up values as a fraction of 1
for (int i=0;i<MAX_PRIZES;i++) {
f_max += 1 / (float) m_prizevalues[i];
}
// generate a random floating point number in the range of the total value of all prizes
float f_select = MathUtils.random(f_max);
// loop through prizes and select the one that matches the randomly generated value
for (int i=0;i<MAX_PRIZES;i++) {
if (f_select < (1 / (float) m_prizevalues[i])) {
// This prizes matches the selected value, stop searching
i_prize = i;
break;
} else {
// Does not match, deduct value of this prize and check against next
f_select -= (1 / (float) m_prizevalues[i]);
}
}
return i_prize;
}
Let me know in the comments below if you can see improvements that could be made, or can spot any problems and especially if you know of a better way that this can be done. One problem I can see is that at very high values the algorithm could start hitting the bounds of floating point accuracy. That could in principle cause a very high valued item to never get selected. For my own needs I'm not going to be in that magnitude so I've not gone to the trouble of calculating at what point that might start to be an issue.
This handy bit of code can be used in any situation where you need to select an item where higher valued items need to be more rare. A good example would be spawning loot in a rogue-like dungeon crawler. In that case you want your 10,000 gold value magic sword to be generated as loot a hundred times less frequently than your 100 gold value regular sword.
It becomes trickier when you need to make the higher valued items proportionally less common than your lower valued items. That means that a plastic toy valued at "1" should appear ten times more frequently than a metal toy valued at "10". The trick is to add up the values of the items as fractions of one. So the toy valued at "1" becomes "1/1" and the toy valued at 10 becomes "1/10". Add these together and generate a number in that range and you can easily select the cheap toy proportionally more often than the expensive one.
The algorithm in java looks like this:
private int getPrize() {
int i_prize = 0;
float f_max = 0;
// loop through prizes and total up values as a fraction of 1
for (int i=0;i<MAX_PRIZES;i++) {
f_max += 1 / (float) m_prizevalues[i];
}
// generate a random floating point number in the range of the total value of all prizes
float f_select = MathUtils.random(f_max);
// loop through prizes and select the one that matches the randomly generated value
for (int i=0;i<MAX_PRIZES;i++) {
if (f_select < (1 / (float) m_prizevalues[i])) {
// This prizes matches the selected value, stop searching
i_prize = i;
break;
} else {
// Does not match, deduct value of this prize and check against next
f_select -= (1 / (float) m_prizevalues[i]);
}
}
return i_prize;
}
Let me know in the comments below if you can see improvements that could be made, or can spot any problems and especially if you know of a better way that this can be done. One problem I can see is that at very high values the algorithm could start hitting the bounds of floating point accuracy. That could in principle cause a very high valued item to never get selected. For my own needs I'm not going to be in that magnitude so I've not gone to the trouble of calculating at what point that might start to be an issue.
This handy bit of code can be used in any situation where you need to select an item where higher valued items need to be more rare. A good example would be spawning loot in a rogue-like dungeon crawler. In that case you want your 10,000 gold value magic sword to be generated as loot a hundred times less frequently than your 100 gold value regular sword.
RSS Feed