Descripción algorítmica del algoritmo de búsqueda A*

Función A*(inicio, destino)

var cerrada:= conjunto vacío

var q := make_queue(ruta(inicio))

Cuando q no está vacío

var p := remove_first(q)

var x:= p El último nodo de

Si x está cerrado

Continuar

Si x = objetivo

Devolver p

Agregar x a cerrado

Cada y(x) en el sucesor

Cola(q,p,y)

Devolución fallida Un* cambio La capacidad de comportarse por sí mismo es basado en una función de coste heurística, que es muy útil en los juegos. El equilibrio entre velocidad y precisión hará que tu juego se ejecute más rápido. En muchos juegos no es necesario encontrar la ruta óptima, sólo una aproximación. Lo que necesitas depende de lo que esté sucediendo en el juego o de qué tan rápida sea la máquina que ejecuta el juego. Supongamos que tu juego tiene dos terrenos: llanuras y montañas. El coste de moverse en las llanuras es 1 y el coste de moverse en las montañas es 3. Entonces el algoritmo de la estrella A pensará que la distancia en las llanuras puede ser tres. veces el de las montañas para realizar una búsqueda equivalente. Esto se debe a que puede haber un camino desde la llanura hasta la montaña. Establecer la distancia de evaluación entre dos puntos adyacentes en 1,5 puede acelerar el proceso de búsqueda de A*. Entonces A* comparará 3 y 1,5, que no es peor que comparar 3 y 1. Sin embargo, a veces puede ser mejor subir la montaña que dar vueltas hasta la base. Por lo tanto, dedicar más tiempo a buscar algoritmos para moverse por las montañas no siempre es confiable. Nuevamente, para lograr este objetivo, puede hacer que el algoritmo de la estrella A se ejecute más rápido reduciendo el comportamiento de búsqueda en la parte inferior de la colina. Esta debilidad puede ajustar el costo de acción de montaña del algoritmo de la estrella A de 3 a 2. Ambos métodos darán una sólida estrategia de acción.