Heurística para el Pathfinding A*
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.
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