Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (476)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (532)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Fast A* code I  (Read 2002 times)
0 Members and 1 Guest are viewing this topic.
Offline Paposo

Senior Newbie





« Posted 2010-06-21 20:05:23 »

Hello guys.
First sorry for my bad english
I publish two versions of A* code. The first  is a very, very  fast version but consumes memory. The other is quick but in cases where the algorithm is extended in scope (no way) is slower
The algorithm works with N dimensions. Allows any type of grid and square, cubic, hexagonal, tetrahedral, etc.. Each node can have a cost distinto.Tambien allows movement in one direction more than it costs in the reverse direction (up mountains is harder than downloading them, etc.).
In my PC to find a way into a grid of 1000000 nodes needs only 15 ms. The version that requires less memory requires about 18 ms on average but can not find path to cost about 1s.
I hope you find it useful. Any improvement will be very welcome.

Bye,
    Paposo
Offline Paposo

Senior Newbie





« Reply #1 - Posted 2010-06-21 20:07:18 »

The user interface.

For use the code you  create the interface AStarMapa. This contains the heuristic and another methods.

package ia.astar;


/**
 * El Algoritmo de busqueda 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 getNumNodos()-1
 *
 */
public interface AStarMapa {
   /**
    * Devuelve el numero total de nodos que contiene la rejilla o grafo
    */
   int getNumNodos();
   
   /**
    * 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 atravesar que otros. Por ejemplo
    * un terreno llano, boscoso, pantano, ...
    */
   float getCosteFijo(int nodo);
   
   /**
    * Devuelve el coste asociado a desplazarse desde un nodo a otro.
    * 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);
}
Offline Paposo

Senior Newbie





« Reply #2 - Posted 2010-06-21 20:08:51 »

The fast but memory consuming code.

package ia.astar;

import java.util.BitSet;

public class AStar {

    // Clase que gestiona la lista abierta de Nodos
    static class ListaAbierta {

   int size = 0;
   int[] lista;
   int[] locLista;
   float costeF[];

   public ListaAbierta(float[] costeF) {
       super();
       size = 0;
       lista = new int[costeF.length];
       locLista = new int[costeF.length];
       this.costeF = costeF;

   }

   public void push(int nodo) {
       size += 1;
       lista[size] = nodo;
       locLista[nodo] = size + 1;
       fixup(size);
   }

   public int pop() {

       int nodoAct = lista[1];
       locLista[nodoAct] = 0;
       lista[1] = lista[size];
       locLista[1] = 2;            // Siempre size+1
       lista[size] = -1;
       size -= 1;
       if (size > 1) {
      fixdown(1);
       }
       return nodoAct;
   }

   public void fixup(int k) {
       int j;
       int tmp;

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

      tmp = lista[j];
      lista[j] = lista[k];
      lista[k] = tmp;

      locLista[lista[j]] = j + 1;
      locLista[lista[k]] = k + 1;
      k = j;
       }
   }

   public void fixdown(int k) {
       int j;
       int tmp;

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

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

      if (costeF[lista[k]] <= costeF[lista[j]]) {
          break;
      }

      tmp = lista[j];
      lista[j] = lista[k];
      lista[k] = tmp;

      locLista[lista[j]] = j + 1;
      locLista[lista[k]] = k + 1;
      k = j;
       }
   }

   public boolean existe(int nodo) {
       return (locLista[nodo] > 0);
   }

   public void reordena(int nodo) {
       fixup(locLista[nodo] - 1);
   }

   public boolean isVacia() {
       return size == 0;
   }
    }

    public 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(int origen, int destino, AStarMapa mapa) {
   ListaAbierta abierta = null;
   BitSet cerrada=new BitSet();
   float[] costeF = null;   //   Coste acumulado desde el origen + coste heuristico hasta el destino
   float[] costeG = null;   //   Coste acumulado desde el origen
   int[] padre = null;   //   padre del nodo
   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 null;
   }

   //   Inicializa
   costeF = new float[mapa.getNumNodos()];
   costeG = new float[mapa.getNumNodos()];
   padre = new int[mapa.getNumNodos()];
   abierta = new ListaAbierta(costeF);

   //   Coloca el nodo origen que iniciara el proceso
   costeG[origen] = mapa.getCosteFijo(origen);
   costeF[origen] = costeG[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[nodoAct] + mapa.getCosteFijo(suc) + mapa.getCosteSucesor(nodoAct, suc);
      if (abierta.existe(suc)) {               // Si ya esta en abierta
          if (newG < costeG[suc]) {
         padre[suc] = nodoAct;
         // actualiza costeF
         costeF[suc] -= costeG[suc];
         costeF[suc] += newG;
         costeG[suc] = newG;
         abierta.reordena(suc);
          }
      } else {
          costeG[suc] = newG;
          costeF[suc] = newG + mapa.getCosteHeuristico(suc, destino);
          padre[suc] = nodoAct;
          abierta.push(suc);
      }
       }
   }

   if (!encontrado) {
       return null;
   }

   int cta = 0;
   int nn = nodoAct;

   //   Cuenta los nodos
   do {
       cta++;
       nn = padre[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[nn];
   } while (nn != origen);
   retorno[0] = origen;

   return retorno;
    }
}
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Paposo

Senior Newbie





« Reply #3 - Posted 2010-06-21 20:10:45 »

The minor memory consuming ode but semi-fast

package ia.astar;

import java.util.BitSet;
import java.util.HashMap;

public class AStarObj {

    private static class Nodo {
        float costeF;
        float costeG;
        int pos;
        int idx;

        public Nodo(int idx,float costeF, float costeG) {
            this.idx=idx;
            this.costeF=costeF;
            this.costeG=costeG;
        }
    }

    // Clase que gestiona la lista abierta de Nodos
    private static class ListaAbierta {

   int size = 0;
   Nodo[] lista;
        HashMap<Integer, Nodo> existe=new HashMap<Integer,Nodo>();

   public ListaAbierta(int capacidadInicial) {
       super();
       size = 0;
       lista = new Nodo[capacidadInicial];
   }

   public void push(int idx, float costeF, float costeG) {
       size += 1;
            Nodo nodo=new Nodo(idx,costeF,costeG);
            existe.put(nodo.idx, nodo);
            if(size>=lista.length) {
                resize(size);
            }
       lista[size] = nodo;
       nodo.pos=size;
       fixup(size);
   }

   public Nodo pop() {
            Nodo nodoAct=lista[1];
            existe.remove(nodoAct.idx);
            lista[1]=lista[size];
            lista[1].pos=1;
            lista[size]=null;
            size--;
       if (size > 1) {
      fixdown(1);
       }
            return nodoAct;

   }

   public void fixup(int k) {
       int j;
       Nodo tmp;

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

      tmp = lista[j];
      lista[j] = lista[k];
      lista[k] = tmp;

      lista[j].pos = j;
      lista[k].pos = k;
      k = j;
       }
   }

   public void fixdown(int k) {
       int j;
       Nodo tmp;

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

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

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

      tmp = lista[j];
      lista[j] = lista[k];
      lista[k] = tmp;
                lista[j].pos=j;
                lista[k].pos=k;
      k = j;
       }
   }

   public boolean existe(int idx) {
       return (existe.containsKey(idx));
   }

        public Nodo getNodo(int idx) {
            return existe.get(idx);
        }

   public void reordena(Nodo nodo) {
       fixup(nodo.pos);
   }

   public boolean isVacia() {
       return size == 0;
   }

        void resize(int indice) {
       int newSize=indice*3/2+1;
       Nodo[] tmp=new Nodo[newSize];
       System.arraycopy(lista, 0, tmp, 0, lista.length);
       lista=tmp;
        }

    }

    public AStarObj() {
   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(int origen, int destino, AStarMapa mapa) {
   ListaAbierta abierta = null;
   BitSet cerrada=new BitSet();
   float costeF = 0;   //   Coste acumulado desde el origen + coste heuristico hasta el destino
   float costeG = 0;   //   Coste acumulado desde el origen
        HashMap<Integer, Integer> padre=new HashMap<Integer,Integer>();
   Nodo nodoAct = null;
   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 null;
   }

   //   Inicializa
   abierta = new ListaAbierta(200);

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

   while (!abierta.isVacia()) {
       nodoAct = abierta.pop();
       cerrada.set(nodoAct.idx);
       if (nodoAct.idx == destino) {                           // Se ha encontrado la solucion
      encontrado = true;
      break;
       }
       int[] sucesores = mapa.getSucesores(nodoAct.idx);       // 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 = nodoAct.costeG + mapa.getCosteFijo(suc) + mapa.getCosteSucesor(nodoAct.idx, suc);
                Nodo nodSuc=abierta.getNodo(suc);
      if (nodSuc!=null) {                                 // Si ya esta en abierta
          if (newG < nodSuc.costeG) {
                        padre.put(suc, nodoAct.idx);
         // actualiza costeF
         nodSuc.costeF -= nodSuc.costeG;
         nodSuc.costeF += newG;
         nodSuc.costeG = newG;
         abierta.reordena(nodSuc);
          }
      } else {
                    abierta.push(suc, newG + mapa.getCosteHeuristico(suc, destino), newG);
          padre.put(suc,nodoAct.idx);
      }
       }
   }

   if (!encontrado) {
       return null;
   }

   int cta = 0;
   int nn = nodoAct.idx;

   //   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.idx;
   do {
       cta--;
       retorno[cta] = nn;
       nn = padre.get(nn);
   } while (nn != origen);
   retorno[0] = origen;

   return retorno;
    }
}
Offline Paposo

Senior Newbie





« Reply #4 - Posted 2010-06-21 20:17:39 »

The use:

Make your AStarMapa mapa
call:

int[] path=AStar.getCaminoIndexado(idxNodeOrigin,idxNodeDest , mapa);
or
int[] path=AStarObj.getCaminoIndexado(idxNodeOrigin,idxNodeDest , mapa);

if path==null no way
another path contain the idx for path

Bye,
     Paposo
Offline teletubo
« League of Dukes »

JGO Ninja


Medals: 48
Projects: 4
Exp: 8 years



« Reply #5 - Posted 2010-06-21 20:57:00 »

Paposo, it would be cuter if you use the "code" tag around your code .
 

Offline Paposo

Senior Newbie





« Reply #6 - Posted 2010-06-21 21:05:04 »

Sorry.
These codes not working.
If not let me put preview or post. It does nothing. Ignore what I write
¿My explorer configuration?
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #7 - Posted 2010-06-21 21:24:05 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
public ListaAbierta(int capacidadInicial) {
       super();
       size = 0;
       lista = new Nodo[capacidadInicial];
   }

   public void push(int idx, float costeF, float costeG) {
       size += 1;
            Nodo nodo=new Nodo(idx,costeF,costeG);
            existe.put(nodo.idx, nodo);
            if(size>=lista.length) {
                resize(size);
            }
       lista[size] = nodo;
       nodo.pos=size;
       fixup(size);
   }

   public Nodo pop() {
            Nodo nodoAct=lista[1];
            existe.remove(nodoAct.idx);
            lista[1]=lista[size];
            lista[1].pos=1;
            lista[size]=null;
            size--;
       if (size > 1) {
      fixdown(1);
       }
            return nodoAct;

   }


Maybe i'm being dense, but are you purposely avoiding slot 0 in your open array? (or are you an old VB programmer  Wink )

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Paposo

Senior Newbie





« Reply #8 - Posted 2010-06-22 07:27:30 »

Hello.

The locLista array contains pointers to list. A value of 0 indicates that it is not. If you used  another value (ex. -1)  should initialize the array. By not using the element 0 is not necessary.
In the second version that is not necessary, but I'm very lazy and would not change too much code  Grin

And no, I have never used VB  Wink

Bye,
    Paposo
Offline Jono
« Reply #9 - Posted 2010-06-22 09:46:47 »

Every time you push or pop from a "ListaAbierta" it may run over the entire list in fixup or fixdown: O(n). You could try swapping this with some sort of heap-based implementation to get to O(logn) complexity.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Paposo

Senior Newbie





« Reply #10 - Posted 2010-06-22 14:08:51 »

Hello.

Sorry Jono. No running through the structure. Look closely. (The bit shift is equivalent to K*2 or k/2)
The cost is O (log (n))

Bye,
    Paposo
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

pw (16 views)
2014-07-24 01:59:36

Riven (16 views)
2014-07-23 21:16:32

Riven (14 views)
2014-07-23 21:07:15

Riven (16 views)
2014-07-23 20:56:16

ctomni231 (43 views)
2014-07-18 06:55:21

Zero Volt (40 views)
2014-07-17 23:47:54

danieldean (32 views)
2014-07-17 23:41:23

MustardPeter (36 views)
2014-07-16 23:30:00

Cero (51 views)
2014-07-16 00:42:17

Riven (50 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!