Necesito una mano con con A*Pathfinding (mover jugador con AI)

[rastanthology]

Estaba tratando de hacer un juego para android. Lo que quiero hacer es que cuando uno hace click en la pantalla el jugador vaya hasta ese punto esquivando todos los obstaculos que hay en el medio. Para eso trate de seguir la logica de A*Pathfinding, con los calculos "manhatan". Pero la verdad es que despues de dos dias de tratar de que ande bien cada vez estoy mas mareado.

Algo de info para entender lo que hice hasta ahora:

El mapa esta dividido en 50*50 tiles de 32 pixeles c/u. Cuando se carga el mapa se cargan todos los objetos colisionables en mapindexT[ x] [y] = true. Cuando hago click en cualquier tile le paso al void findpath() la coordenada del tile. Despues este void chequea las colisiones de alrededor de las coordenadas que le paso y despues,  al estilo "Manhatan", el costo de caminar horizontal y verticalmente de ir hasta el lugar donde esta el jugador. Despues determina los valores de los tiles de acuerdo al costo de caminar hasta ahi.

Una vez pasado esto deberia buscar cual es el tile optimo y guardar sus coordenadas en un arraylist. Las estoy grabando en 2. Una para pasarle 1 tile x tile las coordenadas de a donde ir una vez calculado como llegar. Y la otra para limpiar otro array booleano que contiene cuales tiles fueron ya calculados una vez que el jugador se termino de mover.

Una vez calculado como deberia llegar vuelve al loop principal en donde agarro las coordenadas que guarde anteriormente "optimas" de como llegar del arraylist y las voy borrando 1 x 1 a medida que el jugador completa un movimiento de tile entero. Una vez que termina el movimiento total calculado le pido que limpie mi array booleano que contiene los tiles que fueron usados.

Actualmente tengo varios errores que no me dejan esclarecer bien cual es el problema. Habre estado 4~6 horas programando esto y 8~10 debuggeando y corrigiendo. Hay variables que estan al pedo, fui creando variables y borrando a medida que debuggeaba para ver si solucionaba el problema, hay mas de una colgada, pero eso no es lo importante, cuando este andando bien voy a borrar las cosas innecesarias.

Estos eran los problemas que tenia al principio, algunos los resolvi, leer el final del post para ver los problemas del codigo actual:

Los problemas a simple vista que tengo son:

• El jugador no siempre calcula su tile optima, hay veces que si, hay veces que no
• Una vez finalizado el movimiento no siempre limpia mi array, cosa que no le encontre sentido alguno
• Hay veces que el jugador se queda loopeando el movimiento entre 2 tiles, llendo y viniendo
• Si le pido de que esquive un colisionable a veces entra en un loop infinito :/
• Seguramente abra mas, pero necesito que alguien que tal vez no este tan cerca del codigo pueda ver que estoy haciendo mal

Bueno les dejo partes del codigo por que el juego total es bastante largo

De aca se inicia el movimiento

Código (java) [Seleccionar] Expandir


@Override
public boolean onSceneTouchEvent(Scene pScene,
TouchEvent pSceneTouchEvent) {

if (pSceneTouchEvent.getAction() == MotionEvent.ACTION_DOWN) {

    otoy = toy;
    otox = tox;


toy =(int) pSceneTouchEvent.getY() / 32;
tox = (int) pSceneTouchEvent.getX() / 32;

chartouched = false;
onqueuex.clear();
onqueuey.clear();
queue = 0;
Log.d("MO", "tox " + tox + " toy " + toy);
//Game.this.touchmove();
lpath = true;
realfinish = false;
findpath("player", tox, toy);


return true;

};
return false;
}


});

Esta es la funcion que deberia calcular a donde ir:

Código (java) [Seleccionar] Expandir


private void findpath(String who, int ax, int ay) {
int valuesx[][] = new int[3][3];
int valuesy[][] = new int[3][3];
int xx,yy;
int[][] f = new int[3][3];
int[][] h = new int[3][3];
int[][] g = new int[3][3];
int tmpx, tmpy, tmpv;
tmpx = tmpy = tmpv = xx = yy = 0;
boolean[][] ontclosedlist = new boolean[3][3];
firstmove = true;
fx = ax;
fy = ay;
onqueuex.add(fx);
onqueuey.add(fy);
boolean notthere = true;
boolean walkable = true;
if (mapindexT[fx][fy]) { walkable = false; }

if (walkable) {
while (lpath) {
// referenciar los 8 puntos que rodean a donde vamos
valuesx[0][0]= fx - 1;
valuesy[0][0]= fy - 1;

valuesx[0][1]= fx;
valuesy[0][1]= fy - 1;

valuesx[0][2]= fx +1;
valuesy[0][2]= fy - 1;

valuesx[1][0]= fx - 1;
valuesy[1][0]= fy;

valuesx[1][1]= fx;
valuesy[1][1]= fy;

valuesx[1][2]= fx + 1;
valuesy[1][2]= fy;

valuesx[2][0]= fx - 1;
valuesy[2][0]= fy + 1;

valuesx[2][1]= fx;
valuesy[2][1]= fy + 1;

valuesx[2][2]= fx + 1;
valuesy[2][2]= fy + 1;
//--------------------------------------------------
//checkear collidables y conseguir la siguiente tile optima
for (int m=0; m <= 2; m++) {
for (int q=0;q<=2; q++) {


int tvx = valuesx[m][q];
int tvy = valuesy[m][q];
Log.d("MO", "tvx " + tvx + " tvy " + tvy);
if ( tvx >= 0  && tvy >=0) {
if (mapindexT[tvx][tvy]) {
ontclosedlist[m][q] = true;
Log.d("MO", "Collidables X: " + valuesx[m][q] + " Y: " + valuesy[m][q]);

numberofopenlist++;
}
// no entrar en tiles usados
ontclosedlist[1][1] = true;
if (onclosedlist[valuesx[m][q]][valuesy[m][q]]) { ontclosedlist[m][q] = true;}
// else { ontclosedlist[m][q] = true; }
//setear distancia entre el target y el player
// diferenciar x e y de acuerdo al values >>
if (!ontclosedlist[m][q]) {
if ( mx > valuesx[m][q] && my >= valuesy[m][q]) {
g[m][q]= (mx - valuesx[m][q] + my - valuesy[m][q]) * 10;
// Log.d("MO", "Arriba e izquierda" + " mx " + mx + " fx " + valuesx[m][q] + " my " + my + " fy " + valuesy[m][q]);
} else if ( mx <= valuesx[m][q] && my > valuesy[m][q]) {
g[m][q] = (valuesx[m][q] - mx + my - valuesy[m][q]) * 10;  
//Log.d("MO", "Arriba y derecha mx " + mx + " fx " + valuesx[m][q] + " my " + my + " fy " + valuesy[m][q]);
}  else if ( mx >= valuesx[m][q] && my < valuesy[m][q]) {
g[m][q] = ( mx - valuesx[m][q] + valuesy[m][q] - my) * 10;
//Log.d("MO", "Abajo e izquierda" + " mx " + mx + " fx " + valuesx[m][q] + " my " + my + " fy " + valuesy[m][q]);
} else if (mx == valuesx[m][q] && my == valuesy[m][q]) {
g[m][q] = 0;

} else if (mx < valuesx[m][q] && my <= valuesy[m][q]) {
//Log.d("MO", "Abajo y derecha" + " mx " + mx + " fx " + valuesx[m][q] + " my " + my + " fy " + valuesy[m][q]);
g[m][q] = ( valuesx[m][q] - mx + valuesy[m][q] - my)*10;
} else { Log.d("MO", "ERROR DE CALCULO DE COSTOS DE MOVIMIENTO MX: " + mx + " MY: " + my + " valuesx: " + valuesx[m][q] + " valuesy " + valuesy[m][q]); }
//Log.d("mo", "g[m][q] " + g[q][m]  );

} else { // Log.d("MO", "Collisionable");

}
// setear costo diagonal
if ( m == 0 && q == 0 || m == 0 && q == 2 || m == 2 && q == 0 || m == 2 && q == 2) {
h[m][q] = 20;
} else {
// setear costo xy
h[m][q] = 10;
}
// setear costo total;
f[m][q] = g[m][q] + h[m][q];


}
}
}

for (int x = 0; x <= 2; x++) {
for (int y = 0; y <= 2; y++) {
// buscar f optima;
//if (x == 1 && y == 1) { continue; }
if (ontclosedlist[x][y]) {
//continue;
//Log.d("MO", "collisionable \\/");

} else {

//Log.d("MO", "Buscando f opt X: " + x + " Y: " + y + " realx: " + valuesx[y][x] + " realy: " + valuesy[y][x] + " costo:  " + f[x][y]  );
if (x == 0 && y ==0) { tmpx =valuesx[0][0]; tmpy = valuesy[0][0]; tmpv = f[x][y]; xx = yy = 0; }
if (f[x][y] < tmpv) { tmpx = valuesx[x][y]; tmpy = valuesy[x][y]; tmpv = f[x][y]; xx = x; yy = y; exitloop = 0; Log.d("mo", "F optima calculada" + " x " + tmpx +" y " + tmpy + " cost " + tmpv);}

}
ontclosedlist[x][y] = false;

}
}
onqueuelistx.add(tmpx);
onqueuelisty.add(tmpy);
onqueuex.add(tmpx);
onqueuey.add(tmpy);
onclosedlist[tmpx][tmpy] = true;
Log.d( " MO ", "onqueuex: " + onqueuex.get(queue) + " onqueuey: " + onqueuey.get(queue));
queue++;
fx = tmpx;
fy = tmpy;
// llenar lista
// for ( int g1=0; g1<=2; g1++) {
// for (int h1=0; h1<= 2; h1++) {
// if (ontclosedlist[g1][h1]) { onclosedlist[valuesx[h1][g1]][valuesy[h1][g1]] = true; }
// }
// }

//-------------------
// referenciar para donde moverse
if (queue > 30) {
Log.d("MO", "Saliendo del loop! error");
onqueuex.clear();
onqueuey.clear();
queue = 0;
break;}

Log.d("MO", "Fx: " + fx +" Fy " + fy + " cost " + f[xx][yy] + " onqueue " + queue );
// salir del loop
if (fx == mx && fy == my) {notthere = false; realfinish = false; lpath = false; fpath = true; oqueue = queue;
tmoving = true;
onqueuex.remove(onqueuex.size() - 1); onqueuey.remove(onqueuey.size() - 1);
Log.d("MO", "Path calculado, tamaño: " + queue); break;}

}// else { notthere = true; }

}

}
    //}
   //}

}



Una vez calculada entra aca que es donde el jugador se esta moviendo:

Código (java) [Seleccionar] Expandir



                            if (!mloop) {
                            if (fpath) {
                           
                            //lpath = true;
                            int tmx, tmy, rtmx, rtmy;
                            if (!onqueuex.isEmpty()) {
                           
                           
                           
                            tmx  = onqueuex.get(onqueuex.size() - 1);
                            tmy = onqueuey.get(onqueuey.size() - 1);
                            rtmx = mx - tmx;
                            rtmy = my - tmy;
                            if (rtmx == 1 && rtmy == 1) {
                            //diagonal superior izquierda
                            tindex = 4;
                           
                            } else if (rtmx == 1 && rtmy == -1) {
                            // diagonal inferior izquierda
                            tindex = 5;
                            } else if (rtmx == -1 && rtmy == 1) {
                            // diagonal superior derecha
                            tindex = 6;
                            } else if ( rtmx == -1 && rtmy == -1) {
                            //diagonal inferior derecha
                            tindex = 7;
                            } else if (rtmx == 1) { tindex = 1; }
                            else if (rtmx == -1) { tindex = 0; }
                            else if (rtmy == 1) { tindex = 2; }
                            else if (rtmy == -1) { tindex = 3; }
                            Log.d("MO", "tmx: " + tmx + " tmy " + tmy + " rtmx " + rtmx + " rtmy " + rtmy + " tindex " + tindex);
                        onqueuex.remove(onqueuex.size() - 1);
                          onqueuey.remove(onqueuey.size() - 1);
                         
                            } else {
                            fpath = false; realfinish = true;
                           
                            for (int g2 = 0; g2 < oqueue ; g2++) {
                            onclosedlist[onqueuelistx.get(g2)][onqueuelisty.get(g2)] = false;
                            Log.d("MO", "Limpiando camino");
                            }
                            onqueuelistx.clear();
                            onqueuelisty.clear();
                            onqueuex.clear();
                            onqueuey.clear();
                            oqueue = 0;
                            }
                            }
                            if (!realfinish) {
                            ox = jx = (int) player.getX();
                            oy = jy = (int) player.getY();
                            String p = "player";
                         
                            Log.d("MO", "X: " + mx + " Y: " + my);
                           
                            switch(tindex) {
                                                   case 0:
                                                       //derecha
                                                    // mapindex(mx, my, true);
                                                    //    if (collidables(mx, my,p,1)){                                                        
                                                       jx = ox + 8;
                                                       ox = jx;
                                                       mloop = true;
                                                       mx++;
                                                           player.setPosition(jx, oy);
                                                           
                                                           player.animate(new long[]{200, 200, 200}, 3, 5, tmoving);
                                                     //  } else { player.animate(new long[]{200, 200, 200}, 3, 5, moving);}
                                                       
                                                       
                                                           break;
                                                           
                                                   case 1:
                                                    //izquierda
                                                   // mapindex(mx, my, true);
                                                   // if (collidables(mx, my,p,1)) {
                                                        jx = ox - 8;
                                                        ox = jx;
                                                        player.setPosition(jx, oy);
                                                        player.animate(new long[]{200, 200, 200}, 9, 11, tmoving);
                                                        mloop = true;
                                                        mx--;
                                                   // } else { player.animate(new long[]{200, 200, 200}, 9, 11, moving); }
                                                           break;
                                                   case 3:
                                                       //abajo
                                                    //mapindex(mx, my, true);
                                                   // if (collidables(mx, my,p,1)) {
                                                    jy = oy + 8;
                                                    oy = jy;
                                                    my++;
                                                    player.setPosition(ox, jy);
                                                    mloop = true;
                                                    player.animate(new long[]{200, 200, 200}, 6, 8, tmoving);
                                                    //} else {  player.animate(new long[]{200, 200, 200}, 6, 8, moving); }
                                                           break;
                                                   case 2:
                                                       //arriba
                                                    //mapindex(mx, my, true);
                                                    //if(collidables(mx, my,p,1)) {
                                                    jy = oy - 8;
                                                       oy = jy;
                                                       my--;
                                                    player.setPosition(ox, jy);
                                                    mloop = true;
                                                    player.animate(new long[]{200, 200, 200}, 0, 2, tmoving);
                                                   // } else { player.animate(new long[]{200, 200, 200}, 0, 2, moving); }
                                                           break;
                                                   case 4:
                                                    //diagonal superior izquierda
                                                    jx = ox - 4;
                                                    ox = jx;
                                                    jy = oy - 4;
                                                    oy = jy;
                                                    mx--;
                                                    my--;
                                                    player.setPosition(jx, jy);
                                                    mloop = true;
                                                    player.animate(new long[]{200, 200, 200}, 9, 11, tmoving);
                                                    break;
                                                   case 5:
                                                    //diagonal inferior izquierda
                                                    jx = ox - 4;
                                                    ox = jx;
                                                    jy = oy + 4;
                                                    oy = jy;
                                                    mx--;
                                                    my++;
                                                    player.setPosition(jx, jy);
                                                    mloop = true;
                                                    player.animate(new long[]{200, 200, 200}, 9, 11, tmoving);
                                                    break;
                                                   case 6:
                                                    // diagonal superior derecha
                                                    jx = ox + 4;
                                                    ox = jx;
                                                    jy = oy - 4;
                                                    oy = jy;
                                                    mx++;
                                                    my--;
                                                    player.setPosition(jx, jy);
                                                    mloop = true;
                                                    player.animate(new long[]{200, 200, 200}, 3, 5, tmoving);
                                                    break;
                                                   case 7:
                                                    //diagonal inferior derecha
                                                   
                                                    jx = ox + 4;
                                                    ox = jx;
                                                    jy = oy + 4;
                                                    oy = jy;
                                                    mx++;
                                                    my++;
                                                    player.setPosition(jx, jy);
                                                    mloop = true;
                                                    player.animate(new long[]{200, 200, 200}, 3, 5, tmoving);
                                                    break;
                           
                           }
                            }
                   } else {
                           
                   
                    switch(tindex) {
                   
                    case 0:
                    jx = ox + 8;
                       ox = jx;
                       player.setPosition(jx, oy);
                           temp++;
                           if (temp == 3) { temp = 0; mloop = false; if (realfinish) { tmoving = false; } }
                           
                           player.animate(new long[]{200, 200, 200}, 3, 5, moving);
                           
                           break;
                    case 1:
                    jx = ox - 8;
                    ox = jx;
                    player.setPosition(jx, oy);
                    temp++;
                    if (temp == 3) { temp = 0; mloop = false; if (realfinish) { tmoving = false; }}
                    player.animate(new long[]{200, 200, 200}, 9, 11, moving);
                    break;
                    case 2:
                    jy = oy - 8;
                    oy = jy;
                    player.setPosition(ox, jy);
                    temp++;
                   
                    if (temp == 3) { temp = 0; mloop = false; if (realfinish) { tmoving = false; }}
                    player.animate(new long[]{200, 200, 200}, 0, 2, moving);
                    break;
                    case 3:
                    jy = oy + 8;
                    oy = jy;
                    player.setPosition(ox, jy);
                    temp++;
                    if (temp == 3) { temp = 0; mloop = false; if (realfinish) { tmoving = false; } }
                    player.animate(new long[]{200, 200, 200}, 6, 8, moving);
                    break;
                     case 4:
                          //diagonal superior izquierda
                          jx = ox - 4;
                          ox = jx;
                          jy = oy - 4;
                          oy = jy;
                          temp++;
                          player.setPosition(jx, jy);
                     
                          player.animate(new long[]{200, 200, 200}, 9, 11, tmoving);
                          if (temp == 7) { temp = 0; mloop = false; if(realfinish) {tmoving = false;}}
                          break;
                         case 5:
                          //diagonal inferior izquierda
                          jx = ox - 4;
                          ox = jx;
                          jy = oy + 4;
                          oy = jy;
                          temp++;
                          player.setPosition(jx, jy);
                     
                          player.animate(new long[]{200, 200, 200}, 9, 11, tmoving);
                          if (temp == 7) { temp = 0; mloop = false; if(realfinish) {tmoving = false;}}
                          break;
                         case 6:
                          // diagonal superior derecha
                          jx = ox + 4;
                          ox = jx;
                          jy = oy - 4;
                          oy = jy;
                          temp++;
                          player.setPosition(jx, jy);
                     
                          player.animate(new long[]{200, 200, 200}, 3, 5, tmoving);
                          if (temp == 7) { temp = 0; mloop = false; if(realfinish) {tmoving = false;}}
                          break;
                         case 7:
                          //diagonal inferior derecha
                         
                          jx = ox + 4;
                          ox = jx;
                          jy = oy + 4;
                          oy = jy;
                 
                          player.setPosition(jx, jy);
                          temp++;
                          player.animate(new long[]{200, 200, 200}, 3, 5, tmoving);
                          if (temp == 7) { temp = 0; mloop = false; if(realfinish) {tmoving = false;}}
                          break;
                   
                    }
                   
                   }
                    }
                   
                   
                   }
           });
       



A ver si alguien puede ver lo que yo no veo

Desde ya gracias por dedicarle tiempo a este tema

PD: corregi otra cosa q me pase x alto, tambien el jug arranca a moverse a la derecha siempre x mas q no alla terminado de calcular a donde ir, y el loop infinito pasa mas seguido ahora :/

PD2: Le saque algunos errores mas, al parecer me habia confundido pensando en como habia declarado ciertas cosas. Ahora los problemas se reducen a:

El jugador no siempre calcula bien el path, hay veces que entra en un loop que no termina; aunque ahora lo fuerzo a que salga para que sea mas comodo

Otras veces misteriosamente me tira un ArrayOutOfBounds Exception esta linea:


int tvx = valuesx[m][q];
int tvy = valuesy[m][q];

if ( tvx >= 0  && tvy >=0) {

if (onclosedlist[valuesx[m][q]][valuesy[m][q]]) { ontclosedlist[m][q] = true;}

}
y digo misteriosamente por que esta comprendida en el if que no dejaria que entre si esta outofbounds :/. En el log me dice que entra con tvx = tvy = -1


Mi teoria al tener que decidir entre dos tiles con el mismo valor elige uno y para ese lado no puede solucionar el problema. Ahi es cuando no sale del loop. Cuando este mas en frio lo chequeo bien, pero si alguien lo descubre a simple vista mejor