elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Programa resolución laberinto en C
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Programa resolución laberinto en C  (Leído 13,097 veces)
Leafar77

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Programa resolución laberinto en C
« en: 19 Noviembre 2014, 17:17 pm »

Hola buenas a todos. Soy alumno de primero de carrera de ingeniería de software y me dirijo a esta comunidad (otra vez) para pedir ayuda a la voz de la experiencia con un problema en el que estoy atascado.
El ejercicio consiste en hacer un programa en C que sea capaz de resolver un laberinto simple, un camino, que se le ha de pasar al programa por la entrada de texto. El laberinto tiene que ser de 32x32 caracteres binarios, siendo los 0s los espacios vacíos.
Y ha de guardarse en un array bidimend¡sional para trabajar con él.
Tal que así:
Código:
11111011111111111111111111111111
11111011111111111111111111111111
11111011111111111111111111111111
11111011111111111111111111111111
11111011111111111111111111111111
11111000000000000000000111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111100000000000000000111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111100000000000000000000000011
11111111111111111111111111111011
11111111111111111111111111111011
11111111111111111111111111111011
11100000000000000000000000000011
11101111111111111111111111111111
11101111111111111111111111111111
11101111111111111111111111111111
11101111111111111111111111111111
11101111111111111111111111111111
11100000000000000000000000011111
11111111111111111111111111011111

Y la salida del programa ha de darte los movimientos que ha seguido el programa para completar el laberinto. También he hecho que imprima las coordenadas de la posición actual en cada movimiento.

El problema viene cuando al pasarle el laberinto, el programa avanza solo unas pocas posiciones o entra en un bucle. Dando salidas como estas:

Posicion inicial 0x0(ni un avance)
Código:
Array guardado
Mi posicion inicial: 0 x 0

Posicion inicial 3x5 (avanza varias y luego se para)
Código:
Array guardado
Mi posicion inicial: 3 x 5
Down Mi posicion: 4 x 5
Down Mi posicion: 5 x 5
Right Mi posicion: 5 x 6
Right Mi posicion: 5 x 7

Posicion 5x22 (Idem)
Código:
Array guardado
Mi posicion inicial: 5 x 22
Down Mi posicion: 6 x 22
Down Mi posicion: 7 x 22


Posicion 5x9 (Entra en bucle)
Código:
Array guardado
Mi posicion inicial: 5 x 9
Right Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11

Evidentemente algo en la lógica o en el algoritmo esta mal, pero no consigo encontrar el fallo.

Este es mi código:

Código
  1. #include<stdio.h>
  2.  
  3.  
  4. main()
  5. {
  6. int position_fila;
  7. int position_columna;
  8. int ultima_pos_fila, ultima_pos_col;
  9. int sig_fila, sig_columna, ant_fila, ant_columna;
  10. int laberinto[32][32];
  11. int v,t,c,i,x,j, nc;
  12. nc = 0;
  13.  
  14. position_fila = 0;
  15. position_columna = 0;
  16. sig_fila = position_fila + 1;
  17. sig_columna = position_columna + 1;
  18. ant_fila = position_fila - 1;
  19. ant_columna = position_columna - 1;
  20. ultima_pos_fila = ultima_pos_col = 0;
  21.  
  22. v = 1;
  23. nc = 0;
  24.  
  25. for(i=0;i<32;i++)
  26. {
  27. for(j=0;j<32;j++)
  28. {
  29. laberinto[i][j] = 0;
  30. }
  31. }
  32.  
  33.  
  34.  
  35. //Guardar entrada en array bidimensional "laberinto"
  36.  
  37. for(i=0;i<32;i++)
  38. {
  39. for(j=0;j<32;j++)
  40. {
  41. c = getchar();
  42. switch(c)
  43. {
  44. case '1':
  45. {
  46. laberinto[i][j] = 1;
  47. break;
  48. }
  49. case '0':
  50. {
  51. laberinto[i][j] = 0;
  52. break;
  53. }
  54. case '\n':
  55. {
  56. j = j - 2;
  57. break;
  58. }
  59. default:
  60. break;
  61.  
  62. }
  63. }
  64. }
  65.  
  66. //Imprimir laberinto
  67.  
  68. printf("Array guardado\n");
  69.  
  70. for(i=0;i<32;i++)
  71. {
  72. for(j=0;j<32;j++)
  73. {
  74. printf("%d", laberinto[i][j]);
  75. ++nc;
  76. if(!(nc%32))
  77. printf("\n");
  78. }
  79. }
  80.  
  81.  
  82.  
  83.  
  84.  
  85. //Averiguar posicion inicial
  86.  
  87. for(t = 0; t < 32; t++)
  88. {
  89. v = laberinto[0][t];
  90. if(v == 0)
  91. {
  92. position_columna = t;
  93. break;
  94. }
  95. }
  96.  
  97.  
  98. printf("Mi posicion inicial: %d x %d\n", position_fila, position_columna);
  99.  
  100.  
  101. //Resolucion
  102.  
  103. for(x = 0; x < 50;x++)
  104. {
  105.  
  106. // 2 Condiciones:
  107. //[1] Si puedo moverme hacia abajo  (Si el elemento bajo mi posicion es 0).
  108. //[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).
  109.  
  110. if((!(laberinto[sig_fila][position_columna])) && (sig_fila != ultima_pos_fila))
  111. {
  112. ultima_pos_fila = position_fila; //Guardas ultima posicion
  113. ++position_fila; //Mueves hacia abajo
  114. printf(" Down ");
  115. printf("Mi posicion: %d x %d\n", position_fila, position_columna);
  116. }
  117.  
  118. // 2 Condiciones:
  119. //[1] Si puedo moverme hacia la derecha (Si el elemento a la derecha mi posicion es 0).
  120. //[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).
  121.  
  122. else if((!(laberinto[position_fila][sig_columna])) && (sig_columna != ultima_pos_col))
  123. {
  124. ultima_pos_col = position_columna; //Guardas ultima posicion
  125. position_columna++; //Mueves hacia la derecha
  126. printf(" Right ");
  127. printf("Mi posicion: %d x %d\n", position_fila, position_columna);
  128. }
  129.  
  130. // 2 Condiciones:
  131. //[1] Si puedo moverme hacia arriba  (Si el elemento sobre mi posicion es 0).
  132. //[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).
  133.  
  134. else if((!(laberinto[ant_fila][position_columna])) && (ant_fila != ultima_pos_fila))
  135. {
  136. ultima_pos_fila = position_fila; //Guardas ultima posicion
  137. position_fila--; //Mueves hacia arriba
  138. printf(" Up ");
  139. printf("Mi posicion: %d x %d\n", position_fila, position_columna);
  140. }
  141.  
  142. // 2 Condiciones:
  143. //[1] Si puedo moverme hacia la izquierda (Si el elemento a la izquierda mi posicion es 0).
  144. //[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).
  145.  
  146. else if((!(laberinto[position_fila][ant_columna])) && (ant_columna != ultima_pos_col))
  147. {
  148. ultima_pos_col = position_columna; //Guardas ultima posicion
  149. position_columna--; //Mueves hacia izquierda
  150. printf(" Left ");
  151. printf("Mi posicion: %d x %d\n", position_fila, position_columna);
  152. }
  153.  
  154. }
  155.  
  156. }
  157.  

Muchas gracias de antemano por cualquier ayuda y un saludo a la comunidad elhacker!



« Última modificación: 20 Noviembre 2014, 00:32 am por Leafar77 » En línea

_Enko


Desconectado Desconectado

Mensajes: 538



Ver Perfil WWW
Re: Programa resolución laberinto en C
« Respuesta #1 en: 19 Noviembre 2014, 22:39 pm »

Hola, no se exactamente que problemas puedes tener en el código. Pero por lo que recuerdo, uno de los algoritmos mas usados para encontrar la ruta es el algoritmo A Star.

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

Si mal no recuerdo, habia hecho la implementación siguiendo esta guia:
http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003
(disponible español en http://www.policyalmanac.org/games/articulo1.htm)

y este tambien:
http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

necesitas dos listas enlazadas.  Por lo menos leyendo esas guias puedas darte una idea de como sacar la ruta mas eficiente.

Saludos.


« Última modificación: 19 Noviembre 2014, 22:52 pm por _Enko » En línea

engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.514



Ver Perfil
Re: Programa resolución laberinto en C
« Respuesta #2 en: 19 Noviembre 2014, 22:53 pm »

te digo, tu código es más largo de lo que la mayoría intentarán leer también

procura usar las etiquetas GeSHi para publicad código (ya que si no es más difícil de leer)

por ultimo te recomiendo usar el debugger y correr las instrucciones paso a paso para poder ver cual es el error en tu logica más facilmente
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
Leafar77

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: Programa resolución laberinto en C
« Respuesta #3 en: 19 Noviembre 2014, 23:49 pm »

Hola, no se exactamente que problemas puedes tener en el código. Pero por lo que recuerdo, uno de los algoritmos mas usados para encontrar la ruta es el algoritmo A Star.

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

Si mal no recuerdo, habia hecho la implementación siguiendo esta guia:
http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003
(disponible español en http://www.policyalmanac.org/games/articulo1.htm)

y este tambien:
http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

necesitas dos listas enlazadas.  Por lo menos leyendo esas guias puedas darte una idea de como sacar la ruta mas eficiente.

Saludos.

Me he estado mirando el algoritmo que me dices y he sacado alguna idea que puedo aplicar aqui, pero no exactamente lo que me piden en el problema, de hecho es más simple. El programa no tiene que buscar la ruta mas eficiente, basta con una de las rutas, y aunque esta sea un mero "caminito" más que un laberinto.(Como el del ejemplo) Este codigo deberia servir para lo que me piden, pero por algun lado peta.
Gracias por la ayuda!



te digo, tu código es más largo de lo que la mayoría intentarán leer también

procura usar las etiquetas GeSHi para publicad código (ya que si no es más difícil de leer)

por ultimo te recomiendo usar el debugger y correr las instrucciones paso a paso para poder ver cual es el error en tu logica más facilmente

Gracias, no sabia como resaltar el texto! Voy a intentar con el debugger, a ver si consigo algo.
« Última modificación: 20 Noviembre 2014, 15:17 pm por Eternal Idol » En línea

engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.514



Ver Perfil
Re: Programa resolución laberinto en C
« Respuesta #4 en: 19 Noviembre 2014, 23:57 pm »

reglas del foro, procura no hacer doble post, si necesitas decir algo adicional, usa el boton
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Hay algun programa de emulación para Playstation2 de mayor resolución ?
Juegos y Consolas
Ad0nis 3 2,402 Último mensaje 12 Junio 2006, 12:46 pm
por DJ46
Laberinto en Php.
PHP
n3fisto 2 4,626 Último mensaje 20 Marzo 2010, 15:26 pm
por n3fisto
Backtracking - Laberinto
Programación C/C++
hadree 3 7,029 Último mensaje 23 Noviembre 2010, 03:08 am
por do-while
Ayuda con resolucion de skins programa psrockola
Software
luis.krash2 5 5,926 Último mensaje 23 Julio 2013, 21:06 pm
por misterpaco1
programa que resuelva el siguiente laberinto en C#
.NET (C#, VB.NET, ASP)
Emily 4 5,054 Último mensaje 21 Marzo 2017, 17:30 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines