Razón Artificial

La ciencia y el arte de crear videojuegos

Heurística para el Pathfinding A*

Escrito por adrigm el 3 de abril de 2010 en Inteligencia Artificial, Noticias, Programación | 1 Comentario.

Como habrás visto en el artículo de Pathfinding, hay varias maneras en las que puedes calcular la heurística en A*. Se describen unas pocas aquí. También deberías leer el enlace que aparece al final.

Método Manhattan

Este es el método usado en el artículo principal. Su principal ventaja es que normalmente alcanzas el objetivo más rápido que en la mayoría de alternativas. Su mayor inconveniente es que está sobrecargado en comparación con G y por lo tanto reducirá cualquier pequeño modificador que intentes añadir al cálculo, es decir, una penalización de giro o un modificador tipo mapa de influencia. Si no vas a tener en cuenta estas cosas, este método es probablemente tu mejor opción. La ecuación, donde abs= valor absoluto, es:

H = 10*(abs(Xactual-Xdestino) + abs(Yactual-Ydestino))

Atajo Diagonal

Este método equilibra H y G. Su principal ventaja es esa, ya que al estar equilibrado, es completamente capaz de considerar pequeños modificadores como penalización de giro o un modificador de mapa de influencia. Es un poco más lento que el método anterior. La ecuación, donde abs= valor absoluto, es:

xDistancia = abs(abs(Xactual-Xdestino)
yDistancia = abs(Yactual-Ydestino)
if xDistancia > yDistancia:
	H = 14*yDistancia + 10*(xDistancia -yDistancia)
else:
	H = 14*xDistancia + 10*(yDistancia -xDistancia)

Hay muchos otros métodos de calcular H, aunque estos sean probablemente de los más comúnmente utilizados. En general, la estimación más cercana es la distancia actual hasta el objetivo, el A* más rápido encontrará esa meta. Si sobreestimas H con respecto a la distancia actual, A* no te garantizará el mejor camino (en el argot del pathfinding, a esto se llama una “heurística inadmisible”). Por lo tanto, el truco consiste en aproximarte tanto a la distancia actual como te sea posible sin sobreestimarlo. Ambos métodos son admisibles.

Para más información: Amit’s Notes on A* Heuristics

Traducido por Elthan, con el permiso de Patrick Lester.

Un Comentario en "Heurística para el Pathfinding A*"

  1. ivan dice:

    que buena pagina amigo, en verdad que te fascina el mundo de la inteligencia artificial, me pregunto si no conoces metodos heuristicos para resolver otros problemas, como el de hanoi o el de las jarras.

    Suerte, y de nuevo fantastica pagina

Deja un comentario