2. Primeiros caminhos: caminhando em linha reta

Retorne ao exemplo que gerou a necessidade de uma nova técnica de IA para o personagem. Mas simplifique o cenário, deixando-o discreto… você não quer torná-lo tímido. O objetivo aqui é transformar o espaço de representação do jogo em uma malha (grid) de células, como em uma tabela. Assim, o espaço deixaria de ser “contínuo” (sem interrupções) e passaria a ser “discreto” (com posições separadas em intervalos regulares). A Figura 02 ilustra como seria o cenário da Figura 01, mas “discretizado”.

Com certeza você já viu muitos jogos cujos cenários são definidos em malhas regulares, como o apresentado na Figura 02. Na verdade, a maioria dos jogos simplificam a representação contínua do espaço em intervalos regulares. Essa simplificação é útil desde jogos puzzles a jogos de RPG. Então, adote também essa simplificação nos seus algoritmos de planejamento de deslocamento dos personagens.

Comece do básico! Ensine o seu personagem a planejar seu deslocamento de um ponto ao outro da malha regular do cenário, mas sem obstáculos!

Se o personagem deseja alcançar uma posição, como ele se encontra em uma malha, não dá para simplesmente ir em linha reta, como se fosse um espaço contínuo. É necessário, em uma das células da malha, alterar a rota gerando uma quebra de direção, como ilustrado na Figura 03.

Na figura, a seta verde representa o caminho desejado pelo personagem e a seta vermelha representa um possível caminho dele.

Na verdade, você deve perguntar: quando o personagem saberá qual o “melhor caminho”? Por um momento, pode-se dizer que o “melhor caminho” é aquele que gera menor distância de deslocamento. Você verá que há diferentes formas de calcular a “distância” entre dois pontos, mas, por enquanto, assuma que essa distância é fruto do número de células visitadas no deslocamento de um ponto ao outro. E que também o personagem só pode se mover para as células adjacentes horizontais e verticais (as diagonais, não). Quando se usa essas convenções para representar as distâncias, você estará utilizando a Distância de Manhattan.

Considerando o cálculo do melhor caminho realizado através da Distância de Manhattan, veja a Figura 05.

Todos os caminhos representados nessa figura, bem como muitos outros, são caminhos igualmente bons. Pode-se dizer, então que, todos eles são os “melhores caminhos”, pois possuem o número mínimo de deslocamentos a células adjacentes, seja na horizontal ou na vertical.

Se todos são igualmente bons, qual deles o personagem deve adotar?

Uma boa estratégia é usar o que você considera mais “natural”. Em geral, considera-se mais “natural” um ajuste gradual no caminho trilhado, como a sequência de células na rota amarela da Figura 05. Para isso, adote um algoritmo concebido inicialmente para desenhar linhas retas nas telas dos computadores chamado de Algoritmo de Bresenham.

Saiba Mais

Desenvolvido por Jack Elton Bresenham em 1962, na IBM, o algoritmo da linha de Bresenham é responsável por desenhar linhas em uma tela de computador. Ele é um dos primeiros algoritmos descobertos no campo da computação gráfica. Devido à velocidade e simplicidade, ele é implementado em vários hardwares, como plotters e placas gráficas modernas. Atualmente, o nome "Bresenham" é usado para toda uma família de algoritmos estendidos ou modificados do original.

Fonte: IT HISTORY SOCIETY. Dr. Jack Elton Bresenham. Disponível em: <https://www.ithistory.org/honor-roll/dr-jack-elton-bresenham>. Acesso em: 18 maio 2018 (Traduzido e adaptado).

Para mais informações, acesse aqui.