pathfinding para busqueda de caminos dinamico

[vib]

Hola buenas, me ha tocado hacer la IA en un proyecto y la verdad es que investigando voy a implementar para su movimiento un pathfinding, aunque tengo varias dudas:

El juego es un estilo de los enemigos van hacia a ti a atacarte, teniendo de esquivar obstáculos que hay en el mapa y a los propios otros enemigos, asta aquí bien el problema viene:

Tengo casi implementado el algoritmo para desde la posición de 1 enemigo, y sabiendo la posición del héroe, haga el algoritmo del pathfinding y una vez lo tiene recorrerlo.

Eso me ha resultado fácil, la duda es que, la posición del HEROE puede irse modificando en cada bucle, ya que el juego de en tiempo real, la implementacion seria la misma?

Osea, calculo el recorrido, y muevo enemigo por ese recorrido creado, pero si Heroe cambia su posicion, enemigo que vuelva a crear una nueva ruta.
Así es como lo tenia pensando, pero no se si hay alguna forma mejor, ya que esto podría ser muy costosa porque por lo general HÉROE nunca va estar en la misma posición.

Gracias

[blau]

Yo hice algo parecido.. y lo hice a la inversa...

digamos que calculaba para todas las celdas del mapa el pathfinding para el heroe...
es como si hicieses un fill desde la posicion del heroe...
asi independientemente del numero de enemigos el tiempo de calcular el path finding es constante...
si el mapa es grande puede consumir bastante tiempo... porque has de rellenar todo el mapa...
asi que te creas un hilo en background que cada vez que se mueva el heroe recalcule...

Aqui una implementacion que hice basandome en esta idea... pero haciendo que se recalcularan parcialmente los datos de las celdas cuando bloqueabas un camino...
https://www.youtube.com/watch?v=mYLSZJViSDc

EDIT: Quizas no se te ajuste bien la idea en caso de que quieras que los enemigos tb bloqueen..

pero quedate con  la idea un hilo en segundo plano encargado de ir calculando caminos... date cuenta que las unidades no tienen porque recalcular inmediantemente el camino hacia un destino si este se mueve.... el camino seguira siendo más o menos el mismo... y porque se recalcule medio segundo despues de haber movido el heroe no va a pasar nada porque sigas usando el camino anterior.

Yo en principio no tendria en cuenta a los enemigos en el calculo del camino salvo que esten parados, y en caso de que tengas distintas velocidades de enemigos ya se complica la cosa, pero si chocas con otro enemigo que tb esta en movimiento y es mas lento que tu, pararia y recalcularia un camino que si tuviese en cuenta a los enemigos en movimiento.

Un saludo

[vib]

Si era mi idea...lo estoy programando haciendo que salgan diferentes hilos por cada calculo.. buffaunque es un algoritmo lentito
porque mi mapa cada celda ocupa el tamaño de un tile 96x48, pero el mapa del grafo es pixel por pixel, y al tener un mapa de scroll el tamaño es enorme

Aunque hare las rutas localmente por la parte que se imprimen en pantalla...aun asi es costoso

mexi!

[blau]

1) Creo que es mejor un solo hilo que vaya consumiendo de una cola de busquedas...
2) ¿el mapa del grafo es pixel por pixel? eso no lo entiendo... digo yo que aunque tu tile grafico sea de 96x48, supongo que los sprites de las unidades serán más pequeños, y el pathfinding lo podrias hacer entre bloques de 24x24
Incluso podrias agrupar 4 bloques de 24x24 en uno de 48x48 y asignarle a este en una variable los huecos libres que te quedan de 24x24, de esta forma todavia haces que el pathfinding sea más rápido de calcular....

[vib]

Lo hago pixel x pixel porque:

El mapa cada celda ocupa por ejemplo 20x20 pixeles, todos los objetos del mapa, la parte que tocan el suelo ocupan 20x20 tambien.

Que sucede, pues el movimiento es de 2 en 2, osea en una misma celda pueden estar mas de 1 objeto, y esto a la hora de moverse usando un grafo es un problema, entonces he reducido los tamaños de las celdas a 1x1 para resolver ese problema. no?:s

[vib]

Por si alguien quiere verlo o simplemente aprovechar el codigo, os dejoel codigo del algoritmo hecho con algunas pruebas, en c++
Es largo porque las creaciones de los mapas estan hechas manualmente xD

PD. un grafo de tamaño 40*36 tarda 0,2 segundos en resolverlo.....muy muy lento

Código [Seleccionar] Expand


#include <iostream>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>    // std::sort
#include <stdlib.h>
using namespace std;
///0 camino, 1 inacesible, heroe se pone a 5.
/*#define tamX 6//3//6
#define tamY 5//3//5
#define tileX 1////3
#define tileY 2//2//3
*/
/*///mapa1, inici:2-2, fin 2-5
///3*4= 8-6, 8-15
#define tamX 7//3//6
#define tamY 5//3//5
#define tileX 3////3
#define tileY 4//2//3
*/

/*///mapa2, inici 3-1, fin 1-3
///3*4 12-3,   4-9
#define tamX 6//3//6
#define tamY 5//3//5
#define tileX 3////3
#define tileY 4//2//3
*/
///mapa3, el completo
///i 0-0,   9-11, 3*4= 0,0,, 36-33
#define tamX 12//3//6
#define tamY 10//3//5
#define tileX 3////3
#define tileY 4//2//3
struct vertice{
    int posx;///la posicion que ocupa en la matriz
    int posy;
    int valor;
    int pos=-1;///la posicion que ocupa en la array <0,0>=0; <0,1>1, 0,2=2 etc...
    vector<int>adjy;///
    vector<int>adjx;///
    vector<int>adj;///con posiciones direcamtne
    int g=10;
    int f=-1;
    int padrex=-1;///para saber la ruta
    int padrey=-1;
    int padre=-1;
    ///hijo, lo mismo ke el padre pero al reves
    int hijox=-1;
    int hijoy=-1;
    int hijo=-1;

    bool visitado=false;
    ///es la 1r posicion de cada celda del grafo " si cada tile ocupa...3 celdas del grafo pues apuntara
    ///a la 1r celda ke es arriba izkierda
    int maty;
    int matx;
};
struct comparador {///operador para realizar las modificaciones de ordenadcion de mi vector
  bool operator() (vertice i,vertice j) { return (i.f>j.f);}
} mayorF;


int mapa[tamY][tamX];///dimensiones del mapa 6x, 5y
   vertice grafo[tamY*tileY][tamX*tileX];///cada tile del mapa son *10 pixeles
void llenar();
void mapa1();
void mapa2();
void mapa3();
void llenargrafo();
void imprimir();
void ponerAdj();
void saberAdj();
void saberpos();
void BuscarCamino(int,int,int,int);///meto las posiciones "0,0" de las celdas del grafo de los tiles.
void imprimirpos();
int main()
{
   mapa3();
    llenargrafo();
    ponerAdj();
    imprimir();
    BuscarCamino(0,0,36,33);
  imprimir();
    return 0;
}
void BuscarCamino(int iy,int ix, int fy, int fx)
{
     vertice inici=grafo[iy][ix];
     vertice fin=grafo[fy][fx];
     vector<vertice> cola;
///lo ke hace es... si son 2 pixeles a mirar en x, y 3 en y "el tamaño tile es 2x3
            ///pues cuando alla 2 x conb misma posicion entonces metelo sino no...
            /// i se mete en la cola
            vector<vertice>vistox;
            vector<vertice>vistoy;
            int contx=0;
            int conty=0;

     cola.push_back(inici);

    //back es 1r valor, pop es kitarlo
   while (cola.size()>0)///mientras hay elementos
     {
        vertice v=cola.back();

        cola.pop_back();
        if(!v.visitado)
        {
           vistox.clear();
           vistoy.clear();
           contx=0;
           conty=0;

            grafo[v.maty][v.matx].visitado=true;///se mira el visitado de la 1r casilla
            if(v.pos!=fin.pos)///sino hemos llegado
            {
                for(int y1=v.maty; y1<v.maty+tileY; y1++)///recorremos las celdas ke tiene cada "tile grande" en el grafo
                {
                    for(int x1=v.matx; x1<v.matx+tileX; x1++)
                    {
                        for(int i=0; i<grafo[y1][x1].adj.size(); i++)///recorremos todos los adj de cada punto
                        {

                            int vy,vx;///guardo las posiciones asi para que no alla tanto lio,
                            ///quiero la 0,0 de cada tile.
                            vy=grafo[y1][x1].adjy[i];
                            vx=grafo[y1][x1].adjx[i];
                            int ay,ax;
                            ay=grafo[vy][vx].maty;
                            ax=grafo[vy][vx].matx;

                            vertice vadj=grafo[ay][ax];///adj de cada posicion
                            if(!vadj.visitado and vadj.pos!=v.pos)///si esta visitado pake verlo,ke su adj sea diferente a el mismo
                            {
                                int peso=v.g+(abs(vadj.posy-fin.posy)+abs(vadj.posx-fin.posy));
                                ///si tiene mismo padre...esque es una continuacion del tile, sumalo!
                                if(peso<vadj.f or vadj.f==-1 or vadj.padre==v.pos)///si el peso es menor o aun no se a iniciado "-1" metelo
                                {
                                    if(vadj.padre!=v.pos)///si no son mismo padre az como siemrpre.
                                    {
                                        vadj.padre=v.pos;///assignamos el padre de los adj como su padre su posicion
                                        vadj.padrey=v.posy;
                                        vadj.padrex=v.posx;
                                        vadj.f=peso;
                                        vadj.g=vadj.g+v.g;///se le suma
                                        cout<<"padre "<<vadj.padre<<" yo "<<vadj.pos<<endl;
                                    }
                                    else
                                    {
                                        vadj.f+=peso;///le sumamos mas el peso, la g se mantiene.
                                    }
                                    /// cout<< vadj.f<<" vady "<<vadj.posy<<" x "<<vadj.posx<< " finy "<< fin.posy <<" x "<<fin.posx <<endl;
                                    grafo[ay][ax]=vadj;///se iwala para ke coja todas las referencias, es pa trbaajr mas comodo
                                    if(v.posy!=vadj.posy)///kiere decir ke estmaos mirando adj arriba /abajo
                                    {
                                        vistoy.push_back(vadj);
                                        for(int i=0; i<vistoy.size(); i++)
                                        {
                                            if(vistoy[i].pos==vadj.pos)///si hay n=tile de los añadidmos, bien se puede ir
                                            {
                                                conty++;
                                            }
                                        }
                                        if(conty>=tileX)cola.push_back(vadj);
                                        conty=0;
                                    }
                                    else if(v.posx!=vadj.posx)///kiere decir ke estmaos mirando adj arriba /abajo
                                    {
                                        vistox.push_back(vadj);
                                        for(int i=0; i<vistox.size(); i++)
                                        {
                                            if(vistox[i].pos==vadj.pos)///si hay n=tile de los añadidmos, bien se puede ir
                                            {
                                                contx++;
                                            }
                                        }
                                        if(contx>=tileY)cola.push_back(vadj);
                                        contx=0;
                                    }

                                    std::sort (cola.begin(), cola.end(), mayorF);///ordenamos la array apra sacar el menor F
                               }
                            }
                        }


                    }
                }

            }
        }

     }
///padre

    vertice ruta=grafo[1][3];
     ruta=grafo[36][33];
cout<<"camino "<< ruta.pos<<endl;
    while (ruta.padrey!=-1)///x o y es lo mismo!
    {
        cout<<ruta.pos<<endl;
        //grafo[ruta.padrey][ruta.padrex].valor=3;
        grafo[ruta.padrey][ruta.padrex].hijo=ruta.pos;
         grafo[ruta.padrey][ruta.padrex].hijoy=ruta.posy;
          grafo[ruta.padrey][ruta.padrex].hijox=ruta.posx;
        ruta=grafo[ruta.padrey][ruta.padrex];


    }
    ruta=grafo[0][0];
cout<<"camino "<< ruta.hijo<<endl;
   while (ruta.hijo!=-1)///x o y es lo mismo!
    {
        cout<<ruta.pos<<endl;
        for(int y1=ruta.maty; y1<ruta.maty+tileY; y1++)///recorremos las celdas ke tiene cada "tile grande" en el grafo
                {
                    for(int x1=ruta.matx; x1<ruta.matx+tileX; x1++)
                    {
        //grafo[ruta.hijoy][ruta.hijox].valor=3;
        grafo[y1][x1].valor=3;

                    }
                    }
                    ruta=grafo[ruta.hijoy][ruta.hijox];
    }
}


void saberpos()
{
    for(int y1=0; y1<tamY*tileY; y1++){
        for(int x1=0; x1<tamX*tileX; x1++){
                cout<<grafo[y1][x1].pos<<" "<<endl;
        }
        cout<<endl;
    }

}
void ponerAdj()
{
     for(int y=0; y<tamY; y++){
        for(int x=0; x<tamX; x++){

        if(mapa[y][x]!=1)///no es pared solida
            {  // cout<<" estat "<<y<<" "<<x<<endl;
                for(int y1=y*tileY; y1<y*tileY+tileY; y1++){
                    for(int x1=x*tileX; x1<x*tileX+tileX; x1++){
                           // cout<<"grafo y-x "<<y1<<" "<<x1<<endl;
                       ///miramos las 4 posiciones para meterlas
                       if(grafo[y1][x1-1].valor!=1 and x1-1>=0)///su izkierda
                       {  //  cout<<"entra iz "<<x1-1<< "adj a pos "<<grafo[y1][x1-1].pos<<endl;
                            grafo[y1][x1].adj.push_back(grafo[y1][x1-1].pos);
                           grafo[y1][x1].adjy.push_back(y1);
                           grafo[y1][x1].adjx.push_back(x1-1);
                       }
                       if(grafo[y1][x1+1].valor!=1 and x1+1<tamX*tileX)///derecha
                       {//cout<<"entra de "<<x1+1<< "adj a pos "<<grafo[y1][x1+1].pos<<endl;
                           grafo[y1][x1].adj.push_back(grafo[y1][x1+1].pos);
                           grafo[y1][x1].adjy.push_back(y1);
                           grafo[y1][x1].adjx.push_back(x1+1);
                       }
                       if(grafo[y1-1][x1].valor!=1 and y1-1>=0)///arriba
                       {//cout<<"entra arr "<<y1-1<< "adj a pos "<<grafo[y1-1][x1].pos<<endl;
                           grafo[y1][x1].adj.push_back(grafo[y1-1][x1].pos);
                           grafo[y1][x1].adjy.push_back(y1-1);
                           grafo[y1][x1].adjx.push_back(x1);
                       }
                       if(grafo[y1+1][x1].valor!=1 and y1+1<tamY*tileY)///abajo
                       {//cout<<"entra ab "<<y1+1<< "adj a pos "<<grafo[y1+1][x1].pos<<endl;
                           grafo[y1][x1].adj.push_back(grafo[y1+1][x1].pos);
                           grafo[y1][x1].adjy.push_back(y1+1);
                           grafo[y1][x1].adjx.push_back(x1);
                       }
                    }
                }

            }



        }

    }

}
void saberAdj()
{
   for(int y1=0; y1<tamY*tileY; y1++){
        for(int x1=0; x1<tamX*tileX; x1++){
                for(int i=0; i<grafo[y1][x1].adj.size();i++)cout<<" pos y "<<y1<<" "<<x1 <<" = "<<grafo[y1][x1].adj[i]<<endl;
                 //for(int i=0; i<grafo[y1][x1].adjy.size();i++)cout<<" pos y "<<y1<<" "<<x1 <<" = "<<grafo[y1][x1].adjy[i]<<endl;
                 //for(int i=0; i<grafo[y1][x1].adjx.size();i++)cout<<" pos x "<<y1<<" "<<x1 <<" = "<<grafo[y1][x1].adjx[i]<<endl;
                }
    }

}

void imprimir()
{
    for(int y=0; y<tamY; y++){
        for(int x=0; x<tamX; x++) cout<<mapa[y][x]<<" ";
    cout<<endl;
    }

    cout<<endl;
    for(int y1=0; y1<tamY*tileY; y1++){
                for(int x1=0; x1<tamX*tileX; x1++){
                    cout<<grafo[y1][x1].valor<<" ";
                }
                cout<<endl;
            }
}
void imprimirpos()
{

    cout<<endl;
    for(int y1=0; y1<tamY*tileY; y1++){
                for(int x1=0; x1<tamX*tileX; x1++){
                    cout<<grafo[y1][x1].pos<<" ";
                }
                cout<<endl;
            }
}
void llenargrafo()
{   int n=0;
    for(int y=0; y<tamY; y++){
        for(int x=0; x<tamX; x++){
            for(int y1=y*tileY; y1<y*tileY+tileY; y1++){
                for(int x1=x*tileX; x1<x*tileX+tileX; x1++){
                    grafo[y1][x1].pos=n;
                    grafo[y1][x1].valor=mapa[y][x];
                    grafo[y1][x1].posx=x1;
                    grafo[y1][x1].posy=y1;
                    grafo[y1][x1].maty=y*tileY;
                    grafo[y1][x1].matx=x*tileX;

                }
            }
            n++;
        }

    }

}
void llenar()
{
    /* mapa[0][0]=5;
    mapa[0][1]=0;
    mapa[0][2]=0;

    mapa[1][0]=0;
    mapa[1][1]=1;
    mapa[1][2]=0;

    mapa[2][0]=0;
    mapa[2][1]=1;
    mapa[2][2]=6;
    */
    /*mapa[0][0]=0;
    mapa[0][1]=1;
    mapa[1][0]=0;
    mapa[1][1]=1;
    */
    mapa[0][0]=5;//5
    mapa[0][1]=0;
    mapa[0][2]=1;
    mapa[0][3]=1;
    mapa[0][4]=0;
    mapa[0][5]=1;

    mapa[1][0]=1;
    mapa[1][1]=0;
    mapa[1][2]=0;
    mapa[1][3]=0;
    mapa[1][4]=0;
    mapa[1][5]=1;

    mapa[2][0]=0;
    mapa[2][1]=0;
    mapa[2][2]=1;
    mapa[2][3]=1;
    mapa[2][4]=0;
    mapa[2][5]=0;

     mapa[3][0]=0;
    mapa[3][1]=1;///SSSSSS
    mapa[3][2]=1;
    mapa[3][3]=1;
    mapa[3][4]=1;
    mapa[3][5]=0;

     mapa[4][0]=0;
    mapa[4][1]=0;
    mapa[4][2]=0;
    mapa[4][3]=0;
    mapa[4][4]=6;
    mapa[4][5]=0;


}
void mapa1()
{

    mapa[0][0]=0;//5
    mapa[0][1]=0;
    mapa[0][2]=0;
    mapa[0][3]=0;
    mapa[0][4]=0;
    mapa[0][5]=0;
    mapa[0][6]=0;

    mapa[1][0]=0;
    mapa[1][1]=0;
    mapa[1][2]=0;
    mapa[1][3]=1;
    mapa[1][4]=0;
    mapa[1][5]=0;
    mapa[1][6]=0;

    mapa[2][0]=0;
    mapa[2][1]=0;
    mapa[2][2]=5;
    mapa[2][3]=1;
    mapa[2][4]=0;
    mapa[2][5]=6;
    mapa[2][6]=0;

    mapa[3][0]=0;
    mapa[3][1]=0;///SSSSSS
    mapa[3][2]=0;
    mapa[3][3]=1;
    mapa[3][4]=0;
    mapa[3][5]=0;
    mapa[3][6]=0;

     mapa[4][0]=0;
    mapa[4][1]=0;
    mapa[4][2]=0;
    mapa[4][3]=0;
    mapa[4][4]=0;
    mapa[4][5]=0;
    mapa[4][6]=0;

    mapa[5][0]=0;
    mapa[5][1]=0;
    mapa[5][2]=0;
    mapa[5][3]=0;
    mapa[5][4]=0;
    mapa[5][5]=0;
    mapa[5][6]=0;

}
void mapa2()
{

    mapa[0][0]=0;//5
    mapa[0][1]=0;
    mapa[0][2]=0;
    mapa[0][3]=0;
    mapa[0][4]=0;
    mapa[0][5]=0;


    mapa[1][0]=0;
    mapa[1][1]=0;
    mapa[1][2]=0;
    mapa[1][3]=6;
    mapa[1][4]=0;
    mapa[1][5]=0;


    mapa[2][0]=0;
    mapa[2][1]=1;
    mapa[2][2]=1;
    mapa[2][3]=1;
    mapa[2][4]=0;
    mapa[2][5]=0;


    mapa[3][0]=0;
    mapa[3][1]=5;///SSSSSS
    mapa[3][2]=0;
    mapa[3][3]=1;
    mapa[3][4]=0;
    mapa[3][5]=0;


     mapa[4][0]=0;
    mapa[4][1]=0;
    mapa[4][2]=0;
    mapa[4][3]=0;
    mapa[4][4]=0;
    mapa[4][5]=0;


}
void mapa3()
{

    mapa[0][0]=5;//5
    mapa[0][1]=0;
    mapa[0][2]=0;
    mapa[0][3]=0;
    mapa[0][4]=0;
    mapa[0][5]=1;
    mapa[0][6]=1;
    mapa[0][7]=1;
    mapa[0][8]=0;
    mapa[0][9]=0;
    mapa[0][10]=0;
    mapa[0][11]=0;

    mapa[1][0]=1;//5
    mapa[1][1]=0;
    mapa[1][2]=1;
    mapa[1][3]=1;
    mapa[1][4]=0;
    mapa[1][5]=1;
    mapa[1][6]=0;
    mapa[1][7]=0;
    mapa[1][8]=0;
    mapa[1][9]=1;
    mapa[1][10]=1;
    mapa[1][11]=0;

     mapa[2][0]=1;//5
    mapa[2][1]=0;
    mapa[2][2]=1;
    mapa[2][3]=0;
    mapa[2][4]=1;
    mapa[2][5]=0;
    mapa[2][6]=0;
    mapa[2][7]=0;
    mapa[2][8]=1;
    mapa[2][9]=1;
    mapa[2][10]=0;
    mapa[2][11]=0;

     mapa[3][0]=1;//5
    mapa[3][1]=0;
    mapa[3][2]=1;
    mapa[3][3]=0;
    mapa[3][4]=0;
    mapa[3][5]=0;
    mapa[3][6]=1;
    mapa[3][7]=0;
    mapa[3][8]=0;
    mapa[3][9]=1;
    mapa[3][10]=0;
    mapa[3][11]=1;

     mapa[4][0]=0;//5
    mapa[4][1]=0;
    mapa[4][2]=1;
    mapa[4][3]=1;
    mapa[4][4]=0;
    mapa[4][5]=0;
    mapa[4][6]=1;
    mapa[4][7]=0;
    mapa[4][8]=0;
    mapa[4][9]=1;
    mapa[4][10]=0;
    mapa[4][11]=0;

     mapa[5][0]=0;//5
    mapa[5][1]=1;
    mapa[5][2]=1;
    mapa[5][3]=0;
    mapa[5][4]=0;
    mapa[5][5]=1;
    mapa[5][6]=1;
    mapa[5][7]=1;
    mapa[5][8]=1;
    mapa[5][9]=0;
    mapa[5][10]=1;
    mapa[5][11]=0;

     mapa[6][0]=0;//5
    mapa[6][1]=0;
    mapa[6][2]=0;
    mapa[6][3]=0;
    mapa[6][4]=1;
    mapa[6][5]=0;
    mapa[6][6]=0;
    mapa[6][7]=0;
    mapa[6][8]=0;
    mapa[6][9]=0;
    mapa[6][10]=0;
    mapa[6][11]=0;

     mapa[7][0]=0;//5
    mapa[7][1]=0;
    mapa[7][2]=1;
    mapa[7][3]=0;
    mapa[7][4]=1;
    mapa[7][5]=0;
    mapa[7][6]=1;
    mapa[7][7]=0;
    mapa[7][8]=1;
    mapa[7][9]=1;
    mapa[7][10]=1;
    mapa[7][11]=1;

     mapa[8][0]=1;//5
    mapa[8][1]=0;
    mapa[8][2]=0;
    mapa[8][3]=0;
    mapa[8][4]=1;
    mapa[8][5]=0;
    mapa[8][6]=0;
    mapa[8][7]=1;
    mapa[8][8]=0;
    mapa[8][9]=0;
    mapa[8][10]=0;
    mapa[8][11]=0;

     mapa[9][0]=1;//5
    mapa[9][1]=0;
    mapa[9][2]=1;
    mapa[9][3]=0;
    mapa[9][4]=1;
    mapa[9][5]=0;
    mapa[9][6]=0;
    mapa[9][7]=0;
    mapa[9][8]=0;
    mapa[9][9]=0;
    mapa[9][10]=1;
    mapa[9][11]=6;




}






[After]

Usa el algoritmo jump point searchpara optimizar tu Pathfinding, si tienes problemas avísame.