1 - Caminhos pelo mapa

Bom, antes de mais nada, deixe-me preparar um cenário para você! Vou abandonar um pouco o grafo do RN (talvez ele seja citado em menção honrosa), e você vai trabalhar em um mapa que parece um pouco mais com o cenário de um jogo. Que rufem os tambores!

Eis que lhes apresento... a Figura 01!

Ehr... é que ficou tão bonito que eu não tive coragem de fazer outro (gulp!).

O que você tem aqui é um mapa em forma de malha - ou grid, que representará um cenário de um jogo. Os asteroides (esses quadrados com objetos em cinza) representam obstáculos que não permitem a passagem do jogador (o Patrulheiro Estelar), e a nave é o objetivo final que ele deseja alcançar. O personagem pode se mover nas oito direções, e o custo de se movimentar na vertical e horizontal é igual ao custo de mover nas diagonais (considere todos os custos unitários).

Você deve estar se perguntando: aqueles algoritmos da aula passada já não serviriam para encontrar um caminho nesse mapa?

Claro que sim! Pode não ser o melhor caminho possível, mas será um caminho, sem dúvidas. Que tal utilizar um deles como exemplo de como esse mapa seria representado por um grafo, deixando a base prontinha para o estudo dos próximos algoritmos? Parece uma boa ideia.

Antes de começar, eu tenho uma confissão a fazer: eu deixei uma parte de fora da outra aula. Sabe como é, já tinha tanta coisa que fiquei com medo de embananar você. Lembra que na aula passada a escolha do próximo vértice foi meio aleatória? Não que não possa ser feito dessa forma, mas normalmente existe um critério para escolher quem será o próximo vizinho a ser explorado. Por exemplo, eu poderia ter estabelecido que o primeiro vértice a ser visitado fosse aquele cujo preço da passagem fosse mais barata. Não faria mal ao bolso, hein?

Essa estratégia de escolha do próximo vértice tem um nome lindo de doer: heurística.A heurística do algoritmo refere-se ao processo ou estratégia utilizada para tomar determinadas decisões em sua execução.

Então, que tal ilustrar no mapa acima como funcionaria uma DFS utilizando algumas heurísticas? Prepare o coração, que serão alguns passos de simulação!

Se rimou, é verdade. Considerando o mapa acima, uma primeira heurística que você poderia utilizar seria a distância de Manhattan (lembra da bichinha?). Ela seria uma boa heurística caso o movimento só pudesse ser realizado nas quatro direções. Na distância de Manhattan, o cálculo do valor da heurística seria a soma de quantos blocos faltam, na vertical e na horizontal, para chegar ao objetivo. Logo a distância de cada bloco para o objetivo seria dada por:

Distância = |posição_atual.x - destino.x| + |posição_atual.y - destino.y|

Mas eu gosto mesmo é de jogo com movimento nas oito! Quem não ama uma diagonal? Para esse tipo de cenário, existe uma heurística similar, a distância diagonal: será uma medição parecida com a distância de Manhattan, mas você terá de levar em conta os blocos na diagonal também, ok? Nesse caso, a conta fica um pouquinho mais simplificada:

Distância = MAIOR (|posição_atual.x - destino.x|, |posição_atual.y - destino.y|)

Onde MAIOR retorna o maior valor entre os dois existentes nos parênteses, no caso quantos quadrados faltam na horizontal e na vertical. Essa simplificação está levando em conta a possibilidade de o personagem dar o passo na diagonal, o que reduz muitas vezes o custo da distância comparado com a fórmula de Manhattan.

Uma outra heurística que é bastante utilizada é a distância Euclidiana. Nela você utiliza o teorema de Pitágoras para descobrir qual seria a distância em linha reta do ponto do mapa até o ponto de destino. Essa heurística é mais utilizada quando se tem um mapa contínuo, que não segue o padrão do grid, e onde os custos de movimentação podem ser mais variados:

Distância = RAIZ_QUADRADA (|posição_atual.x - destino.x|² + |posição atual.y - destino.y|²)

Que tal uma simulação de uma DFS usando a heurística de distância diagonal?

1.1 - Ponto Inicial

Calcule o custo de mover para cada um dos quadrados vizinhos usando a heurística da distância diagonal. Os referenciais são o patrulheiro estelar e a nave. Como é a primeira vez, vou explicitar as contas para você. Se você contar as linhas e as colunas, vai observar que:

O patrulheiro estelar está na posição (4,1)
A nave está na posição (4,8)

Os vizinhos do patrulheiro estelar são os blocos que representam as posições (3,1), (3,2), (4,2), (5,2) e (5,1). Aplicando a heurística você vai ter:

D(3,1) = MAIOR(|3-4|, |1-8|) = MAIOR(1, 7) = 7
D(3,2) = MAIOR(|3-4|, |2-8|) = MAIOR(1, 6) = 6
D(4,2) = MAIOR(|4-4|, |2-8|) = MAIOR(0, 6) = 6
D(5,1) = MAIOR(|5-4|, |1-8|) = MAIOR(1, 7) = 7
D(5,2) = MAIOR(|5-4|, |2-8|) = MAIOR(1, 6) = 6

Aqui você tem um empate entre várias casas, como vai ser o desempate? Você escolhe o critério. Você pode utilizar o seguinte: em caso de empate, avança primeiro para o vizinho que só muda em uma direção (vertical ou horizontal), para depois ir para o vizinho que altera as duas. É mais uma decisão que foi colocada no algoritmo, logo faz parte da heurística, mas não tem nenhum motivo especial para essa decisão. É só a ideia de tentar ir direto para o objetivo o mais rápido possível.

Seguindo a heurística, dê um passo para a frente (lembra do desempate? Vá reto para só atualizar o valor na horizontal). E, enquanto não chegar no destino, vá repetindo os passos. Lembre-se que na DFS se marcam os nós visitados para evitar que o personagem entre em um ciclo e fique igual a cachorro correndo atrás do próprio rabo! Calculando o valor para os novos vizinhos, você vai ter:

Opa! Bateu de cara com a parede! Continuando com o algoritmo, de acordo com as casas que ainda não foram visitadas.

Ufa, que arrodeio! Mas parece que agora vai.

Chegou!

Então, a DFS consegue sim achar um caminho, mas com certeza dava para ser melhor! O problema é que o algoritmo usa uma heurística de decisão que opera em um nível local: ele só avalia a próxima casa! Como o obstáculo está lá na frente, ele não consegue evitá-lo com antecedência, só quando já está de frente a ele.

Você deve estar se perguntando: mudar a heurística local afeta alguma coisa? Sim! Imagine, por exemplo que o critério de desempate fosse diferente: escolher sempre o vértice mais abaixo, forçando a procura inicial por um caminho na parte inferior do mapa. A sequência de execução levaria a um caminho bem diferente:

O problema é que não dá para ficar adivinhando qual a melhor heurística para cada mapa, principalmente quando os objetos e obstáculos podem mudar de posição em tempo real.

Mas, e se você calcular todos os caminhos possíveis e depois verificar qual é o melhor? Boa! Aí vai dar certo… só que com a BFS/DFS, você vai precisar executar o algoritmo passando por todos os vértices pelo menos uma vez para garantir que achou todos os diferentes caminhos. Isso significa que a operação vai ser MUITO custosa, e em jogos normalmente não existe esse luxo. Tem que rodar rápido, senão o jogador lhe xinga! Imagine se o cenário fosse um pouquinho diferente:

É bem provável que na situação da figura acima, a busca vá primeiro percorrer todos os blocos mais internos dos obstáculos, e só no final consiga achar o caminho que vai por cima!

Por isso, é necessária uma classe de algoritmos que seja capaz de identificar o menor caminho dentro de um mapa (ou grafo) em um tempo de execução que seja aceitável para o jogo. Esse algoritmo é o A* (pronuncia-se A estrela), mas antes de estudá-lo você precisa conhecer o algoritmo base sobre o qual ele é construído: o algoritmo de Dijkstra.