array_random (weighed)

[biyectivo]

Description

This is a function I wrote a long time ago for one of my first games, and ended up dropping it on nearly every project I make. It lets you pick an element at random from an array. It can either return the value or the index, and you can specify weights if you do not want a uniform selection. The weights can also be specified with arbitrary numbers, and the function will normalize those weights to add up to 100%. Finally, all arguments are optional, so if you don't specify anything it is equivalent to choose(0,1), if you only specify the array it will select an element at random uniformly (i.e. equal weights) and if you only specify a weights array it will assume the array is a consecutive index array ([0,1, 2, ...]) up to the size of the weights array.

Uses

A lot, but it's super useful for dropping random loot, procedural generation of levels, procedural generation of enemy waves depending on level difficulty, etc. Check the write-up I made on random number generation if needed here. Page 3 specifically talks about this.

Examples

Say we have a possible items drop array for a monster loot or treasure chest (I'll specify them a strings for exemplification purposes, probably these would be structs or object references on an actual game):

self.items = ["Coins", "Shield", "Sword", "Gem"];

Then:

• var _item = array_random(self.items, [0.4, 0.3, 0.2, 0.1], false); - Returns a random item from the items array (which should have four items). The first item is weighed at 40% chance, the second at 30% and so on.
• var _item = array_random(self.items, [40, 30, 20, 10], false); - Exactly the same as before. The function will normalize the weights. This allows to think on loot chances as proportional to one another (for example, something with weight 66 will have double chance than something with weight 33, regardless of what the total sum of weights are).
• var _item_idx = array_random(self.items, [0.4, 0.3, 0.2, 0.1], true); - Same as before, but returns the index of the selected item instead.
• var _item_idx = array_random(self.items); - Returns a random item from the items array, with equal weights. Equivalent to self.items[irandom(array_length(self.items-1))].

Also:

• var _item_idx = array_random(,[0.4, 0.3, 0.2, 0.1]) - Returns a random number from [0, 1, 2, 3], with the specified weights.
• var _item_idx = array_random() - Returns a random number from [0, 1], uniformly. Equivalent to choose(0,1).

Current code

The current code works good. I'm sure we can clean it up a little and make it a bit more robust to be included in this package, but it's a good start.

///@function			array_random(array=[], probabilities=[], return_index=false)
///@description			selects an item or index from the array with the specified probability array
///@param				{array}		_array			the array that holds the values to select from
///@param				{array}		_probabilities	the array that holds the corresponding probabilities
///@param				{bool}		_return_index	if true return selected index; if false [default] return value from _array
///@return				{any}		the randomly selected item or index
function array_random(_array = [], _probabilities = [], _return_index = false) {
	// Specifying an empty _array means [0,1,...] the same size as _probs array
	// Specifying an empty _probs means considering uniform probabilities the same size as _array
	// If both are empty, generate a Bernoulli with p=0.5 (fair coin toss)
	var _arr = _array;
	var _probs = _probabilities;
	var _n = array_length(_arr);
	var _p = array_length(_probs);
	if (!is_array(_arr) && !is_array(_probs) || _n == 0 && _p == 0) {
		return choose(0,1);
	}
	else {
		if (array_length(_arr) == 0) 	for (var _i=0; _i<_p; _i++)		array_push(_arr, _i);
		if (array_length(_probs) == 0)	for (var _i=0; _i<_n; _i++)		array_push(_probs, 1/_n);
		_n = array_length(_arr);
		_p = array_length(_probs);
		if (_n != _p) throw("The value array and the probability array must be of the same size");
		var _neg = false;
		_i=0; 
		while (_i<_p && !_neg) {
			if (_probs[_i] < 0)		_neg = true;
			else _i++;
		}
		if (_neg) throw("The probability array cannot have negative values");
			
		
		// Normalize probability array
		var _sum = 0;
		for (var _i=0; _i<_p; _i++)		_sum += _probs[_i];
		if (abs(1-_sum) != 1)	for (var _i=0; _i<_p; _i++)		_probs[_i] /= _sum;
		
		// Generate continuous random variable and compare against CDF
		var _u = random(1);
		
		var _i = 0;
		var _cdf = _probs[0];
		while (_u > _cdf && _i<_p) {
			_i++;
			_cdf += _probs[_i];	
		}
			
		if (_return_index)	return _i;
		else return _arr[_i];
	}
}

[Alphish]

Hmmm... I think there are a bunch of different functionalities to be had here, and they might be better split up instead of getting into overloads overload.

One potential derived function would be choose_weight_index(weight1, weight2, ...)
It's pretty similar to your array_random() with no _array given and _return_index being set to true. Because let's face it, if you set _return_index to true, _array argument doesn't matter anyway.

So something like choose_weight_index(0.6, 0.3, 0.1) would choose index 0 with 60% chance, index 1 with 30% chance and index 2 with 10% chance. It wouldn't even need to do any special division-based normalisation; instead, the random would be calculated from the sum in the first place, like so:

function choose_weight_index(_weights) {
    var _weights_sum = 0;
    for (var i = 0; i < argument_count; i++) {
        _weights_sum += argument[i];
    }
    var _value = random(_weights_sum);
    for (var i = 0; i < argument_count; i++) {
        if (_value < argument[i])
            return i;
        else
            _value -= argument[i];
    }
}

Then, for an array based variant, it could be something like choose_weight_index_ext, in a similar way e.g. string_ext(format, args) is an array-based version of string(format, ...args)

Then another derived function could be choose_weighted(item1, weight1, item2, weight2, ...)
So something like choose_weighted("hp_potion", 0.6, "mp_potion", 0.3, "iron_sword", 0.1) would choose HP potion with 60% chance, MP potion with 30% chance and Iron Sword with 10% chance.

I don't yet use arrays here, because I don't want to encourage creating new arrays too much, and array literals create a new array every time the code is run. Still, if someone wants to match up the items array with weights, they might use something like choose_weighted_ext(items, weights), I guess?

Then, for weightless choosing, we would instead apply the function Dragonite mentioned on GMC:

function array_random_element(array) {
    return array[irandom(array_length(array) - 1)];
}

Except I guess I would call it array_get_random(_array) and make an array_delete_random(_array) counterpart. As the name implies, the latter would remove a random element from an array and return its value; I've found myself using it on multiple occasions.

Quite a few design decisions to be had here for sure, but in general I think some extra functions for randomly picking elements (especially picking elements from arrays) would be quite welcome. ^^

[RhyminGarfunkle]

I suggest array_pop_random instead of array_delete_random. It feels more straightforward if you're already familiar with the built-in array_pop and I don't think deleting an index from an array implies that the value will be returned, ds_priorities are the only structures that return deleted data.

I know you said you don't want too many new arrays going around, but I think I'd prefer if a function like choose_weight_index took an array of weights as an argument, instead of a bunch of reals. Passing more than a couple numbers in as arguments would be pretty clumsy, and for many of the proposed use cases I can see myself wanting to pick from dozens or hundreds of options, not just three or four.

[Alphish]

Made a separate issue #26 focusing on the uniform array_get_random/array_pop_random or whatever else we call them. This feature will stay open for discussion and voting about more advanced array randomisation features (mostly the weighed choice).

[gnysek]

There's also this implementation: https://yal.cc/gamemaker-weighted-choose/