Galera, não vou ficar mentindo nem tentando ludibriar ninguém aqui (quanto menos choramingar apelando para a sinceridade), mas o que acontece mesmo é que estou resolvendo um problema na faculdade que gostaria de saber um método mais fácil de resolvê-lo (acredito que com recursividade), porém as idéias são poucas, eu sei q dá pra resolver mais fácil mas ninguem sabe me dizer como.
O problema é o seguinte, eu tenho uma matriz, onde ela possui um rato, um queijo, alguns obstáculos e uma saida. Eu tenho que fazer o caminho do queijo até o rato e do rato até a saída.
Atualmente estou preenchendo uma matriz com zeros (identificando o espaço que ele pode andar), armazenando as posicões de cada coisa (rato, queijo, saidas e obstaculos) num vetor de estrutura criada por mim. E travei na “propagação do cheiro do queijo”. Eu tenho que pegar a posição do queijo, verificar em volta quais espaços esão livres e preencher com 1(até aí tudo bem), depois fazer o mesmo para essa posição e preencher a próxima casa mais perto que contenha 0 com 2… e assim vai… até chegar no rato. Depois faço o mesmo processo do rato até a saída…
Alguém tem uma idéia (não estou pedindo o código pronto) de qual a melhor maneira de fazer isso?
diego, obrigado pela resposta já dá uma forte ajuda em alguns pontos, alguém mais tem alguma sugestão?
Sim, entender de verdade o que ele postou e aplicar. É um dos algorítmos mais eficientes que existem para fazer busca de caminhos.
Outros tutoriais sobre o assunto:
http://wiki.gamegardens.com/Path_Finding_Tutorial
http://www.heyes-jones.com/astar.html
Obrigado pela ajuda de todos novamente.
Estou seguindo esse caminho, entendi o algoritmo e estou aplicando-o. O problema que estou enfrente na verdade é que o algoritmo trabalha com listas, conceito esse ainda que não tenho (vou ver somente semestre que vem, apesar de já dar uma olhada para entender). Mas acredito que há tranquilamente a possibilidade de realizar os cálculos com vetores. Estou fazendo da seguinte maneira:
Declaro uma matriz que será o labirinto e dois vetores que serão as listas (lista aberta e lista fechada).
Preencho a matriz e na posição 0 da lista aberta (que na verdade é um vetor) eu coloco a linha e coluna da posição inicial (o rato do exemplo) e armazeno o valor do tamanho da lista como 0, para ir incrementando depois (para nao ter que varrer todo o vetor num for).
Criei uma função que atualiza a posição, essa função acessa a lista (na posição listaaberta[0].tamanho+1) e armazena o valor da linha e da coluna para os próximos 4 valores (cima, baixo, direito, esquerda) e também obtem o valor de F (utilizei o tutorial que o diego postou). O F nada mais é que um cálculo do menor caminho da posicao inicial até o alvo (do rato até o queijo), que se dá contando em linha reta as linhas e colunas e somando-as. Armazeno na lista (vetor) aberta também a linha e coluna da posição pai das outras que foram verificadas, para montar o caminho depois.
Após verificar o F ( caminho de menor custo), o tutorial do algoritmo A* pede para eu inserir essa posição na lista fechada, atualizar a posição e fazer todas as verificações necessárias (se o rato pode ir até o caminho, se a posição já foi verificada ou não (lista fechada)). O problema é que não entendi como manipular essas listas.
Então gostaria de saber se estou no caminho certo fazendo isso com vetores. Também pensei na possibilidade de usar uma variáel booleana para indicar se a posição já foi verificada ou não.
Qualquer ajuda é bem vinda.
Muito Obrigado.
P.S. Estou enviando o código a quem possa interessar, neste link:
http://pastebin.com/HV8vCghS