Título: «Análisis y clasi cación de métodos de path finding en videojuegos»
Tesista: Patricio Biondelli
Directora: Dra. Laura Cecchi
Carrera: Licenciatura en Ciencias de la Computación
Día y lugar: 13 de diciembre de 2018
Resumen
En el contexto de la robótica, y en el de los vehículos autónomos y los videojuegos, el movimiento es un factor muy importante. Para que un personaje de videojuego o un robot pueda trasladarse desde un punto a otro, necesita de una serie de especificaciones precisas para poder tomar decisiones convenientes.
Dada una región que incluye varios obstáculos y un objeto con tamaño especificado, necesitamos encontrar un camino para el objeto desde el origen al destino.
La búsqueda de ruta, la cual se denomina pathfinding, es la forma en que un objeto encuentra un camino hacia su destino evitando obstáculos.
En la actualidad, la evolución de los videojuegos ha logrado resultados impactantes; son tan precisos y bien logrados que en la mayoría de los casos parecieran ser la vida real misma. Esto implica una complejidad adicional importante a la hora de diseñar los algoritmos de pathfinding.
En esta tesis se han estudiado diversos métodos de representación del espacio de búsqueda, como aquellos basados en grillas y grafos, y también el basado en esferas.
Las representaciones descomponen el espacio en celdas típicamente definidas por puntos, círculos, polígonos convexos o esferas y representan regiones del espacio que están libres de obstáculos. Para su análisis se consideró la posibilidad de utilizar estas técnicas en ambientes físicos o virtuales, su ajuste a entornos dinámicos y el tiempo de acceso.
Asimismo, se analizaron varios métodos de pathfinding que fueron seleccionados tomando como preferencia aquellos que están a la vanguardia, pero que también cubren diferentes tipos de paradigmas y características. De esta manera, hemos analizado métodos de pathfinding que se adaptan a entornos online y otros que pueden trabajar en entornos parcialmente desconocidos o incluso totalmente desconocidos. También, aquellos métodos cuya motivación inicial es la de mejorar la performance de A*, con interesantes propuestas de poda de caminos que pueden ser prescindibles, y otros casos en los cuales se permite a los personajes ir recolectando objetos, o lograr habilidades, para mejorar su desempeño.
Para cada método se analizaron un conjunto de características, que determinamos adecuadas al momento de la selección de una técnica, a fin de determinar si es la que se ajusta al problema que deseamos resolver.
Así, fue posible categorizar los algoritmos de pathfinding basados en ambientes de búsqueda físicos o virtuales, estáticos o dinámicos y si es posible su implementación en tiempo real, entre otros.
Para evaluar la eficiencia de tales algoritmos, se tuvo en cuenta el tiempo de ejecución, el gasto de memoria y propiedades como la optimalidad y completitud.
El relevamiento y análisis realizado en esta tesis se presenta como un punto de inicio para una revisión sistemática de este campo. Asimismo, provee a los investigadores con un marco del progreso parcial actual, que le permitirá seleccionar de entre los algoritmos relevados el que se ajuste a su desarrollo.
