Semanário de Desenvolvimento #6
Se eu tivesse de resumir o que fiz na última semana numa palavra ou expressão diria: A*
Relembrando que eu estou a tratar do sistema de movimento de cada unidade que tem de ter em conta dificuldades de terreno, em vez de andar a reinventar a roda vou simplesmente usar um amigo antigo que já me ajudou noutros projectos.
Esse amigo chama-se A* (lê-se "A asterisco", literalmente), e é um algoritmo que encontra soluções óptimas para resolver um problema num certo espaço de estados. Isto é tudo conversa bonita para dizer algo como "encontra o melhor caminho entre A e B". O A* pressupõe que existe algo como uma definição de estado (ou seja, não é anarquista!), transições de estado, custo e heurística.
Um estado pode ser algo tão simples como uma posição numa grelha, definida por X e Y.
As transições descrevem para que estados é que um pode mudar para. Numa grelha poderia ser algo como Cima, Baixo, Esquerda, Direita (ou também incluir diagonais).
O custo representa o valor prático de transição de um estado para outro. Pensemos que em termos de terreno existem uns que são mais difíceis de atravessar que outros.
Uma heurística é um método teórico qualquer de definir o quão longe um certo estado está do estado final (o destino). Tipicamente para grelhas usa-se a distância euclidiana.
Resumidamente, o algoritmo, começando numa posição inicial vai mantendo um registo de todos os estados que ainda não explorou. Iterativamente, até chegar ao destino ou até não lhe restar nada para explorar, ele escolhe para explorar o estado com a função de custo menor. Esta função de custo é dada pela soma do custo acumulado com a heurística daquele estado. Escolhendo sempre o estado que minimiza isto garante que a solução para chegar ao destino, se existir, é óptima.
Evidentemente, este foi um resumo muito simples do que o A* faz. Tentemos explorar um exemplo:
Na imagem acima a unidade da esquerda quer chegar à posição assinalada com a bola vermelha. Assumamos que a unidade só pode ir nas quatro direcções adjacentes (ou seja, sem movimento diagnonal). Sem mais contexto, qualquer um diria para o gajo fazer uma escadinha até à bola. Mas eu agora digo que as árvores têm um custo de transição maior do que a erva, e que as montanhas não são atravessáveis de todo. Mesmo aqui, vós, inteligentes como sois, saberíeis dizer que o homem tem de passar por baixo da montanha e evitar a floresta.
Parabéns! Na vossa cabeça, vocês acabaram de fazer o A*.
Eis então uma imagem que ilustra um bocadinho melhor o que o computador vai fazer:
Em cada mosaico, os dois números em cima representam o estado (neste caso a posição; sim, começa no zero, na programação é mesmo assim, habituem-se). O número de baixo colorido representa o custo acumulado para se chegar ali.
Inicialmente o algoritmo explora em todas as direcção, incluindo para cima, pois ainda não tem nada pela qual se possa basear para saber por onde se orientar. Na segunda iteração, as posições 1,1 e 0,2 têm exactamente o mesmo custo e a mesma distância à bola, portanto ambas podem ser exploradas. A partir daí a conversa muda: a posição 1,2 não pode ser atravessada, portanto o algoritmo nem a tem em conta. A transição para sair de uma floresta é maior (neste caso 2), e portanto o custo acumulado na posição 2,1 já é de 3 (1 + 2) e será de 5 (1 + 2 + 2) em 2,2.
A azul está o caminho mais fácil e mais barato, sendo que o custo final será de 4 (não representado). Pelo caminho amarelo seria 6. Faça-se notar que o caminho amarelo não seria realmente explorado totalmente, pois o A* iria deixá-lo para trás em favor do caminho azul.
Tentei fazer o A* genérico o suficiente para poder ser utilizado noutras coisas no jogo. Ele pode ser utilizado para várias coisas, nomeadamente:
- obter o custo de uma posição a outra (tendo todos os factores em conta);
- obter o caminho óptimo de uma posição a outra;
- obter todos os movimentos possíveis para uma certa unidade.
Eis um exemplo de todas as posições (a azul claro) que aquela unidade consegue atingir segundo o A*, com uma capacidade de movimento 4:
Perdoem-me este texto algo desnecessariamente técnico, mas o A* merece, tendo em conta a sua ubiquidade em termos de utilização em tantas coisas na nossa vida, mesmo sem o sabermos.
Estou particularmente contente com o facto de ter já conseguido fazer isto, mesmo sabendo que terei uns bugs para resolver, mas pronto. É um passo bastante considerável no desenvolvimento, especialmente se não tiver muitas mais dores de cabeça com ele (admito que faltam uns pormenores...).
Vou começar a trabalhar no sistema de combate, para o qual vou precisar de uma sprite nova, com resolução de 32 por 32 para as animações de porrada. Admito que tenho ficado para trás nesse assunto, mas tenho isto até agora:
Sim, é um bacalhau no escudo. Falta especialmente adicionar sombreamento/iluminação, e talvez fazê-lo menos gordo.