1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Jogo de labirinto

Discussão em 'Programação' iniciada por cnad73, 12 de Novembro de 2006. (Respostas: 4; Visualizações: 1733)

  1. Olá. Sou um novato nestas andanças de programação. Ando a estudar algoritmos e foi-me colocado um problema sobre o qual terei de me debruçar nas próximas semanas. Trata-se de um labirinto de p.e. 10x10 onde se pode marcar o ponto I (início) e o ponto F (fim). Neste labirinto poderão também ser colocados obstáculos na tabela bidimensional. O algoritmo tem que achar o caminho correcto do ponto I ao ponto F. Será que me podem dar algumas luzes sobre como hei-de resolver este problema. Todas as dicas serão bem-vindas.

    Boas programações

    CNAD:x2:
     
  2. _freelancer_

    _freelancer_ Power Member

    Isso não tem muito que saber, penso que será algo do tipo:

    Enquanto não chegares ao fim do labirinto:

    Analizas todas as 7 posições à tua volta (não vale a pena analisares aquela de onde vens)

    Se houver "saidas", escolhes uma e repetes o processo até chegares à posição fim

    Se não houver "saidas" (com excepção daquela por onde vieste), voltas atrás até ao ponto onde tinhas pelo menos 2 saidas (mais uma vez, exceptuando a por onde vieste) e escolhes outra até esgotares as saidas todas nesse ponto, OU, chegares ao fim.

    Espero ter ajudado qualquer coisita.:)

    Edit: Uma coisa muito importante, se fores navegar pela tabela com um par de coordenadas (digamos x,y para linhas e colunas), não faz sentido teres indíces da matriz menores que 0 (ou o valor a que a linguagem que vais utilizar usa para o primeiro indíce), ou maiores que n (onde n é o número de linhas e colunas).

    Se fores utilizar uma numeração sequencial, então não faz sentido indíces menores que 0 ou maiores que n*n-1 (a ultima posição). Porém, se este for o caso, então quando estás numa posição qualquer, para analisares as posições acima ou abaixo tens de subtrair ou adicionar n-1,n e n+1 para cada posição vizinha dessa célula. Confuso? :D
     
    Última edição: 12 de Novembro de 2006
  3. Boa tarde.

    Desde já obrigado pela atenção. Tenho uma dúvida: No início, se se colocar o ponto I no meio da tabela terão de ser analisadas 8 posições. Como tal terei de começar o meu trabalho por aí, certo? E só depois então analisar as outras 7 posições seguintes como foi referido pelo Freelancer. Já agora o algoritmo a utilizar nestes casos é de algum tipo, i.e., há alguma referência para que eu possa pesquisar na net?

    Todas as dicas são bem-vindas.

    Boas programações

    CNAD:x2:
     
  4. Tenho o mesmo trabalho pa fazer...lol
     
  5. VR1

    VR1 Power Member

    Isso que procuras está directamente relacionado com Grafos.

    Existem vários algoritmos para resolver o que pretendes.
    A sua escolha terá que ser feita baseando-te nos seguintes factores: valorização do menor tempo de escolha do caminho ou preferência no caminho mais curto. Podem haver mais variações mas de momento não me recordo.

    Tens aqui um link que usei quando precisei de aprender isso e tem uma aplicação em para perceberes melhor.

    Por exemplo, 2 algoritmos, são o BFS e o DFS. Mais n digo ;)
     
    Última edição: 14 de Novembro de 2006

Partilhar esta Página