labirinto em c++

[felipebranco 0]

Nao sei se alguem ja postou perguntando isso, eu dei uma olhada no forum, no google, e não achei nenhum lugar que desse dicas pra resolver esse exercicio. No maximo vi coisa sem resposta.

Esse é um exercicio que tá no deitel.

 

A proposta dele é usar uma matriz 12x12 com # pra ser a parede e . pra ser o espaço em branco. E ele manda criar o seguinte algoritmo pra sair de qualquer labirinto. "Colocar a mão numa parede e seguir ela até o fim".

 

Eu tentei bastante, tenho uns dois dias pensando em como resolver isso. As funções recursivas pra chamar o movimento, a função de desenhar, tá tudo certo. A única coisa(e talvez a mais importante) é eu conseguir que ele se movimente "segurando a mão numa parede", como a questão pede.

 

Eu tentei estabelecer uma direção do movimento, com velocidade horizontal e vertical, que variam de -1 a 1, e criei uma função gira(), usando seno e cosseno, pra mudar essa direção. Quando o personagem entrasse em um beco sem saída eu daria um gira(2), por exemplo. Isso funciona normal.

 

olha o script do movimento. Ele não funciona mesmo, mas foi o máximo que eu consegui chegar. Eu to perdido é na ideia de seguir um caminho com a mão. Eu não sabia se verificava os quadrados em branco, ou se verificava as paredes, pra fazer o caminho pro cara seguir.

 

Exemplo de labirinto:

 

##############

#. . . . . . . . . . . . . #

. ....#########.....

#..############

#..........................#

##############

 

O negocio de postar tirou a margem toda do codigo.

 

====================================================================

 

void move(int &x, int &y, char maze[height][width], const int height, const int width)

 

// (variavel x, variavel y, array do labirinto, altura, largura)

 

{

static int directionx = 0; //variavel da velocidade horizontal (estatica pra não perder a direção anterior)

static int directiony = 0; // variavel da velocidade vertical

 

static int xtemp = -99; // variaveis que guardam a posição anterior(pra não voltar pro quadrado já caminhado)

static int ytemp = -99;

 

int countpos = 0; //contador do número de possibilidades de andar

 

// ----------------------------------------

// Verificação dos quadrados da frente

// ----------------------------------------

if((x + 1) < width && maze[y][x+1] == '.' && (x + 1) != xtemp) // '.' é o quadrado livre

{

countpos++;

directionx = 1;

directiony = 0;

}

 

if((x - 1) >= 0 && maze[y][x-1] == '.' && (x - 1) != xtemp)

{

countpos++;

directionx = -1;

directiony = 0;

}

 

if((y + 1) < height && maze[y + 1][x] == '.' && (y + 1) != ytemp)

{

countpos++;

directiony = 1;

directionx = 0;

}

 

if((y - 1) >= 0 && maze[y - 1][x] == '.' && (y - 1) != ytemp)

{

countpos++;

directiony = -1;

directionx = 0;

}

 

 

if(countpos == 0) // significa que entrou num caminho sem saída

{

directionx = gira(directionx,directiony,2,0); // meia-volta(+ 2/4 de volta e retorna o Vx)

directiony = gira(directionx,directiony,2,1); // meia-volta(+ 2/4 de volta e retorna o Vy)

xtemp = x; // torna possível o boneco andar pro quadrado anterior

ytemp = y; // torna possível o boneco andar pro quadrado anterior

 

x+= directionx; //anda o boneco

y+= directiony;

}

 

if(countpos == 1) // Uma possibilidade de andar

{

x+= directionx; //anda o boneco

y+= directiony;

}

 

if(countpos>1) // to perdido aqui nessas possibilidades (bifurcações)

{

directionx = gira(directionx,directiony,1,0);

directiony = gira(directionx,directiony,1,1);

 

x+= directionx; //anda o boneco

y+= directiony;

}

 

 

 

 

xtemp = x; // coloca o x atual como o próximo x anterior

ytemp = y; // coloca o y atual como o próximo y anterior

}

 

=======================================================================

 

Se alguém pudesse dar uma dica, eu agradeço. Prefiro até que não dê resposta, pra eu conseguir resolver sozinho.

Ah, e isso não é trabalho de curso não, eu to estudando sozinho.

valeu ae http://forum.imasters.com.br/public/style_emoticons/default/joia.gif

[quitZAUMMM 18]

Olha vendo seu exemplo oq vem na cabeça é você fazer uma espécie daquela jogo 'Pac Man'...

sendo assim.

faz ele testar tds os lados para andar. ai=

if maze[height][width] = '.' {
  //anda 
}
else {
gira();
}

Bom qlqr coisa volte a postar!

[felipebranco 0]

é verdade, ficou parecido com pacman, e é isso que tá errado huahua

eu não consegui imaginar o algoritmo que funcionasse pra esse negocio ae.

 

Tendo a matriz 12x12, com os '.' sendo o caminho livre e o # sendo as paredes, como sair de um labirinto?

A questão fala que pode sair de qualquer labirinto se a gente colocar a mao na parede que a gente tá e seguir em frente sem soltar ela(acompanhando todas as curvas, até o final).

O que eu não consegui fazer é justamente isso, imaginar como transformar isso em linguagem. E fiquei em duvida, porque poderia começar de varias formas, como examinando as casas em branco, ou examinando as paredes, fazendo um caminho aparente dentro delas, pra poder acompanhar as curvas.

Complicado...

 

De qualquer forma eu to anotando aqui os exercicios que nao consigo fazer, pra quem sabe um dia huahua

[quitZAUMMM 18]

desculpe mas naum entendi muito bem esse "colocar a mao na parede" !!

[Kandrade 7]

O colocar a mão na parede seria seguir pelos limites da matriz e pelos limitadores.

Não sei se ficou claro.

 

Vou pensar numa solução e posto depois algum comentário.

 

http://forum.imasters.com.br/public/style_emoticons/default/grin.gif

[quitZAUMMM 18]

no q eu entendi entaum ele pode fazer assim, exemplo neh:

o labirinto esta numa parte assim:

 

##########

#.......x.....### entenda o ponto 'x' como o jogador

##..#######

 

ai ele pode fazer uma condição q :

se o jogador tiver encostado na parede e a frente dele estiver livre ele vai avançando caso ñ tenha + lugar pra ir a frente ele volta e verifica c existe caminho livre nas laterais c existir ele soh usa a função gira(); c continuar encostado na parade!

 

bom cara to tentando te ajudar na medida do q eu entendi =D

 

qlqr coisa volte a postar

[Kandrade 7]

Pensei algo rápido aqui.

 

Uma das posições será a saída para o labirinto correto?

 

Voce testará sempre se a posição atual do objeto é a posição solução.

Se não for voce poderá escolher entre no máximo 4 caminhos. Nesses caminhos voce terá movimentos inválidos e movimentos não desejáveis que serão os que não acompanham a parede.

Opte pelos que seguem a parede e sempre guarde o último movimento para não criar uma repetição.

 

Se precisar de alguma ajuda pra desenvolver ou quiser discutir essa idéia é só postar.

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

[felipebranco 0]

Eu tentei seguir dessa forma. Pra 0 ou 1 caminhos, o meu algoritmo funciona direito, sem voltar e tudo. Inclusive quando entra em um beco e não dá pra ir adiante ele dá meia volta.

No caso de ter mais de um caminho pra ir, eu pensei em botar ele pra dar um giro pra direita sempre. Mas isso não é o ideal, porque dar um giro pra direita nem sempre significa seguir o caminho "segurando a mao".

 

Por exemplo:

 

############

.......................... #

.........O................#

#### | #######

#### | #######

(3 caminhos, tirando o de voltar)

Vamos virar pra direita e seguir.

 

 

############

.........................#

...........---->----O#

#### | #######

#### | #######

(ele para aqui e não deve virar a direita, e sim a esquerda, se quiser

acompanhar o trajeto do labirinto com a mao na parede)

 

O que mata meu algoritmo é não saber como expressar logicamente essa "mao na parede"

 

 

# ........__________|###

# ....._|###########

# .....|############

 

Hmm, quem sabe colocando numeros representando as paredes, e botar pra fazer uma busca pelos mais provaveis e fazer o boneco de verdade preferir os lugares mais proximos dos numeros altos.

Teve uma questão de como movimentar um cavalo em todas as casas do xadrez sem repetir que indicava pra usar isso, chamava de heuristic parece, e eu até consegui fazer ela.

 

2| ........__________|311

2| ...._|32222222232111

2| ....|311111111111111

 

Sei lá, nao tenho tem ideia.

 

A questao depois dessa pede ainda pra criar um gerador de labirinto. É f*** viu. A maior parte das questões do deitel são do tipo pra fazer coisas comuns e criar funções de output e organizar dados. Mas tem uma ou outra que é mais de lógica, que eles abusam. E uns projetos desafio que eu nem pego pra tentar, lá ta escrito que pode demorar semanas ou meses pra terminar huahua

 

As piores são as que a gente tem uma forma simples de enxergar na vida real e pra passar pro computador tem que mudar completamente a visão.

[felipebranco 0]

Kandrade, o que voce disse sobre preferir as posições que tenham parede é até certo, mas se botar só isso na função, o boneco pode ficar rodando no labirinto por um tempão, principalmente se tiver abertura de mais caminhos em cada lugar que ele entrar. Aí é como confiar num random http://forum.imasters.com.br/public/style_emoticons/default/no.gif

[Kandrade 7]

Creio que seguir a parede seja a solução.

Se tenho vários caminhos a percorrer posso optar por seguir a parede. Uma hora ou outra ele acha a saída.

Não haverá looping, creio que não. No máximo ele percorrerá o labirinto todo e no final encontrará a saída.

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

 

 

Kandrade, o que voce disse sobre preferir as posições que tenham parede é até certo, mas se botar só isso na função, o boneco pode ficar rodando no labirinto por um tempão, principalmente se tiver abertura de mais caminhos em cada lugar que ele entrar. Aí é como confiar num random http://forum.imasters.com.br/public/style_emoticons/default/no.gif

[felipebranco 0]

hmm, mas como testar se ele segue a parede?

 

Eu tenho que guardar uma variavel da direção da frente do boneco, ou simplesmente pegar aquelas variaveis do meu programa direção x e direção y(que variam de -1 a 1), e criar uma condição de verificar a parede, né?

Aí eu testo se a posição que tá à direita do boneco é livre ou não, e se for eu faço a curva.

 

Acho que a unica posição que dá problema é essa, porque o resto a variavel da posição anterior acaba anulando:

######

..............

.....O........

##...###

 

Aí boto esse como um caso especial

if(3 opções de caminho, e 2 abertos e 2 fechados nas diagonais)

{

while(direitaLivre() == false)

gira(1);

...

 

Eu vou ir tentando pra ver se consigo, qualquer coisa eu posto depois, valeu pela ajuda!

}