Na semana passada, conversamos em nosso blog sobre mudanças que permitiriam que os inimigos (biters) não se encontrassem, mas essa não era a única atualização relacionada aos biters. Por coincidência, as atualizações desta semana incluíram o que trabalhamos nas últimas semanas - atualizando o sistema de busca por inimigos.
Procure uma maneira
Quando uma unidade quer se mudar para algum lugar, primeiro precisa entender como chegar lá. No caso mais simples, você pode ir direto ao objetivo, mas às vezes surgem obstáculos no caminho - pedras, árvores, ninhos inimigos (desovadores), unidades de jogadores. Para pavimentar o caminho, precisamos informar à função de desbravador a posição atual e final, e o desbravador retornará para nós (talvez depois de muitas medidas) um
caminho que é simplesmente um conjunto de pontos de passagem que a unidade deve mover para chegar a destino
Para realizar seu trabalho, o pathfinder usa um algoritmo chamado A * (pronunciado "Uma estrela"). Um exemplo simples de encontrar um caminho usando A * é mostrado no vídeo: o biter quer encontrar um caminho ao redor de rochas. A função de localização de caminho começa a explorar o mapa ao redor da picadora (o estudo é mostrado por pontos brancos). No início, ela tenta ir direto ao objetivo, mas assim que alcança os penhascos, "derrama" em ambas as direções, tentando encontrar uma posição a partir da qual novamente será possível avançar para o objetivo.
O algoritmo deste vídeo é mais lento, para que você possa ver melhor como ele funciona.Cada ponto na animação representa um
nó . Cada nó lembra a distância desde o início da pesquisa e a distância estimada entre o nó e o destino (essa estimativa é calculada pela
função heurística ). É graças à função heurística que A * funciona - ele direciona o algoritmo na direção certa.
No caso mais simples, essa função é simplesmente calcular a distância em uma linha reta do nó à posição de destino - esta é a abordagem que usamos no Factorio desde o início do desenvolvimento e, graças a isso, o algoritmo se move inicialmente em uma linha reta. No entanto, essa não é a única opção - se a função heurística souber de alguns dos obstáculos, ela poderá direcionar o algoritmo ao seu redor, o que aceleraria a pesquisa, pois não precisaria examinar os nós extras. Obviamente, quanto mais inteligente a heurística, mais difícil é implementar.
Uma função simples de estimativa de distância heurística linear é boa para encontrar caminhos em distâncias relativamente curtas. Nos convinha nas versões anteriores do Factorio - quase sempre os mordedores se moviam por longas distâncias apenas porque estavam irritados com a poluição, e isso não acontecia com muita frequência. No entanto, agora temos artilharia. A artilharia pode facilmente disparar contra um grande número de mordedores do outro lado de um grande lago (e "agrificá-los"), após o que eles tentam pavimentar o caminho ao redor do lago. O vídeo abaixo mostra como o algoritmo A * simples que usamos anteriormente tenta contornar o lago.
Este vídeo mostra a velocidade do algoritmo na realidade; ele não é abrandado.Redução de bloco
Encontrar um caminho é uma tarefa longa da história, e existem muitas técnicas para melhorá-lo. Algumas dessas técnicas pertencem à categoria de
pesquisa de caminho hierárquico : nesse caso, o mapa é simplificado a princípio, o caminho está localizado nesse mapa simplificado, que é usado para encontrar o caminho real. Repito, existem várias implementações específicas dessa técnica, mas todas elas exigem simplificação do espaço de pesquisa.
Como você pode simplificar o mundo do Factorio? Nossos mapas são gerados aleatoriamente e mudam constantemente: colocar e excluir entidades (por exemplo, colecionadores, paredes ou torres) - essa é provavelmente a mecânica mais básica de todo o jogo. Não queremos recontar todo o mapa simplificado toda vez que adicionamos ou removemos uma entidade. Ao mesmo tempo, se simplificarmos o mapa novamente toda vez que precisarmos encontrar uma maneira, podemos facilmente perder todo o ganho em desempenho.
Uma das pessoas com acesso ao código-fonte do jogo (Allaizn) teve uma ideia. que eu implementei como resultado. Agora, essa ideia parece óbvia.
O jogo é baseado em blocos de 32x32 peças. O processo de simplificação substitui cada bloco por um ou mais
nós abstratos . Como nosso objetivo é melhorar a busca por um caminho ao redor dos lagos, podemos ignorar todas as entidades e considerar apenas os ladrilhos: você não pode se mover na água, na terra que pode. Separamos cada bloco em
componentes separados. Um componente é uma área de bloco na qual uma unidade pode passar de um bloco dentro de um componente para qualquer outro bloco do mesmo componente. Na imagem abaixo, o bloco é dividido em dois componentes separados, vermelho e verde. Cada um desses componentes se tornará um nó abstrato - na verdade, todo o bloco é reduzido para dois "pontos".
O pensamento mais importante de Allaizn era que não precisamos armazenar um componente para cada bloco de mapa - lembre-se dos componentes do bloco ao longo do perímetro de cada bloco, porque estamos interessados apenas no que outros componentes estão conectados (em blocos vizinhos) de cada componente, e isso depende apenas das peças que estão na borda do bloco.
Pesquisa de caminho hierárquico
Então, descobrimos como simplificar o mapa, mas como usá-lo para encontrar caminhos? Como eu disse, existem muitas técnicas hierárquicas de busca de caminhos. A idéia mais simples é encontrar o caminho usando nós abstratos do começo ao objetivo, ou seja, o caminho será uma lista dos componentes dos blocos que você precisa visitar. Em seguida, usamos a série de boas pesquisas antigas A * para descobrir especificamente como mover de um componente do bloco para outro.
O problema aqui é que simplificamos demais o mapa: e se mudar de um bloco para outro é impossível, porque algumas entidades (por exemplo, rochas) bloqueiam o caminho? Ao reduzir blocos, ignoramos todas as entidades; portanto, sabemos apenas que os blocos entre os blocos estão de alguma forma conectados, mas não sabemos absolutamente nada sobre se é possível passar de um para outro.
A solução é usar a simplificação simplesmente como uma "recomendação" para uma pesquisa real. Em particular, vamos usá-lo para criar uma versão inteligente da função de pesquisa heurística.
Como resultado, obtivemos o seguinte esquema: temos dois descobridores: o
descobridor de base , que encontra o caminho real, e o
descobridor abstrato , que fornece a função heurística ao descobridor de base. Cada vez que o pathfinder base cria um novo nó base, ele chama um pathfinder abstrato para obter uma estimativa da distância do alvo. O descobridor abstrato age na ordem oposta - começa com o alvo de busca e abre o caminho para o início, passando de um componente do bloco para outro. Quando uma pesquisa abstrata encontra o bloco e o componente em que um novo nó base é criado, ela usa a distância do início da pesquisa abstrata (que, como eu disse, é a posição do objetivo de toda a pesquisa) para calcular uma estimativa da distância do novo nó base ao alvo geral.
No entanto, a execução do pathfinder inteiro para cada nó individual estará longe de ser rápida, mesmo que o pathfinder abstrato se mova de um bloco para outro. Portanto, em vez disso, usamos um esquema chamado "Reverse Resumable A *". "Reverso" significa que, como eu disse acima, é realizado do objetivo ao início. “Renovável” significa que, depois de encontrar um bloco interessante para o pathfinder de base, salvamos todos os seus nós na memória. Na próxima vez em que o pathfinder base criar um novo nó e precisar de uma estimativa de distância, apenas olharemos para os nós abstratos salvos da pesquisa anterior. Ao mesmo tempo, há uma alta probabilidade de que o nó abstrato necessário ainda esteja na memória (no final, um nó abstrato cobre a maior parte do bloco e, geralmente, o bloco inteiro).
Mesmo que o pathfinder base crie um nó localizado em um bloco que não é coberto por nenhum dos nós abstratos, não precisamos executar toda a pesquisa abstrata novamente. Um recurso conveniente do algoritmo A * é que, mesmo depois de "terminar o trabalho" e encontrar um caminho, ele continua a execução, explorando os nós em torno dos nós já estudados. E é exatamente isso que fazemos se precisarmos de uma estimativa de distância para um nó base localizado em um bloco ainda não coberto pela pesquisa abstrata: retomamos a pesquisa abstrata dos nós armazenados na memória até que ela se expanda para o nó de que precisamos.
O vídeo abaixo mostra um novo sistema de busca de caminhos em ação. Círculos azuis são nós abstratos; pontos brancos - pesquisa básica. O pathfinder no vídeo é muito mais lento que o jogo para mostrar como ele funciona. À velocidade normal, toda a pesquisa leva apenas alguns tiques. Observe que a pesquisa básica, que ainda usa o antigo algoritmo que sempre usamos, simplesmente “sabe” magicamente como se mover ao redor do lago.
Como o pathfinder abstrato é usado apenas para obter uma estimativa heurística da distância, a pesquisa básica pode facilmente sair do caminho proposto pela pesquisa abstrata. Isso significa que, embora o esquema de redução de blocos ignore todas as entidades, o pathfinder básico pode ignorá-las quase sem problemas. Devido à ignorância de entidades no processo de simplificação do mapa, não precisamos repeti-lo novamente toda vez que uma entidade é adicionada ou removida, é suficiente cobrir apenas os blocos que foram alterados (por exemplo, como no caso de um aterro de lixo), o que acontece com muito menos frequência do que a colocação de entidades.
Além disso, isso significa que usamos essencialmente o mesmo pathfinder que usamos há anos, apenas a função heurística foi atualizada. Ou seja, essa alteração não afetará muitos outros sistemas e afetará apenas a velocidade da pesquisa.