Algoritmo de Pledge

Novamente, pensou que o seu algoritmo era bom o suficiente para escapar do labirinto e novamente, o seu buggle está agora num labirinto onde o seu algoritmo anterior falhou. Dê-lhe uma hipótese: copie-e-cole o seu código e aperte o botão "Executar" e veja a sua criação falhar. A armadilha é no formato de um "G" maiúsculo. O buggle entra na armadilha e segue a borda interior. Num determinado momento, encontra a direção norte livre, vai nesta direção e cai de novo na armadilha.

O algoritmo de Pledge (em homenagem a Jon Pledge of Exeter) pode resolver este labirinto.

Este algoritmo é uma modificação do anterior para evitar obstáculos. Escolhe aleatoriamente uma direção e deixe o buggle ir nesta direção. Quando encontra um obstáculo, uma pata (por exemplo, a da esquerda) é mantida na parede a seguir o obstáculo enquanto conta as curvas. Quando o buggle está de volta à direção original dele e a soma das curvas deu 0, o buggle deixa o obstáculo e continua a manter a direção original dele.

Observe que o uso de "total turning" ao invés de simplesmente o "current direction" permite que o algoritmo evite armadilhas no formato G. Se alguém escolhe a esquerda para dentro da armadilha acaba a girar 260 graus pelas paredes. Como dissemos antes, o algoritmo simplório "current direction" entra num ciclo limitado à medida que deixa a parede mais à direita a apontar para a esquerda e anda para a secção curvada na esquerda de novo.

O algoritmo de Pledge não deixa a parede mais à direita devido ao total de curvas não ser zero neste ponto. Segue a parede na volta toda, a deixa-o finalmente a apontar para a esquerda no "fundo exterior"

Objetivo do exercício

Agora tem que modificar a sua solução para implementar o algoritmo de Pledge para escapar deste labirinto.

Mude o seu método keepHandOnSideWall() para contar a quantidade de curvas feitas pelo buggle (+1 quando gira para a esquerda e -1 quando gira para a direita). Esta contagem pode necessitar a adição de um valor inteiro angleSum no seu programa.

Escreva um método booleano isDirectionFree(dir) a indicar se a direção dada está livre, ou seja, se pode mover naquela direção (Observe que a demonstração usa a direção NORTH para isto). Pode recuperar a direção atual do buggle a usar o método getDirection(). Pode mudar a sua direção (sem se mover) a usar setDirection(dir). Não se esqueça de guardar a direção anterior do seu buggle (numa variável exclusiva) antes de verificar se a sua direção favorita está livre para depois recuperar o seu estado.

Também pode ter que mudar o resto do seu código, mas estas mudanças podiam ser poucas.

[!python]

Não se esqueça que se tem um método que modifica uma variável global (como angleSum), deve garantir que declara esta variável como global. Sem ele, o método cria uma variável de mesmo nome e a global nunca é modificada.

def myMethod():
  global angleSum
  ...
  angleSum = angleSum + 1
[/!]
Deve ajustar a sua direção para a sua favorita (NORTH é a recomendada). Então, deve escrever o loop principal algoritmo. Em outras palavras, enquanto o seu buggle não encontra o biscoito dele, tem que mover para a frente até ao próximo obstáculo na sua direção favorita. Então, ponha uma pata na parede (a usar keepHandOnSideWall()) enquanto a soma de curvas não for null (nula) e a direção favorita não estiver livre. Faça-o até que encontre o seu baggle.