1

Im trying to create a weighted random system for my game in unity using C#.

Player starts with N events, but as the game goes on the amount of events increases. At first all the events are equally likely, probability 1/N, but the player can use modifier to make some event more likely, like some events have double the probability to occur or in some cases they can force an event to happen no matter what.

I have found that widespread approach to do weighted randoms is to sum all the weights, generate random number up to the sum of weights and then iterate over choises and accumulate the weights until the accumulator > generated value.

Now i might be overthinking this, but to me it seems like there are some issues with this approach.

For example: Player has 7 choises, each has a weight of 1/7 and sum weights is 1. Now if 1 event gets a double modifier its new probability is 2/7 making the sum of weights 8/7. This leads me to think that i should subtract 1/42 from the weights of the other events to keep the sum as 1. Otherwise its not actually double probability, i think.

Another example: Player forces an event to occur 100%. This means 1 event has weight of 1 and all the other has weight of 0. Now it depends a bit of the implementation of the Random function but in theory nothing stops the random from spewing out 0 and then depending on the order of the events any event with 0 can happen.

If you have notices i have kept the weights between 0 and 1. This allows me to use weights and probabilities interchangeably since weight of 1/7 also means probability of 1/7. Also this way i dont have to calculate the sum of the weights, since its always 1.

Am i overthinking the problem and its actually not that complex?

Additional note: Some of you might suggest ordering the list of events based on the weights from largest to smallest. Since the RNG system is core of the gameplay and happens very often it might not be wize in performance perspective to sort the events, given that there might be different modifiers in play everytime a new random is pulled.

Also if in the 7 choise example, when i double chance of 1 event and instead of 2/7 i would use 2/8 and everything else is 1/8 then its actually not double the probability as 2/7 > 2/8.

Guru Stron
  • 102,774
  • 10
  • 95
  • 132
Marko Taht
  • 1,448
  • 1
  • 20
  • 40
  • Does this answer your question? [Data structures for loaded dice?](https://stackoverflow.com/questions/5027757/data-structures-for-loaded-dice) – Peter O. May 29 '22 at 11:19
  • Especially, consider the rejection sampling method I mention there, where weights are expressed as a _function_ rather than as a _number_. – Peter O. May 29 '22 at 11:19
  • You sum the weights each time. If your seven events all start at a probability of 1, then the sum is seven and each probability is 1/7. If you change one weight to two then your sum isn't 7 anymore, it's 8. Six events have a probability of 1/8 and the seventh has a probability of 2/8. – Chuck May 29 '22 at 11:41
  • You said, "i would use 2/8 and everything else is 1/8 then its actually not double the probability as 2/7 > 2/8." but again if you change the weight then there is no comparison to the X/7. You are doubling the weight, so the event that's 2/8 should happen twice as often as the other events, which are now 1/8, and I'm pretty sure 2/8 is exactly two times 1/8. – Chuck May 29 '22 at 11:44
  • @Chuck THe idea behind the 2/7 > 2/8 is that 1/7 is ~14% probability. so 2/7 is ~28% probability. But 2/8 is a 25% probability. So there is a difference of ~3%. – Marko Taht May 29 '22 at 13:22
  • @PeterO. I think it might work. Only weakness will be the situation where only 1 event is possible (all others have a weight of 0) As with large enough of event pool it might be hard to hit that 1 event. With modifier of type "Event X has 100% prob" its easy to detect and handle separately, but you could achieve same effect with "Event x has 0% prob" placed on all but 1. And this is not so easy to detect. – Marko Taht May 29 '22 at 13:40
  • There is no 2/7 probability. The only way you get to 2/7 is if you reduce all the other weights to compensate. What happens if you set one weight to 2 and then another weight to 3? What do the weights really mean? "Double the odds" as opposed to *what?* If you mean that a weight of 2 should happen twice as often as a weight of 1, then that's what my math does. When you use your math, and everything is normalized to X/7, then setting a value to 2 must mean the other values get set to less than 1 to make the sum be 7. – Chuck May 29 '22 at 13:53
  • @Chuck Yea i think im overcomplicating things :D Its all about point of reference. But you make a point. – Marko Taht May 29 '22 at 13:58
  • If you want to double the odds in your normalize-to-sevenths math then you're saying you want one double weight plus six single weights to sum to 1, or 2*x + 6(x) = 1. This is 8x=1 or each weight is 1/8, with your double weight as 2/8. You can call this sevenths by multiplying numerator and denominator by 7/8 and get that your single weight is 0.875/7 and your double weight is 1.75/7, but this isn't as easy to work with, or read, or understand, as just weight/(Sum(weights)) which would be 1/8 and 2/8. – Chuck May 29 '22 at 13:59
  • Also 1.75/7 is 0.25 and 0.875/7 is 0.125, so checks out that the double weight case is double the odds of the single weight case. Just one more angle and then I'll stop harping on this lol (trying for a friendly explanation here :)) is that if you keep to sevenths math and you say 2/7 is double, fine but if all the other weights are 1/7 then you wind up with a total probability of 8/7, which is impossible because it's more than 1 (100%). If you scale back to 0:1 then you wind up with the odds I calculate above, 0.125 and 0.25. – Chuck May 29 '22 at 14:03
  • @Chuck Undless i subtract 1/42 from all other. But i now realized... there is 1 more issue... How do i handle 1% increase in probability... – Marko Taht May 29 '22 at 14:22
  • @Marko Taht: In my opinion, the case where one event has a 100% chance of happening should be handled by bypassing the weighted random choice system. – Peter O. May 29 '22 at 14:58
  • @PeterO. I agree. And like i said. In a situation where there is a single modifier that sets 100% chance for 1 event its easy to handle. But if we have a situation where we have multiple modifiers that end up making the single event 100% case, that is not that simple to check, unless i pre-calculate the weights and spesifically check for this situation. – Marko Taht May 29 '22 at 17:02
  • 1
    If you want to increase the odds by 1% then you make the weight 1.01. New value is 1.01/7.01, which is 0.144. Unchanged values are 1/7.01, which is 0.14265. What is 1% more than 0.14265? (1.01*0.14265)=0.144. Weight/Sum(weights) works out to exactly what you want every time. – Chuck May 29 '22 at 20:35

1 Answers1

0

Try this: https://github.com/cdanek/kaimira-weighted-list

Disclaimer: I wrote it, but it's exactly what you're looking for.

It doesn't need to hit the list multiple times for a get operation. This solution gets a result from a weighted list in O(1). It's also (hopefully) trivially simple to implement.

Chris
  • 444
  • 2
  • 12