2

I looked at multiple stack overflow articles and couldn't find a reasonable response. If there is a duplicate please indicate.

I have a list of items. Something like:

String giantRat []={"Bandage", "Healing Potion", "Minor Healing Potion", "Rat Teeth", "Fur", "Rat Tail", ""};

This indicates the possible items this giantRat can drop.

There is a correlated array with matching index that holds what I would hope is the weighted probability of the occurence. Something like:

int giantRatDropRate[]={1,1,1,6,8,3,5};

These would be scaled up to say, 50 (multiplied each by 2) and then I would theoretically role a 50 sided dice (Random). This seems like it's been the wrong approach and I can't figure out a way to do this.

Again, the idea is to roll a die and choose 1 item from the list based on weighting. Maybe the dice roll is the wrong way. Any help appreciated.

Joseph Erickson
  • 938
  • 3
  • 8
  • 24
  • A roulette wheel algorithm may help you out here. Such as, http://stackoverflow.com/questions/298301/roulette-wheel-selection-algorithm/320788#320788 – pds Feb 22 '15 at 16:47
  • It seems overwhelmingly complicated for a new programmer like myself, but thanks for the reference. – Joseph Erickson Feb 22 '15 at 16:51

5 Answers5

3

Use Random.nextInt(n), where n is the sum of your weights; then, depending on the interval where the result int drops, you determine the item; e.g. if it is 0 - take the 1st item; if it is between 3 and 8 (inclusively) - take the forth item.

You can easily convert array of weights into array of interval boundaries: just sum all preceding elements. Then, having random int, just go over this interval boundaries array and stop when your random int becomes bigger than the current element of the array.

Because length of the interval is determined by the weights, probability is also determined by it.

Nikita Astrakhantsev
  • 4,701
  • 1
  • 15
  • 26
2

A simple approach could be as follows. No need to *2, because probabilities will be the same.

    String giantRat []={"Bandage", "Healing Potion", "Minor Healing Potion", "Rat Teeth", "Fur", "Rat Tail", ""};


    int[] a = {1,1,1,6,8,3,5};
    int sum = 0;
    for(int i: a)
       sum += i;
    Random r = new Random();
    int s = r.nextInt(sum);  //Get selection position (not array index)

    //Find position in the array:
    int prev_value = 0;
    int current_max_value = 0;
    int found_index = -1;
    for(int i=0; i< a.length; i++){ //walk through the array
      current_max_value = prev_value + a[i];
      //is between beginning and end of this array index?
      boolean found = (s >= prev_value && s < current_max_value)? true : false;
      if( found ){
        found_index = i;
        break;
      }
      prev_value = current_max_value;
    }

    String selection = "unknown";
    if( found_index != -1 ){
      selection = giantRat[found_index];
    }
    System.out.println(selection);

Example at http://ideone.com/xyQlvN

pds
  • 2,242
  • 1
  • 22
  • 20
  • 1
    This is really well done. I appreciate you taking time to write it out. Thanks for the example. I'll definitely have to study this out and understand it better. – Joseph Erickson Feb 22 '15 at 17:21
  • Dude, not to beat a dead cow here, but this was fantastic. I've read it a few times, and while the sytnax makes sense, the logic is beyond me. No idea how you crafted this solution but well done sir. It's implemented into my game and works perfectly. Well done, sir. And again, thanks for taking time to help out. – Joseph Erickson Feb 23 '15 at 19:11
  • @JosephErickson, it's a pleasure and I'm glad it works for you. Not to be draconian, but I do agree with the other answers, in that you really should go through the process of problem finding to problem solving. It's worth investing your time into understanding how your (this) code works. Feel free to ask about a line number / which parts aren't clear. – pds Feb 23 '15 at 20:28
  • no worries. I was actually going to develop a different method. Because I'm working with small numbers (<300) i was just going to have a method that creates an array that is X long where x is the amount of weighting, and each index will hold 1 of the weighting. But all in all, your solution was great. – Joseph Erickson Feb 24 '15 at 02:08
  • @ pds see below for my own answer after you suggested I not float on your laurels. Thanks for the help man. (And yes, I gave you a shout out below). – Joseph Erickson Feb 24 '15 at 05:01
1

Simply compute the interval of values that each element has. Let's forget about the multiplication by 2 which doesn't bring anything.

The first element has a weight of 1, so its interval is [0, 1[.

The second one has a weight of 1, so let's start its interval at the value of the previous one, and add 1: [1, 2[.

Same for the third one: [2, 3[.

The 4th one has a weight of 6, so its interval is [3, 9[.

Continue until the end.

Then roll your dice, and find the element which has an interval covering the dice value.

JB Nizet
  • 678,734
  • 91
  • 1,224
  • 1,255
  • Is there a stock java class to check an interval? I feel like I run into this issue constantly with switch statements being inflexible. – Joseph Erickson Feb 22 '15 at 16:53
  • Not in the JDK. But it's a matter of 10 lines of code. – JB Nizet Feb 22 '15 at 16:55
  • Please clarify 10 lines? Apologies if your answer is implicit, I'm very new to programming so everything has to be spelled out for me. Also, I appreciate your response. – Joseph Erickson Feb 22 '15 at 16:57
  • I won't write the code for you. Try something. What is an interval? It's a low limit (int) and a high limit (int). How do you know if an interval contains a number? If the low limit is <= number, and the high limit > number. Write that as code, and you have your class. – JB Nizet Feb 22 '15 at 16:59
  • No one was asking for the code to be written. Also, I find when I have expertise about a subject and someone is sincerely asking for guidance, if I'm less condescending about my expertise the interaction seems to go a lot better. That's advice that will likely aid you in your life. – Joseph Erickson Feb 22 '15 at 17:03
  • Maybe you should apply that advice to yourself. I will handle my life on my own, thank you. Instead of telling me how I should handle my life, maybe you could try writing code instead of jumping on your keyboard 2 minutes after I helped you, for free, to complain about imaginary condescendance. – JB Nizet Feb 22 '15 at 17:10
  • No need for defensiveness. Frank feedback. You can accept it or ignore it. – Joseph Erickson Feb 22 '15 at 17:12
  • If you want to read more about this approach in the general case, you can read about [inverse transform sampling](http://en.wikipedia.org/wiki/Inverse_transform_sampling) of probability distributions. – eigenchris Feb 23 '15 at 16:23
0

One way that you could do it is have each index stored in an array of size 50. So:

 int[] giantRatDropRate = new int[50];
 giantRatDropRat = { 0 , 0 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3... };

Then if you like, you can randomly shuffle the array, refer to Random shuffling of an array

Finally, use the random number generator to get the index from that array: double d = 50.0 * Math.random(); String action = giantRat[giantRatDrop[(int)d]];

Community
  • 1
  • 1
Gregory Basior
  • 300
  • 1
  • 9
0

Great news: I took the non-draconian approach suggested by @pds in the comments section and came up with my own solution. I think @pds solution in the answer section is a more eloquent solution, but here is my own take after studying his and thinking about my problem a little:

https://gist.github.com/anonymous/f985c1839e5a6be94883

Joseph Erickson
  • 938
  • 3
  • 8
  • 24