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.