Bitacora

• Pathfinding

Apuntes

Pathfinding

A*

Similar al BFS pero con un heuristico

• Heuristico: toma decisión de que ruta seguir según información previa. Puede no ser la mas corta, pero es mas rápido

Similar al Dijkstra, estima que tan cerca esta cada nodo de la meta

Incorpora pococ a poco los nodos a la solucion

Eficiente y rápido

Muy usado en la programación de videojuegos

open list : lista de nodos pendientes de evaluar

close list: nodos posibles de la ruta final. Cada nodo debe decir de donde vino

Como funciona

• Mete el nodo de inicio a la open list
• Agrega los nodos adyacentes a este
• Elimina el punto inicial de la open-list y lo agrega a la close-list
• Escoge el que tenga un valor F menor, para volver a empezar
• En el momento que la meta este en un adyacente, el algorimo para y calcula con los nodos de la close list
• (Se puede agregar la posibilidad de movimientos diagonales)

Formula

F= G + H

• G: costo de moverse desde un punto dado a otro
  • Se debe asignar costos para los movimientos horizontales/verticales y diagonales
  • Cada nuevo paso se le debe sumar cuanto le tomo llegar ahí
• H: costo estimado de todas las posiciones al final

Formas de calcular H

Distancia de euclides

• dx = targetX-currentX
• dy = targetY-currentY
• H = sqrt