El Pathfinding consiste básicamente en encontrar un camino esquivando los obstáculos que puedan interponerse. Existen varios algoritmos que encuentran un camino. El de Dijkstra, el A* y el BFS son sólo algunos de los más importantes; siendo el A* el que obtiene el resultado óptimo en la menor cantidad de tiempo.
Pero, es bastante complicado. Por lo que estuve trabajando en un algoritmo distinto que fuera más fácil de entender.
Básicamente, tenemos un área con distintos nodos interconectados que forman un grafo. Para movernos entre los nodos lo que hacemos es simplemente convertir el grafo en un tree expandiendo desde el nodo inicial hasta llegar al destino. Una vez que lo alcanzamos, recorremos el tree hacia arriba hasta encontrar el nodo inicial. Lo que obtenemos es el camino invertido (nos podríamos ahorrar el paso de invertir el camino si comenzamos a expandir desde el destino hasta encontrar el punto de partida).
En realidad, el sistema es bastante similar al algoritmo de Dijkstra, pero más fácil de entender. Encuentra siempre el camino que requiere recorrer menos nodos.
Pueden ver un ejemplo de su funcionamiento aquí (seleccionen el nodo haciendo click en él y luego hagan click en el destino).
Pueden descargar el .fla aquí.
No hay comentarios:
Publicar un comentario