- Para implementar perseguição por monstros em um jogo 8-bit top-down no estilo Zelda, movimento simples em linha reta não basta; o texto compara Dijkstra e A* e busca os compromissos da busca de caminhos para jogos
- O movimento em linha reta para ao bater em uma parede, mas, com wall-sliding, é possível se mover ao longo da parede, melhorando a sensação de controle e também criando elementos estratégicos para prender monstros no terreno
- O algoritmo de Dijkstra garante o caminho mais curto, mas explora amplamente a região ao redor do nó inicial; em um jogo em que o destino muda a cada frame, ele faz mais cálculos do que o necessário para obter a próxima direção
- O A* prioriza a busca pela distância até o destino e examina primeiro a direção do destino; quando encontra uma parede, investiga nós ao redor e não revisita nós já vistos, conseguindo encontrar rotas alternativas
- Em mapas de jogos, é possível ajustar velocidade e dificuldade de implementação com grafos implícitos, que não exigem criar listas de adjacência previamente, busca por tiles e heurísticas baseadas em geometria, como limite de profundidade de iteração
Contexto do jogo e requisitos básicos
- Em um jogo 8-bit top-down no estilo Zelda baseado no PPU466, os monstros precisavam perseguir o jogador
- O PPU466 tem restrições semelhantes às de consoles de fantasia como o PICO-8: gráficos 8-bit, 4 cores por tile, plano de fundo fixo e poucos sprites
- O objetivo era fazer com que os monstros seguissem o jogador sem simplesmente parar ao bater numa parede ou ficarem presos de maneiras indesejadas
Movimento em linha reta e wall-sliding
- A abordagem mais simples é traçar uma linha reta entre o monstro e o jogador e mover-se nessa direção
- Usando apenas isso, o monstro para no instante em que encosta numa parede
- Ao aplicar wall-sliding, quando ele bate numa parede, não para; em vez disso, move-se ao longo dela
- No movimento do jogador, é uma técnica que torna o controle perto de paredes e cantos mais responsivo, e é usada em praticamente todos os jogos
- Ela é usada desde Pac-Man, e Pac-Man Championship Edition DX+ adiciona um efeito de faíscas quando o jogador faz wall-slide
- Ao combinar movimento em linha reta com wall-sliding, é possível prender monstros em determinados tipos de terreno
- Alguns jogos usam isso como elemento estratégico; o safespotting de Runescape é um exemplo
- Como esse não era o comportamento desejado neste jogo, foram avaliados algoritmos reais de busca de caminhos
Limitações do algoritmo de Dijkstra
- O algoritmo de Dijkstra é intuitivo de implementar e garante o caminho mais curto
- O problema é que ele faz muito mais trabalho do que o necessário
- Ele encontra os caminhos mais curtos do nó inicial até todos os outros nós do grafo
- É possível parar ao encontrar o nó de destino, mas não há como direcionar a busca para uma direção específica do destino
- Em videogames, como o jogador está sempre se movendo, o destino do monstro muda a cada frame
- O que o monstro precisa está mais próximo de saber para qual direção se mover agora do que de obter o caminho inteiro
- É possível pré-calcular o caminho mais curto para cada pixel ou tile do mapa, mas isso consome muita memória
- Em plataformas legadas ou com recursos limitados, Dijkstra não é adequado
Por que A* combina com busca de caminhos em jogos
- O A* Search Algorithm usa informações de distância entre o nó inicial e o destino para definir a prioridade da busca
- No primeiro passo, ele tenta priorizar a direção que vai em linha reta até o destino
- Diferentemente de Dijkstra, ele não gasta muito tempo explorando a direção oposta se isso não for necessário
- Se uma parede bloqueia o caminho, ele examina nós ao redor para tentar contorná-la
- Como em Dijkstra, ele não revisita nós já vistos; por isso, mesmo que seja necessário voltar muitas vezes, eventualmente encontra uma rota alternativa
- No exemplo, o monstro que usa A* não fica preso atrás da parede
Estrutura de dados de grafo implícito
- Em livros-texto, um grafo é representado por uma lista de nós e uma matriz ou lista de adjacência, mas em jogos é possível criar nós adjacentes de forma mais flexível
- Por exemplo, em uma tela de 256×240 pixels, cada coordenada de pixel pode ser vista como um nó
- Os pixels adjacentes incluem 8 direções: cima, baixo, esquerda, direita e as 4 diagonais
- O peso de movimento para cima, baixo, esquerda e direita é 1; o peso do movimento diagonal é √2, ou seja, cerca de 1,4
- Em vez de criar uma enorme lista de adjacência previamente, é possível gerá-la na hora apenas para os nós que forem efetivamente visitados
- Pixels que estão sobre uma parede ou ocupados por outro sprite não são posições válidas para o monstro, portanto são excluídos dinamicamente da lista de adjacência
- Com essa abordagem, não é necessário excluir manualmente no editor de mapas os nós que não podem ser adjacentes
Heurísticas que refletem a geometria do mapa
- Alguns elementos do A* podem ser ajustados diretamente à estrutura geométrica do mapa
-
Tamanho do passo
- Em vez de usar pixels como nós, em um jogo 2D baseado em tiles é possível usar tiles como nós
- A busca em unidades de tile reduz bastante o número de iterações necessárias para encontrar um caminho até o jogador, acelerando a pesquisa
- Nesse caso, o caminho não é uma lista exata de movimentos frame a frame, mas algo mais próximo de uma sequência de direções que o monstro deve seguir
- Como o monstro normalmente não se move a uma velocidade de 1 tile por frame, mesmo em um caminho baseado em tiles, a informação realmente necessária é a direção que permite chegar ao jogador
- Um caminho baseado em pixels tem a mesma natureza, e o monstro pode nem se mover a 1 pixel por frame ou em unidades inteiras de pixels
-
Profundidade de iteração
- No A*, quando um nó sai da fila de prioridade, ele é a última etapa do melhor caminho visto até então
- Se o algoritmo for interrompido após um número fixo de iterações, é possível obter a melhor estimativa de caminho até aquele momento para o caminho mais curto até o destino
- Mesmo sem executar o algoritmo até o fim, é possível obter uma direção de avanço razoável
- A profundidade máxima de iteração deve ser ajustada de acordo com a geometria do nível
- Se a profundidade for pequena demais, o monstro ainda pode ficar preso atrás de uma parede
- No exemplo, com profundidade fixa de 30 tiles, dependendo da posição do jogador, o monstro fica preso e não consegue avançar
- Como o A* é recalculado a cada frame, podem surgir loops
- No primeiro frame em que chega à parede, ele calcula que deve ir para baixo
- No frame seguinte, calcula que deve ir para cima
- Com essa repetição, o monstro fica preso em um loop
- Quando o jogador entra no alcance de busca do monstro, ele consegue encontrar o caminho correto
- Com uma profundidade fixa de
1, esse fenômeno aparece de forma ainda mais extrema: o monstro continua voltando para o pixel com a menor distância euclidiana até o jogador
Compromisso com pré-cálculo
- Para tornar isso mais refinado, é possível pré-calcular a profundidade máxima necessária para que o A* encontre um caminho a partir de qualquer posição do mapa
- Ao contrário do pré-cálculo completo de caminhos no estilo de Dijkstra, o que precisa ser armazenado é apenas esse único valor máximo
- Dada essa profundidade máxima, o A* consegue encontrar um caminho válido em tempo real
1 comentários
Comentários do Hacker News
Truques que usei com A* em um MMO em produção: 1) se você tiver grafos hierárquicos, como no nível da cidade, entre cômodos dentro de edifícios e dentro de cômodos, dá para encontrar um caminho de um ponto em uma sala de um prédio de uma cidade até outro ponto em uma fração de milissegundo
2) se você armazenar os metadados da busca A* atual no próprio nó do grafo, não precisa manter um array associativo separado
3) em vez de seguir o caminho resultante ao pé da letra, é melhor usá-lo como entrada para um comportamento de direção que tenta cortar caminho até o próximo nó do percurso sempre que possível. Se for um caminho até outro personagem, faça o personagem-alvo deixar “migalhas de pão” e adicione-as ao caminho quando a nova posição não puder ser alcançada em linha reta a partir do último nó do caminho
2b) isso é compactado em uma máscara de bits de 16 bits: 8 pedaços de 2 bits, ou seja, 8 direções, armazenados em uma tabela hash
2c) cada pedaço de bits tem quatro estados: FULL_BLOCK (parede), HARD_BLOCK (objeto grande que impede a passagem pelo tile em qualquer direção), SOFT_BLOCK (objeto pequeno que bloqueia a passagem por um canto), NO_BLOCK (tile vazio ou tile com um objeto muito pequeno)
Assim, quando uma unidade dentro de um edifício procura um caminho, não precisa verificar obstáculos em todos os tiles. Se o objeto não for enorme e, pela orientação da rotação, não bloquear os cantos de entrada e saída, também é possível atravessar um tile que tenha um objeto. Por fim, para que a simulação não quebre quando o jogador esquece de colocar portas, os agentes também podem atravessar paredes
https://store.steampowered.com/app/2287430/Metropolis_1998/
Enquanto o personagem estiver dentro dessa “bolha”, dá para pular completamente as verificações de colisão com o mundo
Na faculdade eu não entendia por que A* era tão difícil em RTS, mas, depois de ver a explicação de que, para impedir que as unidades atravessem umas às outras, tudo que se move precisa ficar desviando de todas as outras unidades e recalculando rotas o tempo todo, passei a respeitar ainda mais Command & Conquer
Pessoalmente eu evitaria isso, a menos que houvesse um motivo muito forte
Pensei muito em busca de caminhos rápida para acelerar uma IA de Quoridor feita em Scala, e os truques que aprendi foram estes
MPAA (A* adaptativo de múltiplos caminhos) é bom em situações em que obstáculos são adicionados e você precisa explorar a mesma área várias vezes. Dá para alimentar a busca com resultados anteriores para torná-la mais rápida
JPS (Jump Point Search) é atraente em teoria porque pode reduzir muito o número de “nós” a considerar, mas a sobrecarga de encontrar os pontos de salto aumentou tanto que, na prática, não houve ganho de velocidade. Talvez exista uma forma de combinar as ideias de MPAA e JPS, mas, quando você começa a mexer criativamente no algoritmo, pequenos detalhes conceituais podem facilmente dar um tiro no próprio pé. Por exemplo, usar
>quando era preciso>=pode fazer com que, em certas situações, você deixe de garantir o verdadeiro caminho mais curtoAo armazenar nós abertos, em vez de um heap de verdade, se o valor máximo de prioridade for um inteiro relativamente pequeno, vale considerar uma fila de prioridade por buckets. Como o array interno é indexado pela prioridade, inserções e remoções ficam bem rápidas
Quoridor é jogado em uma grade 9x9, e buscas de caminho repetidas são essenciais para determinar o quão perto um jogador está do objetivo e se o objetivo ainda é alcançável. Para avaliar os movimentos possíveis em uma posição específica, é preciso verificar se nenhum movimento torna impossível chegar ao objetivo. Planejo publicar isso em alguns meses, e deve incluir pelo menos três “motores” de decisão: mtdf (uma variação de minimax), MCTS (uma versão paralela com alguns truques) e um híbrido misturando catboost
O interessante é que isso pode ser usado como tabela de consulta para a função heurística, em vez da distância em linha reta usual. Por exemplo, no início de cada turno, dá para inicializar essa tabela com o algoritmo de Floyd-Warshall refletindo as paredes já colocadas. Usei essa técnica em um problema parecido e ela acelerou bastante o A*, além de ser muito simples. Mas era A* puro, sem MPAA nem JPS
Muitos anos atrás, adicionei à implementação de JPS do PathFinding.js um recurso para visualizar a busca recursiva que encontra os nós de salto. A demonstração online está aqui: https://qiao.github.io/PathFinding.js/visual/
Se houver mais de um inimigo, pode ser vantajoso simplesmente rodar Dijkstra uma vez do ponto de vista do jogador e fazer cada monstro consultar o caminho ótimo até o jogador
O custo de cálculo fica mais previsível quando o número de monstros muda
O problema de profundidade pequena demais da última animação parece um comportamento interessante. Parece que o monstro está “esperando para ver para qual lado você vai”
Se você fingir que vai para um lado e depois mudar de direção, será que não dá para enganá-lo? Felizmente, humanos são bem tolerantes com esse tipo de coisa e parecem modelar qualquer coisa como se tivesse inteligência
Basicamente, bastaria fazer o inimigo atualizar a rota só depois de um pequeno atraso, em vez de a cada frame. Assim, por causa da “inércia”, ele seguiria o caminho antigo e o jogador poderia enganá-lo
Um uso interessante de A* no contexto de jogos: havia um programador que precisava criar o adversário controlado pelo computador para um jogo do início dos anos 2000
Ele abstraiu as opções que a IA tinha no jogo e fez o A* encontrar a menor distância nesse grafo. O legal foi que não era o uso tradicional de pathfinding no mundo do jogo, mas sim encontrar um caminho sobre a representação das escolhas que o computador podia fazer, de modo que o caminho mais curto representasse a melhor estratégia possível
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
Também há materiais de referência (não são meus): https://github.com/agoose77/goap-resources
Humanos parecem supor que eles mesmos e outros humanos usam padrões de raciocínio parecidos, e uma profundidade de pensamento semelhante, em atividades totalmente diferentes, como planejar rotas, avaliar risco/recompensa ou organizar um evento daqui a 6 meses. Se vários “espaços de busca” puderem ser codificados como grafos adequados a um algoritmo comum, durante o jogo, em estado de imersão, a IA ganha uma plausibilidade de parecer ponderada e quase como uma personalidade
Quando eu estava aprendendo A* na faculdade, ao mesmo tempo passamos por aquele problema peculiar em um servidor público de Minecraft
O servidor engasgava muito, então rastreamos o problema e descobrimos que zumbis estavam presos em um loop tentando encontrar um caminho para entrar em uma vila completamente bloqueada por uma grande cerca. Ou seja, a implementação da época era ingênua e nunca desistia
Lembro que havia um relatório de bug explicando em bastante detalhe como corrigir isso
Isso podia ter um impacto bem perceptível no fps, especialmente quando vários animais tentavam atravessar uma entrada impossível de passar. Claro, também dá para dizer que é extremamente realista como comportamento de gato insistindo muito em passar por uma porta fechada. Seria ainda mais realista se, assim que você abrisse a porta, o gato mudasse de ideia imediatamente e perdesse o interesse em passar!
Talvez haja interesse neste artigo sobre sistemas multiagentes que usam A* em terreno desconhecido: https://www.researchgate.net/publication/333917261_Implement...
Este artigo e a thread do HN têm boas dicas. Ainda não tive muitas oportunidades de usar A*, mas sei que existe uma boa biblioteca Haskell: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...