Navegação e descoberta de caminhos

Quem vê os jogos de hoje, com NPCs indo de um lado para o outro, não sabe o quanto é complexo para eles realizarem tarefas que, para nós, são triviais. Uma delas é o deslocamento nos mundos virtuais. Como no exemplo que foi citado na apresentação da disciplina, do pobre cavalo tentando atravessar o chão. Agora, irei apresentar outro, dessa vez, sem esse problema.

Só para ter uma ideia, imagine um jogo com muitos NPCs ao mesmo tempo, como os jogos de Estratégia em tempo real (ou RTS – Real-Time Strategy). Posso citar as séries StarCraft, Age of Empires, Age of Mythology, Total War e os sucessos League of Legends e DOTA (bem, esses últimos são chamados de MOBA – Multiplayer Online Battle Arena, que é, na verdade, uma subcategoria dos jogos RTS). Como ilustração, usarei um jogo menos conhecido chamado 0 A.D., que você pode jogar enquanto estuda. Como se trata de um jogo livre e de código aberto, é permitido baixar sem a preocupação de estar usando um jogo pirata! Como desenvolvedor de jogos, você deve se preocupar com esses piratas que não valorizam o seu trabalho, não é mesmo?

A Figura 09 apresenta uma captura de tela desse jogo. Nela, é possível observar tropas de duas equipes se enfrentando e também identificar um problema clássico de navegação com vários NPCs: passagens mais estreitas do que a formação da tropa gerando uma confusão no início da passagem. Por esse problema, muitas vezes, vemos NPCs “rodando” de um lado para o outro sem saber para onde ir por seu caminho estar bloqueado. A movimentação de uma tropa humana não faria isso. O guerreiro que ficasse rodando no mesmo ponto seria considerado maluco e, possivelmente, ganharia uma dispensa no próximo ataque. Se bem que, numa guerra, é bem possível que esses considerados malucos ganhem é uma promoção.

Há inúmeras formas de resolver os problemas de movimentação que foram citados. As mais utilizadas são a utilização de algoritmos de descoberta de caminhos (ou pathfinding) e a de comportamentos de navegação (ou steering behaviors). Para a primeira, é necessário ter um “mapa” do ambiente por onde os NPCs irão se deslocar. Com o mapa, utilizam-se algoritmos de busca para achar o menor caminho entre a localização atual do NPC e a localização para onde ele quer ir. Claro, alguém com “inteligência” usaria o menor caminho.

Veja, por exemplo, a Figura 10, nela está o mapa onde o NPC deverá encontrar o melhor caminho entre sua localização (origem) e onde ele quer ir (destino).

Mesmo sabendo qual é o menor caminho entre a origem e o destino, você deverá instruir o computador a calculá-lo. Mas como isso poderá ser feito?

Uma opção para o cálculo é o NPC testar todos os caminhos possíveis e, com isso, achar qual o menor deles. Entretanto, lembre-se de que um jogo normalmente requer tempo rápido de resposta, uma vez que precisa gerar cerca de 30 quadros por segundo. Ou seja, o NPC precisa verificar todas as possibilidades de caminho para calcular seu percurso ótimo em menos de 0,03 segundos. Enfatizando que estou deixando de lado o tempo de renderização do jogo, que também é alto. Se o cálculo levar mais tempo do que isso, você terá lag no jogo e vários jogadores reclamando (falando mal de você). Então, se o cenário for pequeno e se o jogo apresentar um ou dois NPCs, talvez nem percebam lag. Mas se o cenário for grande e/ou tiver uma quantidade grande de NPCs, como os apresentados na Figura 09, vai precisar de uma boa otimização nas técnicas de descoberta de caminhos para que não haja nenhuma reclamação. Até aqui, tudo bem? Então, prepare-se para aprender como fazer isso ainda nessa disciplina!