Hacker News Reader

Comment by EarthLaunch | Hacker News Reader

Why does weighted randomness seem so difficult for games? Are there any libraries that simplify this? I couldn't find any for JS.

So I created my own "algorithms" for things like randomly choosing which type of plants spawn in the world. It weighs them by the local frequency of each land-type. Eg if there's more swamp nearby, it's more likely to spawn cattails.

It's awful. Not intuitive. Weights have to be passed in ordered smallest to largest. Posting in hopes someone will correct my entire approach or point out an industry-standard way of doing these things.

  Utils.weightedRandom(percents, types)

  function weightedRandom(weight, outcomes){
    var randNumber = Math.floor(Math.random()*100)
    for(let i=0; i<weight.length; i++){
      if(randNumber<weight[i]){
        return outcomes[i]
      }
      else {
        randNumber -= weight[i]
      }
    }
  }

View on HN

In Python:

    random.choices(population=['A', 'B', 'C', 'D'],
                   weights=[3, 2, 5, 7])

https://docs.python.org/3/library/random.html#random.choices

Thank you very much! That led me to a JS clone[0].

Python has amazing math libraries. I use numjs[1] for everything, which is a port of numpy. I frequently wish I had use of Python's libraries.

0: https://github.com/parmentf/random-weighted-choice

1: https://github.com/nicolaspanel/numjs

Here's the standard algorithm for this problem

    function weightedRandom(weight, outcomes){
      var total = sum( weight );
      var roll = Math.random()*total; // value in the range [0,total)
      var seen = 0;
      for(let i=0; i<weight.length; i++) {
        seen += weight[i];
        if(roll<seen)
          return outcomes[i];
      }
    }

Statistics is actually pretty hard to get right, and it is the nature of the problem space that errors aren't immediately apparent unless one actually runs analytical regression on the algorithm to confirm it has the right "shape," which (a) can be time-consuming given the complexity of the algorithm and (b) doesn't tend to be part of unit tests because unit test doctrine is pathologically opposed to nondeterminism.

(This last pert is not an unsolvable problem, and in fact random algorithms should be unit tested. But it requires the right kind of unit testing).

On occasion I have written a seeded large n statistical test that passes & the submitted with the seed fixed. I think this is the soundest approach, although it has a "your random number is 7" feel to it.

In your example, the weights need to add up to 100 to work correctly, right? The issue with the code in the article is that the weights did not add up to 1.

Right, I'm using a percentage. The article's bug reminded me of this directly!

https://leetcode.com/problems/random-pick-with-weight/

First dent in my anti-leetcode opinions. Thanks.

IIRC the other solution is to make a tree structure instead of a CDF. Can't remember if it's a good solution though.

I've been pondering a way to implement a quantum random number generator into a game. Could this be useful at all?

What is the general benefit to a quantum random number generator versus a regular one? Is it that it's more truly random, or has a better distribution, or?

Reply on news.ycombinator.com