Investigación y Posgrado

Sitios de Interés

Logo Uncoma UNCOMA
Logo Pedco PEDCO
Logo SIU SIU Guaraní
Logo Correo Correo electrónico FAI
Logo facebook FAI en Facebook
Logo Twitter FAI en Twitter  
boton telegram FAI en Telegram

En caso de emergencia médica dentro del Campus llamar a

sien

Teléfono: 107

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.

 

Foto del día de la defensa con su tutora y el tribunal integrado por los profesores Dra. Nadina Martínez Carod y Mg. Gerardo Parra

Foto del dia de la defensa  

Ver otras tesis FaI ]