1 - Representando o espaço do jogo como um grafo

Na aula passada, você conheceu o algoritmo de Bresenham, que é ótimo para traçar retas (ou algo bem próximo de uma reta! ) em espaços discretos. O problema é que nem sempre o caminho direto até o objetivo está livre! Às vezes tem um Snorlax dormindo por ali, e você vai ter de pensar em um outro jeito de chegar no próximo ginásio…

Quando você se encontra em um cenário em que é necessário traçar um caminho que desvie de obstáculos ou áreas onde não se pode caminhar (ninguém quer brincar de andar pela lava não é mesmo?), torna-se necessário usar algoritmos mais sofisticados, que entendam que andar por um terreno de grama macia é bem melhor do que andar pelo terreno de pedras pontiagudas. Você precisará de algoritmos que entendem a noção de que um caminho é melhor do que o outro!

Para compreender esses algoritmos, você precisará aprender uma estrutura de dados que facilitará em muito a sua vida: os grafos.

Grafos são uma teoria matemática extremamente rica e complexa, com muitos detalhes, formalismos e teoremas a provar, mas não irei abordar esse lado matemático aqui! O que vai se precisar por enquanto é entender o conceito do grafo e como se pode implementar um no computador, ok?

Em primeiro lugar, o grafo é uma estrutura que representa as informações em função de dois elementos: vértices (ou nós) e arestas. Os vértices normalmente representam um dado ou uma informação, enquanto as arestas representam uma ligação entre esses dados.

Ok, ficou um pouco vago não foi? Dando um exemplo então: imagine que você precisa programar uma viagem pelo estado, e os preços da gasolina, mais infinitos do que a guerra dos Vingadores, estão fazendo as passagens de ônibus ficarem muito caras.

Então para começar seu planejamento, você faz uma lista das cidades do estado (não esqueça das que você quer visitar) e do preço das passagens entre elas. Pronto! Imagino que você chegou em algo como o que é visto na Figura 02.

Que mapa bonito, hein? Perceba que você pode fazer várias análises em cima desse mapa:

• Não existe uma linha direta de Santa Cruz para Pau dos Ferros, quem quiser viajar de um para o outro vai ter de ir primeiro para outra cidade!
• Viajar direto de Natal para Pau dos Ferros (45 reais) é mais barato do que viajar para Mossoró (40) e depois ir para Pau dos Ferros (10);
• Viajar de Natal para Caicó (20 reais) é mais caro do que ir primeiro para Santa Cruz (10) e de lá para Caicó (8).

Agora eu vou contar um segredo... o mapa acima pode ser representado por um grafo! As cidades seriam os vértices, enquanto as retas (que representam as rotas da viagem) seriam as arestas. Mas a aresta especifica mais do que uma ligação entre as cidades: ela também traz o quanto custa ir de uma cidade para a outra. Quando isso ocorre, se diz então que essa aresta tem um peso ou custo de travessia. Existem grafos em que as arestas não têm peso, e normalmente só representam a ligação entre os vértices. Já já explico sobre isso! Primeiro vou colocar aqui um desenho mais clássico do grafo (Figura 03), que representa o mapa (Figura 02) acima:

Um outro conceito que vem dessa estrutura de grafo é a noção de caminho, que nada mais é do que o percurso que você faz de um nó a outro no grafo. Por exemplo, um caminho de Natal para Santa Cruz pode ser construído de várias formas:

• Direto, Natal para Santa Cruz;
• Passando por Caicó, depois Santa Cruz;
• Passando por Mossoró, depois Santa Cruz;
• Passando por Mossoró, depois Caicó, depois Santa Cruz;
• Passando por Pau dos Ferros, Mossoró, Babilônia, Japão…

Deu pra entender? Um caminho é composto pela sequência de vértices que você visita de um ponto A para um ponto B, independentemente se é uma sequência mais direta até o objetivo, ou se você vai arrodear e gastar todo o dinheiro com passagens! Na verdade, a lista acima representa vários caminhos possíveis entre Natal e Santa Cruz (ok, o último não, porque coloquei cidades que não estavam no grafo ). E qualquer caminho desses serve, não é?

Depende. Nesse caso, seria melhor escolher um caminho que gastasse menos dinheiro, não é mesmo? Então o caminho direto, que tem um custo de 10 reais, é melhor do que os outros caminhos, que vão para mais de 30 reais. Quando existe um caminho entre dois pontos cujo custo para percorrer é menor do que os outros, se diz que ele é o menor caminho entre os dois pontos. Se um grafo não possui peso nas arestas, essa noção de menor caminho é diretamente associada com o tamanho do caminho (afinal é tudo igual, então quanto menos arestas percorrer, menor será o caminho!). O mesmo não é verdade quando se tem um grafo com peso nas arestas: o menor caminho pode passar por mais vértices e arestas do que o caminho direto.

Veja por exemplo o caminho entre Natal e Caicó: o caminho direto tem um custo de 20 reais, enquanto o caminho que passa por Santa Cruz custa 10 reais para chegar em Santa Cruz e 8 reais para chegar em Caicó, totalizando 18 reais (dá pra comprar um suco e um salgado na rodoviária!). Dessa forma, o menor caminho nesse caso passa por mais vértices do que o caminho direto.

Porque quando se trabalha com cenários de jogos, principalmente com obstáculos e terrenos, você irá utilizar essa noção! Lembra dessa figura da aula passada?

Pode-se representar esse mapa como um grafo também, seguindo a mesma ideia da aula passada: cada célula (quadrado) do mapa será um vértice do grafo. E as arestas? Serão o custo de movimentação entre os quadrados. Por padrão, ir de um quadrado para o outro custará 1 (a mesma ideia da aula passada).

Mas se você for fazer tudo igual a aula passada, ele não vai traçar uma linha reta do mesmo jeito e ficar preso?

Se tudo tiver 1 como custo, sim! Mas uma estratégia que se pode fazer é atribuir um custo muito grande para os quadrados que contêm as pedras e os que estão em volta deles. Por exemplo, imagine que os quadrados com pedras teriam um custo de um milhão para serem atravessados! Dessa forma, a tendência é que o caminho passe por casas que fazem a volta pelo lado de fora do obstáculo, desviando e permitindo que o personagem chegue ao seu objetivo, que é a nave.

Essa estratégia também pode ser usada em jogos que possuem terrenos distintos. Nesse caso, não há um bloqueio do movimento do personagem, apenas um custo adicional para transpor determinados tipos de terreno (vegetação densa, pântanos, desertos). É comum que uma rota traçada pelo computador leve o personagem por um caminho onde ele possa se movimentar um maior número de casas conservando o máximo de energia, o que significa preferir caminhos em terrenos mais suaves, indo para os terrenos mais árduos apenas quando não há mais opção.

Uma coisa que vale a pena destacar: no grafo do exemplo, estou assumindo que o custo de ir de Natal para Mossoró é igual ao custo de ir de Mossoró para Natal. Ou seja, o grafo é não-direcionado: a aresta serve como mão-dupla, e nosso caminho pode ir e voltar por ela com o mesmo valor. Existem grafos onde as arestas são direcionadas, ou seja, é uma via de uma mão: você pode ir, mas não pode voltar. Nesses casos pode ocorrer de ter um custo para ir do nó A até o nó B, e um custo diferente para ir do nó B até o nó A. Na representação visual, as arestas possuem uma seta indicando a direção do movimento.

Você agora vai ver como se pode implementar os grafos computacionalmente!