Repositorio Institucional de Documentos

Desarrollo de una inteligencia artificial para un juego de baloncesto Isaac Clerencia Pérez PROYECTO FIN DE CARRERA Septiembre de 2010 Director: Diego Gutierrez Departamento de Informática e Ingeniería de Sistemas Ingeniería en Informática Centro Politécnico Superior, Universidad de Zaragoza Curso 2009-2010 Desarrollo de una inteligencia artificial para un juego de baloncesto RESUMEN El trabajo realizado en este proyecto ha sido el desarrollo de un juego de baloncesto con una inteligencia artificial para que una persona pueda jugar contra ella. El resultado es el primer simulador deportivo 3D bajo una licencia libre. En primer lugar se hizo un análisis del proyecto en el que se estudió el juego completo con especial énfasis en la inteligencia artificial. A continuación se realizó un diseño de alto nivel de los principales subsistemas del juego. En cuanto a la estructura general del juego, se planeó un bucle principal con soporte para diferentes estados de juego, utilizando una pila para mantener los estados actualmente en ejecución, incluyendo menú, partido y pausa. De esta manera el estado encargado de recibir eventos y actualizar los gráficos y otras variables del juego es el que se encuentra en el tope de la pila. Es muy sencillo volver de un estado al anterior pues sólo tenemos que desapilar el tope. La siguiente parte importante fueron las estructuras de datos para el partido (jugadores, equipos y partido), sus contrapartes gráficas en 3D y la relación entre ellas. Además se programó las partes de simulación física para obtener un comportamiento realista de la pelota cuando rebota contra el suelo o el aro, así como para detectar colisiones entre jugadores o intercepciones de la pelota. Por último, la parte más importante fue la inteligencia artificial, objetivo principal del proyec- to. Una parte fundamental de la inteligencia artificial es la captura de información para poder tomar decisiones adecuadas. No es eficiente que la IA compruebe a cada momento el estado de todo el resto de jugadores, por lo que se desarrolló un sistema de eventos, de tal modo que la inteligencia artificial es notificada de cualquier hecho importante en el partido. Este sistema de eventos usa un patrón Observer de tal manera que los objetos que quieren recibir eventos pueden suscribirse a él. Contando con el sistema de gestión de eventos, se desarrolló una inteligencia artificial jerárquica contando con tres niveles fundamentales a nivel de jugador y un nivel superior de equipo. Los tres niveles de IA individual culminan en un sistema de acciones de alto nivel en el que es fácil dar instrucciones complejas a los jugadores. En el sistema de acciones se apoya la IA de equipo, basada en una máquina de estados capaz de reaccionar ante los eventos del partido para elegir el estado adecuado para actuar ante la situación actual del partido. Para incrementar la flexibilidad de la IA y ponerla al alcance del usuario final se implementó la posibilidad de modificar la IA mediante scripting sin necesidad de recompilar el juego. Es posible añadir o redefinir estados de la IA de equipo escribiendo sencillos ficheros en Javascript. Para ayudar a mejorar la IA se cuenta con un sistema de pruebas que permite definir escenarios y ejecutarlos de manera automática para comprobar el efecto que posibles cambios en la IA producen en el juego. 1 Índice general 1. Introducción 1 1.1. Objetivo...................................... 1 1.2. Alcance ...................................... 1 1.3. Trabajoprevio................................... 1 1.4. Motivacióndelproyecto ............................. 2 1.5. Líneasgenerales.................................. 2 1.5.1. Estrategia................................. 2 1.5.2. Métodosytécnicas............................ 3 1.5.3. Herramientas............................... 3 1.6. Convencionesadoptadas ............................. 4 1.7. Estructura de este documento . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Trabajo desarrollado 6 2.1. Física ....................................... 7 2.1.1. Elección de un motor de física . . . . . . . . . . . . . . . . . . . . . . 7 2.1.2. Open Dynamics Engine . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.3. Utilización de ODE en un proyecto con Ogre . . . . . . . . . . . . . . 9 2.2. Inteligenciaartificial ............................... 11 2.2.1. Sistemadeeventos............................ 11 2.2.2. Acciones ................................. 12 2.2.3. Inteligencia artificial de equipo . . . . . . . . . . . . . . . . . . . . . . 13 2.2.4. Scripting con Javascript . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.5. DepuracióndelaIA ........................... 14 3. Resultados 15 4. Conclusiones 19 4.1. Descripciónresumida............................... 19 4.2. Valoracióncrítica................................. 19 Anexos I ÍNDICE GENERAL ÍNDICE GENERAL A. Diseño 21 A.1.Introducción.................................... 21 A.2. Estructura general del juego . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 B. Física 25 B.1. Uso de ODE en In Your Face . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 C. Inteligencia artificial 29 C.1.Introducción.................................... 29 C.2. Arquitectura básica de la inteligencia artificial . . . . . . . . . . . . . . . . . . 30 C.3.Gestordeeventos................................. 31 C.4.IAjerárquica ................................... 33 C.4.1. Acción básica y steering behaviours ................... 33 C.4.2. Acciones: Action::Base . . . . . . . . . . . . . . . . . . . . . . . . . . 36 C.4.3. IAs de equipo: AI::Base . . . . . . . . . . . . . . . . . . . . . . . . . 42 C.5. Inteligencia artificial AI::Standard ........................ 44 C.6. Scripting de la inteligencia artificial AI::Standard ................ 53 C.6.1. Elección de un lenguaje y plataforma de scripting . . . . . . . . . . . . 53 C.6.2. QtScript.................................. 53 C.6.3. Uso de QtScript en InYourFace . . . . . . . . . . . . . . . . . . . . . 54 C.7. Métodos de depuración y mejora de la IA . . . . . . . . . . . . . . . . . . . . 60 D. Licencia 64 Índice de figuras 70 Índice de tablas 71 Bibliografía 72 II Capítulo 1 Introducción 1.1. Objetivo El objetivo de este proyecto es diseñar e implementar un juego de baloncesto en tres dimensiones que incluya una inteligencia artificial. Este juego será el primero de este tipo en ser publicado bajo una licencia libre. El entorno para el desarrollo ha sido el sistema operativo Linux. Se ha utilizado C++ como lenguaje principal de implementación y la biblioteca Ogre3D como motor gráfico. El juego es multiplataforma y es posible ejecutarlo en Linux, MacOS X y Windows. El software desarrollado se distribuye bajo licencia GNU GPL. 1.2. Alcance La complejidad del problema abordado es considerable, especialmente en algunos aspectos como la física del juego y la inteligencia artificial. Para poder trabajar en el desarrollo de la inteligencia artificial, prioridad del proyecto, ha sido necesario desarrollar anteriormente el resto de partes necesarias del juego, como la física o el sistema de eventos. 1.3. Trabajo previo En el desarrollo de este proyecto se aprovechan una serie de bibliotecas y herramientas preexistentes que han hecho posible la implementación en un periodo de tiempo razonable. Entre las más importantes se cuentan: •Distribuciones de GNU/Linux Debian/Ubuntu •Motor 3D OGRE 1 1. Introducción 1.4. Motivación del proyecto •Biblioteca de simulación de dinámica de solidos rígidos ODE •Biblioteca de interfaz gráfica CEGUI •Bibliotecas C++ Boost •Toolkit Qt para tipos abstractos de datos, acceso a bases de datos y red •Lenguaje de programación C++ Además se utilizan otras bibliotecas de C++ menos importantes para facilitar tareas como la gestión de argumentos en la línea de órdenes. 1.4. Motivación del proyecto El proyecto se planteó debido a un interés personal en el desarrollo de videojuegos. El diseño y programación de los mismos plantea un gran número de interesantes retos tanto a nivel de arquitectura del programa como a nivel de física e inteligencia artificial. 1.5. Líneas generales 1.5.1. Estrategia El proyecto se ha dividido en tres fases principales: Investigación: durante esta fase se realizó el estudio de los distintos campos que abarca este proyecto como son la inteligencia artificial en videojuegos, la física, reglas del juego, etc. Los resultados obtenidos se reflejan en los anexos correspondientes. El tiempo a emplear en esta primera fase se fijó en un mes. Análisis y diseño: se realizó el análisis del proyecto y un diseño de alto nivel para la estructura general del juego. Esta fase duro entorno a un mes. Desarrollo: implementación del juego. Se planificó inicialmente en tres meses pero el tiempo final fue de cuatro meses. En la tabla 1.1 se expone el cronograma estimado. Id Paquete de trabajo Inicio Fin 1 Investigación t0t0+ 1m 2.1 Desarrollo: análisis y diseño t0+ 1m t0+ 2m 2.2 Desarrollo: implementación t0+ 2m t0+ 5m Tabla 1.1: Cronograma estimado 2 1. Introducción 1.5. Líneas generales En la tabla 1.2 se expone el cronograma real. Id Paquete de trabajo Inicio Fin 1 Investigación t0t0+ 1m 2.1 Desarrollo: análisis y diseño t0+ 1m t0+ 2m 2.2 Desarrollo: implementación t0+ 2m t0+ 6m Tabla 1.2: Cronograma real 1.5.2. Métodos y técnicas El empleo de L A T EX como sistema de documentación permitió una integración sencilla de capítulos escritos de forma independiente. Así como un fácil mantenimiento de la bibliografía. La metodología de ingeniería del software empleada ha sido la programación extrema (Extreme Programming). La programación extrema es una de las metodologías para el desarrollo ágil de software. Está especialmente indicada para sistemas donde los requisitos pueden cambiar, como es el caso de este proyecto, cuyos objetivos no están claramente definidos aparte del general, creación de una AI. Uno de los principios de la programación extrema es el feedback. En el caso de los proyectos tradicionales, el feedback se obtiene a través del contacto con el cliente. Si ésto ocurre frecuentemente, en iteraciones pequeñas, la respuesta se obtiene antes y se puede aprender y realizar cambios de forma más rápida. En el caso de este proyecto, el papel de cliente lo han asumido terceras personas que han probado el juego y que han proporcionado información de gran utilidad acerca de posibles mejoras o problemas existentes. 1.5.3. Herramientas Desarrollo Las tareas de desarrollo han constado principalmente de codificación. También se han utilizado herramientas adicionales para la gestión del proyecto o el control de versiones. Las herramientas utilizadas para todo ello se describen a continuación: •Vim: Potente editor de texto. •Blender: Herramienta de modelado 3D •Subversion: Herramienta de control concurrente de versiones. •Trac: Sistema de gestión de proyectos software. 3 1. Introducción 1.6. Convenciones adoptadas Documentación Las herramientas utilizadas para la edición y generación de toda la documentación han sido las siguientes: •Vim: Potente editor de texto. •L A T EX: Lenguaje de marcado para la creación de documentos, formado por un conjunto de macros de T EX. Se ha utilizado para la generación de la presente documentación. •inkscape: Programa de dibujo vectorial •Dia: Editor de diagramas 1.6. Convenciones adoptadas Representación de nombres de fichero y comandos •Los nombres de fichero a los que se haga referencia en el texto aparecerán siempre en letra cursiva. •Los nombres correspondientes a órdenes del sistema u otros programas aparecerán en letra negrita. Código fuente con realzado de sintaxis Los fragmentos de código fuente y ficheros de especificación que tengan un formato determinado aparecerán en un recuadro gris como se muestra a continuación: int main ( ) { p r i n t f ( " Hello , world " ) ; } Contenido de ficheros y salida de programas La salida de programas o contenido de ficheros que no tengan una determinada sintaxis aparecerá en fuente monoespaciada con el siguiente formato: Render System=OpenGL Rendering Subsystem [OpenGL Rendering Subsystem] FSAA=0 Full Screen=No RTT Preferred Mode=PBuffer Video Mode=800 x 600 4 1. Introducción 1.7. Estructura de este documento 1.7. Estructura de este documento La documentación del proyecto consta de la memoria principal y una serie de anexos, acompañados de la bibliografía. La memoria está organizada en cuatro capítulos: introducción, trabajo desarrollado, resultados y conclusiones. En el primero de ellos se describe el objetivo del proyecto, su alcance, el trabajo previo, el contexto, las líneas generales y una breve reseña de las convenciones utilizadas. El capítulo sobre el trabajo desarrollado ofrece una visión general sobre cada una de las principales tareas realizadas y sistemas implementados. Finalmente, el capítulo que contiene las conclusiones está dividido en tres secciones: descripción resumida, valoración crítica e incidencias. Por otro lado, los anexos incluidos son los siguientes: A. Diseño: Este anexo ofrece información sobre el diseño del juego, sin entrar en detalles en la física y la inteligencia artificial. B. Física: Este anexeo ofrece detalles sobre la resolución de los problemas relacionados con la simulación física en el juego. C. Inteligencia artificial: Este anexo contiene ´ la descripción del diseño de la inteligencia artificial para el juego. D. Licencia: Este anexo contiene el texto oficial de la GNU General Public License, bajo la cual se licencia todo el software de este proyecto. 5 2. Trabajo desarrollado 2.2. Inteligencia artificial Por último, tenemos otros eventos que no encajan en las anteriores categorías, como por ejemplo, un evento que se lanza cada segundo de tal manera que la inteligencia artificial tenga una oportunidad de ejecutarse cada segundo aunque no haya eventos en el partido, y otro evento que indica que la acción que un jugador estaba llevando a cabo se ha terminado. Usando este último evento es posible definir jugadas complicadas, como por ejemplo indicar a un jugador que tiene que esperar a que otro compañero de equipo vaya a una posición para realizar un pase. 2.2.2. Acciones La inteligencia artificial usa un sistema de estados para saber cual es el objetivo actual del equipo. Este objetivo puede ser defender, subir la pelota a la canasta contraria o intentar anotar. Los eventos pueden disparar transiciones entre estos estados (como en el caso de final de posesión o de un robo de balón) o simplemente desencadenar acciones sin cambiar el estado, por ejemplo, intentando interceptar un pase realizado por el equipo contrario. Para dar instrucciones a los jugadores del equipo, la inteligencia artificial utiliza un sistema jerárquico de acciones. En el nivel más alto tenemos acciones de alto nivel como por ejemplo cubrir a un contrario, interceptar la bola, realizar un tiro a canasta o intentar robar el balón. Estas acciones están compuestas por un conjunto de acciones básicas. Las acciones básicas son los movimientos más simples posibles y se caracterizan por ser deterministas. Incluyen instrucciones como girar, saltar o tirar a canasta con unos parámetros fijos (fuerza y dirección). En un principio parece que con estos dos tipos de acciones es suficiente, pero cuando se realiza una simulación pronto se hace obvio un grave problema. Los jugadores se chocan entre ellos, se salen del terreno de juego y realizan acciones similarmente no inteligentes. Si tuvieramos que introducir comprobaciones para estas situaciones en cada acción de la inteligencia artificial de alto nivel, sería increiblemente complicado y lento escribir nuevas acciones. Una acción tan sencilla como moverse a una posición del terreno de juego necesitaría varias comprobaciones. Para resolver este problema, se introdujeron steering behaviours [1, 3], esto es, diferentes modos de comportamiento que un agente puede tener en cuanto a su movimiento. Estos comportamientos pueden incluir cosas como ir a una posición, seguir a un jugador, no salirse del terreno de juego o no chocarse con otros jugadores, y pueden ser combinados entre ellos. Para calcular el movimiento de un jugador simplemente se ejecutan los distintos comportamientos y se suma el resultado de cada uno de ellos. Si, por ejemplo, queremos que un jugador vaya a una determinada posición sin salirse de la pista y sin chocarse con otros jugadores, simplemente tenemos que añadir los comportamientos, ir a una posición de la pista,no salirse del campo yno chocarse con otros jugadores. La mayoría del movimiento será guiado por el primer comportamiento, pero si el jugador va a chocarse con otro jugador el comportamiento de no chocarse rectificará la dirección del jugador para evitar la colisión. Si al intentar evitar la colisión el jugador va a salir fuera del terreno de juego, el comportamiento apropiado rectificará su dirección y velocidad. 12 2. Trabajo desarrollado 2.2. Inteligencia artificial 2.2.3. Inteligencia artificial de equipo Una vez que tenemos las acciones básicas que permiten asignar instrucciones a los jugadores podemos centrarnos en la inteligencia artificial a nivel de equipo. Figura 2.3: Diagrama de estados básico de la IA La inteligencia artificial de equipo está implementada mediante una máquina de estados, cuyo diagrama de estados básico podemos observar en la figura . Estos estados establecen las acciones a ejecutar por los diferentes jugadores y son notificados de los eventos del partido. Estos eventos recibidos pueden causar una transición a otro estado. Por ejemplo, el primer estado se llama BeforeMatch y su único objetivo es colocar a los jugadores en la posición inicial. Cuando este estado recibe el evento MatchStart se pasa al estado FreeBall. El objetivo de la inteligencia artificial en este estado es conseguir la posesión de la pelota, y lanzarse al ataque o preparar la defensa dependiendo de la probabilidad estimada de conseguir la posesión. Otros estados básicos son Attack,TryToScore yDefend. Estos tres estados son los que están activos la mayor parte de un partido. Los estados básicos están implementados en C++ e incluyen métodos para analizar situaciones en el partido, como por ejemplo, estimar la probabilidad de que un pase sea interceptado o las posibilidades de que un tiro a canasta sea exitoso. Estos análisis a menudo incluyen interesantes problemas geométricos. 13 2. Trabajo desarrollado 2.2. Inteligencia artificial 2.2.4. Scripting con Javascript La IA también incluye una posibilidad de ampliación muy interesante. La mayoría de estados pueden sobreescribirse mediante scripting. También es posible añadir nuevos estados para crear inteligencias artificiales más complejas. Para añadir o modificar estados tan solo es necesario escribir pequeños ficheros en JavaScript, sin necesidad de recompilar el programa. Esto proporciona una gran herramienta al usuario final para modificar el comportamiento de la IA. 2.2.5. Depuración de la IA Para facilitar la depuración y la mejora de la IA se utilizan tres aproximaciones diferentes. Por una parte, el programa cuenta con un sistema de registros del juego, basado en log4cpp, que registra de manera jerárquica los eventos que ocurren. De este modo es posible tener registros verbosos que se pueden activar y desactivar fácilmente cuando queremos depurar una parte determinada de la IA. En segundo lugar, existe un mecanismo llamado etiquetas de jugadores que permite a diferentes partes de la IA añadir información de depuración a los jugadores. Estas etiquetas pueden ser activadas durante el partido de tal manera que es posible ver, para cada jugador, que acción están realizando y algunos otros parámetros que explican su comportamiento. Esta información se muestra sobreimpresa acompañando al jugador por el terreno de juego. Por último, y sobre todo orientado a la mejora de la IA, el tercer método es la ejecución de pruebas. Es posible escribir escenarios de prueba en ficheros XML, conteniendo una configuración inicial del partido, incluyendo las posiciones de los jugadores, quien tiene el balón y cual es el estado de los equipos. Estos escenarios también permiten establecer condiciones de éxito y fracaso, así como un límite de tiempo. Estos escenarios de prueba, ejecutados un alto número de veces, permiten comprobar el efecto de cambios en la IA en los resultados del juego. mediante la ejecución de los mismos 14 Capítulo 3 Resultados El resultado del proyecto ha sido un juego de baloncesto en 3D al que pueden jugar dos jugadores o un jugador contra una inteligencia artificial. El juego consta de un sistema inicial de menús para elegir el tipo de juego deseado, equipos y controladores entre otros. El jugador controla a su equipo mediante el teclado, pudiendo realizar tiros, lanzamientos a canasta y seleccionar el jugador que desea controlar. La figura 3.1 contiene una secuencia de partes de fotogramas en la que el usuario está dirigiendo un ataque. En el fotorama número tres podemos observar como su compañero de equipo hace un bloqueo para proporcionar al jugador un tiro claro en el fotograma cuatro, que finalmente se convierte en canasta. 15 3. Resultados Figura 3.1: Atacando 16 3. Resultados La inteligencia artificial tiene en cuenta la posición de los jugadores, del balón, el tiempo restante de posesión y es capaz de realizar movimientos que desmarquen a sus jugadores, estimar posibilidades de pase y tiros a canasta, eligiendo las mejores opciones. La IA no está al nivel de las inteligencias artificiales de juegos profesionales, con gran cantidad de recursos y años de desarrollo, pero resulta un enemigo interesante durante los primeros partidos. Además, gran parte del esfuerzo realizado se ha centrado, no en que la IA fuera excepcional, sino en que fuera extensible y fácil de mejorar. Para un desarrollador con experiencia en C++ debería ser sencillo mejorar el núcleo de la IA. El proyecto fue ideado desde el primer momento como software libre, por lo que otros desarrolladores están invitados a mejorar el juego. Algunos desarrolladores ya han mostrado su interés en colaborar con el proyecto cuando sea posible. Por otra parte, otros usuarios menos avanzados pueden intentar añadir nuevas jugadas a la IA utilizando el sistema de scripting. En la figura 3.2 vemos a la IA realizando un tiro desesperado cuando su posesión está a punto de expirar. Se puede observar el contador de tiempo de partido, el marcador y el reloj de posesión. Figura 3.2: Tiro al final de posesión Como vemos en la figura 3.3, donde también podemos observar las notificaciones de eventos en 17 3. Resultados el partido, el tiro tuvo éxito. Figura 3.3: Canasta El proyecto es jugable y resulta divertido durante unos cuantos partidos. Sin embargo la IA todavía es bastante precedible, por lo que resulta fácil aprender algunos trucos que hacen fácil batirla. Sin embargo, la capacidad de mejorar la IA mediante scripting hace que sea muy sencillo añadir nuevas jugadas para hacer el juego más divertido y proporciona una manera alternativa de disfrutar el juego, programando jugadas para la IA. 18 Capítulo 4 Conclusiones 4.1. Descripción resumida Se ha creado un juego de baloncesto en tres dimensiones (In Your Face). El juego incluye una inteligencia artificial para que una persona pueda jugar contra el ordenador, aunque también es posible que dos jugadores humanos jueguen entre ellos. 4.2. Valoración crítica Aportaciones En opinión del autor, la principal aportación de este proyecto fin de carrera es la creación del primer simulador deportivo en 3D con una inteligencia artificial bajo una licencia libre. Existen muy buenos simuladores deportivos propietarios, pero hasta ahora no había ninguna implementación libre de una inteligencia artificial de este tipo. Cumplimiento de los objetivos El principal objetivo del proyecto se ha cumplido, la creación de una inteligencia artificial para un juego de baloncesto. Sin embargo, el trabajo necesario para esta tarea ha sido bastante superior al esperado por lo que sólo uno de los objetivos secundarios, la posibilidad de ampliar el juego utilizando un lenguaje de scripting, se ha podido llevar a cabo. Trabajo futuro A pesar de la gran cantidad de trabajo realizado, el proyecto tiene bastantes posibilidades de ampliación. Entre ellas se pueden destacar la posibilidad de juego en red que, debido a la arquitectura de acciones, debería ser sencillo de implementar. 19 4. Conclusiones 4.2. Valoración crítica Otras ampliaciones interesantes serían la posibilidad de jugar competiciones completas y la mejora de las estadísticas recogidas durante partidos. En cuanto al modo de juego, una posibilidad interesante era implementar un interfaz de tiempo bala, similar al efecto de la película Matrix o de algunos juegos como Max Payne 2. Por supuesto, la inteligencia artificial también puede ser mejorada enormemente. Una de las opciones más interesantes a explorar es modificar la IA para que esté más parametrizada, de tal manera que las constantes que afectan a la inteligencia artificial (como por ejemplo, cuanto riesgo correr en tiros y pases, etc.) sean fácilmente modificables. De este modo es posible crear un sistema de autoentrenamiento de la inteligencia artificial, modificando parámetros y realizando simulaciones hasta obtener mejoras en los resultados. 20 Anexo A Diseño En este anexo se ofrece información sobre el diseño del juego, sin entrar en detalles en la física y la inteligencia artificial, tratados en otros anexos. A.1. Introducción Todos los videojuegos, independientemente del tipo del mismo, suelen tener un diseño básico similar. Desde el punto de vista de la programación, el principal componente de todo juego es el bucle principal del juego. Este bucle se ejecuta constantemente mientras el juego está en funcionamiento y se encarga de, teniendo en cuenta la posible interacción del usuario, recalcular el nuevo estado del juego y representarlo gráficamente. El bucle principal en un juego suele tener un aspecto similar a este: while ( ! end_of_game ) { ge t _in p ut ( ) ; calculate_new_state (); draw_output (); } Además del bucle principal, prácticamente todo juego requiere un sistema de menús para configurar ciertos aspectos del mismo, así como algún tipo de sistema de pausa para poder parar la ejecución del juego temporalmente. Otro componente importante en un videojuego es el sistema de control del mismo y la gestión de dispositivos de entrada, como el ratón o el teclado, necesaria para este propósito. En este anexo trataremos el diseño general del juego, centrándonos en los tres aspectos recién mencionados y dejando otros más específicos de este juego en general, como la física o la inteligencia artificial, para posteriores anexos. 21 B. Física B.1. Uso de ODE en In Your Face si la posesión ha expirado: lanzar el evento de posesión expirada sino: modificar el estado del juego para que el jugador posea el balón •Colisión entre 2 jugadores si uno de los dos está parado: si el otro se está moviendo por encima de un límite: falta sino: si uno tiene la bola: si el otro se está moviendo por encima de un límite: falta 28 Anexo C Inteligencia artificial En este anexo se ofrecen detalles sobre el diseño de la inteligencia artificial para el juego. C.1. Introducción La inteligencia artificial es la ciencia que se encarga de estudiar la creación de máquinas inteligentes y, en especial, programas inteligentes. Podemos decir que un programa o un agente de un programa es inteligente si tiene la capacidad de estudiar su entorno y reaccionar de la manera correcta para lograr algunos objetivos de una manera similar a la que lo haría un ser humano. Cuando hablamos de diseñar una inteligencia artificial para un juego, estamos haciendo referencia al hecho de proveer al programa de los mecanismos suficientes para que pueda comportarse de una manera aparentemente inteligente. A continuación estudiaremos la arquitectura básica de la inteligencia artificial desarrollada y entraremos en detalle sobre las distintas técnicas utilizadas, como máquinas de estados, IA jerárquica y steering behaviours. También expondremos algunos de los problemas geométricos y físicos básicos encontrados en la implementación y como se han resuelto. 29 C. Inteligencia artificial C.2. Arquitectura básica de la inteligencia artificial C.2. Arquitectura básica de la inteligencia artificial La arquitectura básica de la IA está reflejada en la figura C.1. Figura C.1: Diagrama de alto nivel de la IA El gestor de eventos es el encargado de distribuir los eventos que se generan en los distintos puntos de la aplicación. Estos eventos llegan a las inteligencias artificiales de los equipos, las cuales, después de consultar el estado del resto de elementos del juego, establecen las acciones a ejecutar por los jugadores. 30 C. Inteligencia artificial C.3. Gestor de eventos C.3. Gestor de eventos La inteligencia artificial necesita obtener información de su entorno para poder calcular la mejor forma de actuar. Podemos intentar obtener esta información utilizando dos aproximaciones: encuesta y sistemas de eventos. El método de encuesta se limita a que el código de la IA busque la información adecuada en el momento que la necesita. Este método es adecuado en algunas situaciones como, por ejemplo, la evaluación de las probabilidades de éxito al decidir si realizar un pase a un compañero de equipo. Sin embargo, hay información para la que este método no es óptimo. Por ejemplo, no sería razonable que en cada ejecución de la IA debíeramos comprobar si tenemos la posesión del balón o no. En estos casos es más apropiado utilizar un sistema de eventos. En el ejemplo anterior, cuando un jugador nuevo se hace con el control de la bola, se lanza un evento GotBall que la IA recibe y es en ese único momento cuando la IA puede comprobar si ha habido un cambio de posesión o no. Mientras no llegue un evento de cambio de posesión, la IA puede seguir ejecutándose presumiendo que no ha habido tal cambio. En el proyecto se ha utilizado la aproximación del sistema de eventos, aunque la IA utiliza encuesta para obtener más información para saber como reaccionar correctamente a un evento. La arquitectura del sistema de eventos está reflejada en la figura C.2. Figura C.2: Diagrama del sistema de eventos Los eventos están definidos en su propio espacio de nombres, Event y representan todos los eventos del partido en los que la IA puede estar interesada. Cada evento puede incluir datos relevantes al mismo. A continuación se muestran algunos ejemplos de eventos: 31 C. Inteligencia artificial C.3. Gestor de eventos •MatchStart: se genera de manera artificial para comenzar el partido •Second: se genera cada segundo •GotBall: se genera cuando un jugador recibe el balón, incluye el jugador que lo ha recibido •FreedBall: se genera cuando un jugador suelta el balón, ya sea para pasarlo o realizar un tiro a canasta, e incluye el jugador que lo ha soltado •Input: se genera cuando un humano pulsa o suelta una de las teclas asociadas a un controlador, incluye la función de la tecla y si ha sido pulsada o soltada •FailedShot: se genera cuando un tiro a canasta falla, es decir, baja por debajo del nivel del aro sin entrar por el mismo •ActionFinished: se genera cuando un jugador completa la acción que tenía asignada, incluye el jugador que ha realizado la acción Como vemos, algunos eventos representan hechos reales del partido, mientras que otros son artificiales, como los de entrada de datos por parte de un jugador humano. Estos eventos se generan desde distintas partes de la aplicación y se envían al gestor de eventos (EventManager) utilizando el método postEvent. Éste encola los eventos recibidos para procesarlos en el bucle principal de la aplicación. Cualquier objeto del juego puede implementar la interfaz EventObserver, basada en el patrón de diseño Observer, para recibir notificaciones de eventos. Durante el procesado de eventos, el gestor envía por orden todos los eventos encolados a todos los observadores que se han registrado para ello. En la práctica el principal observador de eventos es la clase principal del partido, MatchView. Esta clase se encarga de procesar los eventos oportunos y redistribuir todos los eventos a los dos equipos. Existía la opción de que los equipos fueran también observadores, en lugar de distribuir los eventos desde el objeto del partido, pero de este modo podemos estar seguros de que la clase que representa al partido recibe los eventos antes que los equipos, pudiendo reaccionar a ellos en primer lugar. Cuando la clase equipo recibe un evento, ésta notifica a la IA de manera que pueda alterar las acciones de los jugadores basándose en este nuevo evento en caso de que sea necesario. 32 C. Inteligencia artificial C.4. IA jerárquica C.4. IA jerárquica A la hora de programar la inteligencia artificial del juego es necesario tener en cuenta desde las decisiones estratégicas de equipo (¿qué jugada utilizar?, ¿qué hacer si pierdo de 3 puntos y quedan 5 segundos?) hasta los detalles más obvios (no salirse del campo con el balón) pasando por decisiones personales de dificultad intermedia (¿con qué ángulo debo tirar a canasta?). Como se puede apreciar, los tipos de decisiones que ha de tomar la IA son muy diferentes entre sí, por lo que lo más aconsejable es tener una IA jerárquica, con diferentes capas que se ocupen de las distintas clases de decisiones. A continuación introduciremos cada una de estas capas, empezando por las de más bajo nivel. C.4.1. Acción básica y steering behaviours La acción básica y los steering behaviours representan la parte más básica del movimiento de los jugadores. Una acción básica es una estructura de datos capaz de representar una acción de bajo nivel que un jugador debe realizar. Estas acciones son: •Stand: permanecer parado •BasicMove: movimiento básico •BasicPass: pase •Turn: giro •Jump: salto •BasicShoot: tiro básico Además la acción básica contiene información sobre la dirección del tiro o pase y la posición en la que el jugador debe colocar sus brazos. Aunque en principio estas acciones básicas parecen suficiente para realizar los movimientos de los jugadores, tan pronto como se ejecuta una simulación nos encontramos con problemas obvios. Por ejemplo, tomemos el problema de jugadores chocando entre ellos, algo que ocurre con mucha frecuencia. Para solucionar esto con las acciones básicas, sería necesario comprobar manualmente de manera continua si estamos a punto de chocar con un jugador, y en ese caso modificar la acción de movimiento para evitar el choque, y después restaurar el destino original del jugador cuando ya no hay riesgo de colisión. Con esta solución creamos un nuevo problema, ya que es posible que al intentar evitar a un contrario, un jugador que controla el balón se salga del terreno de juego, por tanto sería necesario comprobar que la trayectoria establecida para evitar la colisión no sale del terreno de juego. Resulta evidente que es necesario otra capa para tratar estos problemas de movimiento de una manera más comoda. Esta capa adicional son los steering behaviours. 33 C. Inteligencia artificial C.4. IA jerárquica Los steering behaviours (comportamientos de dirección) son diferentes modos de comportamiento que un agente puede tener en cuanto a la dirección y velocidad de su movimiento. Ejemplos de estos comportamientos pueden ser ir a una posición determinada, evitar obstaculos o perseguir a otro agente. Combinando estos comportamientos simples se pueden obtener esquemas de movimiento complejos de una manera muy sencilla. De esta manera es posible asignar a los jugadores acciones estratégicas como seguir a un rival o ir a una posición determinada a la vez que mantiene el comportamiento básico, como evitar salirse del terreno de juego o minimizar los choques con otros jugadores. Como solución al problema comentado anteriormente, todos los jugadores tendrían siempre asignados los comportamientos de evitar choques y no salirse del terreno de juego. Cuando queremos que un jugador vaya a una posición determinada se le asigna un nuevo comportamiento para ir a determinada posición. En cada paso del juego, el jugador consultara todos los comportamientos y obtendrá la dirección que debe seguir como la composición de todos ellos. Si no hay riesgo de colisión o de salirse del campo, la dirección vendrá determinada únicamente por el comportamiento de moverse a una posición dada. Si por el contrario hay riesgo de colisión, el comportamiento de evitar colisiones modificará la dirección para evitar el choque con los otros jugadores. Existe una clase llamada SteeringManager que se encarga de gestionar varios comportamientos y generar el resultado final que determinará la dirección de un jugador. Esta es el sencillo método que realiza el cálculo: Ogre : : Vector3 SteeringManager : : v e l o c i t y ( ) { Ogre : : Vector3 vel = Ogre : : Vector3 : : ZERO; Ste e ri n g : : Base ∗s ; foreach ( s , mSteerings ) { vel += s−>v e l o c i t y ( ) ; } return vel ; } Algunos de los comportamientos implementados en el juego son: •Seek El comportamiento seek recibe como parámetro una posición destino que el jugador quiere alcanzar y en cada iteración devuelve la velocidad y dirección ideales para alcanzar ese punto. En la figura C.4.1 podemos ver la relación entre la dirección al destino y la velocidad normalizada. 34 C. Inteligencia artificial C.4. IA jerárquica Código: Ogre : : Vector3 Seek : : v e l o c i t y ( ) { Ogre : : Vector3 d e s i r e d V e l o c i t y ; / / i f we are c lo se enough to the d esi r e d point , stop i f ( pl ay er ()−> g e t P o s i t i o n ( ) . p os i ti on E qu al s ( mTarget , 0 . 0 5 ) ) { d e s i r e d V e l o c i t y = Ogre : : Vector3 : : ZERO; / / otherwise move towards i t }else { d e s i r e d V e l o c i t y = mTarget −play er ()−>getPosition (); desiredVelocity[1] = 0; d e s i r e d V e l o c i t y . normalise ( ) ; } return desiredVelocity ; } •Avoid El comportamiento avoid no recibe parámetros y en cada iteración busca el jugador más próximo y en caso de estar en nuestra trayectoria devuelve una velocidad y dirección apropiadas para evitar la colisión. En la figura C.4.1 podemos observar como se realiza el cálculo de la dirección para evitar colisoines. 35 C. Inteligencia artificial C.4. IA jerárquica Código: Ogre : : Vector3 Avoid : : v e l o c i t y ( ) { Ogre : : Vector3 d e s i r e d V e l o c i t y = Ogre : : Vector3 : : ZERO; Ogre : : Vector3 pos = pla ye r ()−>getPosition (); pos [ 1] = 0; MatchView ∗match = MatchState : : g e t S i n g l e t o n P t r ()−>matchView (); / / get c l o s e s t p la yer in a bounding box / / in the d i r e c t i o n the player i s moving PlayerView ∗cp = match−>getNearestCollidingPlayer(player ()); i f ( cp ) { / / get the matrix to change between a b sol u te / / coor di n ate s and c oord in a tes from the player ’ s / / point of view and i t s i n v ers e Ogre : : Matrix4 coord = player ()−>getCoordinateChangeMatrix (); Ogre : : Matrix4 inv = coord . in ver s e ( ) ; Ogre : : Vector3 np = coord ∗cp−>getPosition (); / / i f the opponent i s l e s s than a meter ahead of us i f ( np [2] < 1) { float dev = np [ 2 ] ; i f ( fabs ( dev ) < 0. 1 ) { i f ( dev > 0) { dev = 0 . 1 ; }else { dev = −0.1; } } / / c a l c u l a t e an avoiding d i r e c t i o n i n v e r s e l y p r o p o r t i o n a l / / to the d i s t a n c e in p la yer ’ s view c o o r d i n a te s Ogre : : Vector3 d i r e c t i o n d e s t (0 ,0 , −1/ dev ) ; / / transform the d i r e c t i o n to abs ol ute c oo rd in aa te s directiondest = inv ∗directiondest; Ogre : : Vector3 d i r e c t i o n = d i r e c t i o n d e s t −pos ; d e s i r e d V e l o c i t y += d i r e c t i o n ; } } return desiredVelocity ; } C.4.2. Acciones: Action::Base Las acciones representan la siguiente capa en la inteligencia artificial. Una acción representa una actividad de duración relativamente corta que un jugador puede realizar. A continuación se listan las acciones del juego: 36 C. Inteligencia artificial C.4. IA jerárquica •BlockShot: intentar realizar un tapón •Defend: defender a un jugador, siguiéndolo por el campo •GetBall: intentar coger el balón •InterceptBall: intentar interceptar un pase •Move: moverse en una determinada dirección •MoveTo: moverse a una determinada posición •Pass: pasar el balón a un compañero •Shoot: intentar un tiro a canasta •Steal: intentar robar el balón •Wait: no hacer nada Como se puede apreciar hay algunas acciones que ya se encontraban entre las acciones básicas, como la acción Pass. La diferencia entre ambas se encuentra en la inteligencia con la que cuenta cada una de ellas. La acción Pass sabe elegir la mejor manera de hacer un pase y puede no ser determinista, mientras que la acción básica BasicPass ya tiene determinados todos los parámetros del pase y se limita a realizarlo. Todas las acciones del juego heredan de la clase Action::Base. Esta clase, además de determinar la interfaz que deben cumplir el resto de acciones, proporciona funcionalidad genérica a todas ellas, que describimos a continuación: •Infraestructura básica Cada acción está asociada a un jugador, por lo que Action::Base proporciona métodos para establecer y obtener el jugador al que está asociado una determinada acción. Además cada acción es registrada en una tabla hash para poder obtener la acción a partir de su identificador. También se proporcionan las funciones para saber si una acción ha terminado y generar el evento apropiado. •Steering manager El steering manager se encarga de almacenar los diferentes comportamientos que está acción emplea para describir su movimiento. Para saber la dirección final que el jugador debe tomar, se evalúa cada uno de los diferentes comportamientos, sumando cada una de las direcciones que devuelven para obtener una dirección única. •Esperar un determinado tiempo void BaseAction : : waitTime ( double t ) Es posible indicar que la acción debe terminar una vez pasado un número determinado de segundos. 37 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard C.5. Inteligencia artificial AI::Standard La inteligencia artificial de equipo está basada en una máquina de estados. Los estados deben heredar de la clase abstracta TeamState::Base, que define la interfaz que éstos deben cumplir, listada a continuación: •vir t ual void e n t e r ( ) = 0; Método a ejecutar cuando se entra en este estado •vir t ual void e x i t ( ) = 0; Método a ejecutar cuando se sale de este estado •virtual QString n o t i f y ( const Event : : Base &event ) = 0; Notifica al estado sobre la llegada de un nuevo evento. La cadena devuelta indica el nuevo estado al que se debe cambiar. En caso de que no sea necesario un cambio de estado devolverá una cadena vacía. •virtual TeamPlay ∗getPla y ( ) = 0; Devuelve las acciones que deben realizar los jugadores según el estado actual del estado. •vir t ual bool hasChanged () = 0; Devuelve verdadero si ha habido cambios en las acciones que los jugadores deben ejecutar desde la última vez que se consultaron. Se pueden observar los estados básicos y sus transiciones por defecto en el diagrama C.5. 44 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard Figura C.5: Diagrama de estados básico de la IA Cuando se lanza la IA se establece automáticamente el estado inicial, BeforeMatch. A continuación la IA se limita a recibir eventos y notificar al estado actual. Si el estado determina que es necesario un cambio, la IA ejecuta el método exit() del estado actual, cambia al estado siguiente y ejecuta el método enter() de éste. El estado BeforeMatch se encarga de mover a los jugadores a las posiciones iniciales para el comienzo del partido. Cuando llega el evento MatchStart se pasa al estado FreeBall. Este estado es el que tienen ambos equipos cuando la bola no está en posesión de ninguno de ellos. En este estado se examina la posición del balón en el campo y la distancia al mismo del jugador más cercano de cada equipo, para determinar cual es la probabilidad de que el equipo consiga la posesión. Basándose en esta información las reacciones pueden ser las indicadas en la tabla C.1. 45 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard Probabilidad Posición balón Acción del equipo p >0.8 Cualquiera El jugador intenta coger la bola y el resto del equipo se lanza al ataque 0.8 >p >0.6 Zona de ataque El jugador intenta coger la bola y el resto del equipo se lanza al ataque 0.8 >p >0.6 Resto de zonas El jugador intenta coger la bola y el resto del equipo espera 0.4 >p >0.2 Cualquiera El jugador intenta coger la bola y el resto del equipo defiende 0.2 >p Cualquiera El equipo completo defiende Tabla C.1: Resumen de acciones de FreeBall Cuando un equipo consigue el balón pasa al estado Attack, mientras que el equipo contrario pasa al estado Defense. El propósito del estado Attack es conseguir llevar el balón hasta la posición de ataque. En primer lugar, si el jugador que tiene el control de balón no es el base, se le pasa el balón a éste, de manera que sea él el encargado de llevar el ataque. En este estado se incluye la lógica necesaria para no incurrir en un campo atrás, esperando al base si es necesario. Una vez se ha llegado a la posición de ataque se realiza una transición al estado TryToScore, cuyo objetivo es intentar conseguir una canasta. En el estado TryToScore el jugador que posee el balón realiza una estimación de las posibilidades de encestar que tiene, evaluando diversos parámetros, como la distancia hasta la canasta, el hecho de que haya algún jugador que pueda taponar cerca y la habilidad del jugador. Además también se tiene en cuenta el tiempo de posesión que queda, de tal modo que, según se aproxima el final de la posesión, la probabilidad de que el jugador decida tirar crece. Otro detalle a tener en cuenta durante el ataque es si nuestro lanzamiento va a ser de dos o tres puntos. Debido a la forma irregular del área de dos puntos no sería sencillo escribir una función para calcular si el jugador se encuentra en ella o no. La opción elegida para saber rápidamente el valor que tendría una canasta si un jugador lanza desde su posición actual, y también para poder realizar otras consultas similares necesarias por la inteligencia artificial como, por ejemplo, si un jugador está en la zona, ha sido usar un mapa de bits. Para permitir crear diferentes pistas de manera sencilla se creó un script en Ruby usando la biblioteca ImageMagick que dibuja tanto la imagen de la pista normal como este mapa de bits. A continuación se muestra parte del código, en el que se dibujan las líneas que delimitan los campos, los círculos centrales y las partes del circulo del área pequeña: #sidelines gc . r e c t a n g l e ( 0 ,0 , $ cour tlen gth , $courtwidt h ) #halfline gc . l i n e ( $h oriz_ ce nter ,0 , $horiz_c enter , $courtwidth ) # c e n t er c i r c l e s gc . c i r c l e ( $ho riz_cen ter , $ver t_ ce nt er , 46 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard $ho ri z_c en te r + c e n t e r s m a l l c i r c l e r a d i u s , $ v er t _c e nt e r ) gc . c i r c l e ( $ho riz_cen ter , $ver t_ ce nt er , $ho ri z_ ce nte r + c e n t e r c i r c l e r a d i u s , $ v e r t _c en t e r ) # . . . gc . push # draws the continuous c i r c l e in the key gc . c l i p _ p a t h ( ’ c on t _ ke y _c i rc l e_ p a th ’ ) gc . c i r c l e (579 , $v er t_ ce nter ,579 ,579+365) gc . pop gc . push gc . s t r o ke ( ’ white ’ ) gc . st r oke _ das h arr a y (41 ,36) # draws the dashed c i r c l e in the key gc . c l i p _ p a t h ( ’ das hed _ke y_c irc le_ pat h ’ ) gc . c i r c l e (579 , $v er t_ ce nter ,579 ,579+365) gc . pop El mapa de bits se carga de manera sencilla en un objecto de tipo Ogre::Image durante la construcción del objeto que representa la pista: mCourtBitmap . load ( " basketcourtmap . png " , Ogre : : ResourceGroupManager : :DEFAULT_RESOURCE_GROUP_NAME) ; Contamos con un método de utilidad para transformar entre las coordenadas de los jugadores en la pista y el pixel que representa esa posición en el bitmap: Ogre : : Vector3 CourtView : : courtToBitmap ( Ogre : : Vector3 pos ) { int width = mCourtBitmap . getWidth ( ) ; int he ig ht = mCourtBitmap . getHeight ( ) ; Ogre : : Vector3 bitPos ; bi tPos [0] = pos [0]∗100 + width / 2 ; bi tPos [2] = pos [2]∗100 + he ight / 2 ; return bitPos ; } Para comprobar si la posición de un jugador está en la zona de tres puntos tenemos el siguiente método: bool CourtView : : p os Is Thr ee Po int er ( Ogre : : Vector3 pos , CourtSide si de ) { i f ( ( sid e < 0) && ( pos [0 ] < 0)) { return true ; } i f ( ( sid e > 0) && ( pos [0 ] > 0)) { return true ; } Ogre : : Vector3 bitPos = courtToBitmap ( pos ) ; Ogre : : ColourValue c = mCourtBitmap . getColourAt ( ( int ) b itP os [ 0 ] , ( int) bi tP os [ 2 ] , 0 ) ; i f ( ( c . r < 0 .01 ) && ( c . g < 0 .0 1) && ( c . b < 0 . 0 1 ) ) { return true ; } return f a l s e ; } 47 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard Como vemos, el método comprueba en primer lugar si el jugador está en la mitad de la pista opuesta a donde debe encestar, en cuyo caso siempre será un tiro de tres [2]. En caso contrario, se transforma su posición en la pista al pixel adecuado en el mapa de bits y se obtiene el color en ese punto. A continuación comprobamos si el color de la zona es negro (color asignado a la zona de tres puntos como se puede ver en el mapa de bits mostrado en la figura C.6) y devolvemos el valor adecuado dependiendo del color. Figura C.6: Mapa de bits para diferenciar zonas de la pista En caso de que no se considere apropiado realizar un tiro a canasta, el jugador que controla el balón estudiara la posibilidad de realizar un pase a un jugador que se encuentre en una mejor posición para tirar a canasta. El resto de jugadores tiene diversas posiciones a las que se van desplazando de manera aleatoria con el objetivo de facilitar un pase sencillo al poseedor del balón. En el estado Defense cada jugador realiza un marcaje personal al jugador correspondiente del equipo atacante, utilizando la acción DefendPlayer para ello. Cuando el equipo contrario realiza un pase, se estudia la posibilidad de interceptarlo y, en caso de que parezca posible, el jugador con más posibilidades intenta alcanzar la bola. 48 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard Figura C.7: Cálculo de la posibilidad de intercepción de pase Para la intercepción del pase, como se puede apreciar en la figura C.7, en primer lugar se descartan los jugadores que no se encuentran entre los jugadores involucrados en el pase. Para los jugadores restantes, se calcula la distancia desde su posición hasta el punto más cercano a ellos en la trayectoria de la bola. Además se calcula el tiempo que a la bola le costará llegar desde las manos del jugador a esos posibles puntos de intercepción. A continuación se incluye la función que realiza los cálculos geométricos para obtener toda la información necesaría sobre la intercepción: Geom : : I n t e r c e p t i o n I n f o Geom : : p a s s I n t e r c e p t i o n I n f o ( Ogre : : Vector3 ballPos , / / i n i t i a l p o s i t i o n of the b a l l Ogre : : Vector3 ballDir , / / d i r e c t i o n of the b a l l PlayerView ∗r ece ive r , / / p o s i t i o n of the p lay er / / who w i l l r e ce i v e the b a l l 49 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard TeamView ∗interTeam / / team t h a t w i ll t r y to / / i n t e r c e p t the b a l l ) { I n t e r c e p t i o n I n f o r e s u l t ; / / we are not i n t e r e s t e d in the v e r t i c a l speed of the b a l l f or / / i n t e r c e p t i o n purposes b a l l D i r [ 1] = 0; Ogre : : Vector3 recPos = receiver −>node()−>getPosition (); / / gat he r a l l in for mat ion about the p o s i t i o n of t he / / de fe ns iv e p l a y e r s wrt the b a l l and the r e c e i v i n g p l ay er / / d i s ca r d the p l aye r s which are not in the zone / / between the b a l l and the r e c e i v i n g p l ay er / / b a l l D i r i s the normal of both of t he l i m i t i n g p la nes / / we a ls o have a p oi nt f or the f i r s t plane ( ba llPos ) and / / another one fo r the second one ( recPos ) / / a plane i s define d as A, B,C,D (A,B,C being the normal ve cto r / / and D d e fi ni ng the p o s i t i o n along the normal ) / / the d i s t a n c e from a p oi nt to a plane i s x∗A+y∗B+zC−D, where / / x , y , z are the c o o rdi n a t e s of the po in t / / normalise b a l l D i r to get a normal v e cto r fo r both plan es Ogre : : Vector3 n BallDir = b a l l D i r ; nBallDir . normalise ( ) ; r e s u l t . b a l l D i r = nBallDir ; / / get D f or the b a l l plane and fo r the r e c e i v e r plane double bpd = nBallDir . dotProduct ( ba ll Pos ) ; double rpd = nBallDir . dotProduct ( recPos ) ; / / get the normal of the plane in which the b a l l i s moving and D / / for t h a t plane Ogre : : Vector3 normal = Ogre : : Quaternion ( Ogre : : Radian ( Ogre : : Degree ( 9 0 ) ) , Ogre : : Vector3 : : UNIT_Y) ∗nBallDir ; / / as the plane we ’ re i n t e r e s t e d in i s the one who has b allPos on / / i t we know t h a t x∗A+y∗B+zC−D equals 0 , and thus we can get D normal . normalise ( ) ; double bdd = normal . dotProduct ( ballPo s ) ; / / now we have a l l the in fo rmati on r eg arding the planes and can / / check which p la ye rs are a c t u a l l y between them 50 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard for (int i =0; i <5; i ++) { PlayerView ∗p = interTeam −>playerView ( i ) ; double dotProduct = nBall Di r . dotPro duct ( p−>node()−>getPosition ()); / / d i s t a n c e to the b a l l plane double b al l Pl an eD i st an ce = dotProduct −bpd ; / / d i s t a n c e to the r e c e i v e r pl ane double r e c e i v e r P l a n e D i s t a n c e = dotProduct −rpd ; i f ( ( b a l l P l a n e D i st a n c e > 0) && ( r e c e i v e r P l a n e D i s t a n c e < 0 )) { r e s u l t . p l aye r s [ i ] . betweenPlanes = true ; receiverPlaneDistance = −receiverPlaneDistance; / / now we know t h i s p la yer i s between the planes and we / / can c a l c u l a t e the d i s t a n c e t o t he pl ane of the b a l l // movement double ballDirectionDistance = normal . d otPro duct ( p−>node()−>getPosition())−bdd ; / / c a l c u l a t e the time i t w il l take the b a l l to reach the / / p o s it i on in which the p layer should i n t e r c e p t i t double t imeLe ft = b a l l Pl a n e Di s t an c e / b a l l D i r . le ngt h ( ) ; double distanceLeft = fabs(ballDirectionDistance) − timeLeft ∗playerSpeed; / / a d i s t a n c e below 0 means t h a t the p l aye r can a c t u a l l y / / reach the i n t e r c e p t i n g p os it i o n . note t h a t an / / i n t e r c e p t i o n i s s t i l l p o s s i b l e even i f d i s t a n c e L e f t i s / / g r e a t e r than 0 , as the pl aye r w i ll use the arms to t r y / / to reach the b a l l i f ( d i s t a n c e L e f t < 0) { d i s t a n c e L e f t = 0; } r e s u l t . p l aye r s [ i ] . b a l lPl a n e D ist a n c e = ba l l Pla n e D i sta n c e ; r e s u l t . p l ay e rs [ i ] . d i s t a n c e L e f t = d i s t a n c e L e f t ; r e s u l t . p l aye r s [ i ] . timeLeft = timeLeft ; }else { r e s u l t . p l aye r s [ i ] . betweenPlanes = false; } } / / r e t ur n the r e s u l t s from a l l the c a l c u l a t i o n s to l e t the AI / / decide i f an i n t e r c e p t i o n should be attemped and which pl ay er / / should t r y to perform i t return result ; } Una vez que tenemos todos estos datos es fácil calcular cual de los jugadores tiene más posi- 51 C. Inteligencia artificial C.5. Inteligencia artificial AI::Standard bilidades de alcanzar el punto de intersección antes de que la bola pase por él. En el caso del ejemplo, aunque el primer jugador se encuentra más cerca de la trayectoria de la bola, el segundo tiene más del doble de tiempo para recorrer la distancia que le separa de ella, por lo que tiene más probabilidades de interceptar el pase. Además de estar pendiente de los intentos de pase, en el estado de defensa la IA también intenta realizar tapones ante los intentos de tiro. Mediante un algoritmo sencillo, donde la variable más influyente es la distancia al jugador que realiza el tiro, se decide cual de los jugadores es el más idoneo para intentar realizar el tapón. El estado WaitAfterScore sólo se utiliza para esperar unos segundos tras una canasta antes de proseguir el juego. El estado ThrowIn es el que guía las acciones de un equipo cuando tiene que volver a poner el balón en juego tras una canasta, una falta o un fuera de banda. 52 C. Inteligencia artificial C.6. Scripting de la inteligencia artificial AI::Standard C.6. Scripting de la inteligencia artificial AI::Standard Una de las claves para la creación de una comunidad de contribuidores activa alrededor de un juego libre es que la barrera de dificultad para contribuir sea mínima. El proceso de descargar todas las bibliotecas, realizar cambios en el juego y compilarlo no es trivial, por lo que, para proporcionar una manera sencilla de modificar el comportamiento de la inteligencia artificial, se ha creado una interfaz de scripting. Mediante esta interfaz se puede cambiar el comportamiento de los estados de la IA, así como añadir nuevos estados. C.6.1. Elección de un lenguaje y plataforma de scripting Antes de implementar la interfaz de scripting se estudiaron los siguientes lenguajes de scripting con sus mecanismos asociados para exponer los objetos relacionados con la IA: •Boost.Python. Python es un lenguaje de programación de propósito general. Existe una biblioteca del proyecto Boost llamada Boost.Python que permite interoperar fácilmente entre Python y C++. •LuaBind. Lua es un lenguaje de programación diseñado específicamente para extender otras aplicaciones con una interfaz de scripting. LuaBind es una biblioteca similar a Boost.Python, y de hecho inspirada en ella, que permite integrar fácilmente Lua con C++. •QtScript. QtScript es un lenguaje de scripting basado en el estándar ECMAScript (como, por ejemplo, JavaScript) incluido en la biblioteca Qt. La principal ventaja de Boost.Python sobre el resto es que el lenguaje de programación subyacente es mucho más potente, contando con un gran número de bibliotecas de utilidades. Sin embargo, la ejecución de la IA debe ser muy rápida, por lo que los estados implementados no deberían ser demasiado sofisticados, y está ventaja no resulta por tanto demasiado importante. Tras evaluar las tres plataformas, QtScript fue la elegida, en primer lugar por la facilidad de integración con el código existente, así como por el hecho de que el lenguaje QtScript, muy similar a JavaScript, es mucho más sencillo que los otros dos y, debido a su popularidad en la red, conocido por una mayor cantidad de posibles contribuidores. C.6.2. QtScript QtScript es un motor de scripting basado en el estándar ECMAScript incluido en la biblioteca Qt desde la versión 4. A continuación se muestra un ejemplo básico de ejecución de código ECMAScript con QtScript: QScriptEngine engine ; qDebug ( ) << "1 + 2 = " << engine . ev a lua t e ( "1 + 2" ) . toNumber ( ) ; 53 C. Inteligencia artificial C.7. Métodos de depuración y mejora de la IA C.7. Métodos de depuración y mejora de la IA Una vez tenemos una versión inicial de la inteligencia artificial, es importante ser capaz de depurarla cuando aparecen problemas, así como de introducir mejoras en ella. Para esto se utilizan tres métodos distintos. En primer lugar, utilizando log4cpp, se ha creado un sistema de registro de información desde la aplicación. Este método está fundamentalmente orientado a la depuración de problemas. La información producida puede ser muy verbosa por lo que el sistema se ha organizado de manera jerárquica, haciendo sencillo activar y desactivar el registro de subsistemas del juego a distintos niveles. Esto permite obtener información de ejecución con gran cantidad de detalle de la parte concreta que queramos depurar. Este es un ejemplo de uso del sistema de registros en el gestor de eventos, en el que sólo se registrará el evento en caso de que la categoría eventmanager esté activada: log4cpp : : CategoryStream debug = log4cpp : : Category : : g e t I n s t a n c e ( " eventmanager " ) . debugStream ( ) ; debug << " Posting event " << event −>p r i n t a b l e ( ) ; En segundo lugar, existe un sistema para mostrar en tiempo real información sobre la IA para cada jugador. Este sistema muestra etiquetas sobre los jugadores en el juego, incluyendo diferente información sobre el estado de la inteligencia artificial. Una de las opciones es mostrar la acción que el jugador está realizando en ese momento, opcionalmente incluyendo los parámetros de la misma. Por ejemplo, si un jugador está moviéndose a una determinada posición, la información mostrada será: Player 3 Moving to (3,8) Esta opción se muestra en la figura C.8. 60 C. Inteligencia artificial C.7. Métodos de depuración y mejora de la IA Figura C.8: Etiquetas de depuración de la IA Las opciones adicionales pueden mostrar si la acción está terminada y si hay otras acciones que dependen de está acción. Otra información muy interesante que podemos obtener con este método son las probabilidades de éxito estimadas si el jugador lanza a canasta desde su posición actual, así como las posibilidades de éxito si realiza un pase a otros jugadores. Mediante esta característica es fácil apreciar si los cálculos de probabilidades se aproximan a la realidad, así como ver como de adecuado es un determinado límite impuesto a los tiros o a los pases. La información ofrecida en estas etiquetas es fácilmente ampliable si es necesario. El tercer método consiste en escenarios de prueba. Este método puede utilizarse de dos maneras diferentes. En primer lugar, podemos utilizarlo para reproducir fácilmente una situación que muestra un problema con la IA. Sin una manera de establecer escenarios de prueba repetibles es muy difícil depurar problemas que puede que se reproduzcan de manera muy poco frecuente en circunstancias muy especiales. 61 C. Inteligencia artificial C.7. Métodos de depuración y mejora de la IA Mediante un escenario de prueba podemos crear la situación concreta que causa el problema para después, probablemente usando el sistema de registros o las etiquetas de depuración, diagnosticar el problema. Una vez resuelta podemos ejecutar de nuevo el mismo escenario de prueba y comprobar que la IA se comporta como esperamos. El segundo caso de uso es para la realización de posibles mejoras en la IA. Imaginemos que vamos a hacer un cambio a una determinada estrategia de ataque. Podemos ejecutar un escenario de prueba en el que se utilice esa estrategia un alto número de veces y ver cual es el porcentaje de éxito de la jugada. A continuación hacemos nuestro cambio y volvemos a ejecutar el mismo escenario, observando si la probabilidad de éxito ha subido o no. Los escenarios se definen en ficheros XML y permiten establecer la mayoría de paramétros del partido, como los equipos que juegan, la posición de los jugadores, quien controla la pelota, la IA a utiliar o el estado en el que se encuentran las IAs de ambos equipos. Para determinar si la prueba ha tenido éxito se utiliza el sistema de eventos. Podemos establecer un evento que determinará si la prueba ha sido un éxito, como por ejemplo, la consecución de una canasta. Así mismo, podemos configurar un evento que hará que el resultado de la prueba sea fallo. Además, el sistema de pruebas también soporta límites de tiempo, de tal manera que una prueba se declare automáticamente éxito o fracaso una vez pasado un determinado tiempo. A continuación podemos ver un ejemplo de escenario de prueba: < t e s t > <match > <matchteam home=" l o c a l " s ide =" l e f t " name="Memphis G r i z z l i e s " / > <matchteam home=" v i s i t o r " s id e =" r i g h t " name=" Toronto Raptors " / > </ match > <team id="0" a i=" t es t1 _0 " i n i t i a l s t a t e =" t r y t o s c o r e "> < p la ye r index ="0"> < b a l l / > <pos x="4" y="0" / > </ player > </ team > <team id="1" a i =" t e s t1_ 1 "> < p la ye r index ="0"> <pos x="6" y="0" / > </ player > </ team > <s uccess event ="5" / > <timeout seconds=" 10 " r e s u l t =" f a i l u r e " / > </ t e s t > En este caso simplemente determinamos las posiciones de un jugador de cada equipo, asignamos la posición de la bola a uno de ellos y decidimos la IA que van a utilizar los equipos. Además, establecemos como estado inicial para el primer equipo TryToScore. El evento número 5 es Score por lo que consideramos el test como un éxito si se registra una canasta en los primeros diez segundos y como un fracaso en caso contrario. 62 C. Inteligencia artificial C.7. Métodos de depuración y mejora de la IA Para ejecutar una prueba, invocamos a inyourface de la siguiente manera: . / inyour fa ce −gametype t e s t −t e s t t e s t −shoot . xml La ejecución del simulador en este caso es totalmente automática y registrará al finalizar el resultado de la prueba. 63 Anexo D Licencia A continuación se adjunta el texto de la licencia GNU General Public License, bajo la cual se distribuye el software del presente proyecto. GNU GENERAL PUBLIC LICENSE Version 2, June 1991 Copyright (C) 1989, 1991 Free Software Foundation, Inc. 675 Mass Ave, Cambridge, MA 02139, USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. Preamble The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software—to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation’s software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too. When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things. To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it. 64 D. Licencia For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights. We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software. Also, for each author’s protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors’ reputations. Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone’s free use or not licensed at all. The precise terms and conditions for copying, distribution and modification follow. Terms and conditions for copying, distribution and modification 0. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The “Program”, below, refers to any such program or work, and a “work based on the Program” means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term “modification”.) Each licensee is addressed as “you”. Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does. 1. You may copy and distribute verbatim copies of the Program’s source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program. You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee. 2. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions: 65 D. Licencia (a) You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change. (b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. (c) If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: if the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.) These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it. Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program. In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License. 3. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following: (a) Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, (b) Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, (c) Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.) 66 D. Licencia The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable. If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code. 4. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 5. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it. 6. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients’ exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License. 7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program. If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances. It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose 67 D. Licencia of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice. This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License. 8. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License. 9. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and “any later version”, you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation. 10. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally. NO WARRANTY 11. Because the Program is licensed free of charge, there is no warranty for the Program, to the extent permitted by applicable law. except when otherwise stated in writing the copyright holders and/or other parties provide the program “as is” without warranty of any kind, either expressed or implied, including, but not limited to, the implied warranties of merchantability and fitness for a particular purpose. The entire risk as to the quality and performance of the Program is with you. Should the Program prove defective, you assume the cost of all necessary servicing, repair or correction. 12. In no event unless required by applicable law or agreed to in writing will any copyright holder, or any other party who may modify and/or redistribute the program as permitted above, be liable to you for damages, including any general, special, incidental or consequential damages arising out of the use or inability to use the 68 D. Licencia program (including but not limited to loss of data or data being rendered inaccurate or losses sustained by you or third parties or a failure of the Program to operate with any other programs), even if such holder or other party has been advised of the possibility of such damages. END OF TERMS AND CONDITIONS 69