Flow fields: compartilhar um destino sem compartilhar um caminho rígido

Compartilhe a consulta de destino, que é cara

Quando muitas unidades têm o mesmo destino, um flow field pode substituir buscas de rota individuais repetidas por uma orientação compartilhada. Cada unidade lê a direção próxima à sua posição atual, de modo que o deslocamento não exige construir mais um caminho completo. O resultado reutilizável, porém, continua pertencendo a um destino e a um modelo de movimento específicos. Emerson descreve uma implementação em tiles; Patel explica a busca subjacente de todas as origens até um único objetivo. [1][2]

Separe custo de travessia, integração e direção

Mantenha o custo de entrar em um terreno ou atravessá-lo separado do custo integrado para chegar ao objetivo. Em um modelo de grafo discreto, defina D(goal) = 0 e resolva D(x) = min(c(x,y) + D(y)) sobre as arestas de saída válidas. Com pesos não negativos, uma busca de Dijkstra reversa pode construir essas distâncias. Percorra as arestas invertidas, mantendo seus custos originais no sentido direto.

Armazene explicitamente um marcador de inalcançável. Escolha uma direção de saída válida usando o mesmo modelo de custo; simplesmente seguir o vizinho com a menor distância armazenada não basta quando os custos das arestas diferem.

Exemplo prático: a menor distância restante nem sempre indica a rota mais barata

Em uma bifurcação, a rota A custa primeiro 8 e depois tem custo restante de 1. A rota B custa primeiro 1 e depois tem custo restante de 4. Os totais são 8 + 1 = 9 e 1 + 4 = 5. O campo deve guiar a unidade para B, embora a distância restante de A seja menor.

Suponha que 200 unidades compartilhem esse destino e essa classe de movimento. Elas podem compartilhar o mesmo campo já concluído; isso não significa que a resolução de colisões ou o steering sejam compartilhados nem gratuitos. Esses custos e quantidades de unidades são ilustrativos: descrevem um projeto, não um ganho de desempenho medido.

Construa um campo que possa ser inspecionado

Comece com um mapa pequeno contendo uma parede, uma faixa de custo alto e um bolsão inalcançável. Desenhe separadamente os custos de travessia, os valores integrados e as direções escolhidas. Siga as setas a partir de cada célula alcançável e verifique que se chega ao destino sem ciclos. Confirme que a orientação diagonal respeita as mesmas regras de canto usadas para gerar as distâncias.

Use como chave dos campos em cache o objetivo, a classe de movimento e a versão relevante do terreno. Reconstrua os dados afetados quando uma ponte desaparecer ou uma permissão de travessia mudar. Publique juntas as gerações de campo concluídas, para que as unidades nunca leiam distâncias e direções parcialmente atualizadas. Teste as transições entre os limites de tiles e unidades que entram por posições inesperadas.

Planeje separadamente o compartilhamento e a execução física

Muitos objetivos ou classes de movimento distintos reduzem o reaproveitamento e multiplicam os dados em cache. Células grosseiras podem esconder passagens estreitas, e vetores interpolados perto de paredes podem apontar através de obstáculos. Um campo fornece orientação de rota; folga do corpo, separação entre unidades, tráfego em gargalos e ocupação do destino ainda precisam de tratamento explícito. Faça o profiling separado da construção do campo, da rotatividade do cache, da amostragem e do movimento local antes de decidir quanto movimento de multidão o campo compartilhado realmente economiza.

Fontes

• [1] Crowd Pathfinding and Steering Using Flow Field Tiles — Elijah Emerson, Game AI Pro.
• [2] Flow Field Pathfinding for Tower Defense — Amit Patel, Red Blob Games.