Es muy habitual en todo tipo de juego querer generar entidades, ya sean enemigos, balas, items, etc… de forma aleatoria, para dotar al juego de un cierto grado de incertidumbre y que no pueda haber nunca dos partidas exactamente iguales, fomentando la rejugabilidad del titulo en cuestión.
Al hablar de una selección ponderada me estoy refiriendo a que cada uno de los datos, del conjunto de ellos que se van a tener en cuenta, lleva asociado una determinada importancia relativa, un peso respecto al resto de los datos. A mayor peso, mayor será la probabilidad de que un dato concreto resulte escogido, no siendo totalmente aleatoria la selección.
Un planteamiento elegante para implementar una selección aleatoria ponderada, es valerse de una búsqueda binaria junto con una selección aleatoria del valor a buscar, trabajando con rangos que representen la menor o mayor probabilidad de que cada dato resulte escogido.
Hay que tener siempre en cuenta que la práctica totalidad de métodos de generación de números aleatorios usados de forma habitual ( UnityEngine.Random, System.Random, etc… ) no son en ningún caso realmente aleatorios ( pseudo-aleatoriedad ), existiendo tendencias, llegando a poder ser predecibles los resultados. Aquí dejo un par de artículos curiosos relacionados: #1 #2
public static int ChooseWeightedRandom (
int[] p_weights )
{
int i = 0;
int acum = 0;
int[] cdfWeights = new int[ p_weights.Length ];
foreach ( int weight in p_weights )
cdfWeights[ i ] = ( acum += p_weights[ i++ ] );
return RecursiveBinarySearch (
Random.Range ( 0, acum ),
cdfWeights,
0,
p_weights.Length - 1 );
}
public static int RecursiveBinarySearch (
float p_value,
int[] p_cdfWeights,
int p_init = 0,
int p_end = -1 )
{
if ( p_end <= -1 )
p_end = p_cdfWeights.Length - 1;
int center = Mathf.FloorToInt ( ( p_init + p_end ) * 0.5f );
float valueCenterMax = p_cdfWeights[ center ];
float valueCenterMin = ( center > 0 ) ? p_cdfWeights[ center - 1 ] : 0f;
// El valor en busqueda se encuentra dentro del rango central
if ( p_value > valueCenterMin && p_value <= valueCenterMax )
return center;
// El valor no pertenece a ningun rango de la coleccion
else if ( p_init == p_end )
{
// Para el caso especial de estar buscando el valor cero ( 0 )
// por hacerse la comprobacion sin incluir el limite inferior
if ( p_value == 0f )
return center;
return -1;
}
// El limite inferior del rango central es mayor al valor que se busca
else if ( p_value < valueCenterMin )
center = RecursiveBinarySearch ( p_value, p_cdfWeights, p_init, center - 1 );
// El limite superior del rango central es menor al valor que se busca
else if ( p_value > valueCenterMax )
center = RecursiveBinarySearch ( p_value, p_cdfWeights, center + 1, p_end );
// Finalizando le recursion
return center;
}
El código está suficientemente comentado como para no requerir de mucha explicación extra 😉 ChooseWeightedRandom recibe una lista ordenada de «pesos» o prioridades, que se modifica para que pase a representar una lista ascendente, desde el cero hasta el sumatorio de todos los pesos, de los rangos de valores que engloba cada una de las posibles opciones.
int[] listOriginal = new int[] { 2, 1, 4, 3 }
int[] listRanges = new int[] { 2, 3, 7, 10 } // 0-2, 2-3, 3-7 y 7-10
El método RecursiveBinarySearch, como su propio nombre indica, se ejecuta de forma recursiva hasta que llegado cierto punto, cuando se valida una condición de parada o caso base, se comienzan a devolver resultados ascendiendo por la pila ( LIFO ) de llamadas.
La búsqueda binaria requiere trabajar sobre una colección ordenada de datos. El funcionamiento del algoritmo es muy simple, comprobándose una y otra vez si el valor que se está buscando se encuentra en la mitad inferior o superior de la lista, quedándose con esa mitad para volver a realizar la comprobación y nuevamente seleccionar la mitad que interese, hasta dar con el valor.
La única diferencia con respecto a la implementación típica de búsqueda binaria, es que me interesaba trabajar con rangos, lo que a su vez facilita poder realizar búsquedas de números con decimales. Por ello se usan las variables valueCenterMin|Max, que toman el valor mínimo y máximo del rango central en análisis respectivamente. Se da por encontrado el rango al que pertenece el valor indicado cuando es superior al limite inferior del rango actual en análisis e igual o inferior al limite superior (lim inf,lim sup].
Valores: { 2, 1, 4, 3 } -+-> { 2, 3, 7, 10 }
Rangos : (0-2] , (2-3] , (3-7] , (7-10]
Buscar: 0
Init: 0 End: 3 | Center: 1 -> (2,3]
Init: 0 End: 0 | Center: 0 -> [0,2]
Indice: 0
Buscar: 2
Init: 0 End: 3 | Center: 1 -> (2,3]
Indice: 1
Buscar: 2.1
Init: 0 End: 3 | Center: 1 -> (2,3]
Indice: 1
Buscar: 4
Init: 0 End: 3 | Center: 1 -> (2,3]
Init: 2 End: 3 | Center: 2 -> (3,7]
Indice: 2
Buscar: 10
Init: 0 End: 3 | Center: 1 -> (2,3]
Init: 2 End: 3 | Center: 2 -> (3,7]
Init: 3 End: 3 | Center: 3 -> (7,10]
Indice: 3
Buscar: 11
Init: 0 End: 3 | Center: 1 -> (2,3]
Init: 2 End: 3 | Center: 2 -> (3,7]
Init: 3 End: 3 | Center: 3 -> (7,10]
Indice: -1
Buscar: -2
Init: 0 End: 3 | Center: 1 -> (2,3]
Init: 0 End: 0 | Center: 0 -> [0,2]
Indice: -1