C Algoritmo para procurar uma saida

[Arkcanjou]

Preciso de uma luz com um algoritmo que dada um labirinto encontre o menor caminho possivel até a saida

 

 

O que eu fiz até o momento é que a partir do ponto de inicio o codigo vai definindo um valor de "peso" para cada movimento até que ele encontre a saida e isso tudo fica em uma matriz.

 

Usando essa matriz de exemplo como eu poderia encontrar o menor caminho até o valor 99

#  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #
#  #  #  #  #  14 13 12 11 10 9  8  7  6  5  4  3  #
#  #  #  #  #  #  14 13 12 11 10 9  8  #  4  3  2  #
#  #  #  #  #  #  15 14 13 12 11 10 9  #  3  2  1  #
#  #  #  #  #  #  #  15 14 13 #  11 10 11 #  1  0  #
#  #  #  #  #  #  #  #  99 #  #  #  #  #   #  #  # #

No lugar das cerquilhas são valores que representam posiçoes invalidas troquei apenas para ficar melhor para visualizar

 

 

 

[arfneto]

Se você não tem uma sólida formação em matemática sugiro tentar estudar alguns dos algoritmos clássicos desse tipo, antes de programar algo.

 

58 minutos atrás, Inutilzao disse:

O que eu fiz até o momento é que a partir do ponto de inicio o codigo vai definindo um valor de "peso" para cada movimento até que ele encontre a saida e isso tudo fica em uma matriz

 

Acho que é uma ideia muito boa! Nesse caso o peso deve ser 1 porque todos os caminhos tem o mesmo custo: a distância.

 

Tente algo em torno de matriz de adjacência, a representação comum disso que está escrevendo, e o algoritmo de Dijkatra, que acho que são conceitos mais simples de entender. Nesse tópico pode ter algo que ajude você a escrever algo:

[Plástico Bolha]

Implementei o A* com JS, pelo menos a lógica dá pra ser reutilizada.

 

https://github.com/PlasticoBolha/Search-algorithms---JS/blob/master/SearchAlgorithms.html

[Plástico Bolha]

@vangodp Ele vai sofrer um pouco mais