Avatar do usuário
gabrielsch
Colaborador
Colaborador
Autor
Mensagens: 254
Registrado em: Dom Abr 10, 2016 3:34 am
Karma: 629

[Engine] Pathfinding com Algoritmo de Dijkstra

Seg Jul 18, 2016 10:33 pm

Pathfinding
com Algoritmo de Dijkstra
Versão Recomendada: Game Maker Studio 1.4.1749

Imagem
Linhas amarelas demarcam o menor caminho entre os dois pontos.

Sobre: O Algoritmo de Dijkstra é um algoritmo usado para obter o menor caminho entre um ponto e outro, por meio desse algoritmo é possivel extrair o menor caminho para qualquer ponto a partir de um ponto inicial. Este exemplo implementa este algoritmo (não exatamente da melhor maneira) por cima de um sistema de grafos (ainda não completo).

Controles:
  • Q - Abre um grafo
  • W - Salva o grafo atual
  • Enter - Calcula o menor caminho entre dois pontos

Mudanças planejadas:
  • Melhorar o desempenho nos scripts de desconexão de nós.
  • Permitir o uso de uma matriz de adjacência para o calculo do menor caminho.
  • Implementar (de fato) o suporte ao uso em ambientes 3D.

Download: 
Dropbox

Créditos: David Galles pela incrível visualização do algoritmo.
1
Imagem

Tags:
 
Avatar do usuário
Gonzo
Membro
Membro
Mensagens: 204
Registrado em: Sáb Ago 22, 2015 8:49 pm
Karma: 269

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Seg Jul 18, 2016 10:45 pm

Em qual situação que usa esse Pathfingding? não faço a menor ídeia cara..
......∩____∩............_______...
......| (• ◡•)| ノ\(❍ᴥ❍ʋ)..
Não seja uma cabrita selvagem "tutankhamun"
 
Avatar do usuário
gabrielsch
Colaborador
Colaborador
Autor
Mensagens: 254
Registrado em: Dom Abr 10, 2016 3:34 am
Karma: 629

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Seg Jul 18, 2016 11:26 pm

Gonzo escreveu:
Em qual situação que usa esse Pathfingding? não faço a menor ídeia cara..

Esse tipo de sistema é ótimo para inteligências artificiais, por exemplo, quando é necessário que o NPC ou inimigo vá até um ponto utilizando um caminho melhor definido. Exemplos de jogos que utilizam esse tipo de sistema são os jogos feitos utilizando a Source Engine, os bots se movimentam pelos mapas utilizando esse sistema de navegação
Imagem
 
7f55842f
Membro
Membro
Mensagens: 35
Registrado em: Sex Jun 24, 2016 11:33 pm
Karma: 51

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Ter Jul 19, 2016 10:54 am

Po cara, podia pegar toda essa tua "fodeza programística" e fazer um jogo.
 
Avatar do usuário
gabrielsch
Colaborador
Colaborador
Autor
Mensagens: 254
Registrado em: Dom Abr 10, 2016 3:34 am
Karma: 629

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Ter Jul 19, 2016 12:18 pm

7f55842f escreveu:
Po cara, podia pegar toda essa tua "fodeza programística" e fazer um jogo.

O tópico tem como objetivo compartilhar com os usuários um material com utilidade para seus jogos, sem duvidas, se necessário,  usarei em meus projetos futuramente. Na minha humilde opinião você podia pegar toda essa tua "fodeza comentarística" e fazer comentários  de peso.

EDIT: Tópico atualizado com uma lista de melhorias a serem feitas em versões posteriores.
Imagem
 
7f55842f
Membro
Membro
Mensagens: 35
Registrado em: Sex Jun 24, 2016 11:33 pm
Karma: 51

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Ter Jul 19, 2016 7:15 pm

Não cara, não citei isso pra desmerecer o seu trabalho nem nada do tipo, é que realmente um jogo com essas suas habilidades vai ficar no mínimo interessante, adoraria ver toda essa habilidade aplicada em um projeto.
1
 
Avatar do usuário
rhenandias
Novato
Novato
Mensagens: 14
Registrado em: Sáb Ago 22, 2015 7:24 pm
Karma: 5

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Qua Jul 20, 2016 2:26 pm

Essa área de teoria de grafos, busca, e tals é algo que eu queria começar a estudar, você tem algum material a respeito que você goste pra recomendar?
 
Avatar do usuário
gabrielsch
Colaborador
Colaborador
Autor
Mensagens: 254
Registrado em: Dom Abr 10, 2016 3:34 am
Karma: 629

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Qui Jul 21, 2016 3:36 pm

rhenandias escreveu:
Essa área de teoria de grafos, busca, e tals é algo que eu queria começar a estudar, você tem algum material a respeito que você goste pra recomendar?

Não tenho nenhum material de fato sobre isso, o pouco que eu aprendi sobre esse assunto foi nas aulas de Matemática Discreta da faculdade, sei que existem várias aulas no Youtube tanto sobre Matemática Discreta quando Teoria de Grafos, explorar a Wikipédia também é uma ótima escolha pra recolher assuntos semelhantes e que se conectam com o tópico.
Imagem
 
netoult
Novato
Novato
Mensagens: 1
Registrado em: Seg Jun 22, 2020 10:26 pm
Karma: 0

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Seg Jun 22, 2020 10:28 pm

Boa noite, por acaso ainda tem o algoritmo disponível? Tenho um trabalho de facul, que estão me exigindo exatamente esse tipo de implementação, e gostaria de utilizar seu game como exemplo.
 
Avatar do usuário
Dotto Meister
Novato
Novato
Mensagens: 16
Registrado em: Qua Jun 19, 2019 8:43 pm
Karma: 50

Re: [Engine] Pathfinding com Algoritmo de Dijkstra

Ter Jun 23, 2020 8:36 pm

Tudo bom netoult?

O tópico é de 2016 e provavelmente o autor nem mesmo receba notificação de resposta.

Há uma série de exemplos do algoritmo na internet, veja se algum atende sua necessidade, ex:
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
https://www.programiz.com/dsa/dijkstra-algorithm
1