Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bottom-Heavy Random Number

Tags:

java

Right now, I'm trying to make an Item drop table for a minigame.

In this game, I would like for you to receive certain items more commonly than others, with some items having a very low chance of being picked.

I have tried using something along the lines of:

Random rand = new Random();
int chance = rand.nextInt(100) + 1;
if(chance > 2){
     //give common item;
}
else if(chance == 1){
     //give rare item
}

However, when you do this over a scale of 50+ items, it becomes very tedious to create, modify, as well as the code takes a long time to execute.

So, is there some kind of bottom-heavy random that will create a large amount of low numbers (1's, 2's, etc.) and very few high numbers (50's, 60's, etc.)?

like image 810
user3344572 Avatar asked Feb 23 '14 23:02

user3344572


2 Answers

Use Random.nextDouble() to generate a number in [0,1), then you can use Math.pow() to give it a non-linear bias and scale it up to cover your range, e.g.:

 int randomBiased (int max, float bias) {
     float v = Math.pow(random.nextDouble(), bias); 
     return (int)(v * max);
 }

Or if you prefer a one-liner:

 int value = (int)(100 * Math.pow(random.nextDouble(), bias));

This is useful because you can adjust bias to tweak the "rareness" of rarer items. A bias > 1 will favor lower numbers, < 1 will favor higher numbers, 1 will be uniform.

For example, randomBiased(100, 2.0) will give the same result distribution as Tim B's answer.


Note also that you can use any function that maps [0,1) to [0,1) to modify the bias; for example, you could use a cubic to bias all results away from the center (see the graph):

int randomFavorEdges (int max) {
    float v = random.nextDouble();
    v = 3*v*v - 2*v*v*v;
    return (int)(v * max);
}

Another example is that you can get one half of a Gaussian distribution using Math.abs(random.nextGaussian()) instead (see Christian's answer). The caveat is you have to keep trying that until you get a number less than 1 (it can go outside the range [-1,1]). However, you can take advantage of the large range by adding a scaling parameter that can be tweaked to taste:

int randomGaussian (int max, float scale) { 
    double v;
    do {
        v = Math.abs(random.nextGaussian() / scale);
    } while (v >= 1.0);
    return (int)(v * max);
}

Truth be told, after looking at the test results below, personally I like the Gaussian distributions with a higher scale value -- rare items become much rarer but without as intense a bias towards common items as the exponential distribution.


Update: I've created a project on ideone that demonstrates the methods listed above. Here is an example for 10000 samples of 30 values:

Name :  Uniform  Pow(0.5)  Pow(2.0) Pow(10.0)    G(1.0)    G(3.5)     Cubic 
0    :      337        11      1872      7118       365       946      1126 
1    :      359        33       744       511       406       939       517 
2    :      327        60       589       328       360       876       407 
3    :      330       101       458       224       370       846       307 
4    :      347       103       445       170       395       817       310 
5    :      344       131       366       141       374       727       257 
6    :      326       148       358       147       416       691       275 
7    :      326       180       309       106       373       645       254 
8    :      314       195       295       129       335       575       282 
9    :      331       227       311        79       356       506       219 
10   :      329       245       325        84       376       458       258 
11   :      340       241       230        75       370       366       228 
12   :      367       290       251        75       366       320       215 
13   :      343       294       264        70       345       243       237 
14   :      313       317       256        60       344       211       224 
15   :      346       331       240        66       358       186       210 
16   :      353       363       204        48       338       131       226 
17   :      329       373       213        55       344       157       193 
18   :      323       417       200        57       327        86       230 
19   :      323       446       219        56       354        75       208 
20   :      321       466       211        43       296        56       209 
21   :      339       496       205        40       297        34       267 
22   :      338       484       192        48       278        37       237 
23   :      335       523       168        46       290        19       306 
24   :      327       571       162        31       251        18       279 
25   :      322       573       216        49       263         7       302 
26   :      323       580       152        35       277        11       311 
27   :      333       596       209        41       268         9       354 
28   :      316       590       158        38       250         6       495 
29   :      339       615       178        30       258         2      1057 

Note that you can really make rare objects rare with high bias value for the Math.pow() method or a high scale value for the Gaussian method. This also shows the bias of the cubic S-curve away from the center.

like image 181
Jason C Avatar answered Nov 07 '22 11:11

Jason C


Yes, essentially you need to change the probability distribution. There are a few ways to do this but one of the easiest will just be to use a non-linear scaling factor before and after.

i.e. instead of

int i = random.nextInt(100);

you do:

int i = Math.sqrt(random.nextInt(100*100));

The random number gives you an even spread over the range, but square root will compress numbers together as you go up - so higher numbers are more likely. You can always do 100-i to then go back to lower numbers being more likely and you can change the steepness of the curve to adjust the probability as you like.

*

An alternative approach (and easier to control) is to use combinations of random numbers. Basically instead of doing one number from 0-100 you do two numbers from 0-50 and add them together, or three numbers, or four numbers. The more separate rolls you do and combine the more steep the curve becomes.

This will weight the odds towards the center of the table, 0 and 100 become equally unlikely and 50 becomes likely. You can either use that and place unlikely things at both ends, or you can generate the number over twice the range you need and then if it is over the range flip it.

i.e.

int i = random.nextInt(100)+random.nextInt(100);
if (i > 100) {
   i = 200-i;
}
like image 37
Tim B Avatar answered Nov 07 '22 10:11

Tim B