Jump to content
Sign in to follow this  
WolfmanZ

[Resolvido] Duvida em C, Labirinto.

Recommended Posts

WolfmanZ

Boa noite,

Tenho uma duvida em relação a um projecto. É dado num ficheiro .txt um labirinto com a posição inicial e a posição final do labirinto. Nesse mesmo ficheiro tem de ser carregado e depois preencher o labirinto utilizando o algoritmo DFS. Só posso utilizar um passo de cada vez e pela seguinte ordem de testes: CIMA, ESQUERDA, BAIXO e por fim DIREITA.Na utilização deste algoritmo o prof obrigou a usarmos pilhas como estrutura de dados. Na faculdade cheguei a falar desse tipo de estrutura de dados mas não chegamos aprofundar, daí não estar a 100% a vontade nesta parte da materia. Em baixo deixo o codigo que neste momento tem um erro. Até este momento o meu código já carrega o ficheiro e já consigo preencher a primeira coluna e a ultima linha consoante as regras de preenchimento(imagem 1).

c2ac789a7e45e402c02ef506c1d9ece9.gif

Mas até agora não fui obrigado a utilizar estrutura de dados e sim apenas os testes de preenchimento. A partir deste momento sou "obrigado" a utilizar a estrutura de dados porque tenho de voltar "atrás" para verificar as posições já preenchidas se pode ser feito outro teste.Segue uma imagem como o actual labirinto deve estar preenchido no final.

604495482c5852a1cbca6c5cdbfb4b62.gif

Edited by WolfmanZ
GeSHi

Share this post


Link to post
Share on other sites
HappyHippyHippo

podes apresentar o ficheiro txt com a informação do labirinto ? (e explicar a informação existente se assim for necessário)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
HappyHippyHippo

P.S. Não sei se posso utilizar estruturas de dados misturado com recursividade.

sim podes e deves ...

mais é difícil pela dificuldade de ler o teu código, mas uma coisa me pareceu : deverias ter acessos inválido à memória quando fazes verificações nos limites do labirinto

------------------------------------------------------------------------------

fica aqui uma solução ...

não te aconselho a usar-la por duas razões:

- se o trabalho é de criação de pilhas, o código apresentado não cria, usa uma pilha que já existe ... fica para tu pensares qual ...

- o teu professor deverá conhecer o fórum ... não será necessário dizer mais ...

nota : o código tem 180 linhas onde 90 é só para ler o ficheiro com o labirinto

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Maze {
 uint32_t width, height, startx, starty, endx, endy;
 uint32_t * maze;
};

#define maze_pos(maze, x, y)                                 (maze.maze[(y) * maze.width + (x)])

#define maze_pos_wall_up(maze, x, y)                         ((maze_pos(maze, (x), (y)) >> 0)  & 0xf)
#define maze_pos_wall_down(maze, x, y)                       ((maze_pos(maze, (x), (y)) >> 4)  & 0xf)
#define maze_pos_wall_left(maze, x, y)                       ((maze_pos(maze, (x), (y)) >> 8)  & 0xf)
#define maze_pos_wall_right(maze, x, y)                      ((maze_pos(maze, (x), (y)) >> 12) & 0xf)
#define maze_pos_wall_set(maze, x, y, up, down, left, right) (maze_pos(maze, (x), (y)) = ((right & 0xf) << 12) | ((left & 0xf) << 8) | ((down & 0xf) << 4) | ((up & 0xf) << 0))
#define maze_pos_wall_set_up(maze, x, y, wall)               (maze_pos(maze, (x), (y)) = (maze_pos_wall_right(maze, (x), (y)) << 12) | (maze_pos_wall_left(maze, (x), (y)) << 8) | (maze_pos_wall_down(maze, (x), (y)) << 4) | ((wall & 0xf)                     << 0))
#define maze_pos_wall_set_down(maze, x, y, wall)             (maze_pos(maze, (x), (y)) = (maze_pos_wall_right(maze, (x), (y)) << 12) | (maze_pos_wall_left(maze, (x), (y)) << 8) | ((wall & 0xf)                       << 4) | (maze_pos_wall_up(maze, (x), (y)) << 0))
#define maze_pos_wall_set_left(maze, x, y, wall)             (maze_pos(maze, (x), (y)) = (maze_pos_wall_right(maze, (x), (y)) << 12) | ((wall & 0xf)                       << 8) | (maze_pos_wall_down(maze, (x), (y)) << 4) | (maze_pos_wall_up(maze, (x), (y)) << 0))
#define maze_pos_wall_set_right(maze, x, y, wall)            (maze_pos(maze, (x), (y)) = ((wall & 0xf)                        << 12) | (maze_pos_wall_left(maze, (x), (y)) << 8) | (maze_pos_wall_down(maze, (x), (y)) << 4) | (maze_pos_wall_up(maze, (x), (y)) << 0))

#define maze_pos_value(maze, x, y)                           ((maze_pos(maze, (x), (y)) >> 16) & 0xffff)
#define maze_pos_assign(maze, x, y, value)                   (maze_pos(maze, (x), (y)) = (maze_pos(maze, (x), (y)) & 0xffff) | ((value & 0xffff) << 16 ))

struct Maze maze_create(const char * file);
void        maze_output(struct Maze maze);
int         maze_dfs(struct Maze maze, uint32_t x, uint32_t y, uint32_t step);
void        maze_destroy(struct Maze maze);

int main(int argc, char ** argv) {
 struct Maze maze;

 maze = maze_create("input.txt");

 maze_dfs(maze, maze.startx, maze.starty, 1);
 maze_output(maze);

 maze_destroy(maze);

 return 0;
}

struct Maze maze_create(const char * file) {
 struct Maze maze;
 FILE * fd = NULL;
 char buffer[1024];
 uint32_t x, y;

 if ((fd = fopen(file, "r")) == NULL) {
   printf("Unable to open input file\n");
   exit(-1);
 }

 if (fgets(buffer, 1024, fd) == NULL || sscanf(buffer, "%u,%u", &maze.width, &maze.height) != 2) {
   fclose(fd);

   printf("Unable to read maze size from the input file\n");
   exit(-1);
 }
 maze.maze = malloc(sizeof(uint32_t) * maze.width * maze.height);

 for (x = 0; x < maze.width; x++)
   maze_pos_wall_set_down(maze, x, maze.height - 1, 1);

 for (y = 0; y < maze.height; y++) {
   maze_pos_wall_set_right(maze, maze.width - 1, y, 1);

   if (fgets(buffer, 1024, fd) == NULL) {
     free(maze.maze);
     fclose(fd);

     printf("Unable to read maze horizontal walls at row : %d\n", y);
     exit(-1);
   }

   for (x = 0; x < maze.width; x++) {
     if (buffer[x * 2 + 1] == '-') {
       maze_pos_wall_set_up(maze, x, y, 1);
       if (y != 0)
         maze_pos_wall_set_down(maze, x, y - 1, 1);
     }
   }

   if (fgets(buffer, 1024, fd) == NULL) {
     free(maze.maze);
     fclose(fd);

     printf("Unable to read maze vertical walls at row : %d\n", y);
     exit(-1);
   }

   for (x = 0; x < maze.width; x++) {
     if (buffer[x * 2] == '|') {
       maze_pos_wall_set_left(maze, x, y, 1);
       if (x != 0)
         maze_pos_wall_set_right(maze, x - 1, y, 1);
     }
   }
 }

 if (fgets(buffer, 1024, fd) == NULL) {
   free(maze.maze);
   fclose(fd);

   printf("Unable to read maze final horizontal walls\n");
   exit(-1);
 }

 if (fgets(buffer, 1024, fd) == NULL || sscanf(buffer, "%u,%u", &maze.startx, &maze.starty) != 2) {
   free(maze.maze);
   fclose(fd);

   printf("Unable to read maze start position from the input file\n");
   exit(-1);
 }

 if (fgets(buffer, 1024, fd) == NULL || sscanf(buffer, "%u,%u", &maze.endx, &maze.endy) != 2) {
   free(maze.maze);
   fclose(fd);

   printf("Unable to read maze end position from the input file\n");
   exit(-1);
 }

 fclose(fd);

 return maze;
}

void maze_output(struct Maze maze) {
 uint32_t x = 0, y = 0;

 for (y = 0; y < maze.height; y++) {
   for (x = 0; x < maze.width; x++)
     printf("+%s+", maze_pos_wall_up(maze, x, y) ? "--" : "  ");
   printf("\n");

   for (x = 0; x < maze.width; x++) {
     printf("%c", (maze_pos_wall_left(maze, x, y) ? '|' : ' '));
     if (maze_pos_value(maze, x, y))
       printf("%2d", maze_pos_value(maze, x, y));
     else
       printf("  ");
     printf("%c", (maze_pos_wall_right(maze, x, y) ? '|' : ' '));
   }
   printf("\n");

   for (x = 0; x < maze.width; x++)
     printf("+%s+", maze_pos_wall_down(maze, x, y) ? "--" : "  ");
   printf("\n");
 }
 printf("\n");
}

int maze_dfs(struct Maze maze, uint32_t x, uint32_t y, uint32_t step) {
 maze_pos_assign(maze, x, y, step);

 if (x == maze.endx && y == maze.endy)
   return -1;

 if ((step != -1) && (y > 0) && !maze_pos_wall_up(maze, x, y) && (maze_pos_value(maze, x, y - 1) == 0))
   step = maze_dfs(maze, x, y - 1, step + 1);

 if ((step != -1) && (x > 0) && !maze_pos_wall_left(maze, x, y) && (maze_pos_value(maze, x - 1, y) == 0))
   step = maze_dfs(maze, x - 1, y, step + 1);

 if ((step != -1) && (y < maze.height - 1) && !maze_pos_wall_down(maze, x, y) && (maze_pos_value(maze, x, y + 1) == 0))
   step = maze_dfs(maze, x, y + 1, step + 1);

 if ((step != -1) && (x < maze.width - 1) && !maze_pos_wall_right(maze, x, y) && (maze_pos_value(maze, x + 1, y) == 0))
   step = maze_dfs(maze, x + 1, y, step + 1);

 return step;
}

void maze_destroy(struct Maze maze) {
 free(maze.maze);
}

input.txt

8,8
- - - - - - - - 
| |     |       |
        - - -   
| |     |     | |
          - -   
| | |   | |   | |

| | |   | |     |

|   |     |   | |
      - -       
|   |         | |
      - - - -   
|   |           |
  - - - - - - - 
|               |
- - - - - - - - 
0,0
4,0

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
WolfmanZ

Boa tarde,

Obrigado pela solução mas o meu problema persiste em criar a pilha e não na leitura do ficheiro.

Share this post


Link to post
Share on other sites
Flinger

Mas o teu professor obriga a que a própria estrutura do labirinto seja um pilha (o que não faz sentido, embora se possa usar pilhas dentro das estruturas), ou que uses uma pilha para percorrer todo o labirinto???

Esta última faz todo o sentido, e tens aqui um exemplo de como o fazer (em pseudo-código)

http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode

BTW, tens aqui uma ajuda para entender melhor as stacks:

http://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Edited by Flinger

Share this post


Link to post
Share on other sites
HappyHippyHippo

eu percebi qual era a dúvida, e já referi no post anterior:

mais é difícil pela dificuldade de ler o teu código

o código ao não estar indentado (normalmente) nem me dou ao trabalho de ler

se tiveres dúvidas em como apresentar o código indentado, utiliza o edito simples fo fórum (primeiro botão do editor)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
WolfmanZ

Tenho de usar um dos dois algoritmos, DFS em pilha ou BFS em lista de salto para percorrer todo o labirinto.

Eu optei por usar o DFS porque achei que fosse mais simples.

Obrigado pelo os links, irei dar uma vista de olhos e tentar implementar dessa maneira.

Share this post


Link to post
Share on other sites
Flinger

O DFS não é nada dificil, como podes ver pelo link que postei. São meia dúzia de linhas, onde a única pequena alteração que tu tens de fazer é a ordenação pela qual são inseridos os elementos na pilha, devido às especificidades do teu problema :

pela seguinte ordem de testes: CIMA, ESQUERDA, BAIXO e por fim DIREITA.

O segredo aqui está em definir muito bem as estruturas que usas. Separar o que é a pilha do que é a estrutura do labirinto, e a forma, dentro do labirinto, como representas as barreiras. E é nestes pontos que acho que estás a falhar. Lê bem ambos os artigos que postei, e se tiveres dúvidas apita.

O Hippo usa uma forma um pouco obscura (entenda-se, difícil de ler), mas perfeitamente válida e poupada a nível de memória e processamento. E não é nada difícil converter o programa dele para usar uma pilha na travessia DFS.

Share this post


Link to post
Share on other sites
HappyHippyHippo

O Hippo usa uma forma um pouco obscura (entenda-se, difícil de ler)

para alguns admito que sim, mas consigo ler o meu código 10x mais rápido que o apresentado pelo @WolfmanZ

O código já esta indentado.

não estás a reverter as operações de inserção na pilha quando chegas a um beco sem saída

além disso, nunca poderás usar o "else if" porque estás a ignorar os testes quando "caminhares para trás"

olha para o meu código e vê como o processo de decisão está implementado

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Flinger

para alguns admito que sim, mas consigo ler o meu código 10x mais rápido que o apresentado pelo @WolfmanZ

Foi feito por ti, é normal que consigas lê-lo bem. Mas a mim ainda me custou um pouco a perceber como estavas a representar as "paredes" labirinto. A nível de algoritmo, está bastante claro, devido ao uso das macros, mas a nível de estrutura o uso de máscaras de bits torna-o um pouco mais difícil de ler, sobretudo para quem não estiver habituado a este tipo de manipulação. Mais uma vez, acho-o muito bem conseguido, e eficiente, mas para alguém menos experiente, pode ser um pouco difícil de ler.

Por outro lado, eu sempre fui péssimo a ler código de outros :P

Edited by Flinger

Share this post


Link to post
Share on other sites
HappyHippyHippo

o uso de máscaras de bits torna-o um pouco mais difícil de ler, sobretudo para quem não estiver habituado a este tipo de manipulação.

infelizmente, o uso de mascaras de bits é algo que nunca se aprofunda muito quando uma pessoa está a aprender. o que leva a que passe a tentar resolver os problemas através de outros métodos como estruturas. claro que não é errado usar estruturas, mas perdesse a elasticidade mental para pensar em mascaras de bits.

no entanto, quando apresentei o código, disse à partida para ele não o usar, era só para ele ver a função maze_dfs e tirar a ideia de como abordar o problema.

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
WolfmanZ

CRLF - Acho que o meu problema foi não ter usado uma estrutura para o meu maze. Eu uso uma matriz de chars..

HappyHippyHippo - Eu apresentei assim porque esqueci de verificar a indentação :/. Ok vou tentar corrigir esse dois pontos que disseste.

Como é obvio eu não irei usar porque tambem tive uma certa dificuldade a ler e a perceber o teu codigo.

Share this post


Link to post
Share on other sites
thoga31

CRLF - Acho que o meu problema foi não ter usado uma estrutura para o meu maze. Eu uso uma matriz de chars..

HappyHippyHippo - Eu apresentei assim porque esqueci de verificar a indentação :/. Ok vou tentar corrigir esse dois pontos que disseste.

Com um membro acertas no nick e com o outro não?

O nome do membro não é CRLF mas sim Flinger, da mesma forma que o HappyHippyHippo não é Stack Overflow.


Knowledge is free!

Share this post


Link to post
Share on other sites
Flinger

CRLF - Acho que o meu problema foi não ter usado uma estrutura para o meu maze. Eu uso uma matriz de chars.

Não quer dizer que esteja errado. O Hippo usa uma matriz também, mas cada valor tem lá dentro a informação sobre os limites das posições.

No teu caso, como não disponibilizaste a função de leitura, não sei como o fazes. Mas o algoritmo em si é fácil.

Partindo do princípio que a tua estrutura Maze é a pilha,


push(posicaoinicial)
Enquanto stack não for vazia
   elemento = pop()
   se (matriz[posicao_do_elemento] == vazio)
       matriz[posicao elemento] = contador
       Se (puder_ir_para_direita)
           push(elemento_a_direita)
       Se (puder_ir_para_baixo)
           push(elemento_a_baixo)
       Se (puder_ir_para_Esquerda)
           push(elemento_a_esquerda)
       Se (puder_ir_para_cima)
           push(elemento_a_cima)

Tem em atenção a ordem das comparações. Numa stack o pop devolve-te o último elemento a ser inserido. Por isso se o primeiro que queres testar é o de cima, este tem de ser o último a ser inserido.

O algorítmo que postei da wikipédia é um pouco diferente, já que carrega para a stack todos os elementos, só depois fazendo o teste se eles já foram visitados ou não.

Também dá, mas eu acho que esta forma é um pouco mais eficiente.

BTW, para usares uma pilha não necessitas de recursividade. A pilha em si já te resolve o problema de voltar atrás.

Edited by Flinger

Share this post


Link to post
Share on other sites
WolfmanZ

Só tenho uma duvida referente ao teu pseudo-codigo, o elemento que referes na 3ª linha será o nó criado antes de fazer o push(posicaoinicial) ?

Obrigado

Share this post


Link to post
Share on other sites
Flinger

Sim. Falta-me o incremento do contador, cada vez que o atribuis a uma posicao.

Edited by Flinger

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.