Mezcla y agrupación en tiempo constante sin estado

Por Alan Wolfe y William Donnelly – Electronic Arts SEED Future Graphics equipo

El desarrollo de juegos combina trabajo duro y oscuros aspectos matemáticos e informáticos para lograr lo que parece imposible en tiempo real. En este artículo, hablaremos sobre cómo mezclar elementos y organizarlos en grupos de tamaños específicos, sin mezclar ni agrupar nada.

El código que acompaña a este artículo se puede encontrar en https://github.com/SEED-EA/O1ShufflingGrouping

Al mezclar aleatoriamente una matriz, se reorganizan aleatoriamente los elementos de esa matriz.

En otras palabras, la lectura aleatoria cambia el índice de un elemento de la matriz en esa matriz.

Dado que la aleatorización de una matriz no crea ni elimina elementos, sabemos que (1) cada índice antes de la lectura aleatoria corresponde exactamente a un índice después de la lectura aleatoria, y (2) cada índice después de la reproducción aleatoria coincide exactamente con un índice antes de la reproducción aleatoria. Incluso si un elemento de la matriz se mezcla aleatoriamente en la misma posición en la que estaba inicialmente (lo que le daría el mismo índice antes y después de la mezcla), sigue siendo una asignación uno a uno.

Las matemáticas tienen un nombre especial para este tipo de mapeo biyectivo: una biyección. En informática, cualquier operación reversible es uno a uno. Esto significa que podemos crear una biyección asociando una suma con una resta, o asociando XOR consigo mismo, pero no podemos usar cosas como división de enteros o desplazamiento de bits, porque pueden hacernos perder información.

La informática suele utilizar hashes en los algoritmos, pero los hashes están diseñados para ser unidireccionales. Los hashes también permiten colisiones en su salida, lo que hace imposible invertir sin ambigüedades un algoritmo hash. Pero si bien los hashes no son reversibles, el cifrado sí lo es. Si cifra datos con una clave, puede descifrar el resultado (el texto cifrado) con la misma clave para recuperar los datos originales (el texto sin formato). Esto significa que podemos usar el cifrado para realizar una biyección, lo que nos permite mapear desde un índice de matriz semilla a un índice aleatorio.

Con este método de mapeo, podemos decir: “Estamos en el índice 2 de la matriz. ¿En qué índice se encuentra este elemento después de la mezcla? Supongamos que numeramos 2 y obtenemos una respuesta de 48. Luego podemos hacer la pregunta inversa: "¿Dónde estaba el índice 48 antes de la mezcla?" El descifrado 48 nos da nuestra respuesta 2. La clave que usamos para cifrar/descifrar nuestro número también se puede usar como una semilla aleatoria para barajar, permitiendo un número arbitrario de barajados diferentes. Compare eso con un código Gray (https://en.wikipedia.org/wiki/Gray_code), que no es de arranque y ofrece solo un orden aleatorio, y rápidamente comenzará a ver la ventaja.

La aleatorización no es el único beneficio de utilizar este método de mapeo: también le permite generar números pseudoaleatorios sin repetirlos. Por ejemplo, digamos que quieres generar todos los números entre 0 y 65535 en orden aleatorio, teniendo cuidado de no repetir ninguno de ellos. Comenzaría haciendo un bucle de 0 a 65535 y dentro del bucle cifraría el índice con un cifrado de bloque de 16 bits para obtener el siguiente número aleatorio. Con este método no puede haber repeticiones porque una repetición no sería descifrable. (y tampoco sería cifrado). Esta técnica se llama "cifrado que preserva el formato" (https://en.wikipedia.org/wiki/Format-preserving_encryption) y se rumorea que es la forma en que las compañías de tarjetas de crédito generan nuevos números de tarjetas que (1) no utilizan una tarjeta de crédito. número de tarjeta. número que se emitió previamente y (2) son criptográficamente aleatorios para que sus números no se puedan adivinar. Sin este método, las compañías de tarjetas de crédito tendrían que generar un número de tarjeta aleatorio, escanear cada tarjeta de crédito emitida para evitar duplicar un número anterior y continuar este tedioso ciclo hasta...