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
» Retorno da GMBR!!!
por theguitarmester Ter 19 Mar 2024, 22:38

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

» 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


Alteração em A*

5 participantes

Ir para baixo

Alteração em A* Empty Alteração em A*

Mensagem por saim Sáb 20 Jul 2013, 11:14

Estou pensando num jogo que usa um pathfinding um pouco diferente do que eu estou acostumado a lidar. Eu sei usar o A*, mas nunca tinha pensado nessa modificação.
É o seguinte, o A* usa o conceito de células. Algumas células são "permitidas" e outras, "proibidas". O caminho é traçado através das células.

O que eu quero, na verdade, ESTÁ previsto pelo A*, mas duma forma que eu nunca estudei nem me preocupei. Eu tenho PONTOS e o que é "permitido" ou "proibido" é o caminho entre um ponto e outro.
Esses pontos são cruzamentos e os caminhos são ruas. Algumas ruas estão bloqueadas, outras não. Eu fiz um desenho pra tentar explicar melhor.
Alteração em A* Pathfind

Claro, eu posso tratar cada um desses caminhos como sequências de células, mas isso me parece desnecessariamente lento.
Alguém tem alguma idéia de como escrever um script nessas condições?
Se apresentar o script pronto, por favor comente. Eu certamente vou querer alterar um monte de coisas, como colocar bloqueios que atrasam, mas não impedem passagem ou obstáculos que são transponíveis mas custam alguma coisa.

Já agradeço com atecedência.
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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por theguitarmester Sáb 20 Jul 2013, 11:46

Li e reli e não consegui o que você quer, você explicou o que queria, mas não consegui entender a diferença do que você quer para o path_find normal.

Eu nunca criei um path findind própio, por não precisar de um exclusivo, visto que já há o do GM, mas acredito que se tentar consigo, então, vou dizer a lógica do que eu faria, e me diga se é algo assim que queres:
1° ele tentaria ir reto, indo na direção de um ponto a outro,, com obstáculos, ele criaria outras rotas próximas para passar.
Desse modo, acho que a velocidade de carregamento seria rápida.
vou criar uma engine...


______Editado:
pensei mais um pouco, e então, cheguei a conclusão que você pode estar querendo um sistema parecido ao do google maps que vai seguindo por ruas e acha o caminho mais perto, seria isto?
theguitarmester
theguitarmester

Games Ranking : Nota C

Notas recebidas : B + C
Data de inscrição : 28/02/2012
Reputação : 139
Número de Mensagens : 2208
Prêmios : Alteração em A* Empty

Medalhas x 0 Tutoriais x 4 Moedas x 0

Ouro x 2 Prata x 2 Bronze x 1

Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 1
Plataformas :
  • Unity


http://guitarmester.no.comunidades.net/index.php?pagina=19362978

Ir para o topo Ir para baixo

Alteração em A* Empty Re: Alteração em A*

Mensagem por saim Sáb 20 Jul 2013, 13:24

Exatamente! Um sistema desses, com a facilidade de que todas as ruas são ortogonais e de mesmo comprimento.
O A* que eu conheço marca as CÉLULAS como permitidas ou proibidas, não as interfaces. Na minha situação, TODAS as células são permitidas, mas ir de algumas pras outras, não.
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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por theguitarmester Sáb 20 Jul 2013, 13:39

bah, tinha começado a fazer a engine em um modo, mas ela não vai dar certo!
vou excluir ela o que precisa, e refazer de um nova forma, que de para ir andando e ruas que estejam em qualquer direção(ou só em ortogonal se não conseguir). (vou tentar)
theguitarmester
theguitarmester

Games Ranking : Nota C

Notas recebidas : B + C
Data de inscrição : 28/02/2012
Reputação : 139
Número de Mensagens : 2208
Prêmios : Alteração em A* Empty

Medalhas x 0 Tutoriais x 4 Moedas x 0

Ouro x 2 Prata x 2 Bronze x 1

Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 1
Plataformas :
  • Unity


http://guitarmester.no.comunidades.net/index.php?pagina=19362978

Ir para o topo Ir para baixo

Alteração em A* Empty Re: Alteração em A*

Mensagem por luiz_eldorado Sáb 20 Jul 2013, 14:30

Bem, fui ver agora o script do A*, é algo realmente muito complicado de ler Alteração em A* 916736

Mas eu pude perceber que existe uma array (na verdade, várias arrays) que mostram quais células estão bloqueadas ou livres. Então, bastaria fixar as bloqueadas que você quer, de uma forma que o script não "desbloqueie" elas (provavelemente, o A* só bloqueia, não faz o contrário).

Algo como colocar, em algum lugar um "fechada[x,y]=true;".
luiz_eldorado
luiz_eldorado

Games Ranking : Nota C

Notas recebidas : C
Data de inscrição : 30/07/2011
Reputação : 47
Número de Mensagens : 928
Prêmios : Alteração em A* Empty

Medalhas x 0 Tutoriais x 0 Moedas x 0

Ouro x 0 Prata x 0 Bronze x 1

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

http://luizpontes.tk/

Ir para o topo Ir para baixo

Alteração em A* Empty Re: Alteração em A*

Mensagem por Rodrigo Santiago Sáb 20 Jul 2013, 14:46

Você poderia usar uma dll, mais rápida, porque você terá que colocar os quadrados pretos coom objetos dentro da função.

Pra ficar mais rápido coloque colisão retangular, circular, diamante mais não precisa.
Rodrigo Santiago
Rodrigo Santiago

Games Ranking : Nota B

Notas recebidas : C + C + B
Data de inscrição : 28/07/2012
Reputação : 73
Número de Mensagens : 1281
Prêmios : Alteração em A* Empty

Medalhas x 0 Tutoriais x 0 Moedas x 0

Ouro x 3 Prata x 1 Bronze x 3

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

Ir para o topo Ir para baixo

Alteração em A* Empty Re: Alteração em A*

Mensagem por saim Sáb 20 Jul 2013, 15:01

Reli a teoria do A*. Parece que vai ser só uma questão de ignorar as células com obstáculo no caminho, como se ela fosse uma célula "proibida" e, no mais, considerar que todas as células são "permitidas". O andamento do cálculo DEVE dar conta do resto.

Mas tem a possibilidade de eu "dar a volta" e dar de cara com uma célula já percorrida... hm... E se eu considerasse o valor de "F", nesses casos, como algo maior que o possível, de modo que fique impossível para o jogo considerar que aquele caminho é mais vantajoso, mesmo que seja considerado possível? Tipo assim:
Código:
nLinhas := ?; nColunas := ?; impossível := nLinhas * nColunas;
(no loop que checa o melhor caminho){
if (bloqueado){
F := impossível;
}
else {
F := G + H;
}
}
Vou testar e volto a postar assim que tiver algum resultado.
Me digam se acham que o valor de "impossível" não deve ser só linhas x colunas. A princípio, me pareceu a maior trajetória possível num labirinto, mas eu posso estar errado.
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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por theguitarmester Sáb 20 Jul 2013, 15:44

Não conhecia essa teoria do A*, vou ler este artigo agora. interessante...
theguitarmester
theguitarmester

Games Ranking : Nota C

Notas recebidas : B + C
Data de inscrição : 28/02/2012
Reputação : 139
Número de Mensagens : 2208
Prêmios : Alteração em A* Empty

Medalhas x 0 Tutoriais x 4 Moedas x 0

Ouro x 2 Prata x 2 Bronze x 1

Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 1
Plataformas :
  • Unity


http://guitarmester.no.comunidades.net/index.php?pagina=19362978

Ir para o topo Ir para baixo

Alteração em A* Empty Re: Alteração em A*

Mensagem por PedroX Sáb 20 Jul 2013, 17:31

Não consegui entender.

Claro, eu posso tratar cada um desses caminhos como sequências de células

Como seria isso?

_________________


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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por saim Sáb 20 Jul 2013, 21:32

PedroX escreveu:Não consegui entender.
Claro, eu posso tratar cada um desses caminhos como sequências de células
Como seria isso?
Pegue o desenho. Cada rua é um espaço sem células, cada cruzamento é uma célula. Agora, diminua o tamanho de cada célula, até ela ficar do tamanho do cruzamento e preencha as ruas com células. Coloque células "proibidas" preenchendo todos os quarteirões e, onde houver bloqueio, coloque mais uma "proibida".
Funcionar, teoricamente funciona. Mas vai ser MUITO lento. Se eu não conseguir uma solução, tudo bem: vou usar o pathfinding uma vez a cada, digamos, 5 minutos. Não segundos: minutos. Então, se for o último recurso, ainda é viável. Mas não desisti, ainda.

Ah, ainda não testei aquilo que escrevi acima. Minha mulher sequestrou o computador pra jogar candy crush a tarde inteira... ¬¬
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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por Rodrigo Santiago Sáb 20 Jul 2013, 22:29

Apenas pra explicar:
Simplifique quadras e ruas em pontos:
Alteração em A* Y7pr
Quadras são pontos proibidos, pontos rosas são proibidos, amarelo origem e verde destino.
Cinza é o caminho, dai, você poderá multiplicar x e y para que se ajustem a largura das quadras originais
Rodrigo Santiago
Rodrigo Santiago

Games Ranking : Nota B

Notas recebidas : C + C + B
Data de inscrição : 28/07/2012
Reputação : 73
Número de Mensagens : 1281
Prêmios : Alteração em A* Empty

Medalhas x 0 Tutoriais x 0 Moedas x 0

Ouro x 3 Prata x 1 Bronze x 3

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

Ir para o topo Ir para baixo

Alteração em A* Empty Re: Alteração em A*

Mensagem por saim Sáb 20 Jul 2013, 23:06

...muito boa, a idéia!
Eu não tinha conseguido ver o problema dessa maneira. A geometria da grade NÃO PRECISA ser equivalente à geometria da tela. Vai ser um exercício mental transformar isso, mas acho que vai valer a pena.
Vou tentar isso antes de tentar a outra idéia (que estava começando, já). Mas amanhã. Hoje eu tenho que dormir.
Assim que resolver, posto a solução.

[update 23/07/2013] Cara, eu estava olhando o problema com a ótica da origem das sprites (das ruas, quarteirões e cruzamentos) no ponto (0, 0). Isso estava me gerando um monte de problemas que centralizar a origem das sprites resolveria. Resolvi centralizar e ver que consequência isso me traria pra minha grid. Acabou que agora, não preciso mais adaptar nada. O que eu temia que fosse complicar demais meu esquema, acabou simplificando enormemente!
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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por saim Qui 25 Jul 2013, 16:35

DOUBLE POST!!!
Mas é por uma boa causa. O problema parece resolvido. Acabou que com a centralização da sprite, eu até podia usar o A*-padrão, porque a grid FICOU regular. Mas eu já estava com meio-caminho andado, vislumbrando a grid como células sem dimensão. Ainda não sabia - e terminei sem saber - como fazer pra aplicar as dimensões diferentes, mas o script já estava adiantado.

Como cada célula tem apenas 4 direções, achei mais prático ir analisando caso-a-caso do que usar um loop. Pra reduzir a geometria a uma grid, eu tinha usado objetos pros cruzamentos, ruas e quarteirões. Agora sei que não precisava, mas como está feito, vou manter assim - os sons do jogo vão deixar proporcionalmente ínfimo, o aumento do tamanho do arquivo.
Na imagem, a grid em vermelho (isso eu fiz no paint, ela não fica visível no jogo), os quarteirões em preto, as ruas em azul, os cruzamentos em magenta, as células bloqueadas com um círculo branco em volta (as ruas, também uma placa) e o path em amarelo. O início do path com um "V" verde e o final, com um "X" vermelho.
Alteração em A* Grid
E o script:
Código:
// mapAStar(nLinhas, nColunas, linhaOrigem, colunaOrigem, linhaDestino, colunaDestino, xGrid, yGrid, widCel, heiCel);
// cria um path de um cruzamento a outro, levando em conta as ruas bloqueadas, numa grid regular.
// considera as ruas e os quarteirões como células
// pré-supõe a existência de uma array "bloqueado"
var nLinhas, nColunas, linhaOrigem, coluna, linhaDestino, colunaDestino, xGrid, yGrid, widCel, heiCel;
var i; i = 0;
nLinhas := argument[i]; i += 1; // 0; número de linhas na grid
nColunas := argument[i]; i += 1; // 1; número de colunas na grid
linhaOrigem := argument[i]; i += 1; // 2; linha de origem
colunaOrigem := argument[i]; i += 1; // 3; coluna de origem
linhaDestino := argument[i]; i += 1; // 4; linha do destino
colunaDestino := argument[i]; i += 1; // 5; coluna do destino
xGrid := argument[i]; i += 1; // 6; posição do início da grid, na tela
yGrid := argument[i]; i += 1; // 7; posição do início da grid, na tela
widCel := argument[i]; i += 1; // 8; largura de cada célula
heiCel := argument[i]; i += 1; // 9; altura de cada célula

// inicializa os valores básicos
var j, aberta, fechada, proibida, F, G, H, origCol, origLin;
for(i := 0; i < nColunas; i += 1){
    for (j := 0; j < nLinhas; j += 1){
        aberta[i, j] := false;  //false=não inclusa
        fechada[i, j] := false; //false= não inclusa
        H[i, j] := abs(linhaDestino - j) + abs(colunaDestino - i); // custo estimado
        G[i, j] := 0; // custo caminhado (até ser calculado, será 0)
        F[i, j] := G[i, j] + H[i, j];
        origCol[i, j]=i; //todos apontam pra si
        origLin[i, j]=j; // todos apontam pra si
        }
    }

var xa, ya, xi, yi;
xi := colunaOrigem; yi := linhaOrigem; // posição inicial (pra, no final, fazer o caminho inverso)
xa := xi; ya := yi; // posição atual, na grid
fechada[xa, ya] := true;

while(xa != colunaDestino || ya != linhaDestino){
    var FVai, xPr, yPr, preso;
    FVai := nColunas * nLinhas * 10; //começando como valor máximo, FVai equivale a passar por toda a grid
    xPr := xa; yPr := ya; //"Pr” de próximo. Vai que os valores não sejam achados dentro do for...
    preso := 0; // se for igual ao número de alternativas, nenhuma célula adjacente é permitida

    // agora, checar cada uma das 4 células adjacentes

    // célula à esquerda -> 0
    if (xa - 1 >= 0){
        if (fechada[xa - 1, ya] == false){ // se não está na lista fechada
            if (bloqueado[xa - 1, ya] == false){ // se não há nada no caminho
                if (aberta[xa - 1, ya] == false){ // se a célula NÃO está na lista aberta
                    aberta[xa - 1, ya] := true; //põe na lista aberta
                    G[xa - 1, ya] := G[xa, ya] + 10; // re-define G
                    F[xa - 1, ya] := G[xa - 1, ya] + H[xa - 1, ya]; // re-define F
                    origCol[xa - 1, ya] := xa; origLin[xa - 1, ya] := ya; // define a origem
                    if (F[xa - 1, ya] <= FVai){
                        FVai := F[xa - 1, ya];
                        xPr := xa - 1; yPr := ya; // marca a célula pra ser a próxima, caso nada melhor apareça
                        }
                    }
                   else { //se a célula ESTÁ na lista aberta
                        if (G[xa - 1, ya] > G[xa, ya] + 10){ // se por aqui é um caminho melhor
                            G[xa - 1, ya] := G[xa, ya] + 10; // re-define G
                            F[xa - 1, ya] := G[xa - 1, ya] + H[xa - 1, ya]; // re-define F
                            origCol[xa - 1, ya] := xa; origLin[xa - 1, ya] := ya; // re-define a origem
                            }
                        if (F[xa - 1, ya] <= FVai){ // melhor caminho ou não, checa o valor de “F”
                            FVai := F[xa - 1, ya];
                            xPr := xa - 1; yPr := ya; // marca a célula pra ser a próxima, caso nada melhor apareça
                            }
                        }
                } else { preso += 1;} // se bloqueado == true
            } else { preso += 1;} // se fechada == true
        } else { preso += 1;} // se está na beirada

    // célula à direita -> 1
    if (xa + 1 < nColunas){
        if (fechada[xa + 1, ya] == false){ // se não está na lista fechada
            if (bloqueado[xa + 1, ya] == false){ // se não há nada no caminho
                if (aberta[xa + 1, ya] == false){ // se a célula NÃO está na lista aberta
                    aberta[xa + 1, ya] := true; //põe na lista aberta
                    G[xa + 1, ya] := G[xa, ya] + 10; // re-define G
                    F[xa + 1, ya] := G[xa + 1, ya] + H[xa + 1, ya]; // re-define F
                    origCol[xa + 1, ya] := xa; origLin[xa + 1, ya] := ya; // define a origem
                    if (F[xa + 1, ya] <= FVai){
                        FVai := F[xa + 1, ya];
                        xPr := xa + 1; yPr := ya; // marca a célula pra ser a próxima, caso nada melhor apareça
                        }
                    }
                    else { //se a célula ESTÁ na lista aberta
                        if (G[xa + 1, ya] > G[xa, ya] + 10){ // se por aqui é um caminho melhor
                            G[xa + 1, ya] := G[xa, ya] + 10; // re-define G
                            F[xa + 1, ya] := G[xa + 1, ya] + H[xa + 1, ya]; // re-define F
                            origCol[xa + 1, ya] := xa; origLin[xa + 1, ya] := ya; // re-define a origem
                            }
                        if (F[xa + 1, ya] <= FVai){ // melhor caminho ou não, checa o valor de “F”
                            FVai := F[xa + 1, ya];
                            xPr := xa + 1; yPr := ya; // marca a célula pra ser a próxima, caso nada melhor apareça
                            }
                        }
                } else { preso += 1;} // se bloqueado == true
            } else { preso += 1;} // se fechada == true
        } else { preso += 1;} // se está na beirada

    // célula acima -> 2
    if (ya - 1 >= 0){
        if (fechada[xa, ya - 1] == false){ // se não está na lista fechada
            if (bloqueado[xa, ya - 1] == false){ // se não há nada no caminho
                if (aberta[xa, ya - 1] == false){ // se a célula NÃO está na lista aberta
                    aberta[xa, ya - 1] := true; //põe na lista aberta
                    G[xa, ya - 1] := G[xa, ya] + 10; // re-define G
                    F[xa, ya - 1] := G[xa, ya - 1] + H[xa, ya - 1]; // re-define F
                    origCol[xa, ya - 1] := xa; origLin[xa, ya - 1] := ya; // define a origem
                    if (F[xa, ya - 1] <= FVai){
                        FVai := F[xa, ya - 1];
                        xPr := xa; yPr := ya - 1; // marca a célula pra ser a próxima, caso nada melhor apareça
                        }
                    }
                    else { //se a célula ESTÁ na lista aberta
                        if (G[xa, ya - 1] > G[xa, ya] + 10){ // se por aqui é um caminho melhor
                            G[xa, ya - 1] := G[xa, ya] + 10; // re-define G
                            F[xa, ya - 1] := G[xa, ya - 1] + H[xa, ya - 1]; // re-define F
                            origCol[xa, ya - 1] := xa; origLin[xa, ya - 1] := ya; // re-define a origem
                            }
                        if (F[xa, ya - 1] <= FVai){ // melhor caminho ou não, checa o valor de “F”
                            FVai := F[xa, ya - 1];
                            xPr := xa; yPr := ya - 1; // marca a célula pra ser a próxima, caso nada melhor apareça
                            }
                        }
                } else { preso += 1;} // se bloqueado == true
            } else { preso += 1;} // se fechada == true
        } else { preso += 1;} // se está na beirada

    // célula abaixo -> 3
    if (ya + 1 < nLinhas){
        if (fechada[xa, ya + 1] == false){ // se não está na lista fechada
            if (bloqueado[xa, ya + 1] == false){ // se não há nada no caminho
                if (aberta[xa, ya + 1] == false){ // se a célula NÃO está na lista aberta
                    aberta[xa, ya + 1] := true; //põe na lista aberta
                    G[xa, ya + 1] := G[xa, ya] + 10; // re-define G
                    F[xa, ya + 1] := G[xa, ya + 1] + H[xa, ya + 1]; // re-define F
                    origCol[xa, ya + 1] := xa; origLin[xa, ya + 1] := ya; // define a origem
                    if (F[xa, ya + 1] <= FVai){
                        FVai := F[xa, ya + 1];
                        xPr := xa; yPr := ya + 1; // marca a célula pra ser a próxima, caso nada melhor apareça
                        }
                    }
                    else { //se a célula ESTÁ na lista aberta
                        if (G[xa, ya + 1] > G[xa, ya] + 10){ // se por aqui é um caminho melhor
                            G[xa, ya + 1] := G[xa, ya] + 10; // re-define G
                            F[xa, ya + 1] := G[xa, ya + 1] + H[xa, ya + 1]; // re-define F
                            origCol[xa, ya + 1] := xa; origLin[xa, ya + 1] := ya; // re-define a origem
                            }
                        if (F[xa, ya + 1] <= FVai){ // melhor caminho ou não, checa o valor de “F”
                            FVai := F[xa, ya + 1];
                            xPr := xa; yPr := ya + 1; // marca a célula pra ser a próxima, caso nada melhor apareça
                            }
                        }
                } else { preso += 1;} // se bloqueado == true
            } else { preso += 1;} // se fechada == true
        } else { preso += 1;} // se está na beirada

    // checou as 4 direções
    
    if (preso == 4){ // se não há pra onde ir
        if (debug_mode == true){
            show_message("esteve preso, FVai valia " + string(FVai));
            }
        // verifica nos outros caminhos se restou algum ainda não verificado
        var temJeito; temJeito := false; // temJeito de continuar procurando
        for (i := 0; i < nColunas; i += 1){
            for(j := 0; j < nLinhas; j += 1){
                if (aberta[i, j] == true && F[i, j] <= FVai){ // se está na lista aberta e o custo é o menor de todos
                    xPr := i; yPr := j; FVai := F[i, j];
                    temJeito := true;
                    }
                }
            }
        if (temJeito == false){ // se não tem jeito
            return(-1); // encerra o script
            }
        }
    
    xa := xPr; ya := yPr; // muda a célula atual praquela com menor "F"
    fechada[xa, ya] := true; // põe na lista fechada
    aberta[xa, ya] := false; // tira da lista aberta
    
    }

// se até o momento não teve um "return(-1)", o path é garantido
var px, py, Path;
i := 0;

while (1){ // enquanto não tiver um break
    px[i] := xa; py[i] := ya;
    xa := origCol[px[i], py[i]];
    ya := origLin[px[i], py[i]];
    if (px[i] == xi && py[i] == yi){
        break;
        }
        else {
            i += 1;
            }
    }

// agora, adiciona os pontos da array (px, py) ao path, de trás pra frente
Path := path_add();
for (j := i; j >= 0; j -= 1){
    path_add_point(Path, xGrid + px[j] * widCel, yGrid + py[j] * heiCel, 100);
    }
path_set_kind(Path, 0); // ângulos retos
path_set_closed(Path, false); // path aberto
return(Path) //retorna a id do path
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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por Rodrigo Santiago Qui 25 Jul 2013, 17:28

Não entendi o porque desse script todo porque vc não usa o mp_grid?
Rodrigo Santiago
Rodrigo Santiago

Games Ranking : Nota B

Notas recebidas : C + C + B
Data de inscrição : 28/07/2012
Reputação : 73
Número de Mensagens : 1281
Prêmios : Alteração em A* Empty

Medalhas x 0 Tutoriais x 0 Moedas x 0

Ouro x 3 Prata x 1 Bronze x 3

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

Ir para o topo Ir para baixo

Alteração em A* Empty Re: Alteração em A*

Mensagem por PedroX Qui 25 Jul 2013, 18:55

O seu script ficou legal (analisando o código). Estava tentando fazer, mas parei por AQUI. Não parece muito lento. Ainda vou testar o seu novo script.

_________________


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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por saim Sáb 27 Jul 2013, 10:18

Rodrigo Santiago escreveu:Não entendi o porque desse script todo porque vc não usa o mp_grid?
Besteira minha, mesmo. Tem duas explicações.
Como disse antes, eu não estava conseguindo enxergar a simetria, porque não tinha centralizado as sprites, então surgiu a necessidade de criar um script próprio. Mas eu tenho um motivo pra acreditar que o meu script é mais rápido que o built-in (não que isso vá importar, no meu jogo). É que eu checo apenas 4 direções, o built-in permite andar na diagonal, o que significa que checa 8 direções. Se bem que, se não me engano, há um argumento pra isso; ele pode ser usado pra acelerar o script, assim esse trabalho todo pode ter sido causado só por falta de visão mesmo.
A outra explicação é que eu tenho uma pequena aversão aos built-in do game maker. Não uso solid, raramente uso speed e direction e, principalmente, odeio os move_contact. Essa mania começou quanto o move_contact dava erro no jogo todo e criar meus próprios scripts resolviam. Se eu não sei o que está acontecendo, não sei como consertar. Se o script é meu, eu sei o que está acontecendo.
Mas nunca usei o A* built-in, então não tenho como dizer se ele dá algum problema ou não (não vejo como poderia dar).

PedroX escreveu:O seu script ficou legal (analisando o código). Estava tentando fazer, mas parei por AQUI. Não parece muito lento. Ainda vou testar o seu novo script.
Ah, ele funciona! Não cheguei a rodar ele em debug mode (achei o erro antes de fazer isso), mas tem uma mensagenzinha que pode ser irritante, então se quiser eliminar um "if debug mode" no script, pode ser uma boa.
Clique num quadrado magenta pra marcar o começo do caminho, clique outro pra :
a) bloquear aleatoriamente algumas ruas
b) marcar o final do path
c) iniciar o path
A engine não está muito didática, então pode ser meio chato de entender o que eu fiz e, principalmente, PORQUE eu fiz. Mas o script está bem comentado, porque é o tipo de coisa que eu posso usar no futuro.

Essa história toda é porque quero que o jogador vá de um ponto a outro correndo contra o relógio e preciso estabelecer um limite de tempo. A engine não dá o MELHOR caminho, então corro o risco de dar tempo demais ao jogador, mas agora não corro mais o risco de dar um tempo impossível.
Claro, o jogador precisa de uns segundos pra reagir, então vou dar uns segundos antes de começar a contar o tempo e ainda dar 10% a mais, pra ele errar um pouco, mas essa engine me dá o limite mínimo.
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 : Alteração em A* 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

Alteração em A* Empty Re: Alteração em A*

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo


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