Dev - C++ - Ayuda para realizar un programa para resolver laberintos

   
Vista:

Ayuda para realizar un programa para resolver laberintos

Publicado por Gerardo Rolong (2 intervenciones) el 17/07/2014 00:18:13
Hola, el asunto es que necesito ayuda con este proyecto, el cual no tengo ni idea de como hacer.
- Hacer un programa que lea un laberinto escrito en archivo de texto, y como resultado el programa diga si el laberinto tiene solución; de ser así, que la muestre en pantalla.
Especificaciones:
1) El laberinto está conformado por números de la siguiente manera:

0 : representa el camino a seguir, es decir un lugar valido por donde avanzar.
1 : representa una pared.
2 : representa la ubicación de un personaje por así decirlo; es decir va a ser el punto de partida.
3 : representa la salida del laberinto

2) No siempre va a ser el mismo laberinto, es decir se va a probar con diferentes laberintos; los cuales no tienen especificado el tamaño
3) El archivo de texto no tiene espacios entre los números, es decir todos los caracteres están uno al lado del otro en la siguiente forma : " 0000011113 ".
4) El proyecto me lo dejaron en un curso de programación básica, y los temas más avanzados que aprendí fueron arreglos, matrices y datos abstractos(estructuras), así que no puedo aparecer con una solución relativa a temas desconocidos como por ejemplo vectores; así que agradezco que si me quieren ayudar eviten el uso de temas más avanzados de lo que sé.

Información adicional:
Yo sé como leer archivos de texto y también conozco la función cin.getline para leer cada linea; pero entonces ahí está básicamente el problema, como separar esa linae en los caracteres correspondientes o en enteros; en todo caso poder separarlos para ir haciendo las comparaciones al momento de hacer el recorrido por el laberinto.
Agradezco al que me pueda colaborar.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de vangodp

Ayuda para realizar un programa para resolver laberintos

Publicado por vangodp (287 intervenciones) el 17/07/2014 07:17:08
Aun que no he echo uno que lea desde un archivo...no creo que sea mucho complicado.
http://foro.elhacker.net/programacion_cc/ayuda_con_programa_urgente-t404470.0.html
En esa dirección estuvimos liados con ese tipo de programa. E incluso se veia como el programa "busca" una salida.
Hay varios ejemplos que les puedes echar un ojo.
Pero me parece ridículamente fácil saber si hay una salida. Es tan fácil como leer letra a letra y comparar con ese 3 que representa la salida. :S
De todas las formas ve a la pagina y a ver que te parece.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Ayuda para realizar un programa para resolver laberintos

Publicado por Ricardo (5 intervenciones) el 20/07/2014 04:52:49
El laberinto lo implementas sobre una matriz. Para resolverlo necesitas utilizar un vector (arreglo) para implementar una pila (stack). Cada vez que avanzas por el laberinto vas guardando en la pila el movimiento. De esta manera cada casillero del laberinto tiene 8 movimientos posibles (o cuatro, si no consideras movimientos en diagonal). Si luego de probar todos los movimientos posibles de una casilla te das cuenta de que no hay salida, extraer un elemento de la pila para retroceder a la posición anterior y continuar a partir de allí. Cada casilla que visitas en la matriz la marcas como "visitada" para no volver a pasar por allí. No es un problema trivial, pero tampoco es para tanto. Si no quieres usar una pila prueba con recursividad. Suerte!
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Francisco

Ayuda para realizar un programa para resolver laberintos

Publicado por Francisco feco99@yahoo.com (10 intervenciones) el 22/07/2014 10:18:02
/*
Copiar y pegar el siguiente texto en un archivo y nombrarlo "laberinto.txt. O usar el que anexe en el rar (es el mismo)
Se puede modificar completamente, hasta un maximo de 100 columnas por 100 renglones.
Se puede hacer mas grande modificando la linea ----> int m[100][100]; // Matriz que guarda...

111111111111111111111111111111
100010010000000000010001000001
101010011111111100000100010101
101010010000010001111111111101
101010000000010101000000000001
101000011110010101000111111111
101111100000010101000000000001
100000010000000101111111111101
111111011111111101000000000001
100000010001000000001111111111
101111110101002000000000100001
100000000101111111111000000101
100011111100000010100011111111
111110000101110010001000000001
100000111100010011111111111111
101110000101010000000000000001
101000111111111111111111111101
101000000100000000000000010001
101001100101111000000100000001
101100100100001011111111111101
131000100001101000001000000001
111111111111111111111111111111

IMPORTANTE : revisar si se dio enter en la ultima fila del archivo "laberinto.txt"

http://www.lawebdelprogramador.com/foros/Dev-C/1452089-Ayuda_para_realizar_un_programa_para_resolver_laberintos.html

0 : representa el camino a seguir, es decir un lugar valido por donde avanzar.
1 : representa una pared.
2 : representa la ubicación de un personaje por así decirlo; es decir va a ser el punto de partida.
3 : representa la salida del laberinto

Recorriendo el laberinto, utilizando el metodo de la mano derecha, el cual es el mas largo pero el mas seguro consiste en
que si estas atrapado en un laberinto real, toques una pared con la mano derecha y sin dejar de tocarla recorras todo el
laberinto, tarde o temprano llegaras a la salida, siempre y cuando el laberinto no tenga caminos circulares y empieces en uno
de ellos. No es muy util en laberintos reales demasiado grandes, por la cuestion del tiempo, pero en una pc es diferente.

Si no estamos junto a la meta avanzamos, simulando que vamos tocando la pared derechaavanzamos hacia el frente siempre y cuando
exista una pared a nuestra derechasi no, vemos hacia la derecha si no hay pared, si hay, volteamos a la izquierda
y si no, como ultima opcion giramos hacia atras.*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
 
int m[100][100]; // Matriz que guarda los datos del archivo. El maximo del laberinto son 100 filas por 100 columnas. 
                 //Se puede modificar
 
int f,c; // filas y columnas del laberinto
int fp,cp; // coordenadas del jugador
int fs,cs; // coordenadas de la salida o meta
const int ARRIBA=0, DERECHA=1, IZQUIERDA=2, ABAJO=3;
int direccion=ARRIBA; // El jugador inicia viendo hacia arriba
int arriba, abajo, izquierda, derecha; // Aqui guardamos la informacion de la matriz de las 
                                             // cuatro direcciones junto al jugador
 
void leerArchivo() {
     int maxCol;
    FILE *archivo;
    char caracter;
    int codigo;
    bool flag=true; // Sirve para que aumente el numero de columnas solo hasta que encuentre le primer salto de linea
               // suponiendo que el archivo tiene todas las lineas de igual numero de caracteres
 
        archivo=fopen("laberinto.txt","rt"); // abrimos el archivo "laberinto.txt" en modo lectura de texto("rt"
        if (archivo==NULL) { // En caso de que el archivo no exista o que este mal el nombre
           printf("Error en lectura de archivo\n");
           system("pause");
           exit (EXIT_FAILURE); // Terminacion del programa por falla
           }
 
        while(!feof(archivo)) { // Este ciclo sirve para dimensionar nuestra matriz
                caracter=fgetc(archivo);
                codigo = caracter; // obtenemos el codigo Ascii de el caracter
 
                if (codigo==10) { // codigo del salto de linea
                   f++; // Si encontramos un enter añadimos una fila mas a nuestra matriz
                   if (flag) {maxCol=c; flag=false;} // solo lo hacemos una vez
                   c=0;
                } else {
                       m[f][c]=codigo-48;
                       if (m[f][c]==2){fp=f;cp=c;}
                       if (m[f][c]==3){fs=f;cs=c;}
                       c++ ;// añadimos una columna mas a nuestra matriz
                }
        }
        c=maxCol; // si no ponemos esto la matriz queda de una columna
        fclose(archivo);
        //printf ("%d filas, %d columnas",f,maxCol); // para debug
}
 
void MuestraLaberinto() {
     // En esta funcion las paredes se muestran como asteriscos "*", el jugador como "J" y la meta como "M"
    system("cls");
    for (int i=0;i<f;i++) {
        for (int ii=0;ii<c;ii++) {
           if (m[i][ii]==1) printf ("*");
           else if (i==fs && ii==cs) printf ("M");
           else if (i==fp && ii==cp) printf ("J");
           else printf (" ");
        }
    printf ("\n");
    }
    //printf ("Direccion %d, arriba %d, abajo %d, derecha %d, izquierda %d\n",direccion,arriba,abajo,derecha,izquierda); // debug
    system("pause"); // esperamos que el usuario presione una tecla
}
 
void RecorrerLaberinto() {
    int old_fp,old_cp; // Las usaremos para poner un espacio en donde estaba el jugador
 
      old_fp=fp; old_cp=cp; // Guardamos las coordenadas del jugador, para colocar un espacio cuando se mueva                   
 
      arriba=m[fp-1][cp];
      abajo=m[fp+1][cp];
      derecha=m[fp][cp+1];
      izquierda=m[fp][cp-1];
 
      // checamos si la meta esta junto al jugador
      if (derecha==3) direccion=DERECHA;
      else if (izquierda==3) direccion=IZQUIERDA;
      else if (arriba==3) direccion=ARRIBA;
      else if (abajo==3) direccion=ABAJO;
 
      // Si no estamos junto a la meta, avanzamos
      else if (direccion==ARRIBA){ // volteando al norte
        if (derecha==1 && arriba==0) {}// Antes de avanzar checamos si hay pared a la derecha 
         else if (derecha==0) direccion=DERECHA;// si no hay pared a la derecha giramos viendo a la derecha         
         else if (izquierda==0) direccion=IZQUIERDA;// si no, si no hay pared en la izq. giramos viendo hacia alla   
         else direccion=ABAJO;// ultima opcion, abajo giramos viendo hacia abajo
      }
      else if (direccion==1){ // volteando al este/derecha
         if (abajo==1 && derecha==0) {}// Antes de avanzar hacia la derecha checamos si hay pared abajo      
         else if (abajo==0) direccion=ABAJO;// si no hay pared abajo giramos a la derecha, mirando abajo
         else if (arriba==0) direccion=ARRIBA;// si no hay pared arriba giramos
         else direccion=IZQUIERDA;// ultima opcion la izquierda
      }
      else if (direccion==3){ // volteando al sur
         if (abajo==0 && izquierda==1) {}// si no hay pared abajo y a la izq. si, avanzamos      
         else if (izquierda==0) direccion=IZQUIERDA;// si no hay pared a la izquierda giramos
         else if (derecha==0) direccion=DERECHA;// si no hay pared a la derecha giramos 
         else direccion=ARRIBA; // ultima opcion arriba
      }
      else if (direccion==2){ // volteando a la izquierda
         if (izquierda==0 && arriba==1) {}// si hay pared arriba y a la izq. no, avanzamos             
         else if (arriba==0) direccion=ARRIBA;// si no hay pared arriba giramos a la derecha,
         else if (abajo==0) direccion=ABAJO;// si no hay pared abajo giramos 
         else direccion=DERECHA;// ultima opcion volver atras, giramos 
      }
 
      m[old_fp][old_cp]=0; // ponemos un espacio donde estaba el jugador
 
      switch(direccion){ // Movemos al jugador
        case 0:
             m[fp-1][cp]=2; // actualizamos matriz            
            fp--; // Actualizamos coordenadas del jugador         
        break;
        case 1:
             m[fp][cp+1]=2; // actualizamos matriz            
             cp++; // Actualizamos coordenadas del jugador           
        break;
        case 2:
             m[fp][cp-1]=2; // actualizamos matriz            
            cp--; // Actualizamos coordenadas del jugador           
        break;
        case 3:
             m[fp+1][cp]=2; // actualizamos matriz           
            fp++; // Actualizamos coordenadas del jugador           
        break;
      }
}
 
int main() {
    leerArchivo();
    MuestraLaberinto();
    while (fp!=fs || cp!=cs) {// Cuando encontramos la meta, salimos del ciclo
      RecorrerLaberinto();
      MuestraLaberinto();
    }
    system("cls");
    printf ("El jugador llego a la meta\n");
    system("pause");
    return 0;
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Francisco

Ayuda para realizar un programa para resolver laberintos

Publicado por Francisco feco99@yahoo.com (10 intervenciones) el 25/07/2014 15:57:19
Codigo fuente mejorado:

- La matriz ahora es dinamica
- Reestructure las funciones, me parece que ahora esta mas entendible.
- Muestra la solucion. (paso por paso o de una sola vez)
- Inclui el metodo de la mano izquierda.
- Investigue sobre el algoritmo de Tremaux (no implementado aun)
- Investigue sobre el algoritmo de backtracking (no implementado aun)

Espero que les sea util, incluyo archivo comprimido, con exe, codigo guente y tres archivos de texto de ejemplo.
Nota: utilice Dev c++ 4.9.9.2 para compilar.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Francisco

Ayuda para realizar un programa para resolver laberintos

Publicado por Francisco feco99@yahoo.com (10 intervenciones) el 27/07/2014 08:01:11
Mas cambios, le mejore el menu, le puse un metodo de backtracking que muestra la mejor solucion, es recursivo, pero se traba si el laberinto no tiene solucion. voy a seguir mejorandolo. El archivo comprimido contiene el codigo fuente, el executable y tres ejemplos de laberintos en archivo de texto.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Ayuda para realizar un programa para resolver laberintos

Publicado por Brayan (1 intervención) el 11/10/2014 04:50:08
Y si el laberinto tuviera que cambiar cada cierto tiempo ?? El txt esta de mas ??
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Ayuda para realizar un programa para resolver laberintos

Publicado por jamg (1 intervención) el 12/11/2014 15:39:16
hola amigo diculpa me puedes ayudar o pasar el codigo fuente del mismo problema del laberinto pero con pila?, por favor. Saludos
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar