Story Transcript
Grado en Ingenier´ıa Inform´ atica
TRABAJO FIN DE GRADO
´ BUSQUEDA DE CAMINOS EN MAPAS DE VIDEOJUEGOS Desarrollo de t´ ecnicas de b´ usqueda de caminos con preprocesamiento para mapas de videojuegos
Autor:
´ Alvaro Parra de Miguel
Tutor:
Carlos Linares L´ opez
22 de junio de 2015 Universidad Carlos III de Madrid
“Hell, it’s about time.”
Tychus Findlay
i
Agradecimientos Quiero mostrar mi agradecimiento a todas aquellas personas que de una forma u otra me han ayudado a realizar este proyecto. ´ A Carlos Linares L´ opez y Alvaro Torralba Arias de Reyna, porque sin su ayuda y dedicaci´ on inestimables este proyecto no hubera sido posible. A toda mi familia y en especial a mis padres, por todo el apoyo y cari˜ no que siempre me han brindado. A mi novia Sayuri, por llenar de ilusi´on mi vida. A todos los profesores que me han impartido clase a lo largo de estos a˜ nos, por transmitirme sus conocimientos y ayudar a formarme como persona. A todos mis jefes y compa˜ neros con los que he tenido el placer y la suerte de trabajar. Y a todos mis amigos a los que tanto quiero y con los he compartido tan gratos momentos.
ii
´Indice Agradecimientos
II
´ Indice
III
´ Indice de Figuras
VI
´ Indice de Tablas
VII
1. Introducci´ on
1
2. Estado de la Cuesti´ on 2.1. Videojuegos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. Industria del videojuego . . . . . . . . . . . . . . . . . . . 2.1.1.1. El inicio de la industria . . . . . . . . . . . . . . 2.1.1.2. La crisis del 83 . . . . . . . . . . . . . . . . . . . 2.1.1.3. Evoluci´ on hasta nuestros d´ıas y situaci´on actual 2.2. G´eneros en los videojuegos . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Acci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2. Aventuras . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3. RPG (role-playing game) . . . . . . . . . . . . . . . . . . 2.2.4. Estrategia . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.5. Simulaci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.6. Casual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Inteligencia Artificial en videojuegos . . . . . . . . . . . . . . . . 2.3.1. T´ecnicas de IA aplicables en los videojuegos . . . . . . . . 2.3.1.1. Pathfinding o b´ usqueda de caminos . . . . . . . 2.3.1.2. M´ aquinas de estado . . . . . . . . . . . . . . . . 2.3.1.3. Aprendizaje por refuerzo . . . . . . . . . . . . . 2.3.1.4. L´ ogica difusa o fuzzy logic . . . . . . . . . . . . 2.3.2. Metas a conquistar . . . . . . . . . . . . . . . . . . . . . . 2.3.2.1. Pathfinding o b´ usqueda de caminos . . . . . . . 2.3.2.2. Conversaciones . . . . . . . . . . . . . . . . . . . 2.3.2.3. Historias din´amicas . . . . . . . . . . . . . . . . 2.3.2.4. Modelar el comportamiento de los jugadores . . 2.3.2.5. Relaciones sociales . . . . . . . . . . . . . . . . . 2.3.2.6. Escalabilidad . . . . . . . . . . . . . . . . . . . . 2.4. Competici´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 3 3 6 8 10 10 11 11 12 12 12 13 13 13 13 14 14 14 14 14 15 15 15 15 16
´ Indice
´ Alvaro Parra de Miguel
2.4.1. Definici´ on del problema . . . . . . . . . . . . . . 2.5. Pathfinding . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1. Grafo . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1.1. Waypoint o puntos de referencia . . . . 2.5.1.2. Navigation mesh o malla de navegaci´on 2.5.1.3. Voronoi . . . . . . . . . . . . . . . . . . 2.5.1.4. Quadtree o ´arbol cuaternario . . . . . . 2.5.2. Heur´ıstica . . . . . . . . . . . . . . . . . . . . . . 2.5.2.1. Distancia Manhattan . . . . . . . . . . 2.5.2.2. Distancia euclidiana . . . . . . . . . . . 2.5.2.3. Distancia diagonal . . . . . . . . . . . . 2.5.3. Algoritmo de b´ usqueda . . . . . . . . . . . . . . 2.5.3.1. Dijkstra . . . . . . . . . . . . . . . . . . 2.5.3.2. A* . . . . . . . . . . . . . . . . . . . . . 2.5.4. Trabajos previos . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
16 19 19 20 20 21 21 22 23 23 24 24 24 25 26
3. Objetivos
27
4. Desarrollo 4.1. An´ alisis del sistema . . . . . . . . . . . 4.1.1. Requisitos del sistema . . . . . 4.1.2. Casos de uso . . . . . . . . . . 4.2. Dise˜ no del sistema . . . . . . . . . . . 4.2.1. Diagramas de clases . . . . . . 4.2.2. Diagramas de secuencia . . . . 4.3. Pruebas de software . . . . . . . . . . 4.4. Algoritmo de b´ usqueda . . . . . . . . . 4.4.1. Regiones convexas . . . . . . . 4.4.2. Algoritmo para dividir el mapa 4.4.3. B´ usqueda de los caminos . . . 4.4.3.1. Centroides . . . . . . 4.4.3.2. Portales . . . . . . . . 4.4.3.3. Versi´ on final . . . . .
. . . . . . . . . . . . . .
28 28 28 31 34 34 36 37 39 41 42 46 47 47 48
5. Evaluaci´ on 5.1. N´ umero de regiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Comparaci´ on con el caso base . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Competici´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49 50 51 52
6. Conclusiones 6.1. Objetivos . . . . . . . . . . . . . . . . . . . 6.1.1. Desarrollar un agente de pathfinding 6.1.2. Reducir el espacio de b´ usqueda . . . 6.1.3. Algoritmo de b´ usqueda . . . . . . . 6.1.4. Entorno gr´ afico de pruebas . . . . . 6.2. Conclusiones finales . . . . . . . . . . . . .
54 54 54 54 54 55 55
7. L´ıneas Futuras
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . para la GPPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . .
. . . . . .
. . . . . .
56 iv
´ Indice 8. Planificaci´ on y Presupuesto 8.1. Planificaci´ on . . . . . . . . . 8.1.1. Planificaci´ on estimada 8.1.2. Planificaci´ on real . . . 8.2. Hardware y software usado . 8.2.1. Hardware . . . . . . . 8.2.2. Software . . . . . . . . 8.3. An´ alisis econ´ omico . . . . . . 8.3.1. Recursos humanos . . 8.3.2. Recursos de hardware 8.3.3. Resumen . . . . . . .
´ Alvaro Parra de Miguel
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
Bibliograf´ıa
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
57 57 58 58 59 59 59 60 60 61 61
62
v
´Indice de Figuras 2.1. Recreativa Pong de Atari . . . . . 2.2. Videoconsola Atari Pong . . . . . . 2.3. Videoconsola Magnavox Odyssey . 2.4. Nintendo Entertainment System . 2.5. Evoluci´ on de las videoconsolas . . 2.6. Tipos de mapas . . . . . . . . . . . 2.7. Movimientos permitidos . . . . . . 2.8. Representaci´ on de un mapa con un 2.9. Navigation mesh . . . . . . . . . . 2.10. Regiones de Voronoi . . . . . . . . 2.11. Quadtree . . . . . . . . . . . . . . 2.12. Distancia Manhattan . . . . . . . . 2.13. Distancia euclidiana . . . . . . . . 2.14. Distancia diagonal . . . . . . . . . 2.15. Algoritmo Dijkstra . . . . . . . . . 2.16. Algoritmo A* . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . grafo . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
4 5 5 7 8 17 18 19 20 21 22 23 23 24 25 26
4.1. Diagrama de casos de uso . . . . . . . . . . . . . . . . . . 4.2. Diagrama de clases de la interfaz gr´afica de pruebas . . . 4.3. Diagrama de clases del agente . . . . . . . . . . . . . . . . 4.4. Diagrama de secuencia del preprocesamiento . . . . . . . 4.5. Diagrama de secuencia de la b´ usqueda . . . . . . . . . . . 4.6. Interfaz gr´ afica . . . . . . . . . . . . . . . . . . . . . . . . 4.7. Representaci´ on de un mapa con un grafo . . . . . . . . . . 4.8. Regiones convexas . . . . . . . . . . . . . . . . . . . . . . 4.9. Regiones c´ oncavas . . . . . . . . . . . . . . . . . . . . . . 4.10. Comparaci´ on entre regiones convexas y regiones c´oncavas 4.11. Diagram de flujo para generar regiones . . . . . . . . . . . 4.12. Mapa de tipo videojuego dividido en 128 regiones . . . . . 4.13. Mapa de tipo laberinto dividido en 128 regiones . . . . . . 4.14. Mapa de tipo aleatorio dividido en 128 regiones . . . . . . 4.15. Mapa de tipo habitaciones dividido en 128 regiones . . . . 4.16. Uso de centroides . . . . . . . . . . . . . . . . . . . . . . . 4.17. Uso de portales . . . . . . . . . . . . . . . . . . . . . . . . 4.18. Comparativa entre Dijkstra y A* . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
32 34 35 36 37 38 39 41 41 42 43 44 44 45 45 47 47 48
8.1. Diagrama de Gantt - Planificaci´on estimada . . . . . . . . . . . . . . . . . . 8.2. Diagrama de Gantt - Planificaci´on real . . . . . . . . . . . . . . . . . . . . .
58 59
vi
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
´Indice de Tablas 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7.
Requisito AGE-F-01 Preprocesamiento de mapas . . . . . . . . . . . . . Requisito AGE-F-02 Almacenar informaci´on . . . . . . . . . . . . . . . . Requisito AGE-F-03 Cargar informaci´on . . . . . . . . . . . . . . . . . . Requisito AGE-F-04 Buscar caminos . . . . . . . . . . . . . . . . . . . . Requisito AGE-NF-01 Dimensiones de los mapas . . . . . . . . . . . . . Requisito AGE-NF-02 L´ımite de tiempo en la fase de preprocesamiento Requisito AGE-NF-03 L´ımite de tama˜ no del fichero resultante de la fase preprocesamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8. Requisito AGE-NF-04 L´ımite de hilos en la fase de preprocesamiento . . 4.9. Requisito AGE-NF-05 L´ımite de memoria en la fase de b´ usqueda . . . . 4.10. Requisito AGE-NF-06 L´ımite de hilos en la fase de b´ usqueda . . . . . . 4.11. Requisito AGE-NF-07 Prohibidas las comunicaciones . . . . . . . . . . . 4.12. Requisito GRA-F-01 Representar adecuadamente el estado del mapa . . 4.13. Requisito GRA-NF-01 Dimensiones de los mapas . . . . . . . . . . . . . 4.14. Caso de Uso CU01 Preprocesar mapa . . . . . . . . . . . . . . . . . . . 4.15. Caso de Uso CU02 Preparar la b´ usqueda . . . . . . . . . . . . . . . . . . 4.16. Caso de Uso CU03 Realizar la b´ usqueda . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . de . . . . . . . . . . . . . . . . . . . .
29 29 29 29 30 30
5.1. 5.2. 5.3. 5.4. 5.5. 5.6. 5.7.
Experimentos con diferentes regiones . . . . . . Comparaci´ on del agente con el caso base . . . . Resultados competici´ on - Map Set: All . . . . . Resultados competici´ on - Map Set: Game Maps Resultados competici´ on - Map Set: Mazes . . . Resultados competici´ on - Map Set: Random . . Resultados competici´ on - Map Set: Rooms . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
50 51 52 52 52 53 53
8.1. 8.2. 8.3. 8.4. 8.5. 8.6. 8.7. 8.8.
Planificaci´ on estimada . . . . Planificaci´ on real . . . . . . . Recursos humanos estimados Recursos humanos reales . . . Recursos hardware estimados Recursos hardware reales . . Coste total estimado . . . . . Coste total real . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
58 58 60 60 61 61 61 61
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
vii
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
30 30 30 30 31 31 31 32 33 33
Cap´ıtulo 1
Introducci´ on Hoy en d´ıa el pathfining o b´ usqueda de caminos es un problema muy importante que aplica a dominios tales como el de la rob´otica o el de los videojuegos. Aunque es conocido que el problema puede resolverse en tiempo polinomial en el tama˜ no del grafo, este planteamiento no resulta viable para los sistemas que carecen de los recursos de tiempo y memoria necesarios. Esta problem´ atica a˜ nadida hace necesario el estudio de nuevas t´ecnicas que tengan en cuenta dichas restricciones. El crecimiento de la industria de la rob´otica y de los videojuegos ha impulsado la investigaci´on en esta ´ area. Con el fin construir un foro donde poder compartir las investigaciones realizadas en la materia, investigadores de diveras universidades han organizado una competici´ on donde poder comparar y discutir las diversas alternativas en las que est´ an investigando. A lo largo de este proyecto se construye un agente que particip´o en dicha competici´on para resolver el problema de pathfinding teniendo en cuenta extrictas restricciones de tiempo y memoria. Los resultados obtenidos fueron muy satisfactorios porque acab´o siendo declarado como uno de los ganadores de la edici´on de 2012 y ha seguido siendo competitivo en las subsiguientes ediciones. En el resto de cap´ıtulos de la memoria se desgranan los pasos que se han ido dando para la construcci´ on de dicho agente. Estos est´an organizados de la siguiente manera:
- Cap´ıtulo 2. Estado de la Cuesti´ on: En este cap´ıtulo se tratan los componentes que conforman el marco del proyecto. Se habla de la industria de los videojuegos y de su relaci´ on con la Inteligencia Artificial. Explicamos en qu´e consiste la Grid-Based Path Planning Competition y cu´ales son sus reglas. Y terminamos revisando algunas
1
´ Alvaro Parra de Miguel
Cap´ıtulo 1. Introducci´ on
t´ecnicas de pathfindig desde las que podemos partir para solucionar el problema que se nos plantea. - Cap´ıtulo 3. Objetivos: En este apartado damos a conocer cu´al es la motivaci´on de este proyecto y los objetivos que nos planteamos cumplir. - Cap´ıtulo 4. Desarrollo: En este cap´ıtulo exponemos el trabajo realizado, teniendo en cuenta las distintas fases del desarrollo de software: an´alisis, dise˜ no e implementaci´ on. - Cap´ıtulo 5. Evaluaci´ on: En este apartado evaluamos el funcionamiento de nuetro agente y los resultados obtenidos en la Grid-Based Path Planning Competition de 2012. - Cap´ıtulo 6. Conclusiones: En este cap´ıtulo se comprueba si se han alcanzado los objetivos marcados al principio de este proyecto y se incluyen las conclusiones que se han obtenido sobre los resultados. - Cap´ıtulo 7. L´ıneas Futuras: En este apartado se contemplan las posibles l´ıneas futuras que podr´ıan surgir a partir de este proyecto y algunas propuestas para mejorar el funcionamiento del agente. - Cap´ıtulo 8. Planificaci´ on y Presupuesto: En este cap´ıtulo se detalla la planificaci´ on y el presupuesto del proyecto.
2
Cap´ıtulo 2
Estado de la Cuesti´ on En este cap´ıtulo se abordan los distintos elementos que definen el marco del proyecto. Se trata de enfocar el problema desde varios puntos de vista, como pueden ser el social, el econ´omico, el tecnol´ ogico o el t´ecnico.
2.1.
Videojuegos
Los videojuegos se han consolidado como una de las principales industrias del arte y el entretenimiento, actuando como un motor cultural y econ´omico de la sociedad. La relaci´ on entre la Inteligencia Artificial y los videojuegos es doble. Por un lado los videojuegos son un mercado en constante evoluci´ on que halla en las t´ecnicas de Inteligencia Artificial un factor diferenciador. Por otro lado los videojuegos suponen una fuente inagotable de nuevos problemas que ponen a prueba los l´ımites de la Inteligencia Artificial, favoreciendo la b´ usqueda de nuevas soluciones.
2.1.1. 2.1.1.1.
Industria del videojuego El inicio de la industria
El primer gran ´exito comercial de la industria de los videojuegos fue la m´aquina recreativa Pong (Atari, Inc.1 , 1972). Parte del ´exito de Pong se debi´o a que por primera vez se tuvo en cuenta la experiencia de usuario, consiguiendo un juego muy sencillo que cualquier jugador sin experiencia pudiera disfrutar desde la primera partida. Los creadores de Pong hab´ıan aprendido la lecci´ on de su anterior t´ıtulo, Computer Space (Syzygy Co.2 , 1971), la 1 2
Compa˜ n´ıa fundada en 1972 por Nolan Bushnell y Ted Dabney. Compa˜ n´ıa fundada en 1969 por Nolan Bushnell y Ted Dabney.
3
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
primera recreativa en ser distribuida a gran escala. Si bien Computer Space fue popular en los campus universitarios, no consigui´o conectar con el gran p´ ublico debido a su excesiva complejidad y dif´ıcil manejo. Por el contrario, Pong s´ı consigui´o atraer la atenci´on de la gente, marcando un antes y un despu´es en la cultura del entretenimiento. [Kent, 2010]
Figura 2.1: Una m´aquina recreativa original del Pong de Atari
Pero para vislumbrar el comienzo de los videojuegos hay que viajar en el tiempo hasta la d´ecada de 1940, cuando empezaron a surgir los primeros videojuegos experimentales. Como cuando Thomas T. Goldsmith Jr. y Estle Ray Mann fabricaron y patentaron el primer videojuego de la historia [Goldsmith and Ray, 1948]. El Dispositivo de Entretenimiento de Tubos de Rayos Cat´ odicos era un simulador de misiles que usaba circuitos anal´ogicos para su funcionamiento. En los a˜ nos posteriores aparecieron multitud de contribuciones, en su mayor´ıa acad´emicas sin una explotaci´on comercial, que sentaron las bases de la industria del videojuego. Sus creadores sol´ıan ser f´ısicos y matem´aticos que ten´ıan acceso, gracias a las universidades, a los mastod´ onticos computadores de la ´epoca. Un caso destacable fue el del juego Spacewar (1962), desarrollado en el MIT1 por Steve Russell, Martin Graetz y Wayne Wiitanen. Juego que m´ as adelante fue clonado por Syzygy Company bajo el nombre de Computer Space (1971), por Bill Pitts y Hugh Tuck bajo el nombre de Galaxy Game (1971) y por Cinematronics Incorporated bajo el nombre de Space Wars (1977). Atari consolid´ o el negocio de las recreativas gracias a Pong (Atari, 1972). Y unos a˜ nos despu´es hizo lo propio con las videoconsolas gracias a Atari Pong (Atari, 1975), videoconsola que permit´ıa jugar al juego de recreativa del mismo nombre. No fue la primera videoconsola 1
Massachusetts Institute of Technology
4
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
comercial porque varios a˜ nos antes sali´o al mercado Magnavox Odyssey (Magnavox1 , 1972), consola creada por Ralph H. Bear. Pero la videoconsola Atari Pong, a diferencia de la Magnavox Odyssey, fue un rotundo ´exito de ventas. Las razones del ´exito de Atari Pong frente a Magnavox Odyssey fueron: la publicidad que le proporcion´o la recreativa Pong, un producto final mejor acabado y compatibilidad con un mayor n´ umero de televisores.
Figura 2.2: Atari Pong
Figura 2.3: Magnavox Odyssey
Los juegos de ordenador tardaron m´as en consolidarse como una forma de negocio, ganando cuota de mercado de una forma m´ as paulatina que las recreativas o videoconsolas. Durante la d´ecada de 1970 aparecieron multitud de t´ıtulos cuyo c´odigo fue escrito para funcionar en las computadoras centrales de las universidades. La difusi´on de estos juegos era limitada, pero supusieron un punto de apoyo muy importante para las compa˜ n´ıas de videojuegos. Muchos de estos t´ıtulos fueron adaptados a˜ nos m´as tarde para funcionar en ordenadores personales y sus programadores contratados por las primeras compa˜ n´ıas de videojuegos. Si bien los primeros juegos de ordenador sol´ıan funcionar con una interfaz de comandos, esto no supuso un impedimento para que afloraran multitud de g´eneros. Simuladores de deportes como Baseball (Don Daglow, 1971), juegos de estrategia como Star Trek (Mike Mayfield, 1971), aventuras de texto como Hunt the Wumpus (Gregory Yob, 1972), juegos de disparos en primera persona como Maze War (Steve Colley, 1974), etc. Las ideas y conceptos que se forjaron durante estos a˜ nos dejaron una impronta que hoy en d´ıa todav´ıa perdura. Por ejemplo, el juego Multi-User Dungeon o MUD (Roy Trubshaw y Richard Bartle, 1978) fue el primero en plantear un juego de aventuras para multitud de jugadores simult´aneos. Los MMORPG2 modernos son descendientes directos de este juego, si bien han cambiado la interfaz textual a una de gr´ aficos, la mec´anica del juego apenas se ha visto afectada. Hoy en d´ıa todav´ıa persisten versiones de aquel primer MUD como Reinos de Leyenda3 Microchess (Peter R. Jennings, 1976) fue de los primeros juegos en venderse al p´ ublico que consigui´ o cierto ´exito. Este videojuego de ajedrez, cuya primera versi´on ocupaba un u ´nico kilobyte, lleg´ o a conseguir vender m´as de 50.000 copias a los largo de los a˜ nos. Tiempo 1
Compa˜ n´ıa fundada en 1917 por Edwin Pridham y Peter L. Jensen. Massively multiplayer online role-playing game 3 Reinos de Leyenda - www.reinosdeleyenda.es 2
5
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
despu´es sal´ıa al mercado Zork I (Infocom, 1980), versi´on del juego desarrollado a˜ nos atr´ as por Dave Lebling, Marc Blank, Tim Anderson y Bruce Daniels. Zork fue un rotundo ´exito de ventas que super´ o el medio mill´on de unidades vendidas, dando un impulso de gigante a la compa˜ n´ıa Infocom que a˜ nos m´as tarde ser´ıa comprada por Activision. Empresa de la que procede la actual Activision Blizzard, una de las mayores empresas de videojuegos de hoy en d´ıa.
2.1.1.2.
La crisis del 83
Hemos repasado c´ omo en esta primera etapa de la industria del videojuego las recreativas, las videoconsolas y, en menor medida, los ordenadores personales se asentaron como plataformas de entretenimiento. Pero para poder enlazar con el momento actual de la industria hay que repasar un momento clave en la historia de la misma, la crisis del videojuego de 1983. La industria del videojuego hab´ıa vivido un crecimiento sin precedentes, Atari era la empresa que m´ as r´ apido hab´ıa crecido hasta la fecha en la historia de los EEUU1 , lo que dio rienda a la especulaci´ on y a la aparici´on de infinidad de nuevas empresas dedicadas al sector. La crisis golpe´ o con m´as fuerza en los EEUU, lo cual es l´ogico porque era donde se encontraba el mayor n´ umero de empresas dedicadas a este sector. Sin embargo esta problem´ atica no afect´ o a todas las plataformas por igual, siendo las m´as afectadas las recreativas y las videoconsolas. Repasemos las causas que dieron pie al comienzo de la crisis. Por un lado el mercado de las videoconsolas estaba saturado, hab´ıa infinidad de diferentes modelos cada uno con su propio cat´alogo de juegos. La compatibilidad brillaba por su ausencia, incluso entre los diferentes modelos de una misma compa˜ n´ıa. La calidad de muchos de estos videojuegos dej´ o de ser una prioridad frente a la necesidad de conseguir beneficios a corto plazo. Dos juegos de la consola Atari 2600 (1977) ejemplifican esta tendencia: - Pac-Man (1982). Basado en el m´ıtico juego de recreativas. A su creador Tod Frye se le dieron unos plazos demasiado ajustados, lo que unido a que la videoconsola dispon´ıa de menos memoria que la recreativa, dio como resultado una versi´on muy inferior. Aunque Atari lleg´ o a vender 7 millones de copias, la empresa hab´ıa fabricado 12 millones esperando una mayor repercusi´on. - E.T. the Extra-Terrestrial (1982). Un juego sacado a toda prisa para que su lanzamiento coincidiera con la campa˜ na de Navidad siguiente al estreno de la pel´ıcula. De los 5 millones de copias fabricadas solo pudieron colocar un mill´on y medio de copias2 . 1 2
M´ as informaci´ on en Today’s Atari Corp.: A close-up look inside M´ as informaci´ on en Five Million E.T. Pieces
6
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Por otro lado los ordenadores personales eran cada vez m´as asequibles y potentes, m´ as familias pod´ıan permitirse tener uno en casa. Estos nuevos ordenadores ten´ıan m´as prestaciones que las videoconsolas y sus juegos pod´ıan ser mucho m´as complejos. Por ello los juegos de ordenador fueron ganando terreno poco a poco a las videoconsolas. Aunque muchas empresas de juegos para ordenador cerraron por culpa de la crisis, la peor parte se la llevaron las empresas de videoconsolas. La venta de videoconsolas es una importante fuente de ingresos que no percib´ıan las empresas de juegos para ordenador, pero eso se convirti´o en una ventaja cuando el mercado se satur´o y fue imposible colocar una parte importante del stock acumulado. Las m´aquinas recreativas no se libraron de la crisis. Al igual que con las videoconsolas, afloraron multitud de juegos de baja calidad. Pero sin duda, lo que m´as afect´o a la industria de m´ aquinas recreativas fue la devaluaci´on del d´olar. La m´aquinas recreativas segu´ıan funcionando con monedas de un cuarto de d´olar, pero la inflacci´on hab´ıa reducido considerablemente las ganancias. En Jap´ on usaban monedas de Y100, lo que confiri´o una mayor estabilidad a la industria japonesa respecto de la americana. Los efectos de la crisis fueron devastadores, en los tres a˜ nos que dur´o la crisis la recaudaci´ on anual baj´ o de los 3200 millones de d´olares a 100 millones de d´olares1 . Muchas empresas, incluida Atari, entraron en banca rota. El mercado americano no se recuper´o hasta que en 1985 la empresa japonesa Nintendo trajo consigo la videoconsola NES2 (Nintendo, JP 1983, NA 1985, EU 1986). La mejora tecnol´ogica respecto de sus rivales y la calidad de sus videojuegos dejaron atr´ as a todos sus competidores. La empresa Nintendo hab´ıa refundado la industria de las videoconsolas y cambiado para siempre el concepto de los videojuegos. Jap´on se convirti´ o en la potencia hegem´onica de las videoconsolas.
Figura 2.4: Videoconsola NES 1 2
M´ as informaci´ on en The Famicom rules the world! – (1983–89) Nintendo Entertainment System
7
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Un efecto inesperado de la crisis a largo plazo fue el incremento en el n´ umero de jugadores. Durante la crisis se acumul´ o un gran stock de videoconsolas que las tiendas no consegu´ıan vender. En muchos casos era imposible devolver las videoconsolas al fabricante porque este hab´ıa quebrado y la competencia japonesa hac´ıa que el stock quedara obsoleto. Muchas tiendas optaron por liquidar el stock a precios muy bajos, lo que abri´o el mercado de los videojuegos a mucha gente que antes no se hab´ıa animado a probarlos.
2.1.1.3.
Evoluci´ on hasta nuestros d´ıas y situaci´ on actual
Una vez que la industria se hubo recuperado de la crisis el mercado se estabiliz´o, adoptando un modelo que se ha mantenido hasta nuestros d´ıas en el que los grandes protagonistas han sido las videoconsolas y los juegos de ordenador. Por su parte las m´aquinas recreativas han ido perdiendo importancia gradualmente en favor del juego dom´estico, aunque han experimentado breves repuntes gracias a juegos como el Street Fighter II (Capcom, 1991) o Time Crisis (Namco, 1996). Pasada la crisis, la industria de las videoconsolas qued´o en manos de unas pocas empresas japonesas. Primero de Nintendo gracias a la NES (Nintendo, JP 1983, NA 1985, EU 1986), seguida de Sega con su Master System (Sega, JP 1985 ,NA 1986, EU 1987) y unos a˜ nos m´as tarde de Sony y su PlayStation (Sony, JP 1994, NA 1995, EU 1995). No fue hasta el cambio de siglo cuando una compa˜ n´ıa americana, Microsoft, volviera a posicionarse en lo alto de la industria gracias a la Xbox (Microsoft, JP 2002, NA 2001, EU 2002).
Figura 2.5: Evoluci´on de las consolas de sobremesa y port´atiles
8
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Desde entonces y cada pocos a˜ nos los fabricantes sacan al mercado una nueva generaci´on de videoconsolas. En cada generaci´ on se plasman las ideas en las que han estado trabajando los u ´ltimos a˜ nos. Buscan diferenciarse de la competencia y convencer a los jugadores a dar el salto desde sus propios modelos anteriores. Ahora mismo nos encontramos en la octava generaci´ on de videoconsolas, integrada por la Wii U (Nintendo, 2012), Playstation 4 (Sony, 2013) y Xbox One (Microsoft, 2013). Como se puede observar, las compa˜ n´ıas suelen sincronizarse a la hora de sacar al mercado las nuevas videoconsolas. Por otro lado, la din´ amica en la industria de los juegos de ordenador es muy distinta ya que no tienen una plataforma fija con unas especificaciones que no van a cambiar hasta dentro de unos a˜ nos. La evoluci´ on, tanto del hardware como del software, es incesante, por lo que los fabricantes se ven obligados a elegir entre un amplio espectro de jugadores o una mayor complejidad del juego. Lo normal es especificar unos requisitos m´ınimos que garanticen poder jugar y unos requisitos recomendados con los que poder disfrutar de todo el potencial del videojuego. Por ejemplo, la versi´on de PC del juego Grand Theft Auto V (Rockstar North, 2013) pide como m´ınimo 4GB de RAM y recomienda 8GB de RAM. Ahora mismo nos encontramos en un momento muy interesante de la historia de los videojuegos. Nuevas plataformas como los navegadores web, los tel´efonos inteligentes y las tabletas empiezan a ganar cuota de mercado a las plataformas tradicionales. El modelo de negocio se est´ a orientando a la distribuci´on digital en sustituci´on de la compra f´ısica. La desaceleraci´ on en la evoluci´ on de los microprocesadores retrasa la salida al mercado de nuevas generaciones de videoconsolas. La latencia en los juegos online multijugador sigue siendo un problema. Las conexiones dom´esticas a internet est´an preparadas para la descarga de grandes cantidades de informaci´on, no para minimizar la latencia en el intercambio de peque˜ nos paquetes de datos. Existe la incertidumbre de que se genere una burbuja financiera si proliferan las grandes producciones como el juego Destiny (Bungie, 2014). Este tuvo un presupuesto de 500 millones de d´olares, de los cuales 140 millones fueron a desarrollo y 360 millones a marketing y distribuci´on. Seg´ un Newzoo1 los ingresos a nivel global durante el a˜ no 2014 fueron aproximadamente de $81.600.000.000, con un crecimiento anual estimado del 8 %2 . Los ingresos en la zona AsiaPac´ıfico igualaron a los ingresos combinados de Am´erica del Norte y Europa Occidental, pero en la zona Asia-Pac´ıfico se da una tasa de crecimiento anual del 15.2 % frente al estancamiento de los mercados occidentales3 . Segun PwC4 el mercado global de videojuegos crecer´a hasta los $93.100.000.000 en 20195 . 1
Newzoo games market research - www.newzoo.com M´ as informaci´ on en Top 100 Countries Represent 99.8% of $81.5Bn Global Games Market 3 M´ as informaci´ on en Asia-Pacific Contributes 82% of the $6Bn Global Games Market Growth in 2014 4 PricewaterhouseCoopers - www.pwc.com 5 M´ as informaci´ on en Global entretainment and media outlook 2015-2019 2
9
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
La Asociaci´ on Espa˜ nola de Videojuegos (AEVI)1 publica que los ingresos en Espa˜ na durante el a˜ no 2014 fueron de 996 millones de euros2 . Si bien el consumo f´ısico ha descendido ligeramente debido al descenso en la venta de videoconsolas hasta los 755 millones desde los 763 del 2013, el consumo digital ha aumentado dr´asticamente hasta los 241 millones desde los 170 millones del 2013. Por desgracia nos tenemos que remontar hasta el a˜ no 2011 para encontrar el u ´ltimo informe publicado por AEVI sobre la penetraci´on del videojuego en Espa˜ na3 . Seg´ un dicho informe el volumen de jugadores en Espa˜ na es del 24 % frente al 25.4 % de Europa. En Espa˜ na el porcentaje de jugadores aumenta hasta un 45.3 % en la franja de edad de los 7 a los 34 a˜ nos. Del total de jugadores un 59 % son hombres y un 41 % mujeres; desde la fecha del informe existe una tendencia al aumento de jugadoras debido en gran parte al ´exito de los juegos para m´oviles.
2.2.
G´ eneros en los videojuegos
Los videojuegos proporcionan a la Inteligencia Artificial (IA) un campo de pruebas muy interesante de cara a la investigaci´on. Tanto si se plantea resolver el juego desde el punto de vista del jugador, como entorno para una infinidad de problemas aislados [Laird and van Lent, 2001]. Cuando un investigador quiere usar un videojuego para probar una t´ecnica de IA, podr´a ser de utilidad conocer los distintos tipos de juegos y qu´e posibilidades ofrece cada uno de ellos. Vamos a presentar una clasificaci´ on bastante cl´asica tratando los principales g´eneros y sus problem´ aticas. Si bien lo normal es encontrar un juego dentro de un u ´nico g´enero, existen casos que toman elementos de varios g´eneros.
2.2.1.
Acci´ on
En este tipo de videojuegos el jugador debe hacer uso de sus reflejos, punter´ıa y habilidad, a menudo en un contexto de combate o de superaci´on de obst´aculos y peligros. Dentro de este g´enero se agrupan los juegos de disparos, de lucha, de plataformas, etc. Los juegos de acci´ on plantean problemas que por lo general deben resolverse en tiempo real. Siendo el comportamiento de los bots4 uno de los principales focos de investigaci´on. Se busca que los enemigos se comporten de forma natural y racional, evitando patrones que 1
Asociaci´ on Espa˜ nola de Videojuegos - www.aevi.org.es M´ as informaci´ on en El consumo global de videojuegos en Espa˜ na fue de 996 millones de euros en 2014 3 M´ as informaci´ on en El videojugador espa˜ nol: perfil, h´ abitos e inquietudes de nuestros gamers 4 En el ambiente de los videojuegos, se conoce como bot a programas que son capaces de jugar por s´ı mismos el juego en cuesti´ on. 2
10
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
los jugadores puedan aprovechar en su beneficio. La competici´on 2K BotPrize1 premia el desarrollo de bots cuyo comportamiento sea indistinguible del de jugadores humanos.
2.2.2.
Aventuras
En los videojuegos de aventuras el jugador encarna a un protagonista que debe avanzar por la trama interactuando con diversos personajes y objetos. Aunque este tipo de juegos no se han usado tradicionalmente para el estudio de la IA, ofrece, sin embargo, interesantes posibilidades en el desarrollo de t´ecnicas de lenguaje natural para interactuar con los personajes no jugadores o de t´ecnicas de planificaci´on para el desarrollo autom´atico de tramas.
2.2.3.
RPG (role-playing game)
En un principio los juegos de RPG se encontraban en un limbo entre los juegos de acci´ on y los de aventura, seg´ un el ´enfasis puesto en la acci´on o en la historia, pero con el tiempo se han ido consolidando como un g´enero propio de pleno derecho. Este tipo de juegos se caracterizan por una historia profunda y una evoluci´on del personaje a medida que la historia avanza. La exploraci´ on y la interacci´on con otros personajes son claves en los RPG. Si bien parece que el pathfinding o b´ usqueda de caminos est´a resuelto desde hace a˜ nos, a´ un hoy podemos encontrar casos en que los pnjs2 quedan atascados. Esto ha ocurrido en juegos tan famosos como el Diablo 2 (Blizzard North, 2000), Neverwinter Nights (BioWare, 2002) o The Elder Scrolls V: Skyrim (Bethesda Game Studios, 2011). La tendencia en este tipo de juegos es la de generar mundos abiertos cada vez m´as grandes, donde los jugadores pueden explorar libremente e interactuar con el entorno a su antojo. Las dimensiones de este tipo de juegos parecen no tener l´ımites, hac´ıa poco que el juego Grand Theft Auto V (Rockstar North, 2013) bati´o todos los r´ecords con un mapa de 81 kil´ometros cuadrados, pero este mismo a˜ no el juego The Witcher 3: Wild Hunt (CD Projekt RED, 2015) trae un mapa de 136 kil´ometros cuadrados. Lo interesante de estos mundos abiertos es que son din´ amicos y van cambiando y evolucionando sin necesidad de interacci´ on por parte del jugador.
1 2
M´ as informaci´ on en botprize.org personajes no jugadores
11
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
2.2.4.
Estrategia
Los juegos de estrategia se caracterizan por la necesidad de manipular a un numeroso grupo de personajes, objetos o datos, haciendo uso de la inteligencia y la planificaci´on para lograr los objetivos. Aunque la mayor´ıa de estos juegos son fundamentalmente de tem´atica b´elica, los hay tambi´en de estrategia econ´omica, empresarial o social. Cuando se habla de juegos de estrategia hay que diferenciar los juegos en tiempo real como StarCraft II (Blizzard Entertainment), de los que son por turnos como Sid Meier’s Civilization V (Firaxis Games). En este tipo de juegos suele haber un agente que compite contra el jugador humano, este agente deber´a tomar decisiones y planificar una estrategia a seguir para hacerse con la victoria. En los juegos b´elicos de estrategia en tiempo real, el movimiento de las unidades por el mapa ha supuesto un serio problema a resolver. Buscar el camino m´as corto, no entorpecer el paso de unidades aliadas o adaptarse a los cambios del terreno son problemas habituales de los juegos de estrategia. En el juego StarCraft II se emple´o una t´ecnica para mover a la vez a varias unidades de forma coordinada emulando el comportamiento de un enjambre1 .
2.2.5.
Simulaci´ on
Este g´enero se caracteriza por recrear situaciones o actividades del mundo real, dejando al jugador tomar el control de lo que ocurre. Lo habitual es que este tipo de juegos simulen la conducci´ on de veh´ıculos, la gesti´ on de negocios o el manejo de situaciones cotidianas. Iconos del g´enero son juegos como Microsoft Flight Simulator (ACES Game Studio), SimCity (Maxis) o The Sims (Maxis). Un juego de simulaci´ on puro tiene como prioridad el desarrollo de un buen motor f´ısico, pero lo normal es que estos juegos entren tambi´en dentro de los g´eneros de acci´on o de estrategia, permitiendo desarrollar las t´ecnicas propias de estos otros g´eneros en un entorno m´as realista.
2.2.6.
Casual
Cualquier juego que sea sencillo de jugar y que no requiera de mucho tiempo puede considerarse un juego casual. Si bien este tipo de juegos, orientados en especial a los p´ ublicos m´as j´ovenes, son f´ aciles de manejar pero no de desarrollar. 1 M´ as informaci´ on en http://www.teamliquid.net/forum/starcraft-2/132171-the-mechanics-of-sc2-part1The Mechanics of Starcraft 2
12
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Por ejemplo, muchos de estos juegos usan interfaces no convencionales como puede ser la c´amara Kinect. La IA puede ayudar a desarrollar programas de reconocimiento facial, reconocimiento de movimientos, reconocimiento de voz, etc.
2.3.
Inteligencia Artificial en videojuegos
El objetivo que persigue la Inteligencia Artificial es la aplicaci´on de t´ecnicas autom´aticas que permitan resolver problemas para los cuales ser´ıa preciso el razonamiento humano. La IA se ha centrado generalmente en la elaboraci´on de sistemas complejos, los cuales suelen conllevar un fuerte componente algor´ıtmico y un elevado coste computacional. Primero mencionaremos algunas de las t´ecnicas de IA que se emplean en los videojuegos recogidas en [Millington and Funge, 2009], para despu´es repasar algunas metas que a´ un quedan por conquistar seg´ un [Rabin, 2015].
2.3.1. 2.3.1.1.
T´ ecnicas de IA aplicables en los videojuegos Pathfinding o b´ usqueda de caminos
Consiste en determinar el camino a seguir para ir de un punto a otro en un entorno dado. Teniendo un entorno convenientemente representado y decididos los puntos de origen y destino, un algoritmo de b´ usqueda devuelve una lista de vectores que indican las acciones o movimientos necesarios para alcanzar la meta. El algoritmo m´as empleado en la actualidad es el A*.
2.3.1.2.
M´ aquinas de estado
Usar aut´ omatas finitos es una de las t´ecnicas m´as empleadas, define un conjunto finito de estados y unas transiciones entre ellos, con un u ´nico estado activo en cada momento. Lo normal es que cada estado represente un comportamiento, cambiando de estado en respuesta a determinados eventos. Por ejemplo, si un bot est´a en un estado vigilar y se dispara un evento enemigo cercano, esa acci´on cambiar´ıa el estado a atacar . Si en vez de usar aut´ omatas finitos usamos aut´omatas a pila, al contrario que suced´ıa antes, se podr´ a guardar informaci´ on sobre las acciones y estados previos. Por ejemplo, cuando un bot sufre una amenaza puntual y se genera un evento que interrumpe una tarea programada, una vez pasada la amenaza la pila aporta la informaci´on necesaria para retomar su actividad anterior.
13
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on 2.3.1.3.
Aprendizaje por refuerzo
Se trata de una t´ecnica que permite generar funciones de decisi´on a base de prueba y error, recompensando los resultados positivos y penalizando los negativos. Un ejemplo muy representativo de esta t´ecnica est´ a en el juego Black & White (Lionhead Studios, 2001), en el cual el jugador debe ense˜ nar a su mascota gigante c´omo debe comportarse, premiando o castigando sus acciones.
2.3.1.4.
L´ ogica difusa o fuzzy logic
Se trata de una extensi´ on de la l´ ogica cl´asica en la cual los hechos no son estrictamente ciertos o falsos. Por ejemplo, en la l´ogica cl´asica una cerveza puede estar fr´ıa o caliente, mientras que en la l´ ogica difusa puede estar fr´ıa con una certeza de un 40 % (templada), de un 90 % (muy fr´ıa) o cualquier otro valor porcentual entre 0 (nada) y 100 (todo).
2.3.2. 2.3.2.1.
Metas a conquistar Pathfinding o b´ usqueda de caminos
Implementar en un juego el movimiento de agentes suele implicar encontrar caminos que conecten dos localizaciones a trav´es del espacio del mundo representado. Afortunadamente existen soluciones a las formas m´ as b´asicas de este problema, como Dijkstra o A*. Pero el problema a´ un est´ a lejos de estar resuelto cuando: las dimensiones del entorno son demasiado grandes, resulta dif´ıcil encontrar una buena heur´ıstica, el mundo es din´amico o haya que manejar coordinadamente a varios agentes. Por otra parte tambi´en queda mucho trabajo por delante, no solo por conseguir una ruta ´optima en el menor tiempo posible, sino en darle sentido y coherencia a los movimientos de los bots.
2.3.2.2.
Conversaciones
T´ıpicamente las conversaciones en los videojuegos se reducen a cinem´aticas que siguen un gui´on o conversaciones en las que solo se pueden elegir frases preestablecidas. Estos ´arboles de di´alogos son muy costosos de construir pues deben tener en cuenta todos los posibles escenarios, hacen falta guionistas que den forma a los textos y dobladores que pongan las voces.
14
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Explorando un poco nos adentramos en el territorio del lenguaje natural. Se nos plantea un futuro en el que las conversaciones no est´en predeterminadas y puedan surgir conversaciones de forma autom´ atica teniendo en cuenta el contexto de la situaci´on.
2.3.2.3.
Historias din´ amicas
De forma similar a lo que ocurre con las conversaciones, las historias en los videojuegos siguen unos guiones fijos de los que el jugador no puede salirse. En este caso en vez de adentrarnos en el mundo del lenguaje natural nos adentramos en el terreno de la planificaci´on. Es posible que dentro de unos a˜ nos no haya necesidad de guiones prefijados, que la historia se desarrolle de forma din´ amica en funci´on de la interacci´on del jugador con el entorno que lo rodea.
2.3.2.4.
Modelar el comportamiento de los jugadores
Un juego que sea capaz de adaptarse al jugador es el sue˜ no de muchas compa˜ n´ıas de videojuegos. Adaptarse a sus gustos, a su forma de jugar, a su nivel de habilidad, etc. Hoy en d´ıa muchas compa˜ n´ıas recolectan datos on-line sobre el uso de los jugadores en sus videojuegos para modificarlos en consecuencia en posteriores actualizaciones. La idea que se plantea es que los juegos, autom´aticamente, sean capaces de adaptarse a los gustos personalizados de cada jugador.
2.3.2.5.
Relaciones sociales
Cada vez son m´ as frecuentes los videojuegos que albergan un mundo abierto. Estos suelen estar plagados de pnjs1 que “viven sus propias vidas”. Por desgracia estas interacciones sociales son muy limitadas. Ser´ıa muy interesante la aparici´on de mundos abiertos, donde las interacciones entre sus habitantes fuesen lo m´as realista posible e influyeran en el estado del mundo sin necesidad de que influya el jugador.
2.3.2.6.
Escalabilidad
Las t´enicas de IA deben adaptarse a las nuevas plataformas que se usan en los videojuegos. Estas plataformas, por lo general navegadores web y dispositivos m´oviles, cuentan con menos recursos que las plataformas cl´asicas. La IA no debe centrar todos sus esfuerzos 1
personajes no jugadores
15
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
en resolver problemas cada vez m´ as complejos, tambi´en debe buscar formas de refinar las t´ecnicas existentes para que consuman menos recursos.
2.4.
Competici´ on
La motivaci´ on principal de este proyecto fue participar en la primera edici´on de la competici´on Grid-Based Path Planning Competition (GPPC)1 . Dicha edici´on se celebr´o en el marco de la conferencia Symposium on Combinatorial Search (SoCS) de 2012 [Borrajo et al., 2012]. El organizador de la competici´on es Nathan Sturtevant2 , actualmente es Profesor Ayudante Doctor de la Universidad de Denver. Tambi´en ha colaborado como consultor para la compa˜ n´ıa de videojuegos BioWare en temas relacionados con la b´ usqueda de caminos para juegos como el Dragon Age. El objetivo de la competici´ on es el de crear un punto de encuentro donde los investigadores puedan comparar sus trabajos sobre b´ usqueda. Para ello se provee de una bater´ıa de problemas de mapas de cuadr´ıcula3 , se emplean este tipo de mapas porque son usados tanto en investigaci´ on como en aplicaciones comerciales.
2.4.1.
Definici´ on del problema
La competici´ on est´ a orientada al problema del pathfinding en los videojuegos, para el caso particular en el que los mapas est´ an predefinidos y la b´ usqueda deba realizarse en el menor tiempo posible para no restar recursos al motor gr´afico. Se ha simplificado el problema para un u ´nico agente, siendo el mapa est´atico y con costes uniformes. Los mapas que se usan en la competici´on son abstracciones de mapas reales de videojuegos y mapas generados aleatoriamente. Todos los mapas son cuadr´ıculas rectangulares, siendo cada celda de la cuadr´ıcula transitable o no transitable. El tama˜ no m´aximo de los mapas ser´a de 2048 por 2048 celdas. Como un agente solo puede estar en una celda a la vez, el n´ umero de estados de cada mapa ser´a el n´ umero de celdas transitables. El n´ umero m´aximo de estados que puede tener un mapa es de 222 estados, algo m´as de cuatro millones. Los tipos de mapas que se van a usar en la competici´on son:
- Mapas de videojuegos: Mapas reales de videojuegos que han sido adaptados a las caracter´ısticas de la competici´on. Pueden representar edificios o espacios abiertos. 1
M´ as informaci´ on en movingai.com/GPPC M´ as informaci´ on en www.cs.du.edu/˜sturtevant 3 M´ as informaci´ on en www.movingai.com/benchmarks 2
16
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
- Laberintos: Laberintos generados aleatoriamente. El ancho de los pasillos en un mapa puede ser de 1, 2, 4, 8, 16 o 32 celdas. - Aleatorios: Dado un mapa con todas las celdas transitables, se ponen obst´aculos en el mapa de forma aleatoria. Si hay varias regiones inconexas en el mapa, se selecciona la regi´ on m´ as grande y se rellenan de obst´aculos las otras regiones. El porcentaje de obst´ aculos en el mapa puede ser del 10 %, 20 %, 25 %, 30 %, 35 % o 40 %. - Habitaciones: Una malla de habitaciones cuadradas conectadas por puertas aleatorias. Si una habitaci´ on queda aislada se rellenar´a de obst´aculos. El tama˜ no de las habitaciones puede ser de 8x8, 16x16, 32x32 o 64x64 celdas.
Figura 2.6: Tipos de mapas. De izquierda a derecha: videojuego (edificio), videojuego (espacios abiertos), laberinto, aleatorio, habitaciones.
Por cada mapa hay dos archivos. Un archivo que contiene la informaci´on del mapa: el alto, el ancho y qu´e celdas son o no transitables. Y un archivo que alberga una bater´ıa de pruebas. Cada prueba consta de: las coordenadas de la celda de salida, las coordenadas de la celda de meta y la longitud del camino ´optimo que las conecta. Dado que el mapa es una cuadr´ıcula, cada celda puede tener hasta 8 vecinos. Las acciones de las que dispone un agente para desplazarse por el mapa son: movimiento cardinal (Norte, Este, Sur, Oeste) y movimiento diagonal (Noreste, Sureste, Suroeste, Noroeste). Para que un movimiento cardinal sea posible, la celda de destino debe ser transitable. Para que un movimiento diagonal sea posible, la celda de destino y las celdas adyacentes tanto a la celda de origen como a la de destino deben ser transitables. Los respectivos costes para √ movimientos cardinales y diagonales son 1 y 2.
17
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Figura 2.7: Ejemplos de los posibles movimientos en funci´on de los obst´aculos colindantes
La competici´ on se divide en dos fases, una fase offline y otra fase online. En la fase offline se preprocesa el mapa para obtener toda la informaci´on posible que ayude en la b´ usqueda de caminos. Una vez ha terminado el preprocesado, se debe guardar la informaci´on en un archivo. En la fase online lo primero que se hace es cargar a memoria la informaci´on del archivo antes mencionado. Despu´es, para cada problema de la bater´ıa, se busca un camino que conecte las celdas de salida y de meta. Los caminos se pueden devolver enteros o a intervalos. En la fase offline hay un l´ımite de 30 minutos para precomputar cada mapa. No hay restricciones de memoria. Se permite el uso de hilos. El archivo resultante no puede ocupar m´as de 50 MB. En la fase online no hay l´ımite de tiempo. El l´ımite de memoria, incluyendo el programa y la informaci´ on del mapa, es de 51 MB. No se pueden usar varios hilos durante esta fase, toda la ejecuci´ on deber´ a correr sobre un u ´nico hilo. Cada prueba que se ejecute durante esta fase generar´ a los siguientes datos: tiempo total, tiempo de los 20 primeros pasos, mayor tiempo de un intervalo y sub-optimalidad del camino. La sub-optimalidad se entiende como (longitud del camino resultante)/(longitud del camino ´optimo). Para evaluar las soluciones propuestas a la competici´on se usan las siguientes categor´ıas: - Tiempo total y sub-optimalidad del camino completo. - Tiempo de los 20 primeros pasos y sub-optimalidad del camino completo. - Mayor tiempo de un intervalo y sub-optimalidad del camino completo. Todas las categor´ıas son multiobjetivo, se tiene en cuenta el tiempo y la sub-optimalidad. Una soluci´ on se considera vencedora en una categor´ıa si no est´a dominada por ninguna otra soluci´on.
18
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
La organizaci´ on provee a los participantes de una interfaz que no puede ser modificada y una soluci´ on de ejemplo con las funciones b´asicas que ser´an llamadas durante el desarrollo de la competici´ on.
2.5.
Pathfinding
El pathfinding es un dominio de las ciencias de la computaci´on cuyo objetivo consiste en encontrar un camino desde un nodo origen start a un nodo destino goal en un grafo Graph(Vertices, Edges). Aplicado con frecuencia en el ´ambito de los videojuegos, hoy en d´ıa se sigue investigando para conseguir soluciones lo m´as cercanas a la soluci´on ´optima, en el menor tiempo posible, para problemas cada vez m´as complejos. El proceso de pathfinfing podemos dividirlo en tres componentes: el grafo, la heur´ıstica y el algoritmo de b´ usqueda.
2.5.1.
Grafo
Un grafo en el ´ ambito de las ciencias de la computaci´on es una estructura de datos que consiste en un conjunto de nodos (o v´ertices) y un conjunto de arcos (o aristas) que establecen relaciones entre los nodos. En nuestro problema los mapas se representan con grafos en los que cada nodo equivale a una celda transitable y cada arco equivale al coste y acci´ on de movimiento entre dos celdas.
Figura 2.8: Representaci´on de un mapa con un grafo
Cuando el n´ umero de nodos del grafo es demasiado grande para que los algoritmos de b´ usqueda funcionen eficazmente se puede transformar el espacio de b´ usqueda para simplificar el problema. Repasemos a continuaci´on algunas de las t´ecnicas m´as usadas.
19
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on 2.5.1.1.
Waypoint o puntos de referencia
Los waypoints son puntos de referencia seleccionados del espacio de b´ usqueda con los que se genera un subgrafo, en el cual los nodos equivalen a los waypoints y los arcos equivalen a los caminos precomputados que los conectan. A la hora de buscar un camino en el grafo original, si el nodo de origen y el nodo de destino son waypoints del subgrafo, solo necesitamos realizar la b´ usqueda en el subgrafo. Pero si uno de esos nodos no pertenece al subgrafo, har´a falta buscar un camino que lo conecte al subgrafo. Si hay pocos waypoints, la b´ uqueda en el subgrafo ser´a m´as r´apida, pero costar´a conectar los nodos originales al subgrafo. Si hay muchos waypoints, ser´a m´as sencillo conectar los nodos al subgrafo, pero la b´ usqueda en el subgrafo ser´a m´as lenta.
2.5.1.2.
Navigation mesh o malla de navegaci´ on
La navigation mesh o navmesh o malla de navegaci´on, consiste en representar el espacio de b´ usqueda como un conjunto de regiones, las cuales cumplen las siguientes propiedades:
- No existe ning´ un obst´ aculo que se interponga en el camino m´as corto entre dos puntos pertenecientes a la misma regi´on. - Dadas dos regiones conexas A y B, no existe ning´ un obst´aculo que se interponga en el camino m´ as corto entre cualquier punto de la regi´on A y la regi´on B. - Los costes de los movimientos dentro de una misma regi´on son uniformes.
Figura 2.9: Ejemplo de un navigation mesh
20
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Del subgrafo resultante, cada nodo equivale a una regi´on y cada arco equivale a la conexi´ on entre dos regiones.
2.5.1.3.
Voronoi
Voronoi es una t´ecnica para particionar un espacio en regiones. Dado un subconjunto de semillas prefijadas de antemano, cada semilla estar´a asociada a una regi´on de Voronoi. Cada una de estas regiones agrupa a todos aquellos puntos que se encuentran m´as pr´oximos de su semilla que de la semilla de otra regi´on.
Figura 2.10: Ejemplo de regiones de Voronoi
Aunque el espacio de b´ usqueda de nuestro problema sea discreto se puede utilizar Voronoi. Una vez se hayan seleccionado los nodos que actuar´an como semillas, se puede utilizar como funci´on de distancia un Dijkstra que nos dir´a cual es la semilla m´as cercana a cada punto.
2.5.1.4.
Quadtree o ´ arbol cuaternario
Un Quadtree es un tipo de estructura de datos con forma de ´arbol basada en el principio de descomposici´ on recursiva del espacio. En nuestro caso el Quadtree representa el espacio transitable del mapa con regiones cuadradas. Las grandes ´ areas sin obst´ aculos se podr´an representar con pocos cuadrados, mientras que las ´areas con bordes irregulares u obst´aculos necesitar´an de muchos cuadrados peque˜ nos.
21
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Primero abarcamos todo el mapa con un cuadrado, si dentro del cuadrado hay celdas transitables y celdas no transitables dividimos el cuadrado en 4 cuadrados. Repitiendo esta operaci´on de forma recursiva hasta que todas las celdas dentro de un cuadrado sean o transitables o intransitables.
Figura 2.11: Ejemplo de un Quadtree
2.5.2.
Heur´ıstica
La heur´ıstica es el conocimiento parcial sobre un dominio que permite resolver problemas eficientemente. La funci´ on heur´ıstica por lo general se obtiene por la relajaci´on de las restricciones del problema original, permitiendo conseguir una aproximaci´on a la soluci´ on en un tiempo significativamente inferior al que se necesitar´ıa para resolver el problema original. Considerando h*(n) como una heur´ıstica perfecta que devuelve la soluci´on ´optima del problema original, nuestra funci´on heur´ıstica h(n) ser´a admisible si h(n) ≤ h*(n). En el caso del pathfinding se suelen usar como heur´ısticas funciones de distancia para ayudar a un algoritmo A* en la b´ usqueda. Para nuestro problema se podr´ıan usar las siguientes funciones heur´ısticas. Vamos a considerar para los siguientes ejemplos que: el nodo origen ser´a n, el nodo destino ser´ a n’, la distancia entre los nodos en el eje X ser´a x y la distancia entre los nodos en el eje Y ser´ a y.
22
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on 2.5.2.1.
Distancia Manhattan
Formula: f (n, n0 ) = x + y
Figura 2.12: Distancia Manhattan
2.5.2.2.
Distancia euclidiana
Formula: f (n, n0 ) =
√
x∗x+y∗y
Figura 2.13: Distancia euclidiana
23
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on 2.5.2.3.
Distancia diagonal
Formula: f (n, n0 ) = max(x,y) − min(x,y) + min(x, y) ∗
√
2
Figura 2.14: Distancia diagonal
2.5.3.
Algoritmo de b´ usqueda
Un Algoritmo es una serie ordenada de instrucciones, pasos o procesos que llevan a la soluci´on de un determinado problema. Vamos a repasar dos de los algoritmos m´as empleados para resolver problemas de pathfinding en videojuegos. Ser´an nuestro punto de partida y los usaremos para evaluar los resultados obtenidos a lo largo del proyecto.
2.5.3.1.
Dijkstra
El algoritmo Dijkstra es un algoritmo de b´ usqueda no informada con costes. Es un tipo de b´ usqueda en amplitud que siempre expande aquel nodo que tenga menor coste desde el nodo ra´ız, por lo que cumple las siguientes propiedades: - Completitud: Al tratar un problema con un conjunto finito de estados, encontrar´a una soluci´ on si la meta existe y es accesible. - Admisibilidad: Al no haber costes negativos, de haberla, encontrar´a la soluci´on ´optima. - Eficiencia: Buena si la meta est´a cerca. 24
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on - Complejidad: Consume memoria exponencial.
Los mapas de la competici´ on, al tener forma de cuadr´ıcula y costes uniformes, permiten implementar Dijkstra de una forma muy sencilla, solo hay que expandir primero los nodos cardinales y despu´es los diagonales.
Figura 2.15: Estados expandidos por el algoritmo Dijkstra
2.5.3.2.
A*
El algoritmo A-estrella o A* es un algoritmo de b´ usqueda heur´ıstica. A diferencia de Dijkstra que solo expande en funci´ on de la distancia desde el nodo ra´ız, en el algoritmo A* hay que a˜ nadir el coste estimado hasta el nodo destino. Este coste estimado nos vendr´a dado por la funci´ on heur´ıstica que nosotros decidamos. Si la funci´on heur´ıstica es admisible, nunca devolver´ a un valor mayor al coste real necesario para llegar al nodo destino, el A* devolver´ a una soluci´ on ´ optima si el problema es finito y la soluci´on existe.
- Completitud: Al tratar un problema con un conjunto finito de estados, encontrar´a una soluci´ on si la meta existe y es accesible. - Admisibilidad: Al no haber costes negativos y usando una funci´on heur´ıstica admisible, si existe una soluci´ on ´ optima la encontrar´a. - Eficiencia: Depender´ a de la funci´on heur´ıstica. - Complejidad: Si la funci´ on heur´ıstica fuese perfecta consumir´ıa memoria linealmente, pero lo normal es que consuma memoria de forma exponencial.
25
´ Alvaro Parra de Miguel
Cap´ıtulo 2. Estado de la Cuesti´ on
Figura 2.16: Estados expandidos por el algoritmo A*
2.5.4.
Trabajos previos
Existen infinidad de trabajos publicados sobre pathfinding. Si bien durante la fase de investigaci´on de este proyecto se analizaron multitud de ideas y propuestas, vamos a mencionar tres de los trabajos que han causado un mayor impacto en nuestro proyecto. Una de las primera ideas que se estudi´o desarrollar fue la de emplear heur´ısticas en una transformaci´ on del mapa [Rayner et al., 2011]. Teniendo en mente un algoritmo A*, si usamos la distancia eucl´ıdea como funci´on heur´ıstica en el mapa original obtendremos malos resultados; terminaremos explorando muchos m´as estados de los necesarios a poco complicado que sea el mapa. La idea consiste en transformar el mapa para que la distancia eucl´ıdea se aproxime a la distancia real a la meta, esa heur´ıstica se aproxima a la heur´ıstica perfecta por lo que ser´ a de gran ayuda para el A*. Otra idea que se plante´ o fue la detecci´on de basins o pozos en el mapa[Pochter et al., 2010]. Podr´ıamos definir un pozo como una zona que contiene un conjunto de puntos por los que no va a pasar ning´ un camino ´ optimo que conecte dos puntos no pertenecientes a esta zona. Si conseguimos aislar estos basins cuando realizamos la b´ usqueda, nos evitaremos expandir una cantidad considerable de estados. Tambi´en es interesante el planteamiento de los gateways o portales de [Goldenberg et al., 2010], este planteamiento que qued´o aparcado en un primer momento fue retomado posteriormente. La idea es que si tenemos el mapa dividido en regiones, a la hora de conectar dichas regiones entre s´ı no lo hacemos desde los centroides de los grupos, sino a trav´es de puntos en las fronteras entre regiones.
26
Cap´ıtulo 3
Objetivos El objetivo final de este proyecto es el desarrollo de un agente, llamado Bubble Dragon, con el que participar en la Grid-Based Path Planning Competition1 y obtener el mejor resultado posible. La motivaci´ on del proyecto es que la soluci´on final que se presenta a la competici´on resulte vencedora en alguna de las tres categor´ıas existentes. Para que una soluci´on se considere ganadora, ninguna otra soluci´ on puede dominarla en tiempo y longitud del camino. Al ser una competici´ on multiobjetivo puede haber m´as de un ganador en cada categor´ıa. ¿Qu´e objetivos se plantean en este proyecto?
- Desarrollar un agente de pathfinding para participar en la Grid-Based Path Planning Competition. - Reducir el espacio de b´ usqueda durante la fase de preprocesamiento en cualquier tipo de mapa. - Durante la fase de b´ usqueda encontrar caminos, si puede ser ´optimos, en el menor tiempo posible aprovechando la informaci´on obtenida durante la fase de preprocesamiento. - Crear un entorno gr´ afico que permita depurar el c´odigo y obtener informaci´on visual del funcionamiento de los algoritmos.
1
M´ as informaci´ on en GPPC
27
Cap´ıtulo 4
Desarrollo En esta secci´ on se describe el proceso de creaci´on de un agente para participar en la GridBased Path Planning Competition1 . Se comienza detallando el an´ alisis y dise˜ no del sistema para despu´es describir cada uno de los componentes y algoritmos que han sido desarrollados a lo largo del proyecto, intentando justificar de la forma m´ as clara posible las decisiones que se han ido tomando en cada momento.
4.1.
An´ alisis del sistema
En la fase de an´ alisis se van a determinar cuales son los requisitos del sistema, as´ı como cuales son los casos de uso que se han contemplado.
4.1.1.
Requisitos del sistema
Los requisitos del sistema se dividen en dos categor´ıas:
- Agente (AGE): Todos los requisitos relacionados con el procesado de mapas y b´ usqueda de caminos. - Interfaz Gr´ afica (GRA): Todos los requisitos relacionados con la interfaz gr´afica que se utilizar´ a para depurar visualmente el agente.
1
M´ as informaci´ on en GPPC
28
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Adem´as, los requisitos pueden ser de dos tipos: funcional (F) si expresa una funcionalidad que debe tener el sistema o no funcional (NF) si es una restricci´on al dise˜ no o implementaci´on del sistema. De cada requisito se especifica:
1. Identificador: Identificador u ´nico de cada requisito. Compuesto de tres partes: categor´ıa, tipo y n´ umero. 2. Nombre: Resumen del requisito. 3. Descripci´ on: Explicaci´ on detallada del requisito.
AGE-F-01
Preprocesamiento de mapas
Durante la fase de preprocesamiento el agente debe ser capaz de extraer informaci´ on de un mapa dado. Tabla 4.1: Requisito AGE-F-01
AGE-F-02
Almacenar informaci´on
Una vez finalizada la fase de preprocesamiento el agente debe guardar toda la informaci´ on recopilada dentro de un fichero. Tabla 4.2: Requisito AGE-F-02
AGE-F-03
Cargar informaci´on
Al inicio de la fase de b´ usqueda, el agente debe ser capaz de cargar en memoria toda la informaci´ on guardada en el fichero creado al final de la fase de preprocesamiento. Tabla 4.3: Requisito AGE-F-03
AGE-F-04
Buscar caminos
Durante la fase de b´ usqueda el agente debe ser capaz de encontrar un camino que conecte un punto de origen con un punto de destino. Tabla 4.4: Requisito AGE-F-04
29
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
AGE-NF-01
Dimensiones de los mapas
El agente deber´ a ser capaz de operar con mapas de un tama˜ no igual o inferior a 2048x2048 celdas. Tabla 4.5: Requisito AGE-NF-01
AGE-NF-02
L´ımite de tiempo en la fase de preprocesamiento
El agente deber´ a ser capaz de completar la fase de preprocesamiento en un tiempo m´ aximo de 30 minutos. Tabla 4.6: Requisito AGE-NF-02
AGE-NF-03
L´ımite de tama˜ no del fichero resultante de la fase de preprocesamiento
El fichero generado al final de la fase de preprocesamiento debe tener un tama˜ no m´ aximo de 50MB. Tabla 4.7: Requisito AGE-NF-03
AGE-NF-04
L´ımite de hilos en la fase de preprocesamiento
El agente no podr´ a utilizar m´as de 8 hilos durante la fase de preprocesamiento. Tabla 4.8: Requisito AGE-NF-04
AGE-NF-05
L´ımite de memoria en la fase de b´ usqueda
El agente tiene limitado el uso de memoria a 51MB durante la fase de b´ usqueda. Tabla 4.9: Requisito AGE-NF-05
AGE-NF-06
L´ımite de hilos en la fase de b´ usqueda
El agente no podr´ a utilizar m´as de un u ´nico hilo durante la fase de b´ usqueda. Tabla 4.10: Requisito AGE-NF-06
30
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
AGE-NF-07
Prohibidas las comunicaciones
El agente no podr´ a comunicarse con terceras partes bajo ninguna circunstancia, ni acceder a informaci´ on almacenada en la nube. Tabla 4.11: Requisito AGE-NF-07
GRA-F-01
Representar adecuadamente el estado del mapa
Debe crearse un entorno gr´ afico que aporte informaci´on visual del funcionamiento del agente y ayude en la tarea de depurar el c´odigo. Tabla 4.12: Requisito GRA-F-01
GRA-NF-01
Dimensiones de los mapas
El entorno gr´ afico debe ser capaz de representar mapas de un tama˜ no igual o inferior a 2048x2048 celdas. Tabla 4.13: Requisito GRA-NF-01
4.1.2.
Casos de uso
Los casos de uso permiten especificar c´omo deber´ıa interactuar el sistema con los usuarios en diferentes escenarios, dejando claras las funcionalidades que tendr´a que proporcionar a los usuarios. Los actores son entidades externas que interact´ uan con la aplicaci´on. En este caso solo tenemos un actor:
- Evaluador: Herramienta creada por la organizaci´on de la competici´on que interact´ ua con nuestro agente y eval´ ua sus resultados.
31
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Figura 4.1: Diagrama de casos de uso
ID
CU01
Nombre
Preprocesar mapa
´ DESCRIPCION
El agente preprocesa el mapa con el fin de obtener informaci´on que ser´ a utilizada m´as tarde a la hora de buscar caminos
ACTORES
Evaluador
PRECONDICIONES
Ninguna
POSTCONDICIONES
El mapa ha sido preprocesado
ESCENARIO - Cargar el mapa - Configurar el agente para el preprocesamiento - Obtener informaci´on del mapa - Guardar dicha informaci´on en un fichero
Tabla 4.14: Caso de Uso CU01
32
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
ID
CU02
Nombre
Preparar la b´ usqueda
´ DESCRIPCION
El agente se prepara para buscar caminos que conecten pares de puntos, origen y destino, en un mapa dado
ACTORES
Evaluador
PRECONDICIONES
El mapa ha sido preprocesado
POSTCONDICIONES
El agente est´a listo para buscar
ESCENARIO - Cargar el mapa - Cargar el fichero creado en la fase de preprocesamiento - Configurar el agente para la b´ usqueda
Tabla 4.15: Caso de Uso CU02
ID
CU03
Nombre
Realizar la b´ usqueda
´ DESCRIPCION
El agente busca un camino que conecte un par de puntos, origen y destino, en un mapa dado
ACTORES
Evaluador
PRECONDICIONES
El agente est´a listo para buscar
POSTCONDICIONES
Se ha obtenido un camino
ESCENARIO - Buscar un camino que conecte las coordenadas de origen y destino
Tabla 4.16: Caso de Uso CU03
33
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
4.2.
Dise˜ no del sistema
El dise˜ no del sistema en este proyecto viene determinado por la configuraci´on de la competici´on, por lo tanto, nos vemos limitados a desarrollar una arquitectura monol´ıtica en la que nuestro agente debe implementar una interfaz predeterminada. Por otra parte, los exigentes requisitos de memoria en la competici´on han determinado elecciones de dise˜ no como el uso de structs en lugar de clases con tal de ahorrar el m´aximo de memoria posible. A trav´es del uso de diagramas de clases y diagramas de secuencia vamos a tratar de explicar el dise˜ no de este sitema.
4.2.1.
Diagramas de clases
Interfaz gr´ afica de pruebas Definimos una interfaz y una clase a trav´es de la cual vamos a poder seguir de forma visual la traza de los algoritmos durante la depuraci´on de los mismos.
Figura 4.2: Diagrama de clases de la interfaz gr´afica de pruebas
34
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo Agente de la competici´ on
Aqu´ı vemos el dise˜ no del agente, siguiendo la interfaz de la competici´on, el cual se encarga de realizar las fases de preprocesamiento y de b´ usqueda de caminos.
Figura 4.3: Diagrama de clases del agente
35
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
4.2.2.
Diagramas de secuencia
Secuencia de preprocesamiento En el primer paso de la fase de preprocesamiento el evaluador pide al agente que se identifique, despu´es le pasa la informaci´on del mapa para que la analice. El agente, despu´es de tratar los datos, guarda la informaci´on generada en un fichero y devuelve la ejecuci´on al evaluador.
Figura 4.4: Diagrama de secuencia del preprocesamiento
Secuencia de b´ usqueda En el primer paso de la fase de b´ usqueda el evaluador pide al agente que se identifique, despu´es le pasa la informaci´ on del mapa y el nombre del fichero del que puede leer la informaci´on obtenida en la fase previa. Cuando el agente est´a listo para la b´ usqueda devuelve la ejecuci´ on al evaluador para que empiece a mandarle problemas (coordenadas de origen y destino). El agente puede resolver el camino que conecta esas dos coordenadas de dos formas, por un lado puede devolver el camino completo y por otro lado puede devolver el camino en trozos. Es necesario poder devolver el camino por partes para poder evaluar la m´etrica de Mayor tiempo por intervalo vista en la definici´on del problema 2.4.1.
36
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Figura 4.5: Diagrama de secuencia de la b´ usqueda
4.3.
Pruebas de software
En ingenier´ıa del software es fundamental establecer un control de calidad a la hora de desarrollar c´ odigo, las pruebas son una herramienta b´asica que nos ayudan a conseguir un m´ınimo de calidad. En este proyecto, antes de implementar ning´ un algoritmo, se puso especial ´enfasis en la fase de pruebas. Por un lado, se cre´o una bater´ıa de pruebas para comprobar el correcto funcionamiento de los algoritmos y medir su rendimiento (tiempo y distancia por camino). Por otra parte, se desarroll´o un depurador gr´afico para poder trazar el funcionamiento de los algoritmos y tener una ayuda visual que nos indique por qu´e pueden estar fallando. El agente que se present´o a la competici´on no dio ning´ un error durante las distintas fases de la misma, de todos los participantes solo dos consiguieron este logro. Un tipo de pruebas que se han utilizado son las pruebas unitarias de caja negra. Los par´ametros de cada prueba unitaria son: un mapa, una coordenada de origen, una coordenada de destino y la distancia del camino o´ptimo que las conecta. Cada prueba unitaria devuelve: si 37
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
ha sido capaz de encontrar un camino, cu´anto tiempo ha tardado en calcular el camino y la sub-optimalidad del camino encontrado respecto al ´optimo. La organizaci´on nos provee de mapas y problemas de ejemplo1 . En total son unos 512 mapas y para cada mapa hay una media de unos 4000 problemas, por lo tanto tenemos a nuestro alcance un total aproximado de 2 millones de pruebas unitarias. Para realizar la traza de los diferentes algoritmos se dise˜ n´o un depurador gr´afico. Partiendo de la librer´ıa gr´ afica SDL2 , utilizada con frecuencia en la creaci´on de videojuegos, se cre´o un entorno de pruebas ad hoc para pruebas manuales de caja blanca. Este depurador gr´afico fue de vital importancia para poder analizar la informaci´on obtenida en la fase de preprocesamiento, as´ı como para depurar el funcionamiento de los diferentes algoritmos implementados.
Figura 4.6: Interfaz gr´afica
1 2
M´ as informaci´ on en www.movingai.com/benchmarks Simple DirectMedia Layer - www.libsdl.org
38
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
4.4.
Algoritmo de b´ usqueda
El objetivo en la fase de preprocesamiento es la de extraer informaci´on del mapa que agilice la b´ usqueda de caminos. Vamos a estudiar qu´e soluciones se adaptan mejor a nuestro problema concreto y explicar en detalle la soluci´on implementada. Pero antes de nada, ¿es posible usar la fuerza bruta para resolver el problema? En otras palabras, ¿podemos precalcular todos los posibles caminos del mapa para no necesitar buscar en la siguiente fase? Si el tama˜ no m´aximo del mapa es de 2048x2048 nodos, es decir 4*220 nodos, habr´ a un m´ aximo de 16*240 caminos. Si la informaci´on que queremos guardar por cada uno de esos caminos es el siguiente nodo a visitar y cada nodo tiene un m´aximo de 8 vecinos (23 ), necesitamos 128*240 bits = 512 GigaBytes. Dado que el l´ımite de memoria de la competici´ on es de 51 MegaBytes esta soluci´on queda descartada. El mapa de la competici´ on lo representamos como un grafo en el que cada nodo equivale a una celda del mapa. Los arcos que representan movimientos diagonales tienen un coste de √ 2, mientras que los arcos que representan movimientos cardinales tienen un coste de 1.
Figura 4.7: Representaci´on de un mapa con un grafo
Como nos hemos propuesto en los objetivos, y porque no sabemos qu´e tipo de mapas van a predominar en la competici´ on, queremos conseguir una soluci´on que funcione correctamente en cualquier tipo de mapa de los vistos en 2.6. Vamos a analizar las diferentes t´ecnicas mencionadas en el apartado 2.5.1 para ver qu´e ventajas e inconvenientes pueden tener. Waypoints Para usar waypoints hay que tener en mente tres factores: m´etodo para colocar los waypoints, n´ umero de waypoints y conexi´on de nodos al subgrafo. A la hora de posicionar los waypoints est´a claro que no podemos hacerlo de forma manual, pero hacerlo de forma autom´ atica no es tarea sencilla. Las diferentes formas que podemos encontrarnos en los mapas de la competici´on dificultan encontrar una f´ormula para distribuir los waypoints eficientemente a lo largo del mapa. 39
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Por otra parte, si queremos garantizar el poder encontrar caminos ´optimos, deber´ıamos colocar un waypoint en cada arista del mapa. Si hacemos eso en un mapa de tipo random el espacio de b´ usqueda del subgrafo no distanciar´a mucho del espacio de b´ usqueda del grafo original. En cambio si prescindimos de encontrar caminos ´optimos y limitamos el n´ umero de waypoints, su implementaci´ on en mapas de tipo videojuego o laberinto puede dar lugar a que resulte muy complicado encontrar un camino que conecte un nodo cualquiera al subgrafo. Quadtree o ´ arbol cuaternario Los quadtree son una t´ecnica muy buena si tratamos mapas que contengan grandes ´areas transitables. Por ejemplo los mapas de tipo room o algunos mapas de tipo videojuego. Por el contrario, en mapas de tipo laberinto o de tipo aleatorio, el espacio de b´ usqueda que se consigue con un quadtree es casi id´entico al del espacio de b´ usqueda original. Por lo tanto esta t´ecnica es inservible para este tipo de situaciones. Voronoi La problem´ atica de Voronoi es similar al de los waypoints, pues la dificultad que ata˜ ne distribuir las semillas por el mapa de forma eficiente resulta ser un problema todav´ıa m´ as complejo que el que se pretende resolver. Por otra parte si precalculamos el camino de cada celda del mapa a su semilla m´as cercana no necesitaremos buscar el camino que conecte cada nodo con el subgrafo, como pasa al usar waypoints. Pero el camino resultante distar´a mucho del camino ´optimo. Para usar Voronoi hay que predefinir el n´ umero de semillas antes de aplicar la t´ecnica. Si son pocas semillas, tenemos el problema de la sub-optimalidad si conectamos cada punto a su semilla o el problema de buscar un camino que conecte a cada nodo con el subgrafo. Si son muchas semillas, tenemos el problema de que el espacio de b´ usqueda no va a disminuir lo suficiente como para acelerar la b´ usqueda. Navigation mesh Esta t´ecnica est´ a desplazando cada vez m´as a los waypoints en el desarrollo de los videojuegos. Sin duda la que mejor comportamiento tiene de estas cuatro t´ecnicas. Esta t´ecnica obtendr´ a sus mejores resultados en mapas con formas geom´etricas bien definidas como los mapas de tipo laberinto o de tipo habitaciones, lo cual reducir´a considerablemente el espacio de b´ usqueda. Su u ´nico problema es que en mapas de tipo aleatorio, el n´ umero de ´areas que hace falta generar ser´ a tan grande que el espacio de b´ usqueda no se ver´a afectado. Una l´astima, pues 40
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
sin duda era la t´ecnica m´ as prometedora y genera regiones convexas en el mapa que facilitan la b´ usqueda.
4.4.1.
Regiones convexas
Lo ideal ser´ıa poder hacer uso de las regiones convexas que genera la t´ecnica de navigation mesh sin que se vea ralentizada la b´ usqueda de caminos en mapas de tipo aleatorio. Pero, ¿por qu´e queremos dividir el mapa en regiones convexas? Porque la convexidad es una propiedad que facilita enormemente la b´ usqueda. Al dividir un mapa en regiones convexas los obst´ aculos del mapa quedan posicionados en las fronteras entre regiones, por lo que no entorpecen la b´ usqueda como si estuviesen en mitad de una regi´on. Una analog´ıa podr´ıa ser la separaci´ on de paises por elementos de la naturaleza como monta˜ nas y r´ıos.
Figura 4.8: Ejemplo de regiones convexas
Figura 4.9: Ejemplo de regiones c´oncavas
Veamos un ejemplo de regiones convexas y c´oncavas en un mapa de la competici´on para tener una idea general de lo que estamos buscando conseguir.
41
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Figura 4.10: Comparaci´ on entre regiones convexas (izquierda) y regiones c´oncavas (derecha)
Como podemos observar, en el mapa de la izquierda aunque las regiones no sean totalmente convexas la b´ usqueda de caminos ser´a mucho m´as sencilla de realizar que en el mapa de la derecha.
4.4.2.
Algoritmo para dividir el mapa
A la hora de dividir el mapa en regiones convexas tenemos una disyuntiva. Si usamos navigation mesh, el n´ umero de regiones puede ser excesivo en mapas de tipo aleatorio. Nuestra aproximaci´ on es crear un algoritmo que divida el mapa en un n´ umero predefinido de regiones lo m´as convexas posibles. Aunque esto implique que las regiones no ser´an completamente convexas, esperamos que el subgrafo resultante agilice la b´ usqueda de caminos. Si nos fijamos en la comparativa entre regiones convexas y c´oncavas en el mapa de la competici´ on 4.10, se puede apreciar que las regiones convexas tiene menos superficie de contacto con sus vecinas que las regiones c´oncavas. Desde este punto se sigui´o la idea de que si conseguimos dividir el mapa en regiones con fronteras lo m´as peque˜ nas posibles, estas regiones pudieran ser m´ as convexas que c´oncavas. Para dividir el mapa en regiones con la menor frontera posible se emple´o un algoritmo greedy que mediante un proceso iterativo agrupa los nodos en regiones buscando que el tama˜ no de sus fronteras sea el menor posible. Empezamos con una lista de regiones, ordenada de menor a mayor por el tama˜ no de la frontera, que inicializamos introduciendo una regi´on por cada nodo del grafo. Tambi´en hay que definir un n´ umero m´aximo de regiones para indicar al algoritmo cuando debe parar de agrupar. 42
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Figura 4.11: Diagrama de flujo del algoritmo que se utiliza para dividir el mapa en distintas regiones
43
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Veamos qu´e resultados obtenemos al aplicar este algoritmo para 128 regiones.
Figura 4.12: Mapa de tipo videojuego dividido en 128 regiones
Figura 4.13: Mapa de tipo laberinto dividido en 128 regiones
44
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Figura 4.14: Mapa de tipo aleatorio dividido en 128 regiones
Figura 4.15: Mapa de tipo habitaciones dividido en 128 regiones
45
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo
Los resultados son muy interesantes, en el mapa de tipo videojuego los obst´aculos de cierto tama˜ no quedan en su mayor´ıa pegados a las fronteras entre las regiones. Luego para el mapa de tipo habitaciones sorprende que se consigan mantener formas tan regulares y convexas. En el mapa de tipo laberinto se utilizaron laberintos de 8 celdas de ancho y aun as´ı las fronteras son perpendiculares al trazado de los pasillos, reduciendo as´ı su tama˜ no. Por u ´ltimo, en el mapa de tipo aleatorio la mayor´ıa de las fronteras se sit´ uan en cuellos de botella, justamente lo que andamos buscando. Se decide, en vista de los resultados, utilizar este algoritmo para generar un subgrafo de regiones con el que agilizar la b´ usqueda de caminos.
4.4.3.
B´ usqueda de los caminos
Ahora que hemos dividido el mapa en regiones podemos experimentar con multitud de diferentes opciones para realizar la b´ usqueda. Desafortunadamente, el tiempo del que disponemos antes de la competici´ on es limitado y no nos permite poner a prueba todas las ideas que van surgiendo. Debemos priorizar nuestros objetivos y decidir c´omo vamos a emplear nuestro tiempo. Por lo tanto, se decide trabajar en pos de conseguir caminos lo m´ as r´apidos posibles en detrimento de la admisibilidad de los mismos. Aunque no devolvamos el camino ´ optimo, al ser la competici´on multiobjetivo, podemos quedar entre los ganadores si nuestros tiempos son lo suficientemente r´apidos para que nuestra soluci´on no resulte dominada. Nuestro planteamiento consiste en precomputar heur´ısticas direccionales para guiar al agente a trav´es de las distintas regiones del mapa. Si bien esta soluci´on no es admisible, s´ı es completa, pues siempre devolver´ a un camino que conecte los nodos origen y destino.
46
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo 4.4.3.1.
Centroides
Una opci´ on para aprovechar estas direcciones precomputadas podr´ıa ser colocar waypoints en los centroides de las regiones. Por desgracia los caminos resultantes distan mucho del camino ´ optimo.
Figura 4.16: Uso de centroides: origen destino centroide camino
4.4.3.2.
Portales
Si aplicamos la idea de los gateways o portales de [Goldenberg et al., 2010], colocando un portal en cada una de las distintas fronteras entre regiones, reducimos la distancia de los caminos empleando el mismo tiempo.
Figura 4.17: Uso de portales: origen destino portal camino
47
´ Alvaro Parra de Miguel
Cap´ıtulo 4. Desarrollo 4.4.3.3.
Versi´ on final
Repasemos el estado final del algoritmo de b´ usqueda:
- Se ha dividido el mapa en regiones. - Se ha precalculado por qu´e regiones hay que pasar para ir de una regi´on a otra. - Se ha precalculado para cada regi´on qu´e direcciones conectan sus nodos con cada uno de sus portales. - Si el nodo origen y el nodo destino se encuentran dentro de la misma regi´on se emplea Dijkstra para conectarlos.
En la mayor´ıa de los problemas nos piden conectar dos puntos lo suficientemente alejados entre s´ı para que no coincidan en una misma regi´on, pero en caso de que as´ı sea hay que buscar una soluci´ on alternativa que los conecte. La raz´on de utilizar Dijkstra en lugar de A* es porque en este caso concreto Dijkstra es m´as r´apido. Veamos una comparativa entre Dijkstra y A* para mapas de videojuegos de distintos tama˜ nos.
Figura 4.18: Comparativa entre Dijkstra y A* en mapas de videojuegos
Dijkstra, aunque por lo general sea m´as lento que A*, en los casos m´as peque˜ nos se comporta mejor porque utiliza una estructura de datos m´as simple. Al dividir el mapa en muchas regiones, el n´ umero de nodos dentro de una regi´on es muy peque˜ no, por lo que Dijkstra ser´a m´as r´ apido. Se realiz´ o una comparativa de nuestro algoritmo usando Dijkstra y A* y los resultados indicaban que usando Dijkstra el tiempo medio se reduc´ıa a la mitad. 48
Cap´ıtulo 5
Evaluaci´ on En esta secci´ on vamos a evaluar el funcionamiento del agente. Primero veremos como se comporta el agente seg´ un el n´ umero de regiones en que dividamos el mapa, luego compararemos al agente frente a un A* y por u ´ltimo vamos a mostrar los resultados de la Grid-Based Path Planning Competition1 . Para la competici´ on se han empleado una serie de benchmarks [Sturtevant, 2012] con cuatro tipos de mapas: videojuegos, laberintos, aleatorios y habitaciones. Tenemos a nuestra disposici´ on 342 mapas de videojuegos, 60 mapas de laberintos, 70 mapas aleatorios y 40 de habitaciones. Las dimensiones de los mapas de videojuegos var´ıan de 21x30 celdas a 1024x1024 celdas, el resto de los mapas tienen 512x512 celdas. De media cada mapa tiene 4000 problemas por lo que en total tenemos aproximadamente 2 millones de problemas. La m´aquina usada para los experimentos tiene un procesador Intel Core i3-350M a 2.26 GHz y una RAM de 4GB. En la fase de preprocesamiento, el caso m´as complejo no tarda ni un minuto en preprocesarse y genera un fichero 11.3MB. Los objetivos que nos impone la competici´ on de 30 minutos y 50MB quedan cubiertos con un amplio margen.
1
M´ as informaci´ on en movingai.com/GPPC/results.html
49
´ Alvaro Parra de Miguel
Cap´ıtulo 5. Evaluaci´ on
5.1.
N´ umero de regiones
En la siguiente tabla se pueden ver los resultados para el tiempo total, el tiempo m´aximo por paso y la sub-optimalidad para diferente n´ umero de regiones: 1023, 511 y 255. En todos los casos la media del tiempo de b´ usqueda queda por debajo de 1 milisegundo, ya que la mayor parte de los caminos est´ an precomputados y poca o ninguna b´ usqueda es requerida. Hay un caso excepcional cuando se usan 255 regiones en el conjunto de mapas de StarCraft, se observa una anomal´ıa en un mapa de 1024x1024 que tiene 254 regiones aisladas. Esto provoca que no se puedan formar regiones y el algoritmo derive a una b´ usqueda no informada con Dijkstra. Por otro lado, la longitud de los caminos devueltos no es la ´optima, pero en aquellos mapas en que las fronteras entre regiones son realmente peque˜ nas, como en los mapas de tipo laberinto, la diferencia entre el camino resultante y el ´optimo es muy peque˜ na. Analizando estos datos se decidi´ o enviar a la competici´on la soluci´on que define un umbral de 1023 regiones. Aunque los resultados sugieren que una configuraci´on con menos regiones hubiese sido m´ as r´ apida esperamos que una configuraci´on con 1023 regiones sea m´ as consistente de cara a la competici´ on. 1024 groups Total
Longer
(µs)
Step (µs)
512 groups SubOpt
Total
Longer
(µs)
Step (µs)
37 (11)
6 (8)
256 groups SubOpt 1.18 (0.03)
Total
Longer
(µs)
Step (µs)
22 (3)
3 (1)
SubOpt
BG
70 (14)
7 (6)
1.15 (0.04)
1.18 (0.03)
DAO
90 (50)
9 (13)
1.16 (0.11)
45 (24)
5 (7)
1.17 (0.10)
27 (15)
4 (7)
1.18 (0.09)
SC
83 (18)
7 (7)
1.23 (0.05)
46 (12)
6 (8)
1.23 (0.04)
336 (2632)
313 (2632)
1.23 (0.05)
WCIII
66 (14)
12 (13)
1.19 (0.03)
33 (7)
5 (6)
1.20 (0.02)
21 (1)
4 (1)
1.21 (0.03)
Maze 1
178 (26)
6 (1)
1.00 (0)
114 (17)
7 (0)
1.00 (0)
88 (14)
9 (1)
1.00 (0)
Maze 2
180 (13)
6 (0)
1.01 (0)
113 (8)
Maze 4
193 (32)
5 (0)
1.04 (0)
Maze 8
264 (48)
4 (1)
Maze 16
304 (47)
Maze 32
192 (30)
Random 10 Random 20
7 (0)
1.00 (0)
84 (6)
9 (0)
1.00 (0)
98 (16)
4 (0)
1.02 (0)
63 (10)
5 (0)
1.01 (0)
1.11 (0.01)
118 (21)
4 (0)
1.07 (0.01)
69 (12)
4 (0)
1.04 (0.01)
4 (0)
1.26 (0.02)
135 (19)
3 (0)
1.18 (0.02)
77 (10)
3 (0)
1.12 (0.02)
4 (1)
1.17 (0.01)
107 (17)
3 (0)
1.27 (0.02)
70 (10)
3 (0)
1.30 (0.02)
59 (1)
5 (1)
1.20 (0.01)
37 (1)
6 (1)
1.20 (0.01)
26 (1)
6 (1)
1.21 (0.01)
63 (1)
5 (0)
1.20 (0.01)
39 (1)
5 (0)
1.21 (0.01)
29 (1)
6 (0)
1.22 (0.01)
Random 30
68 (1)
6 (0)
1.20 (0.01)
42 (2)
6 (1)
1.21 (0.01)
34 (4)
7 (2)
1.23 (0.01)
Random 40
126 (19)
5 (1)
1.09 (0.01)
71 (10)
4 (1)
1.09 (0.02)
48 (7)
5 (1)
1.08 (0.02)
Rooms 8
64 (1)
5 (0)
1.18 (0.01)
38 (1)
5 (1)
1.19 (0.01)
28 (2)
6 (1)
1.20 (0.01)
Rooms 16
72 (1)
4 (0)
1.07 (0)
37 (2)
4 (0)
1.15 (0.01)
25 (1)
5 (0)
1.18 (0.01)
Rooms 32
68 (4)
4 (0)
1.16 (0.01)
39 (1)
4 (0)
1.24 (0.01)
25 (1)
4 (1)
1.06 (0.01)
Rooms 64
68 (4)
4 (1)
1.12 (0.01)
39 (1)
4 (1)
1.21 (0.02)
25 (1)
4 (1)
1.16 (0.01)
Tabla 5.1: Experimentos con diferentes regiones (Todos los resultados muestran la media y la desviaci´on estandar)
50
´ Alvaro Parra de Miguel
Cap´ıtulo 5. Evaluaci´ on
5.2.
Comparaci´ on con el caso base
En la siguiente tabla se pueden apreciar los resultados de comparar a nuestro agente con 1023 regiones frente a un A* con heur´ıstica de Manhattan. Usamos como heur´ıstica la distancia de Manhattan porque al operar con n´ umeros enteros y no realizar raices cuadradas encuentra caminos en menos tiempo que si usamos la distancia euclidiana o la distancia diagonal. A*-Manhattan
Bubble Dragon
Total time (µs)
Total time (µs)
BG
695
70
DAO
704
90
4120
83
WCIII
892
66
Maze 1
8352
178
Maze 2
12725
180
Maze 4
13931
193
Maze 8
16951
264
Maze 16
15927
304
Maze 32
17751
192
Random 10
323
59
Random 20
522
63
Random 30
1062
68
Random 40
5903
126
Rooms 8
868
64
Rooms 16
1035
72
Rooms 32
1693
68
Rooms 64
3906
68
SC
Tabla 5.2: Comparaci´on del agente con el caso base
51
´ Alvaro Parra de Miguel
Cap´ıtulo 5. Evaluaci´ on
5.3.
Competici´ on
La Grid-Based Path Planning Competition de 2012 tuvo 8 equipos participantes con representaci´ on de Universidades de paises como Chile, Grecia, Estados Unidos, Australia o Espa˜ na. Vamos a repasar los resultados de las tres propuestas que resultaron no dominadas y por lo tanto ganadoras de la competici´on:
- Tree - Conecta todos los puntos del mapa mediante un ´arbol RTT. [Anderson, 2012] - SUB - Genera un grafo de submetas para agilizar la b´ usqueda de caminos ´optimos. [Uras et al., 2012] - PHD - Precomputed Direction Heuristics, nuestra soluci´on. [Parra et al., 2012]
Map Set: All Time (ms)
Length
Total
Max
20
Total
%
PDH
0.130
0.009
0.015
598.7
1.16
SUB
0.662
0.662
0.662
530.3
1.00
TREE
0.009
0.009
0.009
637.8
1.65
Tabla 5.3: Resultados competici´on - Map Set: All
Map Set: Game Maps Time (ms)
Length
Total
Max
20
Total
%
PDH
0.128
0.009
0.017
302.8
1.16
SUB
0.024
0.024
0.024
258.7
1.00
TREE
0.004
0.004
0.004
303.6
1.51
Tabla 5.4: Resultados competici´on - Map Set: Game Maps
Map Set: Mazes Time (ms)
Length
Total
Max
20
Total
%
PDH
0.270
0.010
0.010
3429.7
1.05
SUB
0.100
0.100
0.010
3247.6
1.00
TREE
0.040
0.040
0.040
3622.8
2.16
Tabla 5.5: Resultados competici´on - Map Set: Mazes
52
´ Alvaro Parra de Miguel
Cap´ıtulo 5. Evaluaci´ on
Map Set: Random Time (ms)
Length
Total
Max
20
Total
%
PDH
0.090
0.010
0.010
865.6
1.20
SUB
9.210
9.210
9.210
719.8
1.00
TREE
0.020
0.020
0.020
922.4
1.88
Tabla 5.6: Resultados competici´on - Map Set: Random
Map Set: Rooms Time (ms)
Length
Total
Max
20
Total
%
PDH
0.074
0.008
0.010
719.2
1.20
SUB
0.095
0.095
0.095
606.9
1.00
TREE
0.013
0.013
0.013
1012.8
2.49
Tabla 5.7: Resultados competici´on - Map Set: Rooms
Se han marcado en negrita los resultados no dominados. Nos quedamos muy satisfechos de ver que nuestro agente se ha comportado en la competici´on de forma similar a los resultados obtenidos en nuestras pruebas y en muchas categor´ıas no ha quedado dominado.
53
Cap´ıtulo 6
Conclusiones En este cap´ıtulo repasamos los objetivos propuestos en 3, analizando en qu´e medida se han cumplido, para terminar indicando algunas conclusiones adicionales.
6.1. 6.1.1.
Objetivos Desarrollar un agente de pathfinding para la GPPC
El objetivo principal de este proyecto era la de desarrollar un agente para participar en la Grid-Based Path Planning Competition. Podemos dar este objetivo por conseguido ya que conseguimos entregar una soluci´on a la competici´on sin que diera ningun fallo y que adem´as qued´ o entre los ganadores al no resultar dominada.
6.1.2.
Reducir el espacio de b´ usqueda
Hemos conseguido implementar un algoritmo para transformar el conjunto del espacio de b´ usqueda en un subconjunto de regiones que nos ha permitido reducir el tiempo de b´ usqueda. Es especialmente interesante de cara a los primeros movimientos que debe realizar el agente, ya que podemos devolver una serie de acciones que inician la marcha del agente en direcci´on a la meta, pudiendo luego refinar la b´ usqueda para obtener mejores caminos. Nos habr´ıa gustado poder dedicar m´ as tiempo a este planteamiento.
6.1.3.
Algoritmo de b´ usqueda
Al hacer uso de los portales entre regiones y de las direcciones precomputadas conseguimos devolver un camino en muy poco tiempo. Nos habr´ıa gustado disponer de tiempo para 54
´ Alvaro Parra de Miguel
Cap´ıtulo 6. Conclusiones
experimentar con otros tipos de estructuras para guiar la b´ usqueda y con t´ecnicas para reducir la longitud de los caminos una vez se han obtenido.
6.1.4.
Entorno gr´ afico de pruebas
Hemos desarrollado un entorno gr´afico de pruebas ad hoc para depurar la traza de los algoritmos en tiempo de ejecuci´ on. Ha sido de vital importancia a la hora de desarrollar el c´odigo porque nos ha permitido detectar y corregir de forma muy sencilla y r´apida los fallos que se han ido generando durante el proyecto.
6.2.
Conclusiones finales
Hemos quedado muy satisfechos con el resultado obtenido en la Grid-Based Path Planning Competition de 2012 por parte de nuestro agente Bubble Dragon. No solo no ha quedado dominado en ninguna de las tres categor´ıas existentes, sino que adem´as ha conseguido permanecer no dominado en las siguientes ediciones de 2013 y 20141 . Tambi´en podemos destacar la publicaci´on de un inproceeding en la conferencia International Symposium on Combinatorial Search (SoCS) dentro de la cual da lugar la competici´on de pathfinding. [Parra et al., 2012]
1
M´ as informaci´ on en Resultados GPPC
55
Cap´ıtulo 7
L´ıneas Futuras Este proyecto sirve como base para la creaci´on de un agente para la Grid-Based PathPlanning Competition y como punto de vista para resolver problemas de pathfinding con caracter´ısticas similares. Un posible desarrollo que nos parece muy interesante en vista de los resultados de la competici´on, es la de aplicar nuestra t´ecnica de agrupamiento en el subconjunto generado por el agente SUB de la competici´ on [Uras et al., 2012]. Partiendo de un subconjunto que nos permite obtener caminos ´ optimos, nos preguntamos si al aplicar nuestra t´ecnica podremos generar otro nivel en el grafo que nos permita realizar b´ usquedas en el mismo tiempo que nuestra soluci´ on actual pero obteniendo caminos m´as pr´oximos a la soluci´on ´optima.
56
Cap´ıtulo 8
Planificaci´ on y Presupuesto A continuaci´ on se especifican las partes de las que consta este proyecto, su duraci´on estimada y su duraci´ on real, justificando la diferencia que haya entre ambas. Tambi´en se hace un estudio econ´ omico del proyecto con el fin de hacer un presupuesto del mismo.
8.1.
Planificaci´ on
An´alisis de las tareas en las que se divide el proyecto, incluyendo duraci´on estimada y real, diagramas de Gantt y una justificaci´on de la desviaci´on entre lo estimado y lo real. Las tareas que componen el proyecto son:
- An´ alisis: Analizar las restricciones del proyecto y estudiar los posibles casos de uso. - Dise˜ no: Estudio de los diferentes algoritmos que se plantean utilizar. La fase de dise˜ no se prolonga en el tiempo porque se van tomando decisiones en funci´on de los resultados obtenidos en la implementaci´on. - Implementaci´ on: Se implementa un agente en lenguaje C++ siguiendo las directrices del dise˜ no. - Pruebas: Se realizan pruebas autom´aticas y manuales para verificar el buen funcionamiento de los algoritmos implementados.
57
´ Alvaro Parra de Miguel
Cap´ıtulo 8. Planificaci´ on y Presupuesto
8.1.1.
Planificaci´ on estimada
La estimaci´ on de los tiempos de las distintas partes del proyecto. Tarea
Duraci´ on
Fecha de inicio
Fecha de fin
An´ alisis
3 semanas
17/01/2012
04/02/2012
Dise˜ no
10 semanas
07/02/2012
15/04/2012
Implementaci´ on
11 semanas
21/02/2012
06/05/2012
9 semanas
07/03/2012
06/05/2012
Pruebas
Tabla 8.1: Planificaci´on estimada
Figura 8.1: Diagrama de Gantt - Planificaci´on estimada
8.1.2.
Planificaci´ on real
Duraci´on real del proyecto. Tarea
Duraci´ on
Fecha de inicio
Fecha de fin
An´ alisis
3 semanas
17/01/2012
04/02/2012
Dise˜ no
13 semanas
07/02/2012
06/05/2012
Implementaci´ on
13 semanas
21/02/2012
20/05/2012
Pruebas
11 semanas
07/03/2012
20/05/2012
Tabla 8.2: Planificaci´on real
58
´ Alvaro Parra de Miguel
Cap´ıtulo 8. Planificaci´ on y Presupuesto
Figura 8.2: Diagrama de Gantt - Planificaci´on real
Se puede apreciar un aumento en la duraci´on del proyecto respecto del tiempo estimado, esto es debido a que la fecha de entrega de la competici´on se aplaz´o dos semanas, pudiendo aprovechar ese tiempo extra para seguir mejorando el agente.
8.2.
Hardware y software usado
El equipo y software empleados para llevar a cabo el proyecto.
8.2.1.
Hardware
Portatil HP Pavilion dv6 con procesador Intel Core i3-350M a 2.26 GHz y 4GB de RAM.
8.2.2.
Software
Sistema operativo: Ubuntu 12.04 LTS Compilador: GCC Librerias gr´ aficas: SDL Editores de texto: SublimeText Composici´ on de documentos: LaTeX Edici´ on de imagenes: Gimp Edici´ on de diagramas: Gliffy Mscgen Gantto
59
´ Alvaro Parra de Miguel
Cap´ıtulo 8. Planificaci´ on y Presupuesto
8.3.
An´ alisis econ´ omico
An´alisis del coste del proyecto. El coste del proyecto se desglosa en recursos humanos y recursos de hardware, teniendo en cuenta la planificaci´on estimada y la real. No se contemplan los recursos de software porque todos los programas utilizados eran software libre.
8.3.1.
Recursos humanos
Personas que han participado en el desarrollo del proyecto.
- Experto: Asesora el rumbo de la investigaci´on. - Supervisor: Encargado de seguir el desarrollo del proyecto. - Desarrollador: Encargado de realizar el proyecto.
De media, el desarrollador ha dedicado al proyecto 10 horas semanales, el supervisor 1 hora semanal y el experto media hora semanal. Coste estimado Recurso
Coste hora
N´ umero de horas
Coste total
Experto
50e
16,5
825,00e
Supervisor
35e
33
1155,00e
Desarrollador
25e
330
8250,00e
Total
10230,00e
Tabla 8.3: Recursos humanos estimados
Coste real Recurso
Coste hora
N´ umero de horas
Coste total
Experto
50e
20
1000,00e
Supervisor
35e
40
1400,00e
Desarrollador
25e
400
10000,00e
Total
12400,00e
Tabla 8.4: Recursos humanos reales
60
´ Alvaro Parra de Miguel
Cap´ıtulo 8. Planificaci´ on y Presupuesto
8.3.2.
Recursos de hardware
En este caso solo se ha empleado un ordenador portatil para el desarrollo del proyecto. Se estima su coste seg´ un su amortizaci´on durante la duraci´on del proyecto. Coste estimado Recurso
Coste
Vida u ´ til
Tiempo de uso
Coste amortizado
700e
24 meses
7,7 meses
224,58e
Total
224,58e
HP
Tabla 8.5: Recursos hardware estimados
Coste real Recurso
Coste
Vida u ´ til
Tiempo de uso
Coste amortizado
700e
24 meses
9,3 meses
271,25e
Total
271,25e
HP
Tabla 8.6: Recursos hardware reales
8.3.3.
Resumen
Coste total estimado Recursos
Coste
Recursos humanos
10230,00e
Recursos de hardware
224,58e
Total
10454,58e
Tabla 8.7: Coste total estimado
Coste total real Recursos
Coste
Recursos humanos
12400,00e
Recursos de hardware
271,25e
Total
12671,25e
Tabla 8.8: Coste total real
Existe una desviaci´ on del 21,2 % del presupuesto estimado, esto es debido a que el proyecto se alarg´ o en el tiempo m´ as de lo esperado inicialmente. 61
Bibliograf´ıa S. Kent. The Ultimate History of Video Games: from Pong to Pokemon and beyond...the story behind the craze that touched our li ves and changed the world. Crown/Archetype, 2010. ISBN 9780307560872. URL https://books.google.es/books?id=PTrcTeAqeaEC. J.T.T. Goldsmith and M.E. Ray. Cathode-ray tube amusement device, December 14 1948. URL http://www.google.com/patents/US2455992. US Patent 2,455,992. John E. Laird and Michael van Lent. Human-level ai’s killer application: Interactive computer games. AI Magazine, 22(2):15–26, 2001. URL http://www.aaai.org/ojs/index. php/aimagazine/article/view/1558. I. Millington and J. Funge. Artificial Intelligence for Games. Morgan Kaufmann. Taylor & Francis, 2009. ISBN 9780123747310. URL https://books.google.es/books?id= 1OJ8EhvuPXAC. S. Rabin. Game AI Pro 2: Collected Wisdom of Game AI Professionals. CRC Press, 2015. ISBN 9781482254808. URL https://books.google.es/books?id=7XV3CAAAQBAJ. Daniel Borrajo, Ariel Felner, Richard E. Korf, Maxim Likhachev, Carlos Linares L´opez, Wheeler Ruml, and Nathan R. Sturtevant, editors. Proceedings of the Fifth Annual Symposium on Combinatorial Search, SOCS 2012, Niagara Falls, Ontario, Canada, July 19-21, 2012, 2012. AAAI Press. D. Chris Rayner, Michael H. Bowling, and Nathan R. Sturtevant. Euclidean heuristic optimization. In Wolfram Burgard and Dan Roth, editors, Proceedings of the TwentyFifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. AAAI Press, 2011. URL http://www.aaai.org/ocs/index. php/AAAI/AAAI11/paper/view/3594. Nir Pochter, Aviv Zohar, Jeffrey S. Rosenschein, and Ariel Felner. Search space reduction using swamp hierarchies. In Maria Fox and David Poole, editors, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010. URL http://www.aaai.org/ocs/index. php/AAAI/AAAI10/paper/view/1825. 62
´ Alvaro Parra de Miguel
Bibliography
Meir Goldenberg, Ariel Felner, Nathan R. Sturtevant, and Jonathan Schaeffer. Portal-based true-distance heuristics for path finding. In Ariel Felner and Nathan R. Sturtevant, editors, Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8-10, 2010. AAAI Press, 2010. URL http://aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2092. Nathan R. Sturtevant. Benchmarks for grid-based pathfinding. IEEE Trans. Comput. Intellig. and AI in Games, 4(2):144–148, 2012. doi: 10.1109/TCIAIG.2012.2197681. URL http://dx.doi.org/10.1109/TCIAIG.2012.2197681. Kenneth Anderson. Tree cache. In Borrajo et al. [2012]. URL http://www.aaai.org/ocs/ index.php/SOCS/SOCS12/paper/view/5410. Tansel Uras, Sven Koenig, and Carlos Hern´andez. Subgoal graphs for eight-neighbor gridworlds. In Borrajo et al. [2012]. URL http://www.aaai.org/ocs/index.php/SOCS/ SOCS12/paper/view/5391. ´ ´ Alvaro Parra, Alvaro Torralba Arias de Reyna, and Carlos Linares L´opez. Precomputeddirection heuristics for suboptimal grid-based path-finding. In Borrajo et al. [2012]. URL http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5386.
63