IA - Búsqueda de caminos en juegos - Parte 1

Me gustaría comenzar unas pequeñas entradas acerca de diferentes técnicas de IA para usar en los juegos que podamos desarrollar, o para algún Agente que quisiéramos crear. En estas entradas las cuestiones resueltas serán sobre todo de tipo teórico, sin ver código.

El mundo de la IA es muy amplio, sin embargo, en los videojuegos las técnicas son más simples. Esto es debido, a que los mayores gastos computacionales de los juegos son gráficos. Es por este motivo que las técnicas de IA empleadas resultaran menos complejas. Sin embargo, es cada vez mayor el porcentaje de recursos destinados a nuestra IA. Ello se debe a que el papel que desarrolla la IA en los juegos está cada vez más centrado en el realismo de los personajes. Es decir, todo lo que se resuelva debe tener parecido a un comportamiento "humano". No interesan enemigos con una política fija de actuación, que una vez conocida, nos permita superar el juego con menor dificultad. Interesan personajes que aprendan en función de nuestra forma de jugar, que puedan adaptarse a nuevas situaciones en el juego, etc. Aunque no siempre se consiga este fin, podemos ver que cada vez tenemos personajes con una mayor complicación a los que enfrentarnos.

Me gustaría comenzar hablando de algo fundamental: cómo movernos en un mapa, pensando en un mapa 2 Dimensiones para estas entradas. Que nuestro mapa sea en 2D no implica que los gráficos sean 2D.

Starcraft: Juego con mapa 2D .

Y es que una parte fundamental en los videojuegos es la búsqueda de caminos para movernos por nuestro mapa. Desde los mapas estáticos, hasta los mapas dinámicos el movimiento siempre será necesario la búsqueda del camino al lugar deseado. Sin embargo, los mapas nos plantean problemas para nuestros juegos. Los principales problemas son:

• Representación de un mapa: especialmente mapas grandes
• Buscar el camino para moverme entre dos posiciones de forma eficiente.

Esta primera parte estará basada en la representación que podemos realizar de los mapas. En particular, para está primera parte comenzaremos con formas de representar más clásicas. 

Si  pensamos en "clásico"  en cuanto a utilización de mapas en juegos, lo primero que podemos pensar serán juegos de tablero. ¿Cuáles son las formas de representar mapas que se contemplan inicialmente?

• Grids

• Hexágonos

Este tipo de representación la podemos apreciar en muchos juegos, también en juegos modernos. Son formas sencillas de representación de mapas, el Grid además es muy fácil de pensar. Por otra parte los mapas hexagonales resultan también muy comunes debido a su mayor "libertad" de movimiento y una mayor facilidad para contemplar algunos movimiento. Por ejemplo, un movimiento en diagonal en un Grid (en caso de estar permitido) posee una distancia mayor que un movimiento recto, mientras que en un mapa hexagonal las celdas que podemos alcanzar desde una celda dada se encontrarán a la misma distancia.

Juego con mapa hexagonal

Para los Grids debemos tener en cuenta en que parte del grid se encontrarán los personajes. Es decir, debemos definir previamente si se situarán en los vértices de las celdas, en la cara de las celdas o en los lados de las celdas. Por lo general en los Grids situaremos a los personajes en la cara de las celdas.

Tanto en los grids como en los mapas hexagonales la representación de estos mapas se pueden realizar de dos formas diferentes:

• Mediante grafos
• Mediante Coordenadas

En la representación mediante grafos se suele representar cada celda como un nodo individual del grafo. Además cada nodo se conectará con sus vecinos accesibles mediante el movimiento. No será lo mismo un grafo en el que se permiten movimiento en diagonal que un grafo de movimientos solamente horizontales y verticales.

Además debemos tener en cuenta que pueden existir grafos dirigidos, es decir, grafos en los que podemos ir del nodo A al nodo B pero no al contrario. Por ejemplo al saltar desde gran altura no podríamos retroceder hasta la posición anterior (no se puede escalar). 

También hay que saber que la función de vecindad de un nodo a otro puede variar en función de nuestro agente (personaje). No será igual tener una unidad que pueda avanzar varias casillas de una vez, que otra que sea más pequeña y avance más lentamente pero sea capaz de cruzar lugares estrechos.

Por otra parte en las coordenadas son una representación de una matriz. Es una forma sencilla de representar cada una de las casillas. Sin embargo, para representar vecindades no homogéneas presentar problemas complicados de salvar.

En cada representación de las vecindades de cada celda debemos tener en cuenta los costes de movernos a cada casilla. Es decir, puede no ser lo mismo avanzar hacia la derecha porque tengo un pantano que hacia abajo que tengo una carretera. Además los costes pueden tener también en cuenta tipos de unidades, habilidades, etc. Es por ello que es necesario conocer la función de costes de los movimientos y poder representarlas.

Con esto finaliza la primera parte. En la segunda parte se verán otros métodos más avanzados de representación de mapas, para que, una vez finalizada la representación de mapas, pasemos a la búsqueda de caminos.

Parte 2

Importancia de la búsqueda de caminos: ¿Problemas en la búsqueda de caminos?