A* pathfinding - LITE?

Eu ia fazer um tutorial, mas já existe um TRADUZIDO na internet, então não vou copiar descaradamente, como costumo fazer.
Ainda assim, vale a pena perder um pouco de tempo escrevendo isso.
Você conhece o A* (a-estrela)? Se não, é um metodo de achar o melhor caminho até um ponto, passando por pontos pré-definidos.
Em resumo, nós vamos dividir a tela num grid e achar o melhor caminho pra chegar do ponto A ao ponto B, evitando os pontos ilegais (desviando das paredes).
"Mas o game maker tem uma ferramenta FEITA pra isso".
Tem mesmo. Você sabe como ela funciona internamente? Eu não, portanto não gosto dela. Pra mim, só é bom o que eu consigo entender e re-fazer, se necessário.

Pra entender como funciona o A*, leia o link. Acredite, vale a pena. Além do mais, ele foi escrito numa linguagem para iniciantes, até eu conesgui entender.
Abaixo, a codificação do script, que faz tudo o que você ler naquele link (menos a parte avançada, depois que o caminho está pronto. Aí, também, já é demais pra mim).
Depois, basta escolher um evento sem repetição, como o create (pra não deixar o jogo lento) e chamar o script. Ele retorna o path (caminho) de A a B. Grave esse path numa variável, mande o objeto andar nesse caminho e fim!
Ah, se não for possível achar o caminho através da grade, o script retornará "false".

Código:

//#define AStar1
//AStar1(larguraGrade, alturaGrade, lerguraCélula, alturaCélula, pontoAChegar, objetoAEvitar)
//acha o caminho (path) até o objetivo
//cuidado para que todas as opções de caminho estejam na grid

var lar, alt, larG, altG, mira, parede;

lar=argument0;    //largura total da array ou grid
alt=argument1;    //altura total da array ou grid
larG=argument2;  //espaçamento horizontal da grid
altG=argument3;  //espaçamento vertical da grid
mira=argument4;  //instância a ser atingida (pode ser um objeto)
parede=argument5; //objeto a ser evitado (pode ser um parent)

var i, j, aberta, fechada, g, h, f, origemx, origemy;
for(i=0; i<lar; i+=1){
   for(j=0; j<alt; j+=1){
      aberta[i, j]=false;  //false=não inclusa
      fechada[i, j]=false;  //false= não inclusa
      g[i, j]=0;            //até ser calculado, será 0
      h[i, j]=(abs((mira.x div larG)-i)+abs((mira.y div altG)-j))*10; //meh, melhor calcular logo
      f[i, j]=g[i, j]+h[i, j]; //só "h", por enquanto
      origemx[i, j]=i;        //todos apontam pra si
      origemy[i, j]=j;        // todos apontam pra si
      }
   }

var xo, yo, xs, ys;
xo=x div larG; yo=y div altG; //esses índices equivalem à posição do objeto na grid
xs=xo;        ys=yo;        //use esses quando definer que o caminho é atingível.
fechada[xo, yo]=true          //true=incluso

while(xo*larG!=mira.x || yo*altG!=mira.y){ //enquanto não alcança o objetivo
   var fVai, xPr, yPr;
   fVai=(lar * alt)*10; //começando como valor máximo, fVai equivale a passar por toda a grid
   xPr=xo; yPr=yo;      //"Pr” de próximo. Vai que os valores não sejam achados dentro do for...
   var preso;
      preso=0;
   //agora, checar cada uma das 9 células adjacentes
   for(i=-1; i<2; i+=1){
      for(j=-1; j<2; j+=1){
         if (fechada[xo+i, yo+j]==false){ //se a célula não está na lista fechada
            if (!place_meeting(xo*larG+i, yo*altG+j, parede)){ //se não há nada no caminho
               //agora, sabemos que a célula pode ser usada
               if (aberta[xo+i, yo+j]==false){ //se a célula NÃO está na lista aberta
                  aberta[xo+i, yo+j]=true;                            //põe na lista aberta
                  g[xo+i, yo+j]=g[xo, yo]+10+4*(i==j || abs(i-j)==2); //re-define g
                  f[xo+i, yo+j]=g[xo+i, yo+j]+h[xo+i, yo+j];          //re-define f
                  origemx[xo+i, yo+j]=xo;                            //atualiza origem
                  origemy[xo+i, yo+j]=yo;                            // atualiza origem
                  if (f[xo+i, yo+j]<=fVai){  //se é o menor “f” até agora
                     fVai=f[xo+i, yo+j]; //atualiza "f" máximo
                     xPr=xo+i; yPr=yo+j; //"Pr” de próximo. Não quero atualizar xo, yo antes do fim do loop
                     }
                  }
                  else{            //se a célula ESTÁ na lista aberta
                     if (g[xo+i, yo+j]>g[xo, yo]+10+4*(i==j || abs(i-j)==2)){    //se esse caminho é melhor
                        g[xo+i, yo+j]=g[xo, yo]+10+4*(i==j || abs(i-j)==2); //re-define g
                        f[xo+i, yo+j]=g[xo+i, yo+j]+h[xo+i, yo+j];          //re-define f
                        origemx[xo+i, yo+j]=xo; // atualiza origem
                        origemy[xo+i, yo+j]=yo; // atualiza origem
                        }
                     if (f[xo+i, yo+j]<=fVai){  //melhor caminho ou não, checa o valor de “f”
                        fVai=f[xo+i, yo+j]; // atualiza "f" máximo
                        xPr=xo+i; yPr=yo+j; //"Pr” de próximo. Não quero atualizar xo, yo antes do fim do loop
                        
                        }
                     }
               }
               else{ //tem algo no caminho
                  preso+=1;
                  }
            }
            else{ //fechada[xo+i, yo+j]==true
               preso+=1;
               }
         }
      } //fim dos loops "for" aqui
   if (preso==9){          //se não há pra onde ir
      var temJeito;
      temJeito=false; //”temJeito” de achar outro caminho
      for(i=0; i<lar; i+=1){
         for(j=0; j<alt; j+=1){
            if (aberta[i, j]=true && f[i, j]<fVai){
               xo=i; yo=j;    //pula pra lá
               temJeito=true;  //tem jeito de achar o caminho
               }
            }
         }
      if (temJeito==false){
         return(false)
         }
      }
      else{ //não está preso
         xo=xPr; yo=yPr;            //muda a célula em questão praquela com menor “f”
         }
   fechada[xo, yo]=true; aberta[xo, yo]=false; //tira a célula da lista aberta e inclui na lista fechada
   }

//ainda estamos aqui? Ótimo, isso significa que o caminho está garantido. Vamos traçá-lo.
var px, py, Path;
i=0;
while(1){ //vamos achar a origem de cada ponto e adicioná-lo a (mais) outras arrays
   px[i]=xo;
   py[i]=yo;
   xPr=xo; //um x, temporário, pra próxima declaração
   xo=origemx[xo, yo];
   yo=origemy[xPr, yo];
   i+=1;

   if (xs==xo && ys==yo){
      break;
      }
   }
px[i]=xs; py[i]=ys; i+=1; //adiciona o ponto final (não consegui fazer isso dentro do loop)

//agora, adicionar os pontos da array ao path, de trás pra frente
Path=path_add(); //cria o path
for (j=(i-1); j>=0; j-=1){
   path_add_point(Path, px[j]*larG, py[j]*altG, 100); //adiciona o ponto
   }
path_set_kind(Path, 0);
path_set_closed(Path, false);
return(Path) //retorna a id do path

Uau, imenso, né? É, e meio lento também. Só que ele só será chamado eventualmente, portanto não deixará o jogo lento E você sabe exatamente o que ele faz.

Agora, desfios pros hardcore makers:
- adicione caminhos legais, mas desfavoráveis (caminhos cuja travessia seja mais lenta) e leve isso em consideração no código
- modifique o path de modo que a grid fique hexagonal

EDIT: Ontem descobri que as funções built-in do game maker pre-supõem que você use a versão pro. Suponho que esse script use apenas funções lite. Alguém pode testar isso pra mim?

EDIT2: Apesar de pouca gente (ninguém) ter comentado, eu sigo convencido de que é uma boa usar o A*. Porque ele pode ser adaptado pra gerar o caminho seguindo as coordenadas que você quiser, tipo "SE POSSÍVEL, evite caminhos com areia, mas pode passar sobre a areia se não houver opção" ou "mova-se noma grid hexagonal" ou - esse era o meu objetivo inicial, quando pesquisei a respeito - mova-se em plataformas.
O que significa "mover-se em plataformas"? Pra mim, significa "mover-se sobre os pisos, de preferência, e evitar subidas, pra não cansar". Gostaria que significasse, também, "pular sobre espaços vazios, dar saltos em paredes, pendurar em cordas, etc", mas isso fica pra um futuro mais distante, um script mais elaborado que o que segue abaixo. SIM, eu consegui um script razoável pra movimentação em plataforma. Infelizmente, ainda não é possível fazer o computador entender por completo que a movimentação é em plataforma, então os saltos, escaladas, quedas e demais movimentos elaborados serão adicionados manualmente, através da checagem da posição do piso, o que nos obriga a traçar o path novamente, ao final do movimento. Mas já é um path razoável pra uma plataforma:

Código:

//#define AStarPlataform
//AStarPlataform(widthGrid, heightGrid, widthCell, heightCell, instanceToGet, objectToAvoid)
//finds a path to the goal
//please, make sure every possible cell is IN the grid
//It's an adaptation of the general A* that only allows orthogonal movement and gives preference to the horizontal ones

var wid, hei, widG, heiG, goal, blockin;

wid=argument0;    //width total of array or grid
hei=argument1;    //height total of array or grid
widG=argument2;  //horizontal spacing of grid
heiG=argument3;  //vertical spacing fo grid
goal=argument4;  //instance to hit (may be an object)
blockin=argument5; //object to avoid (may be a parent)

var i, j, open, closed, g, h, f, originx, originy;
for(i=0; i<wid; i+=1){
    for(j=0; j<hei; j+=1){
        open[i, j]=false;  //false=not included
        closed[i, j]=false; //false=not included
        g[i, j]=0;          //till it's calculated, it'll be 0
        h[i, j]=(abs((goal.x div widG)-i)+abs((goal.y div heiG)-j))*10; //meh, better calculate it all at once
        f[i, j]=g[i, j]+h[i, j]; //just "h", for now
        originx[i, j]=i;        //everyone points itself
        originy[i, j]=j;        //everyone points itself
        }
    }

var xo, yo, xs, ys;
xo=x div widG; yo=y div heiG; //those indices mean the object's position at the grid
xs=xo;        ys=yo;        //use these when the path have been made possible
closed[xo, yo]=true          //true=included

while(xo*widG!=goal.x || yo*heiG!=goal.y){ //while we don't reach the objective
    var fVai, xn, yn;
    fVai=(wid * hei)*10; //starting as a maximum value, fVai is equivalent to pass through every knot
    xn=xo; yn=yo;        //"n” for next. Maybe those values won't be reached into th "for"
    var trap;
    trap=0;
    //Now, I'll check each of the 9 adjacent cells
for (j=-1; j!=2; j=(j+2) mod 3){        //this strange "for" will check the top-bottom-middle cells, in this order
        for (i=-1; i!=2; i=(i+2) mod 3){ //this strange "for" will check the left-right-center cells, in this order
            if (closed[xo+i, yo+j]==false && i!=j && i+j!=0){ //if the cell is not on the closed list and is orthogonal
                if (!place_meeting(xo*widG+i, yo*heiG+j, blockin)){ //if there's nothing blicking the way
                    //now, we know the cell may be used
                    if (open[xo+i, yo+j]==false){ //if the cell is NOT on the open list
                        open[xo+i, yo+j]=true;                    //  it on the open list
                        g[xo+i, yo+j]=g[xo, yo]+10-20*(j);        //re-define g (-20j is to let going up as expensive as goind sideways - and going down a lot cheaper)
                        f[xo+i, yo+j]=g[xo+i, yo+j]+h[xo+i, yo+j]; //re-define f
                        originx[xo+i, yo+j]=xo;                    //update origin
                        originy[xo+i, yo+j]=yo;                    //update origin
                        if (f[xo+i, yo+j]<=fVai){  //if it's the smallest “f” so far
                            fVai=f[xo+i, yo+j];    //update maximum "f"
                            xn=xo+i; yn=yo+j;      //"n” for next. Don't wanna update xo, yo before the end of the loop.
                            }
                        }
                        else{            //if the cell IS in the open list
                            if (g[xo+i, yo+j]>g[xo, yo]+10){              //if this is the faster path
                                g[xo+i, yo+j]=g[xo, yo]+10-20*j;          //re-define g (-20j is to let going up as expensive as goind sideways - and going down a lot cheaper)
                                f[xo+i, yo+j]=g[xo+i, yo+j]+h[xo+i, yo+j]; //re-define f
                                originx[xo+i, yo+j]=xo;                    //update origin
                                originy[xo+i, yo+j]=yo;                    //update origin
                                }
                            if (f[xo+i, yo+j]<=fVai){  //faster or not, check the “f” value
                                fVai=f[xo+i, yo+j]; //update maximum "f"
                                xn=xo+i; yn=yo+j; //"n” for next. Don't wanna update xo, yo before the end of the loop.
                                }
                            }
                    }
                    else{ //there is something in the way
                        trap+=1;
                        }
                }
                else{ //closed[xo+i, yo+j]==true or not orthogonal
                    trap+=1;
                    }
            }
        } //end of "for" loops here
    if (trap==9){          //if trapped
        var hope;
        hope=false; //”hope” to find a path
   //check the whole grid, looking for a cell on the open list
        for(i=0; i<wid; i+=1){
            for(j=0; j<hei; j+=1){
                if (open[i, j]=true && f[i, j]<fVai){
                    xo=i; yo=j;    //jump there
                    hope=true;      //there is hope
                    }
                }
            }
        if (hope==false){ //if it's hopeless
            return(false) //give up and return "false". End of loop, end of history.
            }
        }
        else{ //not trapped
            xo=xn; yo=yn;            //change the current cell to the one with smallest “f”
            }
    closed[xo, yo]=true; open[xo, yo]=false; //take the cell out of the open list and  it on the closed list
    }

//We're still here? Great! That means the path has been found. Let's trace it!
var px, py, Path;
i=0;
while(1){ //we'll find the origin of each point and add to (even) more arrays
    px[i]=xo;
    py[i]=yo;
    xn=xo; //a teporary x, for the next statement
    xo=originx[xo, yo];
    yo=originy[xn, yo];
    i+=1;

    if (xs==xo && ys==yo){ //reached the start of the path
        break;
        }
    }
px[i]=xs; py[i]=ys; i+=1; //add the final point (I couldn't manage to do it inside the loop)

//now, let's add the points to the path, backwards
Path=path_add(); //creates path
for (j=(i-1); j>=0; j-=1){
    path_add_point(Path, px[j]*widG, py[j]*heiG, 100); //adds the point
    }

//fix (?) some points. Gotta test it to exaustion before accepting as a good code
for (j=0; j<path_get_number(Path)-2; j+=1){
   if (path_get_point_y(Path, j+1)==path_get_point_y(Path, j+2) && path_get_point_y(Path, j+1)<path_get_point_y(Path, j) && !place_meeting(path_get_point_x(Path, j+2), path_get_point_y(Path, j), blockin)){// && path_get_point_x(Path, j-1)!=path_get_point_x(Path, j)
      path_change_point(Path, j+1, path_get_point_x(Path, j+2), path_get_point_y(Path, j), 100);
      j-=2; //get back, making it a 2-way-loop
      }
   }


path_set_kind(Path, 0);
path_set_closed(Path, false);
return(Path) //return path id

Me desculpem por manter o script em inglês, mas não vou reescrevê-lo só pra "se" alguém ler. Havendo interesse, posso traduzir os comentários e variáveis, mas depois que alguém pedir isso.

achei muito bom saim!
vai ajudar muito para mim!

se puder traduiz!

Está muito bom o pathfinding.
O A* é o mais rápido que já ouvi falar.
Mas dizem que ele pode não conseguir achar um caminho, mesmo existindo.
Isso acontece raramente.
Eu pensei em comentar antes, só que já tinha passado muito tempo.

Caramba, tem tempo que não entro nesse tópico! Não tinha visto que existem comentários... Moçada, desculpe a demora pra responder, o tópico saiu dos "assuntos recentes" sem eu ter visto (25/fev, deve ter sido no carnaval, então... é, acho que sei porque não vi).

Adilson thiago, em breve editarei o tópico, com o script traduzido. Te mando uma MP, quando fizer.

Pedrø, isso aconteceu algumas vezes comigo, enquanto eu tentava traduzir a teoria pra código. Acontece que o A* faz uma série de loops e pega o caminho que parece mais fácil e, se não der, dá uma checada em volta pra ver quais elementos da grid ainda tem opção de repetir o teste. Existem alguns labirintos que, pela ordem de checar os elementos, acaba resultando num vai-e-vem que dá num beco-sem-saída. Aí, não importa quantas células você tenha em volta, uma hora vão acabar as células com vizinhas que ainda não foram testadas.
Só que isso é um erro de código, não da teoria. Uma vez que não restem mais vizinhas, o negócio é procurar pelas células que NÃO são vizinhas. O script faz isso. Agindo assim, não tem como não achar um caminho. Pode ser demorado, pode até não ser o melhor caminho (normalmente, é), mas acha.