Add a method to get a random element with weighted probability (similar to random.choices() in Python)

[rusty-tendrils]

Describe the project you are working on

Loot generation with weighted probabilities.

• Getting a list of items of fixed length based on weighted probability of items.
• {rare: 1, common: 3, empty: 6}, six slots for loot.

Describe the problem or limitation you are having in your project

Using a random float for each roll does not feel like an elegant solution.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Generates a list of loot which can be used directly.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

• Similar to python's random.choices
• Takes a list of items and list of weights and the number of items to be generated (k) and returns a list of same length (k).
• I would be up for implementing it.

var items = ['rare', 'common', 'empty']
var weights = [1, 3, 6]
const K = 6

print(loot_gen(items, weights, K))

['empty', 'empty', 'rare', 'rare', 'common', 'empty']

If this enhancement will not be used often, can it be worked around with a few lines of script?

It can be worked around by computing floats for each item given considering its weight and rolling a random float with randf() multiples times. Weighted Probability in docs

Is there a reason why this should be core and not an add-on in the asset library?

Loot generation of this type is commonly seen in games.

[winston-yallow]

To add another usecase:

I needed something like this in my procedural city generator. I ended up implementing it in gdnative rust because a pure gdscript implementation turned out to be a performance bottleneck in my case. At least when implementing this in a similar way to the cpython implementation (using the cumulative weights internally) this will iterate the whole array at least once. For huge arrays this becomes quite slow in GDScript.

I would love to see this added to core, it would have saved me quite some hassle in multiple of my projects.

For reference the python implementation: https://github.com/python/cpython/blob/main/Lib/random.py#L477
I find the implementation rather elegant:

• find total sum of weights (last item of cumulative weights)
• do a bisect of the cumulative weights with a random float between 0 and the sum of weights
• use that index to pick the item

(This does assume that the cumulative weights list is sorted, which we can if we only allow normal weights to be passed in to the function. Otherwise a check for that would probably be needed)

[Mickeon]

If this enhancement will not be used often, can it be worked around with a few lines of script?

Here's the simplest form of a weighted random choice algorithm as defined in this web page, returning the chosen index or 0 if the weights array is empty:

static func weighted_random(weights: PoolRealArray) -> int:
	var weights_sum := 0.0
	for weight in weights:
		weights_sum += weight
	
	var remaining_distance := randf() * weights_sum
	for i in weights.size():
		remaining_distance -= weights[i]
		if remaining_distance < 0:
			return i
	
	return 0

[winston-yallow]

@Mickeon As I wrote before, approaches based on commulative weights like the one you posted will require at least one full iteration of the array plus however many elements randomly need to be iterated, this is true for the first ones in the article you linked too. That's basically the same as the bisect method from python as the second for loop basically bisects the weights based on the random value and returns the item with the corresponding index.

I see not much difference, except that this lacks the parameters for items and k, which is what makes it so useful for games. But that would be easy to add to your code as well.

As it's basically the same as the python one it has the same performance penalty that I ran into in my city generator. Granted, that was on 3.x, so maybe with GDScript 2 arrays perform better. I would need to profile this to be certain though. I still think this would be good to have in core regardless of performance as it's something very useful for a whole range of games, even if this can be done in GDScript. It won't add much engine bloat but it will add a versatile functionality. So in the question "If this enhancement will not be used often, can it be worked around with a few lines of script?" I think the first part can be answered with "it probably will be used often". I can think of many usecases:

• loot distribution
• procedural generation (for this it would be nice to have it in the RandomNumberGenerator class too so that results are reproducible with a seed)
• difficulty/health distribution for enemies
• ...or anywhere else where one would need a weighted item

[Mickeon]

My reply wasn't in disapproval of the proposal, it was to suggest an additional alternative. In fact, I would argue that some simple way to calculate weighted probability should probably be core.

A method may fit well right inside the RandomNumberGenerator class. To be honest, not all games need the algorithm, but those that do would use it frequently.

[Xrayez]

I think the items should support both Array and Dictionary. If you use Dictionary, you could encode items as keys, and weights as values.

For parameters, I'd switch the order to:

choices(elements, count=1, weights=null, cummulative_weights=null)

because GDScript does not support keyword arguments.

---

• I would be up for implementing it.

Feel free to do so at Goost. We have Random.choice() implemented as well, this proposal will complement it, however I don't mind If you'd like to submit a PR in Godot first. 🙂

But note that there's a related 4 months old proposal #3454 which hasn't been considered for approval, this is why I invite you to contribute to Goost first and hopefully both #3454 and this proposal will eventually land in Godot. If not, that's also ok.

You can look at Random.choice() implementation to see how different Variant containers can be supported.

I added this proposal to goostengine/goost#7.

To be honest, not all games need the algorithm, but those that do would use it frequently.

Indeed, that's actually the development philosophy of Goost: completeness.

[Mickeon]

When I wrote that reply, I was going to mention that Goost has a weighted random choice method, but it actually does not! That did catch me off-guard.

I would say that a weighted probability method is even more needed than pure randomization. Perhaps, it could be optimised in such a way that if no weights are passed in the method, pure random choice is used, anyway.

[Xrayez]

Pure choice() will be actually faster for unweighted choices, both choice() and choices() exist in Python. Besides, choice() works for any sequence/indexable type, like String, not to mention the difference that the first method returns a random pick, while the second returns an array.

The optimization makes sense regardless.

But yes, if Godot chooses to implement such a method, it could provide both functionalities as a single method to prevent bloat (this is not an issue in Goost as long as API is clear and well organized).

[winston-yallow]

I think for now I would just push for a weighted random choice in godot core as a random unweighted pick really is easy to do in GDScript without performance penality like in the weighted choice. So I can understand if a unweighted pick is not done in core (which is where goost is useful for people that want to have a huge number of stuff available). For now I think focussing this proposal on weighted choice is best.

[KoBeWi]

I agree that weighted pick would be useful in core. It has plenty of uses and there's pretty much only single best way to implement it. Right now I use my custom implementation, in 3 different projects. Sure, it could be an addon, but C++ version would be more performant. It mostly matters in procedural generation, where the method can be called hundreds or thousands of times.

As for the implementation, single Dictionary would be better than using 2 arrays. Also, the weights could be integers, for more precision and speed. They can be any number anyways.

[ghost]

I implemented this in my custom build based on Mickeon's code adapted to C++ and only for Arrays. I don't think Dictionary needs this as you're only selecting arrays of keys really. See here goblinengine/goblin@4dd4a05 and here for an updated version that is closer to Python goblinengine/goblin@33d22b4

Is naively implemented with multiple for loops but it seems to be quite fast about 7-20 usec per call.

[joaoh82]

Is this being worked on by anyone? If not, I would like to give it a shot. It seems like it is common agreement that it owuld be useful.

[KoBeWi]

There is no PR open and it's unlikely someone works on it right now.

[rusty-tendrils]

I'm not working on it. Even though I said "I would be up for implementing it.". Please proceed if that was the hold up.