Comprobar si existe un camino correcto

[player]

Hola, tengo un fichero de texto con un laberinto de este estilo que lo cargo en una matriz:

##############E######## ####
#  ##  # ####                       ###  ## #
#                                        #########
########### #####S#########

Una vez cargado, quiero comprobar si existe un camino válido, es decir, que puedo llegar desde E(entrada) hasta S (salida) sin problemas. En este caso debería indicarme que sí, pero por ejemplo, en este otro:


##############E######## ####
#  ##  # ####                       ###  ## #
#                                    ##########
########### #####S#########

Debería decirme que no porque hay una '#' bloqueando la salida, o en este caso tampoco:



##############E######## ####
#  ##  # ####                       ###  ## #
#                    ###################
#                                                          #
########### #####S#########

Porque las '#' bloquean el camino entre la entrada y la salida.

Es muy difícil de implementar algo así? Nunca he hecho nada parecido y no sé por donde buscar.

Gracias.

[Hechelion]

Así como lo planteas, creo que tu mejor solución es usar A* (A star) entre la entrada y la salida.

Te recomiendo buscar mejor documentación pero acá queda explicado la idea del algoritmo

Código [Seleccionar] Expand

http://en.wikipedia.org/wiki/A*_search_algorithm

[player]

Le voy a echar un ojo a ver si me aclaro, es muy dificil de implementar? La entrada y salida pueden estar en cualquiera de los bordes del rectangulo, asi que cada vez habra que buscar un camino distinto según la situación.

Gracias.

[Hechelion]

No, es relativamente sencillo, más complejo es tener la pila para meter y sacar los nodos de forma ordenada.

Lo que el algoritmo hace es recorrer cada nodo adyacente al punto de partida y le asigna un puntaje  que es la suma del costo de moverse hacia ese nodo más un puntaje dado por la distancia hacia la salida (normalmente la famosa distancia manhattan). Luego buscas el nodo con el valor más bajo y repites el procedimiento hasta que llegas a destino o hasta que agotas todos los nodos sin llegar, lo que significa que no hay camino.

[Hechelion]

Andas de suerte  :D

Andaba buscando unos recursos y me tope con un link de A* para principiantes
http://www.policyalmanac.org/games/aStarTutorial_es.htm

[Buffon]

Y andas con suerte por que tengo A* implementado en C++ desde hace unos 6 años, esta tarde cuando llegue a casa busco el juego de estrategia y te paso el código ;)

También lo tengo en Java pero ese es más difícil que lo encuentre xD

[player]

Pues muchas gracias Hechelion por el link, lo leeré con calma para saber de que va el asunto, y a ti también gracias adelantadas Buffon, la verdad que se agradece el algoritmo ya implementado para estudiar ya el código directamente.

[flipper83]

existen implementaciones de a* a mínimo que busques en internet. Hay más soluciones de busquedas de caminos, pero el a* te asegura que camino lo encuentra siempre y siempre es el más corto. Busca en internet pathfinder o pathfinding y encontrarás un montón de info.

[player]

Y qué otras soluciones existen?

He leído algo de búsqueda por amplitud o en profundidad, dado que el problema es sobre cargar un fichero de texto en una matriz y comprobarlo, no serían más asequibles para mí?

El A* la verdad que lo veo algo complicado para mí por el momento.

Gracias.

[The_Dragon_Ladis]

Yo he hecho cosas de este estilo con recursividad en la carrera, aunque dudo que eficiente para un videojuego.

[player]

Algo así recursivo también sería una opción, como voy a usar laberintos muy pequeños y en modo consola, la eficiencia me da un poco igual.

Me podrías pasar información o algún código que tengas hecho para hacerme una idea de cómo va el asunto?

De todas formas, también me interesaría ver lo del A* implementado en C++ porque nunca está de mas aprender lo máximo posible.

Gracias.

[flipper83]

implementaciones de A* en c++ hay a porrillo. pero si quires ver más cositas de estas hazte con un libro que se llama inteligencia artificial un enfoque moderno y ahi tienes pathfinders para aburrir y lo explican muy bien. Hay un libro en inglés, no se si esto es un problema, que se llama artificial inteligence for videogames de ian millington que tiene un capítulo dedicado a a* muy bueno que si no recuerdo mal tiene una implementación en c++ y en pseudocódigo paso a paso.

[blau]

El A* es muy sencillo de implementar, vas a aprender mas y terminar antes implementandolo por tu cuenta que viendo codigos.
;)

[The_Dragon_Ladis]

Voy a rebuscar entre mis practicas de MTP II por si te puede ser de ayuda.

La filosfia es bastante sencilla. Buscas hacia un lado mientras no encuentres un muro mediante llamadas recursivas. Si no es por ahi, buscas hacia otro lado, y asi en las cuatro direcciones (arriba, izquierda, abajo, derecha).

Sobre algoritmos mas avanzadas no puedo ayudarte porque no entiendo del tema aunque implementar uno mismo las cosas siempre ayuda a entenderlas mejor como dicen por ahi.

EDIT:
Lo encontre, aunque ya te digo que es de hace mucho tiempo y no se como andará...

Código [Seleccionar] Expand

int buscarSalidaLaberinto(int** laberinto,int nColumnas,int nFilas,int x,int y)
{
  if(x<0 || y<0 || x==nFilas || y==nFilas)    //Si x o y están fuera del vector
    {
      return 0;     //La salida no está por aquí
    }else
      {
      switch(laberinto[x][y])
      {
        case SALIDA:

          fprintf(stdout,"\nSalida del laberinto en (%d,%d)",x,y);
          fflush(stdout);

          break;

        case ENTRADA:
        case PASILLO:
          laberinto[x][y] = 2;  //Lo marcamos como visitado
          //Buscamos hacia arriba
          if(buscarSalidaLaberinto(laberinto,nColumnas,nFilas,x,y-1)==0)//Si no lo encuentra hacia arriba
            {
              //Buscamos hacia la derecha
              if(buscarSalidaLaberinto(laberinto,nColumnas,nFilas,x+1,y)==0)//Si no lo encuentra hacia la derecha
                {
                  //Buscamos hacia abajo
                  if(buscarSalidaLaberinto(laberinto,nColumnas,nFilas,x,y+1)==0)//Si no lo encuentra hacia abajo
                    {
                      //Buscamos hacia la izquierda
                      if(buscarSalidaLaberinto(laberinto,nColumnas,nFilas,x-1,y)==0)//Si no lo encontramos hacia la izquierda
                        {
                          return 0; //Por aqui no está la salida
                        }
                    }
                }
            }
          laberinto[x][y]=0;
          break;

        case PARED:
return 0;
        case VISITADO:
          return 0;

      }
      }
}

[player]

Gracias por vuestras recomendaciones y consejos, me haré con lo que comentáis de inteligencia artificial e intentaré implementar el A* por mi mismo.

The_Dragon_Ladis gracias por el código, ya me hago una idea de cómo es el asunto, también me servirá bastante para intentar implementarlo de forma recursiva.

Saludos.