Rato no Labirinto

Vê se isso te ajuda…
http://www.policyalmanac.org/games/aStarTutorial_port.htm
Flw

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

Dá uma ajuda ae pessoal!