GMBR
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.
Entrar

Esqueci-me da senha

Últimos assuntos
» Procuro Programador de game maker
por Wou Sex 15 Mar 2024, 10:27

» Retorno da GMBR!!!
por vinians Qui 14 Mar 2024, 19:07

» Mod APK
por gamerainha Qua 13 Mar 2024, 06:30

» Mudar cor de apenas uma palavra
por lunalol Sex 01 Mar 2024, 13:42

» Aceito pedidos de sprites (Com exemplos meus)
por Sevilha Qua 28 Fev 2024, 12:17

» Inventário simples
por Isquilo_Roedor Qui 22 Fev 2024, 15:18

» Problemas na programaçnao de inimigo [jogo DOOM LIKE]
por Black Mirror Dom 11 Fev 2024, 13:34

» ANDROID MULTI TOUCH
por DiegoBr Dom 04 Fev 2024, 12:13

» Servidor de Discord do fórum?
por Lighter Sáb 27 Jan 2024, 17:18

» Save e Load Json
por Klinton Rodrigues Qui 25 Jan 2024, 11:12

» Colisão com mais de um objeto
por aminaro Seg 22 Jan 2024, 15:02

» Oi sou novo aqui
por Thiago Silveira Alexandre Sáb 20 Jan 2024, 20:55

» Como acessar conteudo comprado no marketplace
por macmilam Sex 19 Jan 2024, 07:42

» Devlogs em vídeos do Block Room
por Joton Seg 15 Jan 2024, 16:56

» Alguém aqui já ganha dinheiro com seus games?
por Joton Seg 15 Jan 2024, 16:49

» ACERVO GMBR MAGAZINE
por Joton Qui 11 Jan 2024, 19:21

» como aumentar o obj sem aumentar a colisão??
por GabrielXavier Qua 10 Jan 2024, 07:21

» Asteroid Core - Early Acesse Update [0.2.0.0]
por JOZ. Seg 08 Jan 2024, 14:39

» Versionamento de código com GitHub
por GabrielXavier Seg 08 Jan 2024, 07:32

» Rio Rise - novo launcher do Gta San Andreas SAMP Brasil
por kolesovsup Sex 29 Dez 2023, 07:16

» a funçao approach ainda existe?
por PEDRINDEV Ter 26 Dez 2023, 20:05

» Inimigo ataca até por trás! >:(
por saim Sex 22 Dez 2023, 08:55

» [RESOLVIDO]Spawn após morte
por Deception_1999 Dom 17 Dez 2023, 16:39

» Remunerado $$$ - Procuro programador para ajudar a "montar" um jogo
por theguitarmester Sáb 02 Dez 2023, 16:28

» Game maker nao abre
por Cerf Dom 26 Nov 2023, 12:01


A* pathfinding - LITE?

3 participantes

Ir para baixo

A* pathfinding - LITE? Empty A* pathfinding - LITE?

Mensagem por saim Ter 23 Ago 2011, 16:38

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.
saim
saim

Games Ranking : Nota B

Notas recebidas : C-D-A-B
Data de inscrição : 14/01/2011
Reputação : 136
Número de Mensagens : 3033
Prêmios : A* pathfinding - LITE? Empty

Medalhas x 1 Tutoriais x 6 Moedas x 0

Ouro x 1 Prata x 0 Bronze x 3

Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0

Ir para o topo Ir para baixo

A* pathfinding - LITE? Empty Re: A* pathfinding - LITE?

Mensagem por Adilson thiago Sáb 25 Fev 2012, 13:57

achei muito bom saim!
vai ajudar muito para mim!

se puder traduiz!
Adilson thiago
Adilson thiago

Data de inscrição : 07/02/2012
Reputação : 1
Número de Mensagens : 31
Prêmios : A* pathfinding - LITE? Empty

Medalhas x 0 Tutoriais x 0 Moedas x 0

Ouro x 0 Prata x 0 Bronze x 0

Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0

Ir para o topo Ir para baixo

A* pathfinding - LITE? Empty Re: A* pathfinding - LITE?

Mensagem por PedroX Sáb 25 Fev 2012, 14:51

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.

_________________


Leia o Manual do Iniciante e a Lista de Tutoriais, para aprender bastante sobre o GM.
Recomendo o Manual completo das colisões, bem útil.
O exemplo Criar um chat (banir, kickar, etc) é interessante.

Para seu jogo ficar rápido e legal, aprenda a Aumentar o desempenho do seu jogo.

Aprenda a calcular a velocidade de suas animações


Entre para o Clube do Inglês:
PedroX
PedroX

Games Ranking : Nota B

Notas recebidas : C+B
Data de inscrição : 26/07/2008
Reputação : 311
Número de Mensagens : 6086
Prêmios : A* pathfinding - LITE? Empty

Medalhas x 0 Tutoriais x 17 Moedas x 0

Ouro x 0 Prata x 0 Bronze x 0

Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0

https://web.whatsapp.com/send?phone=5519995935953&text=Pedro

Ir para o topo Ir para baixo

A* pathfinding - LITE? Empty Re: A* pathfinding - LITE?

Mensagem por saim Sex 10 Ago 2012, 17:03

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.
saim
saim

Games Ranking : Nota B

Notas recebidas : C-D-A-B
Data de inscrição : 14/01/2011
Reputação : 136
Número de Mensagens : 3033
Prêmios : A* pathfinding - LITE? Empty

Medalhas x 1 Tutoriais x 6 Moedas x 0

Ouro x 1 Prata x 0 Bronze x 3

Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0

Ir para o topo Ir para baixo

A* pathfinding - LITE? Empty Re: A* pathfinding - LITE?

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo

- Tópicos semelhantes

 
Permissões neste sub-fórum
Não podes responder a tópicos