Implementación

Veremos ahora, como realizar la implementación del algoritmo A* para resolver un problema de búsqueda de caminos (el algoritmo A*, como cualquier otro algoritmo de búsqueda en grafos, puede resolver una gran cantidad de problemas que nada tienen que ver con pathfinding).

Por lo tanto, si deseáramos hacer una implementación general deberíamos tener en cuenta dos cosas: la generalidad del problema a resolver (no sólo pathfinding) y la generalidad del algoritmo a utilizar (no sólo A*). Aquí comenzaremos utilizando un diseño menos flexible para simplificar el diagrama de clases.

El diagrama de clases

La clase List

Representa una lista enlazada. Puede ser una implementación propia o de STL (en caso de estar desarrollando la solución con C++).

La clase AStar

Representa el algoritmo A*. Al momento de su instanciación crea dos listas (nodos abiertos, y nodos cerrados). En implementaciones más generales podría ser una subclase de una implementación general de algoritmos de búsqueda en grafos.

La clase Map2D

La clase Map2D representa el mapa por el cual se intentará resolver el problema. Dicho mapa puede o no poseer información por casillero (si todas las posiciones poseerán el mismo costo, podría almacenarse sólo una lista de obstáculos).
Luego, se relaciona el algoritmo con el mapa sobre el cual se desarrollará.

El método Resolve

Como se puede apreciar en el diagrama anterior, el método recursivo Resolve intenta realizar lo siguiente:

• Busca todas las movidas posibles desde la posición actual que se recibe como parámetro que no se encuentren ya en la lista cerrada.
  -> Para cada una de estas movidas posibles verifica si dicho movimiento ya se ha realizado (es decir, si el nodo se encuentra en la lista abierta).
  -> Si el nodo está en la lista abierta y además, el costo nuevo es menor que el existente, entonces realiza una actualización de costos y de padre.
  -> Si el nodo no fue hallado en la lista abierta, entonces lo inserto en la misma.
• Si la lista abierta está vacía, entonces no existe camino a la solución. Retorna false y termina la ejecución del algoritmo.
• Toma el mejor nodo de la lista abierto (que como está ordenada es el primero).
• Inserta el nodo en la lista de nodos cerrados.
• Verifica si el nodo es la meta. Si es así, finaliza la ejecución del algoritmo retornando true.
• De otro modo, se invoca nuevamente el método Resolve con el nodo tomado recientemente de la lista abierto como parámetro.

¿Donde está el camino a la solución?

Si el método Resolve finaliza retornando true, entonces se ha hallado el camino a la meta, que es el mejor (más corto si todos los costos son unitarios o con mejor costo si no es así). Los nodos que forman parte del camino a la meta se encuentran en la lista cerrada, pero no tienen porque ser todos ellos. Por lo tanto, para recuperar el camino a la meta tomaremos el último nodo insertado en la lista de nodos cerrados y luego por medio de la propiedad del nodo que indica cuál es su padre iremos haciendo el camino inverso hacia el nodo de partida.

La totalidad de los nodos visitados es la cantidad de nodos de la lista abierta (los que queden al finalizar el algoritmo) y la cantidad de nodos de la lista cerrada. Aunque realmente se pudieron abrir más nodos que por estar ya en la lista abierta no finalizaron insertados en ninguna de ellas.

Espero que este artículo les haya resultado de utilidad.

~fuzzyLogic

Pages: 1 2 3

Comentarios (1)