Adaptación del algoritmo de pathfinding A* cooperativo para videojuegos de estrategia en tiempo real

Abstract

RESUMEN: Los algoritmos de "pathfinding" (búsqueda de caminos) son un problema clásico en la computación desde hace ya varias décadas. Dichos algoritmos han encontrado un buen número de aplicaciones en diversos campos. Ejemplos tradicionales de campos de aplicación son la robótica (trayectorias seguidas por los robots en sus desplazamientos) o los videojuegos (rutinas de navegación para el desplazamiento de los personajes y objetos sintéticos en mundos virtuales 2D y 3D). Por ese motivo, los algoritmos de "pathfinding" han formado parte de la inteligencia artificial de los videojuegos. En ese contexto, un gran componente de muchos videojuegos (por ejemplo, los juegos de estrategia en tiempo real) es el "pathfinding" cooperativo, en el cual es importante poder gestionar varios agentes a la vez en un mismo mapa. Existen distintas versiones de algoritmos que funcionan de manera cooperativa como pueden ser LRA* o WHCA*. En este proyecto de TFG se pretenden explorar las ideas iniciales de la publicación original de David Silver sobre "Cooperative A*". Aunque ya se ha avanzado en este tema, el algoritmo presenta aún varios problemas, cuya soluciones y limitaciones no están claramente descritas en la literatura. Por ello, se propone una visión propia investigando y realizando pruebas y análisis de las ideas originales propuestas en esta publicación, así como una implementación propia del algoritmo y la incorporación de las modificaciones que veamos necesarias para un mejor funcionamiento.

ABSTRACT: Pathfinding algorithms have been a classical computational problem for various decades. These algorithms have been applied to solve various problems in a wide range of fields. A traditional example is robotics (the path that a robot should follow when moving) or videogames (navigation routes for playing or non-playing character and moving synthetic objects through 2D and 3D environments). Owing to these reasons, pathfinding algorithms have taken a big presence in videogame artificial intelligence development. In this context a huge component of many videogames (for example, real strategy games) is cooperative pathfinding, which is important to control many agents at the same time in a map. There are various versions of cooperative algorithms like LRA* or WHCA*. In this final degree project, we pretend to explore the initial ideas from David Silver about “Cooperative A*”. Although this field has been progressing, it still has some problems, which were not clear in the literature. Taking this into account, we propose our own version of the algorithm investigating, doing some testing and analyzing the originals ideas proposed in this publication unified with our own implementation of the algorithm and the needed modifications, for better performance.