Exploring a Maze

4.11. Explorando um Labirinto¶

Nesta seção, veremos um problema que tem relevância para o mundo da robótica que está em rápida expansão: como você encontra o caminho para sair de um labirinto? Se você tem um aspirador de pó Roomba para limpar o seu dormitório (como todos estudantes universitários?) você vai querer poder reprogramá-lo usando o que você aprender nesta seção. O problema que queremos resolver é ajudar a nossa tartaruga a encontrar a saída de um labirinto virtual. O problema do labirinto tem raízes tão profundas quanto o mito grego sobre Teseu, que foi enviado a um labirinto para matar o minotauro. Teseu usou uma bola de linha para ajudá-lo a encontrar o caminho de volta depois de matar a fera. Em nosso problema, vamos supor que nossa tartaruga é largada em algum lugar no meio do labirinto e deve encontrar a saída. Veja a Figura 2 para ter uma ideia do que faremos nesta seção.

Figura 2: O Final do Programa de Busca da Saída do Labirinto¶

Para simplificar o problema, vamos supor que o nosso labirinto é dividido em “Quadrados”. Cada quadrado do labirinto é aberto ou ocupado por uma parede. A tartaruga só pode passar pelos quadrados abertos do labirinto. Se a tartaruga se chocar contra uma parede, ela deve tentar uma outra direção. A tartaruga vai exigir um procedimento sistemático para encontrar uma saída do labirinto. Aqui está o procedimento:

Da nossa posição inicial, vamos primeiro tentar ir para o norte de um quadrado e depois recursivamente tentar o nosso procedimento a partir daí.
Se não formos bem sucedidos, tentando um caminho pelo Norte como o primeiro passo, então vamos dar um passo para o sul e repetir nosso procedimento recursivamente.
Se pelo sul não funcionar, então tentaremos dar um passo para o oeste e aplicar recursivamente o nosso procedimento.
Se pelo norte, sul e oeste não acharmos um caminho até uma saída, então vamos aplicar o procedimento recursivamente a partir de um passo para o leste.
Se nenhuma dessas direções funcionar, então não há como sair do labirinto e nós falhamos.

Agora, isso parece muito fácil, mas há alguns detalhes que devemos mencionar. Suponha que nosso primeiro passo recursivo foi para o norte. Seguindo nosso procedimento, nosso próximo passo também seria para o norte. Mas se o norte estiver bloqueado por uma parede, devemos olhar para o próximo passo do procedimento e tentar ir para o sul. Infelizmente esse passo para o o sul nos traz de volta ao nosso ponto de partida original. Se aplicarmos o procedimento recursivo a partir daí vamos apenas voltar um passo para o norte e entrar em um loop infinito. Então, devemos ter uma estratégia para que possamos lembrar das posições onde já estivemos. Neste caso, vamos supor que temos um saco de migalhas de pão que podemos deixar cair ao longo do nosso caminho. Se dermos um passo em uma certa direção e acharmos uma migalha de pão no quadrado, sabemos que devemos voltar imediatamente e tentar a próxima direção em nosso procedimento. Como veremos no código deste algoritmo, a volta é tão simples como retornar de uma chamada de função recursiva.

Como fazemos para todos os algoritmos recursivos, vamos revisar os casos base. Alguns deles você pode já ter adivinhado com base na descrição dada no parágrafo anterior. Nesse algoritmo, há quatro casos base a serem considerados:

A tartaruga bateu em uma parede. Como o quadrado é ocupado por uma parede, não é possível seguir nessa direção.
A tartaruga encontrou um quadrado que já foi explorado. Não queremos continuar explorando a partir desta posição para não entraremos em loop.
Nós encontramos uma borda externa, não ocupada por uma parede. Em outras palavras, encontramos uma saída do labirinto.
Nós exploramos um quadrado em todas as quatro direções sem sucesso.

Para que o nosso programa funcione, precisamos ter uma maneira de representar o labirinto. Para tornar isso ainda mais interessante, vamos usar o módulo turtle para desenhar e explorar o nosso labirinto para que possamos assistir o algoritmo em ação. O objeto maze (labirinto) fornecerá os seguintes métodos para usarmos no nosso algoritmo de busca:

__init__ lê um arquivo com um labirinto, inicializa a representação interna do labirinto, e define a posição inicial da tartaruga.
drawMaze desenha o labirinto em uma janela na tela.
updatePosition atualiza a representação interna do labirinto e altera a posição da tartaruga na janela.
isExit verifica se a posição atual é uma saída do labirinto.

A classe Maze também sobrescreve o operador de indexação [] para que nosso algoritmo possa acessar facilmente o estado de qualquer quadrado em particular.

Vamos examinar o código da função de procura que chamamos searchFrom. O código é mostrado na Listagem 3. Note que esta função recebe três parâmetros: um objeto labirinto, a linha inicial e a coluna inicial. Isto é importante pois, como função recursiva, a busca começa novamente com cada chamada recursiva.

Listagem 3

def searchFrom(maze, startRow, startColumn):
    maze.updatePosition(startRow, startColumn)
   #  Check for base cases:
   #  1. We have run into an obstacle, return false
   if maze[startRow][startColumn] == OBSTACLE :
        return False
    #  2. We have found a square that has already been explored
    if maze[startRow][startColumn] == TRIED:
        return False
    # 3. Success, an outside edge not occupied by an obstacle
    if maze.isExit(startRow,startColumn):
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
        return True
    maze.updatePosition(startRow, startColumn, TRIED)

    # Otherwise, use logical short circuiting to try each
    # direction in turn (if needed)
    found = searchFrom(maze, startRow-1, startColumn) or \
            searchFrom(maze, startRow+1, startColumn) or \
            searchFrom(maze, startRow, startColumn-1) or \
            searchFrom(maze, startRow, startColumn+1)
    if found:
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
    else:
        maze.updatePosition(startRow, startColumn, DEAD_END)
    return found

Olhando o algoritmo, você verá que a primeira coisa que o código faz (linha 2) é chamar o método updatePosition. Isto serve para ajudar você a visualizar o algoritmo para que você possa assistir exatamente como a tartaruga explora seus caminhos no labirinto. Em seguida, o algoritmo verifica os primeiros três dos quatro casos base: A tartaruga bateu numa parede (linha 5)? A tartaruga voltou para um quadrado já explorado (linha 8)? A tartaruga encontrou uma saída (linha 11)? Se nenhuma dessas condições for verdadeira então continuamos a busca recursivamente.

Você vai notar que na etapa recursiva há quatro chamadas para searchFrom. É difícil prever quantas dessas chamadas recursivas serão usadas já que todas elas são conectadas por operadores lógicos or. Se a primeira chamada para searchFrom retornar True então não é necessário fazer nenhuma das três últimas chamadas. Isso significa que um passo para (row-1, column) (ou norte se você quiser pensar geograficamente) está no caminho que leva para fora do labirinto. Se não houver um caminho pelo norte para fora do labirinto, a próxima chamada recursiva é tentada, neste caso para o sul. Se essa chamada falhar, tenta-se pelo oeste e finalmente pelo leste. Se todas as quatro chamadas recursivas falharem, então encontramos um beco sem saída. Você pode baixar ou digitar todo o programa e investigar o que ocorre quando a ordem dessas chamadas é alterada.

O código para a classe Maze (labirinto) é mostrado na Listagem 4, Listagem 5, e Listagem 6. O método __init__ recebe o nome de um arquivo como seu único parâmetro. Este é um arquivo de texto que representa um labirinto usando o caractere “+” para paredes, espaço para quadrados abertos e a letra “S” para indicar a posição inicial. A Figura 3 mostra um exemplo de arquivo com um labirinto. Internamente um labirinto é representado por uma lista de listas. Cada linha da variável mazelist também é uma lista. Esta lista secundária contém um caractere por quadrado usando os caracteres descritos acima. Para o arquivo da Figura 3 a representação interna seria parecida com:

[ ['+','+','+','+',...,'+','+','+','+','+','+','+'],
  ['+',' ',' ',' ',...,' ',' ',' ','+',' ',' ',' '],
  ['+',' ','+',' ',...,'+','+',' ','+',' ','+','+'],
  ['+',' ','+',' ',...,' ',' ',' ','+',' ','+','+'],
  ['+','+','+',' ',...,'+','+',' ','+',' ',' ','+'],
  ['+',' ',' ',' ',...,'+','+',' ',' ',' ',' ','+'],
  ['+','+','+','+',...,'+','+','+','+','+',' ','+'],
  ['+',' ',' ',' ',...,'+','+',' ',' ','+',' ','+'],
  ['+',' ','+','+',...,' ',' ','+',' ',' ',' ','+'],
  ['+',' ',' ',' ',...,' ',' ','+',' ','+','+','+'],
  ['+','+','+','+',...,'+','+','+',' ','+','+','+']]

O método drawMaze usa esta representação interna para desenhar o labirinto inicial na tela.

Figura 3: Um Exemplo de Arquivo com um Labirinto

++++++++++++++++++++++
+   +   ++ ++     +
+ +   +       +++ + ++
+ + +  ++  ++++   + ++
+++ ++++++    +++ +  +
+          ++  ++    +
+++++ ++++++   +++++ +
+     +   +++++++  + +
+ +++++++      S +   +
+                + +++
++++++++++++++++++ +++

O método updatePosition (atualiza posição), como mostrado na Listagem 5, usa a mesma representação interna para ver se a tartaruga bateu em uma parede. Também atualiza a representação interna com um “.” ou “-” para indicar que a tartaruga já visitou um determinado quadrado ou se o quadrado faz parte de um beco sem saída. Além disso, o método updatePosition usa dois métodos auxiliares, moveTurtle (move tartaruga) e dropBreadCrumb (joga migalha), para atualizar a exibição na tela.

Finalmente, o método isExit (é saída) usa a posição atual da tartaruga para testar uma condição de saída. Uma condição de saída é verdadeira quando a tartaruga alcança uma borda do labirinto, como a linha ou coluna zero, ou a última linha (mais inferior) ou última coluna (extrema direita).

Listagem 4

class Maze:
    def __init__(self,mazeFileName):
        rowsInMaze = 0
        columnsInMaze = 0
        self.mazelist = []
        mazeFile = open(mazeFileName,'r')
        rowsInMaze = 0
        for line in mazeFile:
            rowList = []
            col = 0
            for ch in line[:-1]:
                rowList.append(ch)
                if ch == 'S':
                    self.startRow = rowsInMaze
                    self.startCol = col
                col = col + 1
            rowsInMaze = rowsInMaze + 1
            self.mazelist.append(rowList)
            columnsInMaze = len(rowList)

        self.rowsInMaze = rowsInMaze
        self.columnsInMaze = columnsInMaze
        self.xTranslate = -columnsInMaze/2
        self.yTranslate = rowsInMaze/2
        self.t = Turtle(shape='turtle')
        setup(width=600,height=600)
        setworldcoordinates(-(columnsInMaze-1)/2-.5,
                            -(rowsInMaze-1)/2-.5,
                            (columnsInMaze-1)/2+.5,
                            (rowsInMaze-1)/2+.5)

Listagem 5

def drawMaze(self):
    for y in range(self.rowsInMaze):
        for x in range(self.columnsInMaze):
            if self.mazelist[y][x] == OBSTACLE:
                self.drawCenteredBox(x+self.xTranslate,
                                     -y+self.yTranslate,
                                     'tan')
    self.t.color('black','blue')

def drawCenteredBox(self,x,y,color):
    tracer(0)
    self.t.up()
    self.t.goto(x-.5,y-.5)
    self.t.color('black',color)
    self.t.setheading(90)
    self.t.down()
    self.t.begin_fill()
    for i in range(4):
        self.t.forward(1)
        self.t.right(90)
    self.t.end_fill()
    update()
    tracer(1)

def moveTurtle(self,x,y):
    self.t.up()
    self.t.setheading(self.t.towards(x+self.xTranslate,
                                     -y+self.yTranslate))
    self.t.goto(x+self.xTranslate,-y+self.yTranslate)

def dropBreadcrumb(self,color):
    self.t.dot(color)

def updatePosition(self,row,col,val=None):
    if val:
        self.mazelist[row][col] = val
    self.moveTurtle(col,row)

    if val == PART_OF_PATH:
        color = 'green'
    elif val == OBSTACLE:
        color = 'red'
    elif val == TRIED:
        color = 'black'
    elif val == DEAD_END:
        color = 'red'
    else:
        color = None

    if color:
        self.dropBreadcrumb(color)

Listagem 6

def isExit(self,row,col):
     return (row == 0 or
             row == self.rowsInMaze-1 or
             col == 0 or
             col == self.columnsInMaze-1 )

def __getitem__(self,idx):
     return self.mazelist[idx]

O programa completo é mostrado no ActiveCode 1. Este programa usa o arquivo de dados maze2.txt mostrado abaixo. Note que esse exemplo é muito mais simples pois a saída é muito próxima da posição inicial da tartaruga.

++++++++++++++++++++++
+   +   ++ ++        +
      +     ++++++++++
+ +    ++  ++++ +++ ++
+ +   + + ++    +++  +
+          ++  ++  + +
+++++ + +      ++  + +
+++++ +++  + +  ++   +
+          + + S+ +  +
+++++ +  + + +     + +
++++++++++++++++++++++

import turtle

PART_OF_PATH = 'O'
TRIED = '.'
OBSTACLE = '+'
DEAD_END = '-'

class Maze:
    def __init__(self,mazeFileName):
        rowsInMaze = 0
        columnsInMaze = 0
        self.mazelist = []
        mazeFile = open(mazeFileName,'r')
        rowsInMaze = 0
        for line in mazeFile:
            rowList = []
            col = 0
            for ch in line[:-1]:
                rowList.append(ch)
                if ch == 'S':
                    self.startRow = rowsInMaze
                    self.startCol = col
                col = col + 1
            rowsInMaze = rowsInMaze + 1
            self.mazelist.append(rowList)
            columnsInMaze = len(rowList)

self.rowsInMaze = rowsInMaze
        self.columnsInMaze = columnsInMaze
        self.xTranslate = -columnsInMaze/2
        self.yTranslate = rowsInMaze/2
        self.t = turtle.Turtle()
        self.t.shape('turtle')
        self.wn = turtle.Screen()
        self.wn.setworldcoordinates(-(columnsInMaze-1)/2-.5,-(rowsInMaze-1)/2-.5,(columnsInMaze-1)/2+.5,(rowsInMaze-1)/2+.5)

def drawMaze(self):
        self.t.speed(10)
        self.wn.tracer(0)
        for y in range(self.rowsInMaze):
            for x in range(self.columnsInMaze):
                if self.mazelist[y][x] == OBSTACLE:
                    self.drawCenteredBox(x+self.xTranslate,-y+self.yTranslate,'orange')
        self.t.color('black')
        self.t.fillcolor('blue')
        self.wn.update()
        self.wn.tracer(1)

def drawCenteredBox(self,x,y,color):
        self.t.up()
        self.t.goto(x-.5,y-.5)
        self.t.color(color)
        self.t.fillcolor(color)
        self.t.setheading(90)
        self.t.down()
        self.t.begin_fill()
        for i in range(4):
            self.t.forward(1)
            self.t.right(90)
        self.t.end_fill()

def moveTurtle(self,x,y):
        self.t.up()
        self.t.setheading(self.t.towards(x+self.xTranslate,-y+self.yTranslate))
        self.t.goto(x+self.xTranslate,-y+self.yTranslate)

def dropBreadcrumb(self,color):
        self.t.dot(10,color)

def updatePosition(self,row,col,val=None):
        if val:
            self.mazelist[row][col] = val
        self.moveTurtle(col,row)

if val == PART_OF_PATH:
            color = 'green'
        elif val == OBSTACLE:
            color = 'red'
        elif val == TRIED:
            color = 'black'
        elif val == DEAD_END:
            color = 'red'
        else:
            color = None

if color:
            self.dropBreadcrumb(color)

def isExit(self,row,col):
        return (row == 0 or
                row == self.rowsInMaze-1 or
                col == 0 or
                col == self.columnsInMaze-1 )

def __getitem__(self,idx):
        return self.mazelist[idx]

def searchFrom(maze, startRow, startColumn):
    # try each of four directions from this point until we find a way out.
    # base Case return values:
    #  1. We have run into an obstacle, return false
    maze.updatePosition(startRow, startColumn)
    if maze[startRow][startColumn] == OBSTACLE :
        return False
    #  2. We have found a square that has already been explored
    if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END:
        return False
    # 3. We have found an outside edge not occupied by an obstacle
    if maze.isExit(startRow,startColumn):
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
        return True
    maze.updatePosition(startRow, startColumn, TRIED)
    # Otherwise, use logical short circuiting to try each direction
    # in turn (if needed)
    found = searchFrom(maze, startRow-1, startColumn) or \
            searchFrom(maze, startRow+1, startColumn) or \
            searchFrom(maze, startRow, startColumn-1) or \
            searchFrom(maze, startRow, startColumn+1)
    if found:
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
    else:
        maze.updatePosition(startRow, startColumn, DEAD_END)
    return found

myMaze = Maze('maze2.txt')
myMaze.drawMaze()
myMaze.updatePosition(myMaze.startRow,myMaze.startCol)

searchFrom(myMaze, myMaze.startRow, myMaze.startCol)

Auto Avaliação

Modifique o programa de procura no labirinto para que as chamadas para searchFrom estejam em uma ordem diferente. Veja o programa sendo executado. Você pode explicar porque o comportamento é diferente? Você pode prever qual caminho a tartaruga seguirá dada uma ordem determinada?

Next Section - 4.12. Dynamic Programming