O TEMA DO FÓRUM ESTÁ EM MANUTENÇÃO. FEEDBACKS AQUI: ACESSAR

Pathfinding

Iniciado por Brandt, 13/03/2020 às 22:21

13/03/2020 às 22:21 Última edição: 13/04/2020 às 19:59 por Brandt


Pathfinding | v1.2.1 | por Brandt



para RPG Maker VX Ace



Descrição

O título é bem explicativo. Inclúi alguns features levantados como ideia no tópico da @Kawthar (aqui) como:

  • Fazer eventos seguirem outros eventos e o personagem;
  • Lidar com partes móveis no mapa (eventos e tal, que mudam a passabilidade também);
  • E não exigir que o caminho seja percorrido completamente (Ex.: Tem um caminho de A até B, mas um evento parou na frente, bloqueando a passagem. Ao invés de desistir de seguir o caminho, ir até onde dá e parar onde a distância até o destino for menor);
  • Otimizações em todo lugar possível pra evitar destruição e caos total, embora essa parte ainda esteja sendo aprimorada ;P

Instruções

Siga as instruções nos comentários no próprio código.


Changelog

Spoiler


v1.2.1

  • Melhorias para movimento diagonal.

v1.2.0

  • Melhoria de performance para cálculo de rotas impossíveis;
  • Adicionada configuração para limite de tamanho da rota calculada.

v1.1.0

  • Adicionado método cancel_path para cancelamento de rota;
  • Otimização para perseguição de characters.

[close]


Script

Código (Gist)

Versões anteriores


Código (Gist) (v1.2.0)

Código (Gist) (v1.1.0)

Código (Pastebin) (v1.0.1)

[close]

Licença:


~ Masked

Boaaaa!!

Agora esse é o tipo de coisa que eu adoro fazer haha  :wow:

Aliás, curiosamente foi o que tive que fazer semana passada, mas era em um board extremamente reduzido (4x4), acabei usando o basicão mesmo (Dijkstra).

Agora a parte maneira que você adicionou foi ele recalcular a rota em caso de ser obstruido e panz, bom com certeza é uma das coisas mais úteis para se ter em um jogo.

Sempre achei montar esses algoritmos show! Mais um belo trabalho pra sua lista de códigos maneiros!

Não tá afim de trazer essa belezinha pro MV não?

Eu curto também, principalmente quando dá pra ver funcionando depois aheauheua

Essa parte de recalcular quando bate em um obstáculo foi a solução que eu achei pra não ter que recalcular o caminho todo frame (que fritava o framerate hahaha), bom saber que ficou interessante aheuaheua

Esse é um dos que eu curti bastante estudar e fazer, realmente vai entrar pra lista dos maneirinhos.

Credo, Javascript. Algum dia, quem sabe xd
~ Masked

Muito bom!
Típico script que oferece uma outra personalidade ao jogo.
Ótimo trabalho!

Vocês inspiram qualquer um a querer programar ao nível de vocês!
Um ótimo trabalho! Meus parabéns!

14/03/2020 às 09:27 #5 Última edição: 14/03/2020 às 13:29 por Jorge_Maker
Nem cheguei a testar, mas, pela leitura que fiz do código, arrisco dizer que este é o melhor pathfind, em termos de performance e inteligência, feito pro VXAce por estas bandas. :fifufi:
Obrigado pela contribuição, Masked. (o/
Oxe

15/03/2020 às 16:56 #6 Última edição: 15/03/2020 às 17:00 por Brandt
@Darkrafa

Opa, valeu mano \o


@Eliyud

Que bom, acho que esse é meu objetivo hahaha
Obrigado o/


@Jorge_Maker

Hehehehe, afirmação poderosa essa aí, fico lisonjeado pela confiança. Enois \o)





Atualização (v1.1.0)

Acabei precisando refatorar o script pra usar ele aqui, também já aproveitei e dei uma limpada no código (agora tá orientado a objetos mesmo, em contraste com aquela pilha de gambiarra de antes hahaha). O funcionamento do script continua o mesmo, mas adicionei um método para cancelar o pathfinding também. Além disso, consegui otimizar um pouco mais o cálculo da rota principalmente no caso de perseguição de outro character.

Se alguém tiver colocado o script no projeto, recomendo pegar a versão mais nova pelo link no tópico.
~ Masked

12/04/2020 às 23:28 #7 Última edição: 12/04/2020 às 23:36 por Brandt
Atualização (v1.2.0)

Implementei um teste de regiões fechadas usando o algoritmo de flood fill, agora o script não deve mais apresentar lag quando tenta-se encontrar um caminho entre dois pontos entre os quais nunca existe nenhum caminho. O custo disso é um processamento considerável durante o carregamento do mapa, mas não deve ser nada absurdo a ponto de ser perceptível.

Também adicionei uma constante de tamanho máximo para o caminho, dessa forma é possível evitar que o script tente achar caminhos longos demais, gerando lag. O flood fill deve dar conta de evitar boa parte dos caminhos impossíveis, então esse valor pode ficar relativamente alto sem grandes problemas.

Fiquem aí também com algumas demonstrações do algoritmo:



Preenchendo a maior região fechada onde o jogador está + paredes onde ele pode bater




Preenchendo todas as regiões do mapa. O que o pathfinding faz é usar isso e simplesmente não calcular caminhos que tentem começar em um cor e terminar em uma cor diferente.
~ Masked

Mas já?! Quando falou sobre isso no Discord pensei que iria levar um tempinho a mais pra concluir. xD
A sacada de usar o flood fill para lidar com o problema de caminhos bloqueados foi genial! Só ressaltando mais uma vez, este é, com certeza, o Pathfind número um feito pro Meiker. u_u
Oxe

Ah, eu tava com a faca e o queijo na mão né hahaha

A ideia que implementei acabou não sendo bem aquela que comentei no Discord. Por enquanto, optei por calcular todas as regiões no carregamento do mapa mesmo, porque calcular em tempo real limitando à tela pode ter uns drawbacks (não conseguir achar caminhos fora da tela, no caso xd)

Acho que também tem como melhorar a implementação ainda hehe

Valeu Jorge \o
~ Masked

Atualização (v1.2.1)

Dei um tapa no movimento diagonal, que estava um pouco estranho. Agora o script leva em conta que o movimento na diagonal tem uma distância maior que o movimento em quatro direções e otimiza isso. Também deve ter melhorado um pouquinho a performance no caso em que o movimento diagonal está desativado, dado que a checagem das quatro direções adicionais não acontece mais.
Adicionei também parâmetros para movimento diagonal nas funções walk_to e follow.
~ Masked

Scripts assim iam me dar muito jeito à uns 12 anos atrás!
é que na altura sistemas como este era só mesmo no RMXP, quando o Ace chegou havia qualquer coisa mas era diferente


óptimo trabalho

Brandt, se eu tivesse mãos, eu bateria palmas! Seus scripts são ótimos! Continue assim :).
^~^) -Rhyan.