Investigación: Algoritmo A* Pathfinding El algoritmo de búsqueda A* se usa para encontrar un camino desde un nodo inicial a un nodo meta, utilizando un conjunto de soluciones parciales, de las cuales se elige la mejor mediante una comparación de costos estimados.
El área de búsqueda
El usar una cuadrícula para representar relaciones espaciales facilita el desarrollo del algoritmo, pues los movimientos se limitan a verticales, horizontales y diagonales, es decir, el área de búsqueda se limita a una matriz bidimensional. Además, se podrá diferenciar entre aquellos cuadrados que representan “camino transitable” y los que representan “camino intransitable”, por ejemplo, agua o edificios.
Se almacena siempre el “cuadrado padre” de cada uno de los cuadrados que se van identificando como posibles alternativas a seguir, pues al final esto permitirá conocer los cuadrados que forman la ruta seleccionada.
La búsqueda
Se manejan los conceptos de “lista abierta” y “lista cerrada”.
La lista abierta contiene a los cuadrados que son considerados en cada uno de los movimientos.
La lista cerrada contiene a los cuadrados que no serán considerados en cada uno de los movimientos.
La búsqueda inicia con tres acciones:
- El punto inicial se agrega a la lista abierta.
- Se identifican todos los cuadrados adyacentes al punto inicial que sean transitables y se agregan a la lista abierta, con el punto de inicial como “cuadrado padre”.
- El punto inicial se quita de la lista abierta y se agrega a la lista cerrada, pues ya no será considerado (ya que se está “pisando” actualmente).
La clave para determinar qué cuadrados deben recorrerse consiste en una ecuación: F = G + H.
- “G” representa el costo mínimo de movimiento para ir desde el cuadrado actual hacia uno de los cuadrados adyacentes. Una manera de fijar un costo para los movimientos verticales y horizontales, y un costo mayor para los movimientos diagonales (matemáticamente, la raíz cuadrada de la suma de dos cuadrados del costo vertical u horizontal).
- “H” representa una suposición simplificada del costo estimado para ir desde el cuadrado adyacente seleccionado hacia el punto meta. Se puede calcular de distintas maneras, una es el método Manhattan: se ignora si los cuadrados son transitables o no, y se cuentan los costos de ir desde el cuadrado seleccionado hacia el meta, pero sólo moviéndose vertical u horizontalmente.
Para continuar la búsqueda, se elige el cuadrado cuyo valor “F” sea menor y se realiza lo siguiente:
- Se quita el cuadrado seleccionado de la lista abierta y se agrega a la lista cerrada.
- Todos los cuadrados adyacentes que sean transitables y que no estén en la lista cerrada ni en la lista abierta, se agregan a la lista abierta y el cuadrado actual se vuelve su “padre”.
- De los cuadrados adyacentes que ya estaban en lista abierta, se verifica si el nuevo camino (aquél que pasa por el cuadrado seleccionado) tiene un costo “G” menor que el que tenía anteriormente. Si lo tiene, se cambia su “cuadrado padre” al cuadrado actual, recalculando su costo “F”.
Este proceso se repite hasta que:
Se agregue a la lista cerrada el cuadrado del punto meta, en cuyo caso se ha logrado el objetivo.
No se encuentre el cuadrado del punto meta y la lista abierta está vacía (no hay más cuadrados a los que se pueda mover), en cuyo caso no existe un camino al punto meta.
Fuentes:
Lester, Patrick. A* pathfinding for beginners. Julio, 2005. http://www.policyalmanac.org/games/aStarTutorial.htm
A* search algorithm. Wikipedia. http://en.wikipedia.org/wiki/A*_search_algorithm
