Análisis de algoritmos de inteligencia artificial para videojuegos

ESCUELA T´ ECNICA SUPERIOR DE INGENIER´ IA INFORM´ ATICA GRADO EN INGENIER´ IA DEL SOFTWARE An´alisis de algoritmos de inteligencia artificial para videojuegos Analysis of artificial intelligence algorithms for videogames Realizado por David Rico Zambrana Tutorizado por Lorenzo Mandow Andaluz Departamento Dpto. Lenguajes y Ciencias de la Computaci´on UNIVERSIDAD DE M´ ALAGA M´ ALAGA, Noviembre 2016 Fecha defensa: El Secretario del Tribunal Resumen Este documento contiene el Trabajo de Fin de Grado del alumno David Rico Zambrana, estudiante del Grado en Ingenier´ıa del Software, en la Universidad de M´alaga. Este trabajo se ha realizado bajo la tutorizaci´on de Lorenzo Mandow Andaluz, profesor del Departamento de Lenguajes y Ciencias de la Computaci´on. El trabajo se titula An´alisis de algoritmos de inteligencia artificial para videojuegos, y consiste en el desarrollo de una aplicaci´on usando Unity3D en la que se muestren de forma did´actica conceptos de inteligencia artificial aplicada a los videojuegos, como son el pathfinding o b´usqueda de caminos y los steering behaviors o algoritmos de movimiento. La aplicaci´on tiene dos secciones diferenciadas. En una, se muestra al usuario un escenario de juego en el que se pueden seleccionar coordenadas de inicio y destino, y la aplicaci´on muestra y compara los caminos que proporcionan los distintos algoritmos de pathfinding implementados. La otra secci´on de la aplicaci´on consiste en un enfrentamiento en tiempo real entre un jugador humano y un jugador controlado por una inteligencia artificial. En esta secci´on se pueden controlar diversos par´ametros de los steering behaviors que controlan al jugador IA. Palabras clave: B´usqueda de caminos, algoritmos de movimiento, m´aquinas de estado, videojuegos, inteligencia artificial, Unity3D. Abstract This document contais the final dissertation ot the degree student David Rico Zambrana for the studies Grado en Ingenier´ıa del Software, of Universidad de M´alaga. This dissertation has been realised under the supervision of Lorenzo Mandow Andaluz, from the Departamento de Lenguajes y Ciencias de la Computaci´on. The title of this project is Analysis of artificial intelligence algorithms for videogames, and it consists in the development of a desktop application using Unity3D which shows in a didactic manner some concepts of artificial intelligence applied to videogames, as pathfinding or steering behaviors. The application has two separate sections. In the first one, the user is presented with a game scenery in which start and goal coordinates can be chosen, and then the different paths calculated by the various pathfinding algorithms are shown to the user. The other section of the application consists in a real time confrontation between a human player and an artificial intelligence controlled player. In this section, the user can control an array of parameters which control the steering behaviors of the AI player. Keywords: Pathfinding, Steering Behaviors, state machine, videogames, artificial intelligence, Unity3D. ´ Indice general 1 Introducci´on 1 1.1. Motivaci´on.................................... 1 1.2. Objetivos .................................... 1 1.3. Organizaci´on de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Antecedentes 3 2.1. Juegosyvideojuegos .............................. 3 2.2. Pathfinding ................................... 3 2.2.I. A* .................................... 4 2.2.II.HPA* .................................. 4 2.2.III.Suavizado ................................ 4 2.3. Movimiento ................................... 4 2.3.I. Steering behaviors . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Huida .................................. 5 B´usqueda ................................ 5 Deambular................................ 5 2.3.II. M´aquina de estados . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Dise˜no de la aplicaci´on 7 3.1. Visi´ongeneral.................................. 7 3.2. Unity3D..................................... 7 3.3. Pathfinding ................................... 8 3.4. Movimiento ................................... 9 3.5. M´aquinasdeestados .............................. 9 4 Uso de la aplicaci´on 11 4.1. Experimentaci´on con movimiento y m´aquinas de estado . . . . . . . . . . . 12 4.2. Experimentaci´on con pathfinding . . . . . . . . . . . . . . . . . . . . . . . 13 5 Conclusiones y trabajo futuro 15 6 Ap´endice: ampliaciones de la aplicaci´on 17 7 Bibliograf´ıa 19 1 - Introducci´on Este documento representa el trabajo de fin de grado del alumno David Rico Zambrana para los estudios de Grado en Ingenier´ıa del Software de la Universidad de M´alaga. El trabajo, bajo el t´ıtulo de “An´alisis de algoritmos de inteligencia artificial para videojuegos”, pretende mostrar de forma did´actica la aplicaci´on de diversas t´ecnicas de inteligencia artificial para juegos, as´ı como comparar su efectividad y el realismo de sus resultados. Para ello, se ha desarrollado una aplicaci´on en Unity3D en la que se ponen en pr´actica distintos conceptos, principalmente pathfinding y steering behaviors. Se trata de un juego de acci´on en tiempo real, en el que dos personajes se enfrentan en un escenario delimitado, representado con una perspectiva cenital. Los personajes pueden moverse en cualquier direcci´on, y al mismo tiempo pueden disparar en cualquier direcci´on (no necesariamente en la misma en que se mueven). 1.1. Motivaci´on El presente trabajo est´a motivado principalmente por un inter´es en el mundo del desarrollo profesional de videojuegos. El sector de los videojuegos es un sector cultural que cada vez tiene m´as importancia, y como industria mueve cifras equiparables o mayores a las del cine. Adem´as, es una salida profesional del Grado en Ingenier´ıa del Software que, sin embargo, no parece tener mucha consideraci´on en los planes de estudios actuales. Es cierto que existen asignaturas que tratan aspectos espec´ıficos de los videojuegos, y que gran parte del conocimiento general es tan aplicable a los videojuegos como al desarrollo web, pero no deja de haber un vac´ıo en cuanto a las herramientas usadas actualmente en la industria del videojuego, como pueden ser Unity3D o Unreal Engine, y tambi´en en cuanto a t´ecnicas usadas com´unmente en el desarrollo. 1.2. Objetivos Con este trabajo se pretenden conseguir m´ultiples objetivos: Desarrollar una aplicaci´on en Unity3D, demostrando conocer una de las herramientas m´as usadas en el desarrollo de videojuegos profesional. Visualizar de forma did´actica los resultados de distintos algoritmos de b´usqueda de caminos. 1 Visualizar de forma did´actica el comportamiento de un agente controlado por steering behaviors, as´ı como el efecto de variar diferentes par´ametros de ´estos. 1.3. Organizaci´on de la memoria En este primer cap´ıtulo hemos introducido el trabajo realizado. A continuaci´on, en los siguientes cap´ıtulos hablaremos de varios conceptos necesarios para el desarrollo de este trabajo (cap´ıtulo 2: antecedentes), luego se explicar´a el dise˜no y la arquitectura de la aplicaci´on desarrollada (cap´ıtulo 3: dise˜no de la aplicaci´on), un breve manual de usuario de la aplicaci´on donde veremos qu´e cosas se pueden experimentar en cada secci´on (cap´ıtulo 4: uso de la aplicaci´on), y por ´ultimo las conclusiones que se extraen del presente trabajo as´ı como ´areas en las que ser´ıa interesante profundizar (cap´ıtulo 5: conclusiones y trabajo futuro). Un breve ap´endice da unas pinceladas acerca de por d´onde se puede extender este trabajo, y cerramos con las referencias bibliogr´aficas y los agradecimientos. 2 2 - Antecedentes En este cap´ıtulo se van a exponer diferentes conceptos relacionados con el desarrollo de este trabajo. 2.1. Juegos y videojuegos Por juego se suele entender una actividad realizada por uno o varios jugadores, siguiendo un conjunto de reglas establecidas en com´un, con un objetivo l´udico. Sin adentrarnos demasiado en el debate filos´ofico de qu´e es un videojuego y qu´e no es un videojuego (debate muy vivo en los ´ultimos tiempos en las redes, debido al lanzamiento de diversos t´ıtulos que desaf´ıan la concepci´on normal de videojuego, como Gone Home en el que no hay condici´on de derrota, o Johan Sebastian Joust, que se juega con los mandos del PSMove pero sin pantalla), podemos decir que un videojuego es un juego que se ejecuta en un soporte electr´onico. El tipo de videojuegos que nos ocupa tendr´a una salida de imagen a trav´es de alguna pantalla, y recibir´a ´ordenes de uno o varios jugadores humanos a trav´es de alg´un dispositivo hardware dedicado a ello, como puede ser una pantalla t´actil, un mando, un teclado o un rat´on. En este trabajo nos centraremos en los llamados videojuegos en tiempo real, en los que las acciones de los jugadores no se realizan por turnos, sino que tienen lugar en un instante cualquiera dentro del continuo de la simulaci´on. 2.2. Pathfinding Llamamos pathfinding a la b´usqueda del camino m´as corto entre dos puntos, aunque en el ´ambito de los videojuegos se le da m´as importancia a la b´usqueda de un camino que sortee un obst´aculo que al hecho de que dicho camino sea efectivamente el m´as corto. Esto se debe principalmente a dos motivos: en primer lugar, en videojuegos no se dispone de mucho tiempo de procesamiento para calcular un camino, por lo que se prefiere un algoritmo que proporcione una soluci´on aceptable en un tiempo m´ınimo frente a un algoritmo que proporcione una soluci´on ´optima pero en un tiempo mayor; en segundo lugar, generalmente el camino ´optimo no va a resultar tan natural como otros caminos. Existen multitud de algoritmos de pathfinding, pero para este trabajo nos hemos centrado en los m´as destacables. 3 2.2.I. A* A* es sin duda alguna el referente en cuanto a pathfinding. Utiliza una funci´on de evaluaci´on que combina por una parte el coste desde el nodo origen hasta el nodo actual y por otra una funci´on heur´ıstica que estima el coste desde el nodo actual hasta el nodo meta. La clave del ´exito de A* es que, si el heur´ıstico utilizado es admisible, es decir, si no sobreestima el coste de alcanzar el nodo meta, el algoritmo garantiza que se encuentra el camino m´as corto si es que existe, es decir, la soluci´on es ´optima. Adem´as, A* es un algoritmo tremendamente flexible: el coste de computaci´on var´ıa seg´un el heur´ıstico que se utilice. Por ejemplo, si utilizamos un heur´ıstico que siempre d´e como resultado 0, el algoritmo se comporta exactamente como el algoritmo de Dijkstra. Si, por otra parte, utilizamos un algoritmo no admisible, podemos obtener una soluci´on (no ´optima) en un tiempo mucho menor, como defienden algunos autores1. En este trabajo se ha optado por usar un heur´ıstico admisible correspondiente a la distancia en movimiento 8-vecinos entre dos puntos. 2.2.II. HPA* HPA* es un algoritmo de los que llamamos jer´arquico: divide el mapa de juego en bloques, y aplica la b´usqueda de caminos en varios niveles, empezando por el superior y utilizando la informaci´on de niveles inferiores para calcular caminos locales. 2 2.2.III. Suavizado Por lo general, y de forma simplificada, A* se suele implementar sobre una cuadr´ıcula con un movimiento en cuatro u ocho direcciones. En los casos en que el espacio de juego no es discreto sino continuo y los personajes pueden moverse en cualquier direcci´on, se pueden aplicar postprocesados sobre la soluci´on de A* que simplifican el camino, convirtiendo en l´ıneas rectas secciones que originalmente ser´ıan un zigzag, por ejemplo. Existen tambi´en algoritmos como el llamado Theta* que incorporan este tipo de movimiento en cualquier direcci´on, pero en este trabajo se ha optado por aplicar un postprocesado sobre A* por reutilizaci´on de c´odigo. 2.3. Movimiento Para el movimiento aut´onomo de un agente controlado por una inteligencia artificial se usa una combinaci´on de diversas t´ecnicas. En este trabajo se han utilizado steering behaviors combinados con una m´aquina de estados para la toma de decisiones. 1http://realtimecollisiondetection.net/blog/?p=56 2http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/ 4 2.3.I. Steering behaviors Los llamados steering behaviors son comportamientos que, agregados, determinan cu´al ser´a la posici´on del agente en base a su posici´on y velocidad actual, su entorno y sus objetivos. Cada steering behavior cumple una funci´on, y ser´a necesario un nivel superior de decisi´on que determine qu´e comportamientos utilizar en cada momento de juego. De forma abstracta, cada comportamiento recibe la informaci´on que necesite del agente o del entorno y dar´a como resultado un vector que representa una fuerza. Al sumarse los distintos vectores de los comportamientos activos, se obtienen comportamientos con una apariencia compleja y un c´omputo muy sencillo. Huida El comportamiento de huida aplica una fuerza que intenta alejar al agente del punto que se proporcione como entrada. Existe una variante llamada evasi´on que aplica una predicci´on sobre la posici´on futura del elemento que se pretende evitar. B´usqueda El comportamiento de b´usqueda aplica una fuerza que intenta acercar al personaje al punto que se proporcione. Al igual que en el caso anterior, existe una variante llamada persecuci´on que aplica una predicci´on sobre la posici´on futura del elemento que se persigue. Deambular El comportamiento de deambular intenta que el agente se desplace de forma aleatoria pero no ca´otica, evitando los giros bruscos tanto como las l´ıneas perfectamente rectas. 2.3.II. M´aquina de estados En el apartado anterior mencion´abamos que es necesario acompa˜nar a los steering behaviors de un nivel superior de decisi´on que determine qu´e comportamientos deben estar activos en cada momento y c´omo se combinan. Por lo general se utilizan tres aproximaciones: m´aquinas de estados, ´arboles de decisi´on y funciones de utilidad. La m´as sencilla de estas opciones es la m´aquina de estados, que se compone de una serie de estados, las transiciones entre estos estados, las condiciones para que se den estas transiciones, y los eventos que disparar´an las condiciones. 5 Figura 4.2: Men´u de enfrentamiento 4.1. Experimentaci´on con movimiento y m´aquinas de estado La figura 4.2 muestra el men´u de la secci´on de enfrentamiento, en la que un jugador humano se enfrenta a un jugador controlado por una inteligencia artificial. A la izquierda tenemos los controles de los par´ametros del jugador humano, y a la derecha los controles de los par´ametros de la inteligencia artificial. Empezando por la izquierda, con el jugador humano, tenemos un slider que controla la velocidad de rotaci´on del personaje, y otro slider que controla la velocidad a la que se puede desplazar el personaje. A continuaci´on, una casilla nos permite indicar si queremos controlar al personaje con el rat´on o, si no la marcamos, con el teclado. Si elegimos el control con rat´on, haciendo click izquiero sobre el escenario ordenamos al personaje que se mueva a esa posici´on, y haciendo click derecho dispararemos en la direcci´on del puntero. Si elegimos este modo de control, tendremos que seleccionar adem´as el algoritmo de pathfinding que va a usar el personaje para desplazarse de su posici´on a la que le indiquemos. Por otra parte, si preferimos el control con teclado, usaremos las flechas para desplazar al personaje, las teclas W A S D para mirar hacia arriba, izquierda, abajo y derecha respectivamente, y la barra de espacio para disparar en la direcci´on en que estemos mirando. A la derecha tenemos los par´ametros de la inteligencia artificial. En primer lugar, los mismos sliders que para el jugador humano controlan la velocidad de rotaci´on y de desplazamiento del personaje. Un siguiente slider controla cada cu´antos impactos recibidos va a cambiar el comportamiento de la inteligencia artificial, entre un modo agresivo y un 12 Figura 4.3: Escenario de enfrentamiento modo evasivo. Por ´ultimo, dos sliders controlan el tama˜no del vector fuerza resultado de agregar los distintos steering behaviors, y el tama˜no del vector fuerza del comportamiento de evasi´on de obst´aculos, y otros dos sliders controlan la distancia hasta la que intenta acercarse el personaje en modo agresivo y a la que intenta alejarse en el modo evasivo. En la figura 4.3 vemos la pantalla de juego en s´ı. El personaje azul es el controlado por el jugador humano, y el personaje rojo corresponde a la inteligencia artificial. Arriba, a la izquierda aparecen los impactos que ha logrado el jugador humano, y a la derecha los impactos que ha logrado la inteligencia artificial, as´ı como el estado actual de la m´aquina de estados que lo controla. 4.2. Experimentaci´on con pathfinding La figura 4.4 muestra la secci´on de pathfinding, donde se comparan los distintos algoritmos de b´usqueda de caminos. A la derecha aparece el men´u que controla esta secci´on. Mediante una casilla podemos seleccionar qu´e algoritmo queremos ver ejecutar al personaje, aunque mediante una traza se muestran todos los caminos de los distintos algoritmos a la vez. Podemos seleccionar las coordenadas de origen y destino del camino de dos formas: bien introduciendo los n´umeros en los recuadros que aparecen, o bien haciendo click izquierdo sobre el escenario para seleccionar el origen, y click derecho para seleccionar el destino. En la figura 4.5 vemos el resultado tras elegir un camino y pulsar el bot´on Empezar. Los n´umeros que aparecen junto a cada casilla de los distintos algoritmos corresponde al coste del camino encontrado. Sobre el escenario vemos las l´ıneas de colores que corresponden a cada camino. 13 Figura 4.4: Pantalla de pathfinding Figura 4.5: Pantalla de pathfinding tras ejecuci´on de un camino 14 5 - Conclusiones y trabajo futuro A modo de conclusi´on, podemos considerar que los objetivos principales de este trabajo se han cumplido correctamente: se ha desarrollado una aplicaci´on en Unity3D, y en las distintas secciones de la aplicaci´on se pueden visualizar de forma did´actica los resultados de los diversos algoritmos de b´usqueda de caminos y los comportamientos y cambios en un agente controlado por steering behaviors. El desarrollo de este trabajo ha supuesto un acercamiento a Unity3D, uno de los entornos de trabajo m´as importante en la industria del videojuego actualmente, y a la programaci´on en C#. Unity3D ha demostrado ser una herramienta flexible y potente, con una curva de aprendizaje suave, que permite obtener resultados vistosos con relativamente poco trabajo. En cuanto a los algoritmos de b´usqueda de caminos, la comparativa entre los distintos caminos resulta especialmente ilustrativa. Se puede ver que el algoritmo A*, a pesar de proporcionar caminos ´optimos dentro de sus condiciones, est´a limitado de forma natural por las direcciones de movimiento que se le proporcionen. En un entorno con un espacio continuo, como el que se presenta en este trabajo, da resultados mucho m´as naturales un algoritmo con un suavizado, que permita movimientos en cualquier ´angulo. Por ´ultimo, los steering behaviors han demostrado ser muy delicados en cuanto a los valores de los par´ametros que se utilizan para determinar las fuerzas de los distintos vectores. Esto se debe, entre otras cosas, a que el fuerte de los steering behaviors son los comportamientos en grupo, mientras que para este trabajo se han utilizado de forma individual. Cuando se aplican a un n´umero suficientemente grande de agentes, la masa se comporta de forma suficientemente convincente, aunque individualmente haya errores o comportamientos extra˜nos. A partir de este trabajo, ser´ıa interesante seguir incluyendo algoritmos de b´usqueda de caminos para ampliar la comparativa. Por otra parte, ser´ıa interesante ampliar la secci´on de steering behaviors para incluir varios agentes que trabajen en grupo, y poder as´ı comprobar los comportamientos grupales. 15 6 - Ap´endice: ampliaciones de la aplicaci´on La aplicaci´on es f´acilmente ampliable en varias direcciones. En primer lugar, se pueden a˜nadir distintas escenas en las que aplicar otros conceptos que no se han tratado en este trabajo. Por ejemplo, se podr´ıa a˜nadir una escena en la que hacer una demostraci´on de aprendizaje autom´atico. Para ello bastar´ıa con crear la nueva escena en Unity3D, y en la escena del men´u inicial a˜nadir un bot´on que cargue esa escena. En segundo lugar, se pueden ampliar las escenas existentes: es muy f´acil a˜nadir m´as algoritmos de pathfinding, por ejemplo: ya tenemos las clases para los nodos, la estructura para gestionar los distintos algoritmos, etc. La clase correspondiente al algorimo que se quiera a˜nadir solo tiene que heredar de Pathfinding e implementar los m´etodos FindPath y DrawPath. En cuanto a los steering behaviors, se pueden a˜nadir m´as comportamientos en la clase manager, y es f´acil ampliar la m´aquina de estados para incluir los nuevos steering behaviors. Habr´ıa que programar la l´ogica de las transiciones, que est´a en la clase AIPlayerBasic, y enlazar sus valores al men´u de juego resulta trivial a trav´es del editor de Unity3D. 17 7 - Bibliograf´ıa Para el desarrollo de este trabajo se ha recurrido a la siguiente bibliograf´ıa: Millington, I. Artificial Intelligence for Games. San Francisco: Morgan Kaufmann Publishers Inc., 2006. ISBN 0124977820. Russell, S. y Norvig, P. Artificial Intelligence: a modern approach (3rd Ed.). New Jersey: Pearson Education Inc., 2010. ISBN 0132071487. Murray, J.W. C# Game Programming Cookbook for Unity 3D.CRC Press, 2015. ISBN 1466581409. Web: http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/ Fecha de consulta: noviembre 2016. Web: http://theory.stanford.edu/˜amitp/GameProgramming/Variations.html Fecha de consulta: noviembre 2016. Web: https://www.hindawi.com/journals/ijcgt/2008/873913/ Fecha de consulta: noviembre 2016. Web: http://realtimecollisiondetection.net/blog/?p=56 Fecha de consulta: noviembre 2016. Web: http://www.cs.ru.nl/bachelorscripties/2013/Linus van Elswijk 0710261 Hierarchical Path-Finding Theta star Combining HPA star and Theta star.pdf Fecha de consulta: noviembre 2016. Web: http://xfleury.github.io/graphsearch.html Fecha de consulta: noviembre 2016. Web: https://gamedevelopment.tutsplus.com/tutorials/understanding-steeringbehaviors-movement-manager–gamedev-4278 Fecha de consulta: noviembre 2016. Web: http://cstheory.stackexchange.com/questions/11855/how-do-the-state-of-theart-pathfinding-algorithms-for-changing-graphs-d-d-l Fecha de consulta: noviembre 2016. Web: http://www.red3d.com/cwr/steer/ Fecha de consulta: noviembre 2016. Web: https://davidtheory.wordpress.com/2012/11/04/ia-en-unity3d-steering-behaviours/ Fecha de consulta: noviembre 2016. 19 Agradecimientos Este trabajo est´a especialmente dedicado a aquellas personas que me han empujado cuando m´as lo necesitaba, que me han soportado cuando no lo merec´ıa, y que me han ayudado a superar una piedra tras otra. Por supuesto, a mis padres, que no solo me apoyan moralmente sino que adem´as ponen el dinero, y son un ejemplo y una referencia en mi vida. A mis hermanos, Ale y Alberto, que entienden mejor que nadie la presi´on de la recta final, las noches sin dormir, y el impulso de tirarlo todo y volver a empezar cuando ya no queda tiempo. Y a Jes´us, que junto a mis hermanos forman mi equipo de trabajo, y que est´an llevando nuestros proyectos adelante mientras yo termino este trabajo. A Marina. T´u me has dado el ´ultimo empuj´on, el m´as importante, cuando ya hab´ıa decidido abandonar. Me has animado, has estado m´as pendiente que una madre y has confiado en m´ı m´as que yo mismo. No hay caf´e suficiente para pag´artelo. Y a Gema y Mar´ıa tambi´en, porque entre las tres me pod´eis alegrar hasta el peor de los d´ıas. No cambi´eis. Y a Lorenzo, que ha sido un magn´ıfico profesor y, probablemente, el mejor tutor que podr´ıa haber tenido para este trabajo. Gracias a todos. 20