Si en algo he insistido durante mis años en la prensa del videojuego es que los títulos que tanto nos gustan, en mayor o menor medida, tienen una relación cercanísima con las matemáticas. Esto será un choque para quienes odiaban esta asignatura en el colegio, pero una realidad ineludible para cualquier que tenga un mando o un ratón en las manos. Los fans de Pokémon, por ejemplo, ya lo saben.
Pero es el momento de abrir el abanico y empezar a pensar en más títulos. Y qué mejor que hacerlo hablando por primera vez en 3DJuegos de los algoritmos: esa palabra mágica que parece poder hacer de todo, pero que no todo el mundo se atreve a echar un vistazo a su funcionamiento. Es una verdadera pena, porque puede aprenderse mucho sobre distintos aspectos de cómo es un videojuego por dentro.
El algoritmo, en su definición más simple, es una serie de pasos que nos permiten llegar a la solución de un problema. Y trayéndonoslo a nuestra realidad, una receta que podemos darle a los sistemas de un videojuego para que realice ciertas acciones de la forma correcta. Porque sí, la mayor parte de cosas que suceden en un videojuego son problemas matemáticos que se resuelven en tiempo real por las máquinas que ejecutan el programa.
Algoritmos hay muchos con protagonismo en los videojuegos, pero concretamente uno es quien aparece en multitud de ellos, ya que resuelve un problema muy específico y que es común a muchos géneros. Estoy hablando del algoritmo A* o A estrella, que sirve para calcular la ruta más corta entre dos puntos dados. Se trata de una tarea muy básica, pero que está presente más veces de las que crees.
Los Sims 2.
Cuando en un título de estrategia como Age of Empires II haces clic para mover a un personaje, A* está ahí; si un enemigo melé busca rodearte en el modo campaña de un shooter, es bastante factible que este algoritmo esté jugando un papel clave... Y lo mismo en otros títulos como los MOBA, o incluso Los Sims. E incluso si no es A*, posiblemente sea una evolución o una optimización del mismo.
¿Cómo funciona el algoritmo A*?
Como digo, A* es un algoritmo perteneciente a la familia de los PFA o Path Finding Algorithm (Algoritmos de Búsqueda de Ruta en castellano), los cuales le dan una serie de pasos al videojuego para conseguir el camino más rápido a cierto punto. El que nos ocupa, es una evolución de lo que arrancó con el matemático Edsger W. Dijkstra en 1956, simplificando la cantidad de operaciones a realizar por el programa.
Algoritmo de Dijkstra (izquierda) y A* (derecha). Fuente: https://qiao.github.io/PathFinding.js/visual/
Los videojuegos tienen dividido su espacio, de una forma más o menos evidente, en cuadrículas. Lo que hace un PFA es calcular por qué cuadrículas ha de ir un personaje para llegar a cierto lugar sin chocarse con un obstáculo, así como hacerlo de la forma más eficiente y rápida posible. Y lo que les diferencia a cada uno de ellos es la forma de calcular dicha ruta.
"La diferencia en la carga que le pedimos al sistema es sustancialmente más pequeña [con A*]"
El caso que nos ocupa, A*, tiene como revolucionario frente a los métodos más vetustos el hecho de darle una información extra al programa con cada paso. Mientras el algoritmo de Dijkstra simplemente amplía la zona de los posibles caminos al circular por todos las cuadrículas que llevan a las rutas más cortas, terminando la búsqueda al alcanzar la cuadrícula de destino, A* lo que hace es el mismo proceso, pero dándole al algoritmo la distancia en línea recta al destino antes de tomar la decisión de qué cuadrícula evaluar la siguiente.
La diferencia en la carga que le pedimos al sistema es sustancialmente más pequeña. Para el caso práctico de la imagen superior, tenemos 953 operaciones realizadas con Djikstra, mientras que para A* nos vamos a únicamente 108. Esta simplicidad hace que el camino se calcule mucho más rápido, algo clave para que la velocidad de las partidas no se vea ralentizada, especialmente en los primeros juegos que requerían de este tipo de algoritmos.
Aplicaciones de A* en videojuegos
Sobre este tipo de algoritmos de búsqueda de ruta tenemos mucha información en los papers académicos. Los autores Xiao Cui de la Universidad de Melbourne y Hao Shi de la Universidad de Londres, publicaron en 2010 todo un artículo científico sobre el uso del A* en videojuegos. Contrariamente a lo que podamos pensar por su naturaleza más pausada, cuentan que los juegos de estrategia como Age of Empires II tienen más problemas con su implantación (todos hemos tenido a algún monje atrapado en un bosque), que shooters en primera persona.
Age of Empires II: Definitive Edition.
"A* funciona mucho mejor en juegos de disparos en primera persona como Counter-Strike, en los que sólo unas pocas unidades se mueven al mismo tiempo. Una explicación podría ser que el crecimiento exponencial del número de unidades que se mueven al mismo tiempo hace que el entorno del juego sea mucho más dinámico y es difícil proporcionar rutas óptimas para cientos y miles de unidades en tiempo real.", explican en el paper.
Trabajos más recientes, como el de 2023 de Daohong Liu de la Universidad de Pekín publicado en Highlights in Science, Engineering and Technology, además de explicar cómo funciona A* una vez más, habla sobre la aplicación de este algoritmo a NPCs y no ya a personajes controlados por los jugadores. Dado que estamos hablando de títulos potencialmente más complejos y con un mundo más vivo, habla de dos factores interesantes a tener en cuenta: la velocidad y el realismo. No es tan importante que lleve a cabo el camino óptimo, como que se mueva rápido y de una forma convincente; que no parezca un robot.
Evidentemente, las ciencias de la computación siempre buscan optimizar sus recursos y hay algoritmos más potentes en desarrollo, los cuales simplifican la tarea; como pasó con A* frente a Dijkstra y otros menos avanzados. Sea como sea, ahora sabrás que esa unidad en Age of Empires II, cada vez que se mueve, hace cientos de cálculos primero.
Foto de portada de Age of Empires II: Definitive Edition.
En 3DJuegos | El juego más irrepetible de 2024 es una genialidad por hacer las cosas mal a propósito. UFO 50 y su gran apuesta con Barbuta
Ver 0 comentarios