Olá, Badump aqui.
Sobre Pathfiding...
Eu não tinha prometido isso a uns 2 meses atrás... bom, aqui está.
Intrudução, objetivos e problemas
Comparação de métodos tradicionais
Primeira tentativa
Implementação
Problemas surpreendentes
Performance
Leve dois
A ideia
O que mantivemos
Como os problemas surpreendentes foram resolvidos
Formações
Objetivos.
Implementação
Problemas
Desviando de obstáculos (e como isso forçou o pathfinding a mudar)
Movimentação de unidades
Objetivos
Implementação
Considerações sobre largura de banda
Clusters
escolhendo o cenário 2 ou 3
Performance geral e onde estão os problemas
Organização
Introdução, objetivo e problemas
Como todos já devem saber, o Sanctuary pretende ser jogável em escalas de milhares à dezenas de milhares de unidades, ser capaz de funcionar sem problemas não significará nada se, quando der uma ordem às unidades, elas formarem um trem tão longo que você vai pensar que estamos em um mundo anel, e não em uma esfera de Dyson. Então, o que podemos fazer? Fazer as unidades se moverem em bolhas? Sem quaisquer outras regras, é ineficaz. As unidades precisam ao menos de uma organização básica, para que no caso de suas artilharias/escudos serem mais rápidas do que os tanques, eles não façam uma fila para a própria destruição. Em geral, essa parte será tratada pelo código de formação.
Agora, quando se trata de como as unidades se movem, temos muitos comportamentos diferentes para introduzir, de tanques flutuantes que podem passar sobre a água, para bombardeiros de mergulho e qualquer coisa entre eles. São muitas coisas, para ser honesto.
Para o código do pathfinding em si, ele precisa ser capaz de lidar com grandes mapas e dezenas de milhares de unidades. O problema é que todas essas condições precisam ser cumpridas simultaneamente. Sem mencionar o fato que o pathfinding precisa funcionar em conjunto com os outros 2 recursos, os quais aumentam a complexidade do desafio.
E a ultima martelada no caixão é a razão pela qual não poderíamos usar alguma solução já existente.
Comparação de métodos tradicionais
Quando você fala pathfinding, o que vem a mente primeiro? A*? Campos de fluxo? Aquele artigo dos desenvolvedores de Castle Story sobre pathfinding hierárquico? (pode ser encontrado aqui https://www.gdcvault.com/play/1025320/Hierarchical-Dynamic-Pathfinding-for-Large, irei me referir a ele como Hpa*)
Não importa o que você imaginou, o que vem a mente é pelo menos um caminho entre A e B que evita obstáculos. E sem entrar em detalhes sobre como funciona, o algoritmo mais popular para fazer exatamente isso é o A*. É razoavelmente eficiente, mas infelizmente tem um problema sério em casos em que o desempenho cai conforme a área do mapa aumenta. Portanto se o mapa for 5x5, digamos que a perda de performance seja "25", mas se o mapa for 40x40, a perda de perfomance será "1600".
A perda de performance é nossa unidade imaginária que é inversamente proporcional à quantidade de frames
Temos outro problema em mãos: a quantidade de unidades tende à aumentar conforme o mapa aumenta. Então, 2 jogadores com 50 unidades cada em um mapa 5x5 resulta em 2 * 50 * 25 = 2500. E termos 16 players em um mapa 40x40, cada um possuindo 500 unidades, resulta em 1600 * 10 * 500 = 8.000.000. Como se pode ver, o lag tende a aumentar muito rápido conforme a escala aumenta. Agora veremos como podemos combater esse problema. Existem 3 soluções óbvias.
Reduzir o custo computacional de cada cálculo (basicamente, aceleramos tudo em 10x)
Reduzir a quantidade de unidades e/ou de players.
Ter mapas menores.
Agora vamos falar sobre cada um.
O problema com a primeira solução é que mesmo que fizermos tudo 10x mais rápido, 8.000.000 / 10 = 800.000, o custo computacional ainda seria muito grande. Precisaríamos torná-lo 100x mais rápido para que possa ficar na mesma magnitude do primeiro exemplo.
O problema com a segunda solução é que vai contra o objetivo do Sanctuary, mesmo que não coloquemos a "escala acima de tudo", também não visamos uma gameplay que consiste apenas em microgerenciamento.
E o problema com a terceira solução é que ela é, na verdade, a maior causadora de problemas de performance. Reduzir o tamanho do mapa seria a melhor maneira de melhorar a performance. Mas você não pode realmente ter muitas unidades em mapas pequenos, portanto não é adequado para o nosso caso.
De qualquer forma, parece que precisamos de uma solução que combine as vantagens de 2 e 3, mas sem pagar o preço. O que poderia nos ajudar a fazer isso? Vamos começar com os já mencionados campos de fluxo. O que são? E como ajudam? Bom, como o nome sugere, são campos, mais especificamente campos que cobrem todo o mapa.
Como você pode ver nas imagens, os campos de fluxo criam setas que apontam o melhor caminho até o local de destino, independente de onde esteja. Imagine que você é um jogador em um labirinto, e no chão há setas de campo de fluxo. Enquanto você as seguir, sempre chegará ao destino.
Ao menos que não tenha setas, que é o que acontece quando não há caminho até o destino.
Agora, você deve ter uma ideia de como funciona. A questão agora é: "quais são os impactos na performance?" Bom, lembra do nosso exemplo anterior, onde cada unidade precisa calcular seu próprio caminho até o objetivo? Isso não é mais feito. Agora cada unidade apenas olha o campo de fluxo de sua posição atual. Ou seja, praticamente não há custos para ter mais unidades. Então pode-se efetivamente ter um número ilimitado delas no jogo e não sentir nenhuma perda de performance causado pelo pathfinding.
Soa incrível! Vamos começar... Não tão rápido! Há algo que eu ainda não contei sobre os campos de fluxo, que pode mudar os tipos de cálculos que precisaremos efetuar. Lembre-se que os cálculos originais eram unidades totais * tamanho do mapa ao quadrado.
Aqui está a questão: para onde cada unidade está indo? Qual é sua localização alvo? Lembre-se como eu disse que campos de fluxo estão levando a um único local. Bem, o que acontece se você der à 2 unidades uma localização alvo diferente para cada. E se você desse a cada uma dessas unidades uma localização alvo diferente. Nesse caso, você não estará se saindo melhor do que A*, e de fato muito pior, porque campos de fluxo são muito mais lentos que A* para uma única unidade.
Realisticamente, reduzimos massivamente a contagem efetiva de unidades para o propósito dos cálculos, mas não é exatamente 1, não é pequena o suficiente para ser insignificante. Especialmente quando a IA está envolvida, com seus 100.000 de APM. De qualquer forma, não podemos fazer muito mais para reduzir o custo de cada unidade, então tentaremos outra abordagem, e ver o que ela consegue fazer por nós.
E nenhuma solução serve para responder se eu posso alcançar o alvo. Ambos vão perder tempo, mesmo se uma unidade não consiga de modo algum alcançar a localização alvo. Imagine um mapa com ilhas.
Pathfinding hierárquico (recomendo ler a apresentação, é muito boa!), volte aqui quando terminar.
No caso de você precisar de um resumo: O objetivo de Hpa* é permitir ter mundos grandes, tão grandes que você nem terá tempo de se preocupar com o pathfiding de mais de 1 unidade, e não precisará lidar com um terreno mutável.
Agora que eu disse terreno mutável, você acha que os já mencionados métodos conseguiriam lidar com a construção de um muro ou a colocação de uma fábrica, que bloqueia os caminhos das unidades? (dica: eles não conseguem lidar com isso)
É aqui que o Hpa nos salva. Por causa da maneira que o mapa é pré-processado, nos permite atualizar apenas as partes do mapa que foram modificadas, e cada vez que consultamos o pathfinding, obtemos um caminho atualizado. O que é uma grande melhora em relação a A*, já que não é necessário pré-fazer os caminhos no mapa todo. Apenas precisamos construir caminhos em pequenos segmentos e chegar até o destino.
Infelizmente, embora ajude a computar menos, as computações que fizermos serão muito mais complicadas, então o Hpa* só compensa em grandes mapas. Quanto menor o mapa, pior é seu desempenho. E o custo é constante o tempo todo que uma unidade está fazendo o pathfinding. Isso não é exatamente algo bom, mas também não é tão ruim. Ainda sim, pathfinding para dezenas de milhares de unidades fica caro. De qualquer maneira, eu comecei com ele como a primeira tomada em pathfinding, então vamos ver o que aconteceu.
Primeira tentativa
Implementação
Bom, a primeira coisa a fazer é criar a navmesh. Como o artigo descreveu anteriormente, ele tem hierarquias. Então, como codificamos isso? Vamos começar bem do fundo. A primeira camada está simplesmente transformando o terreno em nós. Então cada quadrado 4x4 é agrupado em outro nó de nível superior, e assim por diante.
(1)
O tamanho do 4 é arbritrário. Pode ser facilmente mudado. (Arbitrário agora, importará muito depois)
Agora precisamos adicionar alguns obstáculos.
(2)
Então agora precisamos achar quais nós seriam construídos na primeira camada
(3)
As cores diferentes significam áreas diferentes, você não pode passar da área verde para a vermelha ou vice versa. Mas esta é apenas a camada 1. Obviamente, não há obstáculos entre as células da esquerda e da direita. Então vamos pra próxima camada
(4)
Basicamente precisamos apenas ver se nossa posição e destino atuais são da mesma "cor". Se você está se perguntando porque o vermelho e o verde foram trocados, é para demonstrar que quando 2 células se encontram, elas concordam na cor, por assim dizer.
Ok, aqui está uma explicação técnica. Para cada célula do primeiro nível, fazemos uma lista das vizinhas, para que os quadrados menores tenham apenas 4 ou menos, superior, direito, esquerdo, inferior. E podemos realmente pular isso, pois sempre podemos procurá-lo. Mas imagine que temos uma lista deles por enquanto. Para nós maiores, não podemos pulá-los. E, claro, se o quadrado estiver bloqueado, então não é um vizinho. Nós com 0 vizinhos estão totalmente bem. Afinal, o nó de mais alto nível será tal.
Continuando, faremos um tipo de "preenchimento" no quadrado, e todos os nós que foram preenchidos, criam um novo nó de nível superior. Na foto 3D. Todos os quadrados verdes formam um novo nó de nível superior. E os vermelhos também. Agora esses nós podem conter apenas quadrados que são do mesmo nó base.
Ok, vamos entender algumas terminologias: Nó de base: é o quadrado inteiro, contém múltiplos nós de um nível inferior, e múltiplos nós do mesmo nível. Nó: área coberta pela cor verde/vermelha. Por exemplo, o nó nível 2 é a área total vermelha e verde na figura 3. Um nó de nível 3 cobriria toda a área verde e vermelha na imagem 4, no total há 2 nós de nível 3 na imagem 4 , e 4 nós de nível 2 na imagem 3.
Agora vamos definir vizinhos. Ou seja, cada nó de mesmo nível que é um parente dos vizinhos dos filhos. Ok, aqui um exemplo mais simples de imaginar:
Meus amigos são parentes dos amigos do meu filho (assumindo que crianças tem apenas amigos da mesma idade). Significa que eu não sou amigo das crianças em si, que também não são meus amigos.
E, obviamente, as crianças precisam ter apenas 1 parente. Caso contrário, é um bug. Imagine lutar pela custódia e o juiz lhe dá apenas um par de brincos. lol!
Quando você cria um nó nível 2 de nós nível 1, você continua indo mais alto na hierarquia. Agora você faz o mesmo processo com nós nível 3 para criá-los a partir de nós nível 2. Até chegar no nó mais alto possível. Tal limite é predefinido no início. Agora vamos ver como isso tornaria saber se você pode ir de a para b algo trivial. A resposta é simplesmente verificar os parentes até que um parente em comum seja encontrado. Se você achá-lo, então ótimo, um caminho existe. Se não achar, significa que não há caminho possível. Isso torna a travessia praticamente instantânea. Ou O (log n) comparado à O (N^2) para achar um caminho. Em números, vamos dizer que o mapa tem 5.000 unidades de largura. Com um nó de tamanho 4, o Hpa é cerca de 4 milhões de vezes mais rápido. Agora vamos aumentar o tamanho do mapa em 10x, e fazer os nós do Hpa* em 8 ao invés de 4. Agora é cerca de meio bilhão de vezes mais rápido. Isso é apenas para descobrir se o caminho existe. sem custos de localizar o caminho.
Sobre a travessia, para iniciar precisamos achar o nó que tenham parentes em comum, quanto mais próximo melhor. Depois, precisamos achar um caminho do filho de tal nó que estamos, até o nó em comum que queremos ir. Isso é um pouco mais fácil quando o tamanho é 2 ao invés de 4 ou mais, porque apenas precisamos usar esquerda/direita/cima/baixo, caso contrário, é necessário achar um caminho. Mas não é um grande problema quando se está localizando caminhos em uma pequena grade, exceto se você fizer isso para cada nível. Então é necessário ter algum equilibro entre o tamanho do nó e a quantidades de vezes que precisa viajar. Por exemplo um mapa de 1024x1024 terá log2(1024) = 10 camadas para percorrer. Mas quando o tamanho do nó é 4 terá um log4(1024) = 5 camadas. Fazendo-o ainda maior, com por exemplo 16 nós, nos dará 2.5 camadas, mas não podemos ter 0.5 camadas, então o arredondamos para 3. Isso resultaria no tamanho mínimo de 4096. Que também é 3.
Infelizmente, a travessia, ainda que não seja cara, não é exatamente barata, até no meu PC, eu tive problemas em usar mais de 20.000 unidades com essa abordagem. Ainda que algumas otimizações possam aumentar esse valor, ainda não é bom o bastante, e também há outros problemas.
Problemas surpreendentes.
Um dos problemas é que uma hierarquia é formada, mas você apenas conhece o próximo grande nó, que acaba sendo um problema quando você precisa de uma solução mais precisa. Aqui nesse exemplo, precisamo de um caminho de verde até vermelho. A imagem mostra como isso seria no nível superior. Como você pode ser, o caminho que você pegará é preto, enquanto o roxo é mais preciso. Note que ainda tamos falando sobre caminhos de nível 2, que significa caminhos entre nós de nível 2 dentro de um parente comum de nível 3.
Suavizar esse caminho dará um pouco de dor de cabeça, já que não é exatamente trivial. Além disso, outros problemas podem surgir, como nas imagens abaixo.
O preto seria o que nós normalmente obteríamos. Como agora somos mandados à ir para a direita, o caminho mais curto está logo a frente. Roxo é o que seria se tivéssemos dito para ir ao nó inferior direito (ainda no mesmo parentesco de nós). Mas para isso, precisaríamos saber antecipadamente onde está o objetivo, que seria no próximo nó. E o vermelho seria como poderíamos ter suavizado o caminho.
Agora você poderia perguntar, nós não suavizamos o caminho preto? Bem, o fato é que apenas conhecemos a primeira parte do caminho preto quando ele é executado. Então, até cruzarmos a grossa linha cinza, não temos ideia de onde deveríamos ir. Podemos mitigar esse problema calculando antecipadamente, mas a questão é que o custo aumenta com o número de pré-cálculos. Então, quanto mais longe você for, mais custoso fica. Podemos mitigar isso armazenando em cache, mas quanto mais você pré-calcular, mais propenso será a não funcionar como o desejado quando o caminho precisar ser alterado. Como por exemplo um muro sendo construído. Portanto, é melhor mantê-lo o mais curto possível. E isso não funciona em caminhos longos. Se houvesse paredes ou desvios do caminho perfeito, então ficaria quase impossível fazê-lo escolher bem.
Performance
O custo do algoritmo é ao redor de log(mapSize) * Unit count. E, infelizmente, como mencionado mais cedo, não é exatamente barato. Por mais que seja bom em escalas de centenas de unidades, se torna um problema quando você multiplica pelos milhares. Ainda sim, é uma grande melhora sobre A* por custo de unidade, e não cria picos de atraso como os campos de fluxo, especialmente quando você tem múltiplos alvos para diferentes unidades.
Conseguindo os Dois
Hmm, não seria bom ter um algoritmo que funcione bem para mapas grandes e custasse muito pouco ou nada por unidade... Isso seria ótimo.
A ideia
Você provavelmente poderia ter visto da órbita de Plutão, mas o que fazemos é combinar campos de fluxo e estruturas hierárquicas. Pegamos a parte da hierarquia que nos permite um cálculo quase instantâneo por unidade e adicionamos campos de fluxo a ela, para que cada unidade possa compartilhar o mesmo caminho. Embora, no final, nós ainda acabemos massacrando uma parte importante da hierarquia, enquanto não aumentemos o tamanho do mapa para 11 (estou falando de tamanhos como a superfície da Terra, não um mapa insignificante 40x40km), ele deve funcionar bem o suficiente. E, se o fizermos, então teremos que pensar um pouco mais.
Claro, esses 2 conceitos não são exatamente bons um com o outro. O próximo passo é descobrir o que exatamente precisamos e o que não precisamos. Ter mais coisas que nosso algoritmo não precisa ser capaz ou ser bom em fazer, torna a criação de um algoritmo bem otimizado muito mais fácil. Alternativamente, quais optimizações podemos aplicar e iriam elas quebrar alguma coisa importante?
Bom, vamos começar a pensar em como podemos começar a misturar as duas ideias. Uma maneira seria aumentar o tamanho das células e executar campos de fluxo ao invés de A* e armazenar isso em cache. E embora essa não seria uma má solução, e nos permita reusar muitos de nossos cálculos, ainda envolve tecnicamente a geração de um campo de fluxo em uma grande parte do mapa. Na pior das hipóteses, você ordena um círculo de unidades ao redor da borda do mapa, para convergir no centro. Todos eles acabariam gerando um campo de fluxo em todo o mapa, embora fosse distribuído ao longo do tempo. Também geraria muitas camadas dele, o que significa que seria mais caro que apenas fazer um campo de fluxo comum. Mesmo assim, parece uma solução viável. Mas isso não geraria um campo de fluxo de alta qualidade de qualquer maneira, e podemos fazer melhor. Se o campo de fluxo não for perfeito, podemos usar alguns truques.
E se pudéssemos armazenar em cache ou pré-calcular partes?
Bem, isso já é o que a hierarquia faz, mas queremos ir ainda mais além. Especialmente ter 0 de custo de tempo em execução seria bom. Mas olhando por uma perspectiva hierárquica não nos ajuda muito. Vamos mudar para uma abordagem mais centrada no campo de fluxo.
Ao invés de adicionar campos de fluxo à hierarquia, adicionamos a hierarquia aos campos de fluxo.
À primeira vista, os campos de fluxo não podem ser realmente armazenados em cache, podem? bem, podemos manter todos os pedidos já emitidos, mas isso só começará a ser útil depois que centenas de milhares de comandos forem emitidos. Um mapa 512*512 tem 260k. Qualquer coisa maior tornará o cache impossível. Isso também acabará com nossa memória RAM, então vamos precisar usar um pouco de fita para conseguir armazená-la em cache. (fita magnética ainda é surpreendentemente muito usada, pode olhar no google). Então, se armazenar todas as ordens em cache não será possível, então que tão armazenar apenas algumas pequenas partes e, de alguma forma, usá-lo mais tarde.
Mas o que exatamente iremos armazenar?
Bom, vamos pensar sobre a hierarquia por um segundo. E de volta aos campos de fluxo: como podemos possivelmente alavancar a hierarquia para construir campos de fluxo? Bem... Vamos voltar, nos já possuímos uma espécie de navmesh, construída pelo pathfiding hierárquico. Contém os nós, nós de base, parentes, etc... Podemos usá-lo.
O que mantemos
Continuando, decidimos usar o navmesh, mas não próprio algoritmo de pathfinding que sobrou. Agora precisamos construir uma forma alternativa de pathfinding. Isso, no final, parece com um campo de fluxo.
Vamos fazer uma declaração e ver como podemos usá-la:
Campos de fluxo com centros próximos uns dos outros são praticamente os mesmos quando você se afasta deles.
Aqui algumas imagens que ilustram isso. Todas os 4 tem origens diferentes.
(Eu escrevi o programa que fez essas imagens de campos de fluxo, e o código fonte está no Patreon, perfeito se alguém quer experimentar com seus métodos de campos de fluxo.)
Você vê como o fundo e os lados sempre permanecem basicamente os mesmos? Em média, pode ser um pouco mais claro ou mais escuro, e o início da ponte pode parecer diferente, mas no final e no outro lado, se parecem exatamente iguais.
Isso significa que cada vez que calculamos um campo de fluxo, é meio que um desperdício. Como mover a posição do alvo em 1 unidade, cria um campo de fluxo 99% parecido com o anterior, mas ao mesmo tempo completamente novo.
Temos algumas maneiras de resolver isso, mas temos que levar em consideração um certo recurso. Esse terreno pode mudar, e as áreas que eram passíveis de passagem podem não ser mais. Nós realmente não queremos recalcular cada pedido, isso seria terrível em questão de desempenho.
Então mesmo se otimizarmos e armazenarmos os campos de fluxo, ainda não seria bom o suficiente quando um muro fosse derrubado. Mas essa é a mágica especial da hierarquia, então a adicionamos agora.
Usamos as camadas antigas, mas, francamente, precisamos apenas das 2 primeiras. Então agora temos os terrenos em pedaços de algum tamanho que todos os vizinhos conhecem. Bem... Calculamos os campos de fluxo entre vizinhos. E então, na próxima camada, calculamos o campo de fluxo novamente, mas desta vez, toda a área é pequena, apenas 512x512, com nós de tamanho 32, resultando em 16x16 para um total de 256 nós. O custo de performance no início é o mesmo que ter que calcular 8 campos de fluxo em todo o mapa. O que não é muito ruim, não é realmente significativo.
Claro, essa abordagem acaba causando algumas dificuldades, e calcular os campos de fluxos se conectando é meio complexo. Especialmente quando você considera como as unidades se movem e as suas formações. Esses dois elementos complicam muito o pathfinding.
Aqui algumas imagens dos campos de fluxo resultantes, com diferentes níveis de nós.
Obviamente, quanto menor o nó, mais ele é preciso, mas eu descobri que o equilíbrio é em torno de 16 ou 32.
Desafios
Os primeiros testes mostraram que o pathfinding funcionava razoavelmente bem, mas teve alguns problemas. Como unidades gostando muito de abraçar as paredes, fazendo com que grupos grandes não tivessem um bom desempenho. Também havia aberturas nas paredes. Isso era "tecnicamente" passável, mas na prática não funcionava bem. E, em geral, muitos ajustes em como o próprio navmesh era gerado, que melhoraram muito o pathfinding. Também há uma necessidade de prevenir mudanças bruscas no pathfinding, principalmente para prevenir oscilações nas unidades, e a adição de vários pequenos e outros não tão pequenos recursos aos campos de fluxo, com o objetivo de fazê-los mais amigáveis para as unidades. Outra grande parede de texto virá na próxima semana, então fiquem ligados!