Foros - Stratos

Programadores => General Programadores => Mensaje iniciado por: player en 25 de Agosto de 2010, 11:03:18 PM

Título: Comprobar si existe un camino correcto
Publicado por: player en 25 de Agosto de 2010, 11:03:18 PM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: Hechelion en 25 de Agosto de 2010, 11:18:35 PM
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
http://en.wikipedia.org/wiki/A*_search_algorithm
Título: Re: Comprobar si existe un camino correcto
Publicado por: player en 26 de Agosto de 2010, 12:43:09 AM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: Hechelion en 26 de Agosto de 2010, 02:12:41 AM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: Hechelion en 26 de Agosto de 2010, 06:31:23 AM
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
Título: Re: Comprobar si existe un camino correcto
Publicado por: Buffon en 26 de Agosto de 2010, 10:33:51 AM
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
Título: Re: Comprobar si existe un camino correcto
Publicado por: player en 26 de Agosto de 2010, 05:18:56 PM
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.

Título: Re: Comprobar si existe un camino correcto
Publicado por: flipper83 en 27 de Agosto de 2010, 08:25:24 AM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: player en 27 de Agosto de 2010, 06:06:30 PM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: The_Dragon_Ladis en 27 de Agosto de 2010, 07:20:04 PM
Yo he hecho cosas de este estilo con recursividad en la carrera, aunque dudo que eficiente para un videojuego.
Título: Re: Comprobar si existe un camino correcto
Publicado por: player en 27 de Agosto de 2010, 08:20:37 PM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: flipper83 en 28 de Agosto de 2010, 11:43:41 AM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: blau en 28 de Agosto de 2010, 12:02:18 PM
El A* es muy sencillo de implementar, vas a aprender mas y terminar antes implementandolo por tu cuenta que viendo codigos.
;)
Título: Re: Comprobar si existe un camino correcto
Publicado por: The_Dragon_Ladis en 28 de Agosto de 2010, 01:53:14 PM
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á...
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;

      }
      }
}

Título: Re: Comprobar si existe un camino correcto
Publicado por: player en 28 de Agosto de 2010, 02:01:57 PM
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.
Título: Re: Comprobar si existe un camino correcto
Publicado por: player en 31 de Agosto de 2010, 04:09:58 PM
Bueno, ya he conseguido implementar el algoritmo de forma recursiva, aunque no es demasiado eficiente me sirve para lo que necesito.

Ahora me pondré con el A* a ver que es lo que saco.