[en] This Bachelor Thesis explores one of the less technologically advanced videogame elements: artificial intelligence. It often is a task which draws more computational power from CPU than other elements. For this reason, developers have tried to minimize its execution time making it less complex and using less elements ingame which use it. In this Project, we try to use the GPU, which is already the main computer component used by a videogame, to move compute load from CPU to GPU. We want to open a way to create complex AIs or manage a greater number of AI instances with this change. One of the most used algorithms in the AI field is the A* search algorithm. It is a pathfinding tool. In a videogame, usually the computer moves several units across the map and it is there where A* is used. Moreover, A* search is a non recursive algorithm and it has been widely studied, therefore is a fantastic candidate for our Project. We will work with the OpenCL specification to implement algorithms in GPU. The biggest GPU manufacturing companies have agreed to follow and implement in their devices this specification. We study which ways we can take advantage of the large number of threads a GPU spawns for our A* search algorithm. After several implementations have been coded, we notice that a hybrid implementation where critical spots of the algorithm are parallelized (specifically, node expansion) in GPU outputs a great speedup of the search A* execution time. We hope that thanks to this kind of studies about algorithms widely used in videogames and accessibility to program in GPU there will be videogames deeper and more complex in the near future.

[es] Este Trabajo Fin de Grado trata de explorar uno de los aspectos que menos avance tecnológico ha sufrido dentro de los videojuegos en comparación a otros elementos del mismo: la inteligencia artificial. Siendo una de las tareas que más cómputo en el procesador consume, se ha tratado de minimizar su tiempo de proceso haciéndola más simple y usando menos elementos que la requieran. En este trabajo buscamos ayudarnos de la GPU, componente principal en la ejecución de videojuegos, para repartir la carga del cálculo de la inteligencia artificial entre ella y el procesador de manera que, en un futuro, pueda ser posible la creación de IAs más complejas o manejo de un mayor número de instancias de ellas dando lugar a videojuegos más interesantes. Uno de los algoritmos más utilizados en este ámbito es la búsqueda A*. Éste es usado como un recurso para pathfinding. Es usual que, en un videojuego, necesitemos que el ordenador mueva varias unidades con una determinada IA a través de un mapa. Además, la búsqueda A* es un algoritmo no recursivo y ampliamente estudiado, por lo que es un candidato ideal para nuestro desarrollo. Para implementar algoritmos en GPU haremos uso de la especificación OpenCL que distintas manufactureras de GPUs se han comprometido a implementar en sus dispositivos. Está especificación nos permite comunicarnos con la GPU de manera sencilla y general, sin la necesidad de usar elementos gráficos. Buscamos de qué maneras es posible hacer uso la gran cantidad de hilos de la GPU con el algoritmo A*. Después de la codificación de varias implementaciones, observamos que una implementación que hace uso de la GPU en las partes críticas del algoritmo (más concretamente en la búsqueda A*, en la expansión de nodos) produce una enorme aceleración del tiempo de ejecución de la búsqueda. Esperamos que, en un futuro cercano, gracias a este tipo de estudios sobre algoritmos ampliamente usados en IAs de videojuegos y la creciente accesibilidad a la programación en GPU, pueda usarse este potente dispositivo para este tipo de propósitos y obtener videojuegos con mayor profundidad y complejidad.