Comparación de algoritmos de pathfinding

Abstract

El problema de la búsqueda de caminos o pathfinding es muy recurrente en el mundo de los videojuegos. Estos en muchas ocasiones, tienen personajes que ya sea el jugador o la máquina determinan hacia adonde tienen que ir y estos deben moverse con una ruta relativamente realista, por lo que necesitamos que el coste computacional de la búsqueda de caminos sea el menor posible. Este Trabajo Fin de Grado se centrará en el estudio, implementación y aná lisis de diferentes algoritmos de pathfinding para videojuegos. De esta manera, determinaremos cuál es el más rápido entre los comparados o cuál tiene menos coste computacional, además sirve como ampliación a los contenidos sobre path finding de la asignatura ”Inteligencia Artificial para Juegos” que he estudiado en este grado. Se han estudiado e implementado 3 algoritmos: A*, HPA* y JPS, además de una interfaz gráfica para su ejecución. Se ha escogido A* como algoritmo de referencia y HPA* y JPS por ser algoritmos que mejoran el rendimiento de A*. HPA* aunque no obtenga el camino más corto, obtendrá buenos resultados en menos tiempo que A*. JPS por su parte, que es una modificación de A*, para explotar cualidades de los mapas con mallas de 8 vecinos. Se ha desarrollado una aplicación para facilitar la interacción con los algorit mos mencionados anteriormente. La aplicación contiene 4 pestañas. Las 3 prime ras sirven para ejecutar los algoritmos A*, HPA* y JPS respectivamente, y la última contiene las comparaciones de estos algoritmos. Además se ha añadido un manual que explica el uso de la aplicación y la implementación de nuevas funcionalidades.