|
|
Por Patrick Lester ( Actualizado el 2 de Marzo del 2003)
Versión
imprimible del documento --->
Este artículo es un anexo al artículo principal, “A* Pathfinding para Principiantes”
Como habrás visto en el artículo principal, hay varias maneras en las que puedes calcular la heurística en A*. Se describen unas pocas aquí. También deberías leer los enlaces que aparecen al final de esta página.
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)
end if
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 mira:
Versión
imprimible del documento --->
Traducido por Elthan, con el permiso de Patrick Lester. www.elthanart.tk
|
|
elthan art 2004 ® {=bleu_sur_blanc} IE 1024 x 768 |
|
