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:

private static final char CAMINHO = '.';

private static final char SEM_SAIDA = 'x';

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:

public static boolean procurarCaminho(int linhaAtual, int colunaAtual) { 

    int proxLinha; 

    int proxColuna; 

    boolean achou = false; 

    // tenta subir 

    proxLinha = linhaAtual - 1; 

    proxColuna = colunaAtual; 

    achou = tentarCaminho(proxLinha, proxColuna); 

    // tenta descer 

    if (!achou) { 

        proxLinha = linhaAtual + 1; 

        proxColuna = colunaAtual; 

        achou = tentarCaminho(proxLinha, proxColuna); 

    } 

    // tenta à esquerda 

    if (!achou) { 

        proxLinha = linhaAtual; 

        proxColuna = colunaAtual - 1; 

        achou = tentarCaminho(proxLinha, proxColuna); 

    } 

    // tenta à direita 

    if (!achou) { 

        proxLinha = linhaAtual; 

        proxColuna = colunaAtual + 1; 

        achou = tentarCaminho(proxLinha, proxColuna); 

    } 

    return achou; 

}

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.

private static boolean tentarCaminho(int proxLinha, int proxColuna) { 

    boolean achou = false; 

    if (tabuleiro[proxLinha][proxColuna] == DESTINO) { 

        achou = true; 

    } else if (posicaoVazia(proxLinha, proxColuna)) { 

        // marcar 

        tabuleiro[proxLinha][proxColuna] = CAMINHO; 

        imprimir(); 

        achou = procurarCaminho(proxLinha, proxColuna); 

        if (!achou) { 

            tabuleiro[proxLinha][proxColuna] = SEM_SAIDA; 

            imprimir(); 

        } 

    } 

    return achou; 

}

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:

tabuleiro[proxLinha][proxColuna] = CAMINHO;

imprimir();

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:

achou = procurarCaminho(proxLinha, proxColuna);

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:

if (!achou) {

    tabuleiro[proxLinha][proxColuna] = SEM_SAIDA;

    imprimir();

}

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:

public static boolean posicaoVazia(int linha, int coluna) { 

    boolean vazio = false; 

    if (linha >= 0 && coluna >= 0 && linha < TAMANHO && coluna < TAMANHO) { 

        vazio = (tabuleiro[linha][coluna] == VAZIO); 

    } 

    return vazio; 

}

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:

System.out.println("\n- Procurando solução -\n"); 

    boolean achou = procurarCaminho(linhaInicio, colunaInicio); 

    if (achou) { 

        System.out.println("ACHOU O CAMINHO!"); 

    } else { 

        System.out.println("Não tem caminho!"); 

}

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).

try {

    Thread.sleep(300);

} catch (InterruptedException e) {

    e.printStackTrace();

}

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!