GDC 2017 – Trabajando con RNGs en videojuegos

27 marzo, 2017

Otro de los ejes temáticos del pasado GDC 2017 (ver entrada anterior) fue el tutorial dedicado a revisar fundamentos matemáticos para programadores. Éste estaba soportado por un grupo de interés sobre este tema (Math for Game Programmers) y, evidentemente,  se alejaba ya bastante de la visión conceptual del game design y se adentraba en las entrañas de la programación de los videojuegos. Concretamente, me parecieron interesantes a título personal las dos charlas que llevaron acabo por Squirrel Eiserloh (SMU Gildhall) y Shay Pierce (Dire Wolf Digital). Ambas trataban sobre distintos aspectos de los generadores de números aleatorios (o RNG, Random Number Generator) que se deben tener en consideración cuando se usan en un videojuego. Un tema que me apasiona y del que ya escribí hace bastante tiempo en una breve entrada anterior. Sobretodo por el hecho que los RNGs suelen ser clave en el campo de la seguridad, pero las reglas para usarlos, y lo que queremos de ellos, en el contexto de los videojuegos puede ser un poco distinto.

Por una parte, la presentación de Shay, titulada «Dark Secrets of the RNG«, se enfocaba hacia el uso de un RNG como herramienta para el cálculo de probabilidades y dar algunas lecciones sobre aspectos en su aplicación en videojuegos.  Por ejemplo, en un juego de estrategia o rol, una unidad o personaje ataca a otra y por las reglas se decide que tiene un 90% de probabilidades de acertar al adversario y causar daño. Con un RNG se genera un valor al azar entre 0-99, y si el valor es inferior a 90, se considera que el ataque tiene éxito. Transformar a digital lo que sería una «tirada de dados» en un juego de sobremesa.

Gary Gygax hace su tirada de reacción…

Uno de los dark secrets (secretos oscuros) que trataba Shay es el hecho de que un RNG no basta con que lo sea, también lo debe parecer (como lo del dicho de la mujer del César…). Esta frase que parece no tener sentido significa que, al final quién juega al videojuego es un humano, y resulta que los humanos somos especialmente malos en nuestra percepción de las probabilidades y el azar. Al final, existen un conjunto de casos extremos de «mala suerte» que, con una base de miles de jugadores jugando durante muchas horas, tarde o temprano van a suceder. Si se suceden muchos valores similares consecutivos, ya no nos parece un suceso aleatorio. Pero el caso es que sacar diez veces consecutivas «cara» en diez tiradas de una moneda es muy improbable, pero PUEDE suceder. También, hay ciertos valores que las personas ya damos un evento casi como seguro, cuando no tiene porqué. ¿Quien no se ha enfadado cuando su personaje falla con un 90% de posibilidades? Si nos pasa tres veces seguidas, es que el ordenador claramente está haciendo trampas. Debemos tener en cuenta que, si bien los enemigos van y vienen deprisa, el jugador va a hacer MUCHAS «tiradas» a lo largo de la partida. Por lo tanto, lección 1, a veces no basta con usar un RNG puro y duro y dejar que el destino impersonal se encargue del resto, hay que compensar un poco. Por ejemplo, detectando malas rachas y evitando que se prolonguen demasiado. Hacer trampas para distribuir artificialmente los valores generados. Vamos, lo que en el rol de sobremesa vendría a ser «una ayudita del máster«.

Otro caso similar y muy típico en los videojuegos es el cálculo de la probabilidad de obtener una recompensa. Así pues, por ejemplo, a partir de un RNG decidimos si al derrotar a un jefe del Diablo II obtienes un objeto normal y corriente, un objeto mágico, o quizá uno raro. Pero otra vez estamos que, independientemente de los valores promedio esperados estadísticamente, si tenemos mala suerte, quizá pasan las horas de juego y no obtenemos el ansiado objeto raro. En entornos competitivos esto es peor, pues el mero azar hace que unos jugadores sean más poderosos que otros. En casos como este o parecidos, lección 2, entonces nos recomienda usar un pity timer (o contador «de la pena»). Algún mecanismo para modificar los pesos que rigen la elección de los tipos de recompensa, de modo que a medida que pasan los sucesos, la probabilidad de que finalmente obtengamos una recompensa buena se va incrementando. Cuando por fin se consigue, se reinicializa todo y volvemos a empezar.

Esquema de tablas de recompensas con pesos.

Por otra parte, la presentación de Squirrel,  «Noise-based RNGs», se centraba en otro uso habitual de estas herramientas en los videojuegos, si bien quizá tan aparente para el jugador: la generación procedural de contenidos. O sea, la capacidad de generar objetos al azar, desde instancias aisladas o sistemas de partículas hasta todo el mapa del juego, a partir del valor semilla elegido. Esta capacidad es extremadamente útil también de cara a disponer de una importante compresión de disco o red, pues basta con guardar la semilla para poder generar todos los objetos, sin tener que guardarlos al completo individualmente. ¿Como sino podías disponer de un universo al completo en un ordenador de 8 bits? Sin embargo, para ello es crucial garantizar su determinismo. Dada una semilla, los valores generados han de ser los mismos, siempre en el mismo orden.

En este caso, las lecciones se centraban sobretodo en saber valorar si un RNG es bueno. Bien, en realidad, esto depende de quién lo pregunte. Se debe tener en cuenta que en este contexto no estamos tratando de proteger información confidencial cifrada, sino generar contenidos. Por lo tanto, propiedades especialmente deseables son que sea rápido y que soporte un tamaño de semilla aceptable (normalmente 32 bits es más que suficiente). Evidentemente,  debe mantener las propiedades típicas de un RNG en cuanto a distribución de los valores y longitud de la secuencia generada hasta encontrar ciclos, así como la independencia entre bits de los distintos valores. Pero generar contenidos procedurales en un videojuego, su velocidad de ejecución es clave.

Entonces, veamos como se comporta un RNG típico en ese sentido, ya a nivel de código puro y duro, no conceptual. La opción más simple sería la que nos proporciona la biblioteca estándar de C: la función rand(), que proporciona valores aleatorios de 15 bits. El problema de esta función es que es un poco lenta y proporciona solo 15 bits, que son muy pocos. Para llegar a al menos 32, se suele usar una combinación de tres llamadas (triple rand), que claro está, hace todo el triple de lento. Sin embargo, lo peor de esta llamada desde la perspectiva de la programación de videojuegos es que posee un estado interno, cosa que complica todo en caso de usar múltiples hilos de ejecución (multithreading). De hecho, esta característica es una de las que hay que vigilar más atentamente cuando el uso de RNGs es en el contexto de los videjouegos, en contraste con su aplicación en el campo de la seguridad.

Finalmente, otro aspecto que complica las cosas es el hecho de que dicho estado no suele ser reversible, de modo que solo es posible ir accediendo secuencialmente a los valores, que se dan uno a uno, y no libremente como podría ser un array. Esta propiedad es importante ya que como se genera el mundo puede variar según la dirección por la que avance el personaje (pensemos en 3D), pero el terreno generado ha de ser coherente independientemente de ello. No puede ser que el mundo se genere distinto según si vengo por el norte o por el sur. Por lo tanto, a veces hay que avanzar y retroceder por la secuencia de valores.

Mirando ya algo considerado un buen generador de RNGs a nivel general, nos presentó el Mersenne Twister. Sin embargo, desde el punto de vista de implementación, resulta ser bastante pesado en cuanto al uso de memoria, y es incluso todavía más lento. Por ello, lo que Squirrel proponía a continuación es aprovechar las propiedades de los funciones de generación de ruido  para convertirlas en RNGs con propiedades satisfactorias en cuanto a velocidad, facilidad para el multithreading y capacidad de acceso libre a la secuencia generada.

Un ejemplo de función de ruido.

Así pues, si partimos que, a grosso modo, un generador de ruido es una función que aplica un conjunto de transformaciones sobre un valor de entrada, sin necesidad de un estado (en contraste con los RNGs), esto, de hecho, es muy parecido conceptualmente a una función de hash (como él mismo ya comentó). Pero usarlas no ayuda, pues vuelven a ser muy lentas computacionalmente, desde la perspectiva de lo que desea un programador de videojuegos (¡curiosamente, en seguridad se consideran «rápidas»!). Entonces su propuesta era que el estado del nuevo RNG fuera un simple índice que se va incrementando, y el valor generado el resultado de aplicar una función de ruido sobre dicho índice. La verdad es que el sistema es tan simple que seguramente hay alguna cosa desde el punto de vista de las propiedades matemáticas de los RNGs que se me debe escapar  (él también sospechaba que debía haber algún truco no evidente). Pero en las pruebas de rendimiento que proporcionó en la presentación pareció tener sentido (y con unos resultados que dejaban a otros algoritmos a la altura del betún). Y obteniendo todas las propiedades deseadas desde el punto de vista de programación.

Al final, el caso es que no estamos generando claves criptográficas, sino contenidos de un videojuego, por lo que si no todo es perfecto quizá tampoco pasa nada. Volviendo a la curiosa lección de la primera charla,  en un videojuego es más importante que las cosas parezcan aleatorias para el jugador, que realmente lo sean con el libro de matemáticas en la mano.

Joan Arnedo es profesor de los estudios de Informática, Multimedia y Telecomunicación en la UOC. Director académico del Máster en Diseño y Desarrollo de Videojuegos e investigador en el campo de la ludificación y los juegos serios. Su experiencia se remonta a cuando los ordenadores MSX poblaban la Tierra…

(Visited 28 times, 1 visits today)
Autor / Autora
Joan Arnedo Moreno
Etiquetas
Comentarios
Deja un comentario