Guenas.

Hace tiempo comenté en el foro algunas rutinas de IA para buscar caminos. Con el tiempo y días de aburrimiento creo que he conseguido una implementación decente y equilibrada entre la eficiencia en tiempo y memoria. Agradecería mucho que publicarais vuestras críticas y mejoras.

Es una búsqueda basada en el algoritmo A* . La mayor parte de implementaciones que he visto son bastante cerradas y están pensadas para rejillas cuadradas o hexagonales.

Esta implementación es agnóstica respecto a la estructura del grafo ya que usa un modelo libre indexado para la representación de los nodos. Cada nodo (posición, localización) esta identificado por un int.

El modelo usa los siguientes métodos para trabajar:

int[] getSucesores(int nodo) :
Devuelve un array con los indices de todos los nodos vecinos, es decir todos los nodos en contacto directo a los cuales nos podemos mover.

float getCosteFijo(int nodo) :
Devuelve el coste fijo que va asociado a pisar un nodo concreto. Permite establecer unos nodos mas difíciles de pisar que otros. Por ejemplo un terreno llano, boscoso, ...

float getCosteSucesor(int nodo, int sucesor) :
Devuelve el coste desde un nodo hasta el vecino seleccionado.
Este coste solo debe contemplar el movimiento de un nodo al otro. Útil para definir distintos costes según la dirección del movimiento. Pasar desde un nodo A a su vecino B puede tener mas coste que pasar de un nodo B a su vecino A. Es decir, puede ser mas caro subir una montaña que bajarla.

float getCosteHeuristico(int nodo, int destino) :
Este método va a representar el coste que estimamos para llegar desde el nodo A al nodo B. No tiene porque ser exacto pero cuanto mas exacto mas eficiente sera el algoritmo. Es indispensable que aunque no sea exacto siempre sea menor que el coste real. Un método valido puede ser por ejemplo la distancia euclidea.

boolean isTransitable(int nodo) :
Es un método de ayuda. Permite que sin modificar la lista de vecinos de un determinado nodo se ignore uno de los nodos si este método devuelve false.

El código lo publico a continuación:

/**
* El Algoritmo de busqueda de caminos AStar utiliza un sistema de nodos indexado, lo que permite
* usar cualquier estructura, no solo rejillas cuadradas sino tambien hexagonales, triangulares,
* tedraedricas, n-dimensionales, etc
*
* Los nodos se identifican con un valor entero que representa un indice entre 0 y nº de nodos -1
*
*/
public interface AStarMapa {

/**
* Devuelve un array con los nodos vecinos de un determinado nodo
*/
int[] getSucesores(int nodo);

/**
* Devuelve el coste fijo que va asociado a un nodo concreto.
* Permite establecer unos nodos mas dificiles de pisar que otros. Por ejemplo
* un terreno llano, boscoso, pantano, ...
*/
float getCosteFijo(int nodo);

/**
* Devuelve el coste asociado a desplazarse desde un nodo a otro vecino
* Permite establecer algunas direcciones mas caras que otras. Por ejemplo subir
* desde un terreno llano a una montaña puede ser mas caro que bajar de ella.
*/
float getCosteSucesor(int nodo, int sucesor);

/**
* Devuelve el coste estimado hasta el destino.
* Este coste debe ser ligeramente inferior al que realmente tendra con la suma de los costes fijos
* mas los costes de desplazamiento.
*/
float getCosteHeuristico(int nodo, int destino);

/**
* Devuelve false si el nodo no puede atravesarse
*/
boolean isTransitable(int nodo);
}

***************************************************************************************************
import java.util.BitSet;

public class AStar {

/**
* Gestiona arrays de int dinamicos. Los utiliza internamente el calculo de caminos. Su principal objetivo es la optimización del proceso con un consumo moderado de memoria.
*
*/
public static class DinInt {

int sizeArray = 11;
int[] arr;

/**
* Constructor
*/
public DinInt() {
arr = new int[sizeArray];
}

/**
* Actualiza el elemento de indice idx con el valor x
* Si el array es mas pequeño que el indice se incrementa el tamaño del array.
*
* @param idx
* @param x
*/
public void set(final int idx, final int x) {
if (idx >= sizeArray) {
resize(idx + 1);
}
arr[idx] = x;
}

/**
* Se obtiene el valor el elemento de indice idx.
* Si el array es mas pequeño que el indice se devuelve 0, sin alterar el tamaño del array.
*
* @param idx
* @return
*/
public int get(final int idx) {
if (idx >= sizeArray) {
return 0;
}
return arr[idx];
}

/**
* Modifica el tamaño del array para incluir como minimo hasta el elemento indice.
* Este metodo puede ser lento ya que realiza una copia de todos los elementos del
* array y tiene un rendimiento O(n).
* Para tratar de optimizar su uso tratara de hacer incrementos superiores al necesario
* lo que puede llevar a un mayor consumo de memoria.
*
* @param indice
*/
protected void resize(final int indice) {
synchronized (this) {
int oldCapacity = sizeArray;
int newSize = oldCapacity + (oldCapacity >> 1);
if (newSize <= indice) {
newSize = indice;
}
int[] tmp = new int[newSize];
System.arraycopy(arr, 0, tmp, 0, sizeArray);
arr = tmp;
sizeArray = newSize;
}
}

}

/**
* Gestiona arrays de float dinamicos. Los utiliza internamente el calculo de caminos. Su principal objetivo es la optimización del proceso con un consumo moderado de memoria.
*
*/
public static class DinFloat {

int sizeArray = 11;
float[] arr;

/**
* Constructor
*/
public DinFloat() {
arr = new float[sizeArray];
}

/**
* Actualiza el elemento de indice idx con el valor x
* Si el array es mas pequeño que el indice se incrementa el tamaño del array.
*
* @param idx
* @param x
*/
public void set(final int idx, final float x) {
if (idx >= sizeArray) {
resize(idx + 1);
}
arr[idx] = x;
}

/**
* Se obtiene el valor el elemento de indice idx.
* Si el array es mas pequeño que el indice se devuelve 0, sin alterar el tamaño del array.
*
* @param idx
* @return
*/
public float get(final int idx) {
if (idx >= sizeArray) {
return 0;
}
return arr[idx];
}

/**
* Modifica el tamaño del array para incluir como minimo hasta el elemento indice.
* Este metodo puede ser lento ya que realiza una copia de todos los elementos del
* array y tiene un rendimiento O(n).
* Para tratar de optimizar su uso tratara de hacer incrementos superiores al necesario
* lo que puede llevar a un mayor consumo de memoria.
*
* @param indice
*/
protected void resize(final int indice) {
synchronized (this) {
int oldCapacity = sizeArray;
int newSize = oldCapacity + (oldCapacity >> 1);
if (newSize <= indice) {
newSize = indice;
}
float[] tmp = new float[newSize];
System.arraycopy(arr, 0, tmp, 0, sizeArray);
arr = tmp;
sizeArray = newSize;
}
}

}

/**
* Gestiona la lista de nodos pendientes de procesar.
* Es una cola prioritaria que ofrece acceso directo a un elemento
* para poder actualizarlo en prioridad.
*
*/
private static class ListaAbierta {

int size = 0;
final DinInt lista;
final DinInt locLista;
final DinFloat costeF;

/**
* Constructor
*
* @param costeF
*/
public ListaAbierta(final DinFloat costeF) {
super();
size = 0;
lista = new DinInt();
locLista = new DinInt();
this.costeF = costeF;

}

/**
* Añade un nuevo nodo y reordena.
*
* @param nodo
*/
public void push(final int nodo) {
size += 1;
lista.set(size, nodo);
locLista.set(nodo, size + 1);
fixup(size);
}

/**
* Extrae el siguiente nodo mas prometedor de la cola.
*
* @return
*/
public int pop() {

int nodoAct = lista.get(1);
locLista.set(nodoAct, 0);
lista.set(1, lista.get(size));
locLista.set(1, 2); // Siempre size+1
lista.set(size, -1);
size -= 1;
if (size > 1) {
fixdown(1);
}
return nodoAct;
}

/**
* Intenta llevar la posicion indicada hacia la posicion mas prioritaria.
*
* @param k
*/
public void fixup(int k) {
int j;
int tmp;

while (k > 1) {
j = k >> 1;
if (costeF.get(lista.get(j)) <= costeF.get(lista.get(k))) {
break;
}

tmp = lista.get(j);
lista.set(j, lista.get(k));
lista.set(k, tmp);

locLista.set(lista.get(j), j + 1);
locLista.set(lista.get(k), k + 1);
k = j;
}
}

/**
* Intenta llevar la posicion indicada hasta la posicion menos prioritaria.
*
* @param k
*/
public void fixdown(int k) {
int j;
int tmp;

while (true) {
j = k << 1;
if (!((j <= size) && (j > 0))) {
break;
}

if ((j < size) && (costeF.get(lista.get(j)) > costeF.get(lista.get(j + 1)))) {
j += 1;
}

if (costeF.get(lista.get(k)) <= costeF.get(lista.get(j))) {
break;
}

tmp = lista.get(j);
lista.set(j, lista.get(k));
lista.set(k, tmp);

locLista.set(lista.get(j), j + 1);
locLista.set(lista.get(k), k + 1);
k = j;
}
}

/**
* Comprueba si un determinado nodo se encuentra en la lista.
*
* @param nodo
* @return
*/
public boolean existe(final int nodo) {
return (locLista.get(nodo) > 0);
}

/**
* Trata de mover un nodo hasta una posicion mas prioritaria.
*
* @param nodo
*/
public void reordena(final int nodo) {
fixup(locLista.get(nodo) - 1);
}

/**
* Comprueba se la lista esta vacia.
*
* @return
*/
public boolean isVacia() {
return size == 0;
}
}

protected AStar() {
super();
}

/**
* Permite obtener uno de los caminos mas cortos entre una posicion de origen y una de destino.
* El mapeado puede ser de cualquier numero de dimensiones y distintos costes segun distintas
* direcciones.
* El parametro mapa es el que define las caracteristicas del mapeado
*
* @param origen int Indice de la posicion origen
* @param destino int Indice de la posicion destino
* @param mapa AStarMapa Gestor del mapeado.
*
* @return int[] Indices de los nodos atravesados desde origen hasta destino, ambos incluidos
*/
public static int[] getCaminoIndexado(final int origen, final int destino, final AStarMapa mapa) {
final BitSet cerrada = new BitSet();
final DinFloat costeF = new DinFloat(); // Coste acumulado desde el origen + coste heuristico hasta el destino
final DinFloat costeG = new DinFloat(); // Coste acumulado desde el origen
final DinInt padre = new DinInt(); // padre del nodo
final ListaAbierta abierta = new ListaAbierta(costeF);
int nodoAct = 0;
boolean encontrado = false;

// Si el nodo origen o destino no son transitables es imposible encontrar un camino
if (!(mapa.isTransitable(origen) && mapa.isTransitable(destino))) {
return new int[0];
}

// Coloca el nodo origen que iniciara el proceso
costeG.set(origen, mapa.getCosteFijo(origen));
costeG.set(origen, costeG.get(origen) + mapa.getCosteHeuristico(origen, destino));
abierta.push(origen);

while (!abierta.isVacia()) {
nodoAct = abierta.pop();
cerrada.set(nodoAct);
if (nodoAct == destino) { // Se ha encontrado la solucion
encontrado = true;
break;
}
int[] sucesores = mapa.getSucesores(nodoAct); // Obtiene sucesores
for (int suc : sucesores) {

if (cerrada.get(suc)) {
continue; // Si ya esta explorado lo ignora
}
if (!mapa.isTransitable(suc)) {
continue; // Si no es transitable lo ignora
}
float newG = costeG.get(nodoAct) + mapa.getCosteFijo(suc) + mapa.getCosteSucesor(nodoAct, suc);
if (abierta.existe(suc)) { // Si ya esta en abierta
if (newG < costeG.get(suc)) {
padre.set(suc, nodoAct);
// actualiza costeF
float tmp = costeF.get(suc);
tmp -= costeG.get(suc);
tmp += newG;
costeG.set(suc, newG);
costeF.set(suc, tmp);
abierta.reordena(suc);
}
} else {
costeG.set(suc, newG);
costeF.set(suc, newG + mapa.getCosteHeuristico(suc, destino));
padre.set(suc, nodoAct);
abierta.push(suc);
}
}
}

if (!encontrado) {
return new int[0];
}

int cta = 0;
int nn = nodoAct;

// Cuenta los nodos
do {
cta++;
nn = padre.get(nn);
} while (nn != origen);

// Carga el array con los nodos que forman el camino
cta++;
int[] retorno = new int[cta];
nn = nodoAct;
do {
cta--;
retorno[cta] = nn;
nn = padre.get(nn);
} while (nn != origen);
retorno[0] = origen;

return retorno;
}
}

Espero que os resulte util.

Salut,
Paposo