3. Busca do Caminho do Labirinto

Chegou a hora de implementar a “inteligência” do jogo, na qual o computador irá identificar de forma automática um caminho que liga o ponto de início ao destino no tabuleiro. Para fazer isso, vamos definir duas novas constantes:

A constante de nome CAMINHO representa o caractere que marca o caminho por onde o computador está percorrendo. Já a constante de nome SEM_SAIDA será usada para marcar os caminhos pelos quais o computador já percorreu e que verificou que por lá não é possível alcançar o destino.

Vamos agora à função de busca pelo caminho. Para isso definimos a função “procurarCaminho()”, que recebe dois parâmetros do tipo inteiro, a linha e a coluna de início do caminho. Tente entender o que o código dessa função faz:

Note que essa função retorna um boleano de valor true, caso um caminho tenha sido encontrado; e false, caso contrário. Seu funcionamento é basicamente o seguinte. O algoritmo da função tenta seguir o caminho subindo no tabuleiro (manter coluna, tentando linha anterior), se não der ele tenta descendo (manter coluna e tentar linha posterior), se não der vai pela esquerda (manter linha e tentar coluna anterior) e por último tenta pela direita (manter linha e tentar coluna posterior). Para realizar essas tentativas, é usada a função “tentarCaminho()”, cujo código será mostrado a seguir. Essa nova função recebe como parâmetro a posição do caminho que se quer tentar percorrer.

A função “tentarCaminho()” basicamente realiza vários testes. O primeiro deles é se a posição que se está tentando caminhar é a de destino (tabuleiro[proxLinha][proxColuna] == DESTINO). Se for esse o caso, então é porque o destino foi alcançado e retorna ao valor true. Caso contrário, verifica-se se a posição é válida para caminhar através de uma função “posicaoVazia()”, mostrada mais adiante e que retorna true apenas quando a posição passada como parâmetro estiver vazia, ou seja, é um posição válida para formar um caminho no labirinto (está no tabuleiro e não é uma parede ou obstáculo).

Nesse caso, o caminho é marcado (posição preenchida com o valor da constante CAMINHO) e imprime-se novamente na tela o tabuleiro com os seguintes comandos:

A ideia é então continuar a busca a partir dessa posição marcada. Isto é feito chamando-se novamente a função “procurarCaminho()”. Note que essa função recebe como parâmetro as novas posições “proxLinha” e “proxColuna”., indicando que será realizada a busca a partir dessa nova posição:

Nesse momento é que entra a recursão! O processo mostrado irá se repetir a partir dessa “nova posição inicial”. Caso a função “procurarCaminho()” retorne true, isto indicará que foi possível encontrar um caminho até o destino a partir daquela posição “proxLinha” e “proxColuna”. Caso retorne false, quer dizer que não foi possível encontrar o caminho, então devemos descartar aquela posição. Isto é feito justamente pelos seguintes comandos:

Por fim, a função “tentarCaminho()” retorna ao valor da variável “achou”, indicando se foi possível ou não achar um caminho dentro do tabuleiro. Veja agora o código da função “posicaoVazia()”, utilizado para verificar se uma determinada posição pode ser usada em um caminho dentro do tabuleiro do labirinto:

Basicamente, o que essa função faz é verificar se a posição linha e coluna passada como parâmetro está dentro do tabuleiro e se está vazia, podendo ser utilizada em um labirinto. Para esse código poder ser utilizado, precisamos chamá-lo no final do corpo da função “main()”, adicionando os seguintes comandos:

Esse código chamará a função “procurarCaminho()” a partir da linha e coluna inicial. Lembre-se que essa função vai percorrendo o tabuleiro, marcando o caminho encontrado com os caracteres ‘.’, os caminhos que não levaram a nada preenche-se com ‘x’ e imprime-se o tabuleiro cada vez que ele é modificado. Um possível tabuleiro final é o seguinte:

As posições do tabuleiro preenchidas com ‘x’ indicam posições não percorridas. Já os pontos seguem da posição de início ‘I’ até a posição de destino ‘D’. Note que o caminho não é ótimo, ele vai tentando na sorte. Algoritmos mais inteligentes poderiam ser utilizados para encontrar o caminho ótimo, mas isso está fora do escopo desta aula.

Além disso, podemos ter saídas como a mostrada a seguir, onde não há caminho válido:

Para ficar mais fácil de entender o caminho percorrido pelo algoritmo, você pode adicionar o seguinte código ao final da função “imprimir”. Esse código é responsável por suspender a execução do programa pelo tempo indicado em “milissegundos” (no caso, 300ms).

O bloco try-catch recupera exceções que ocorram na chamada de uma função. A função printStackTrace() retorna a lista de erros que foram gerados a partir de uma exceção. Os detalhes sobre esses dois elementos serão estudados em Programação Orientada a Objetos. Por enquanto, basta lembrar de colocá-los quando o programa solicitar!