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.