En este foro tratamos este problema:
http://foro.elhacker.net/programacio...t404470.0.html http://es.wikipedia.org/wiki/Algorit...Floyd-Warshall https://www.google.es/#newwindow=1&q...loyd%20c%2B%2B
Si lo que quieres es el camino optimo, supongo que el algoritmo Floyd seria una buena opción.
Por Internet esta hay varios lugares donde te explica sobre el tema.
sobre como evitar los obstáculos pues haciendo comparaciones
digamos que estas en la posición:
mapa[y][x];
pues miras acia los lados a ver lo que hay antes de avanzar:
//arriba
if (mapa[y-1][x] == caminolibre)
//avanzar
//izquierda
if (mapa[y][x-1] == caminolibre)
//avanzar
//derecha
if (mapa[y][x+1] == caminolibre)
//avanzar
//abajo
if (mapa[y+1][x] == caminolibre)
//avanzar
te recomiendo que separes los caminos por números positivos ejemplo:
2 camino sin explorar
1 camino explorado
0 pared
así seria para saber si arriba esta libre.
//arriba
if (mapa[y-1][x] == 2)
y--;
Esta claro que no es asi de simples, los ejemplos los tienes en la direccion que te di.
Y el algoritimo floyd te dice el camino optimo.
El que hice prácticamente no busca el camino optimo por que tome como que se lo busca la salida este donde este sin saber donde está.
A cambio el algoritmo floyd sabe todas las posiciones de la matriz por eso te da el camino optimo.
En mi caso no sabe el camino así que lo busca hasta encontrar, eso si sin repetir lo ya explorado.
Depende para que lo quiere, ejemplo si es un juego saber la posición del jugador es algo así como trampa ¿no?
Se supone que si va buscar la salida no me sirve saber donde esta el final, dado que el camino mas corto entre 2 puntos es una linea recta eso es lo que hace ese algoritimo, te busca el camino mas corto.
Pero como dije, se supone que no se donde esta el camino, pues para eso esta el algoritmo A.
Tampoco opte por ese, me base en ver lo que hay en todas las direcciones como si se tratara de mi mismo.
Si estoy en un laberinto no puedo ver mas lejos que lo que alcanza la vista.
Puse una casita de alcance y así va, haciendo comparaciones to el rato, sin saber el "camino optimo".
El camino optimo no varia, será siempre igual sin embargo el mio puede variar a cada ejecución ya que se decide por números aleatorios, primero miro si hay caminos sin explorar "2", en todas las direcciones si hay uno solo lo toma ese pero si hay mas de uno hace a la suerte.
Si entre en un callejón sin salida pues hace lo mismo pero con 1 envés de 2;
Al final me decidí marcar el camino explorado como 0 y el ya explorado como 1.
Bueno hay muchos códigos allí de gente con mas ideas que yo, así que echa un ojo a ver que te parece.
