Simulacion

Algoritmos de búsqueda heurística en tiempo real.
Aplicación a la navegación en los juegos de vídeo.

Resumen
Este trabajo se inició en el marco de un curso de intro d u cción al análisis y
diseño de algorit m o s, dictado en el 2º año de una carrera de infor m á tica. La
motivación fue estudiar cómo se extien de n los concep to s básicos de búsq ue d a
para adapta rlos a los requeri mient o s de los siste ma s de tiemp o real. Como
caso de estudio se eligió la navegación en los juegos de vídeo, por ser un
proble m a que se resuelve natural m e n t e median t e la búsq ue d a. Se consideran
los juegos en tiempo real en los que el entorn o es dema siad o grande o el
terreno

es diná mico, de modo que las estrategias básicas de búsq ue d a

resulta n inadecua da s. En estecontexto, se analiza n e imple me n t a n algorit m o s
de búsque da heurística en tiem p o real los cuales fueron concebidos para
resolver problem a s con estas características.

1. Introducción
La consta n te evolución de los juegos de vídeo ha llevado a que la inteligencia artificial
constit uya uno de los aspectos más impo rta n t e s; es funda m e n t al que los agente s
(entida de sautóno m a s)

controla do s

por

la comp u t a d o r a

se comp o r te n

en forma

inteligente. Un proble ma característico es la navegación , que consiste en deter min a r el
camino más conveniente entre una posición inicial y una posición de destin o. Si bien el
planteo del proble ma es sencillo, el mis mo está lejos de ser trivial debido a la creciente
complejida d de losentor nos simulad o s y los requeri mie n t o s de tiemp o real de los juegos
moder n os [Nareyek - 04 ].
La búsque da es una de las técnicas más utilizada s para resolver los proble ma s de
pathfinding 1 o planificación que se presen ta n en la inteligencia artificial en los juegos de
vídeo. En particular, la búsque da es utiliza da para resolver el proble m a de la navegación.
De los distintostipos de algorit m o s de búsq ue d a (figura 1 ), los algorit m o s búsq ue d a
heurística completa se encuentr a n amplia me n te difun did o s. Sin dudas, el algorit m o A* es
el algorit m o de búsque da heurística más popular [Stout - 96 ].
1 Es importante mencionar una ambigüeda d en la utilización del término pathfinding en la bibliografía referenciada.
Pathfinding se utiliza para hacerreferencia tanto al problema general de encontrar una serie de pasos para llegar a un estado
objetivo partiendo de un estad o inicial, en el contexto de un problema cualquiera, como al problema específico de la
navegación.

Los algorit m o s heurísticos tradicionales mues tra n limitacione s impor ta n t e s cuan do el
espacio

de

búsque da

es demasia d o

grande

o existenfactores

diná micos.

En la

navegación, de los juegos de vídeo en tiemp o real, este proble ma aparece cuan do las
rutas a deter mina r son muy largas, el terreno es modificable o existen muc ho s objeto s
móviles. Bajo esas condiciones, los algorit m o s de búsq ue d a básicos no puede n respo n d e r
en el tiempo requerido y resulta n inadecua d o s. De esta forma, surge la necesida dde
desarrollar nuevas estrat egias de búsq u e d a, que se adap te n a los requeri mie n t o s de
tiempo real de los juegos de vídeo y resuelvan adecua d a m e n t e caminos en condiciones
de incertidu m b r e sobre terre nos de gran extensió n [Laird,Pottinger - 00 ].
Actual me nt e existen dos clases de algorit m o s de búsq u e d a que se adecua n a la
resolución

de

problem a scon

las

características

menciona d a s:

los

algorit mo s

de

búsqueda heurística incre me ntales y los algorit m o s de búsqueda heurística en tiempo
real . Los algorit m o s increme n t ales utilizan infor mació n de búsq ue d a s previas para
encon t ra r soluciones a proble ma s similares posiblem en t e más rápido que realizan d o
cada búsque d a partie ndo de cero...