Como faço para que os agentes A * evitem outros agentes?

Estou implementando um algoritmo multi-agente A * em um mapa de blocos. Os agentes se movem apenas nos eixos X e Y. Evito colisões entre eles verificando onde os outros estão ao calcular caminhos.

Funciona bem, exceto na situação em que os agentes precisam passar o mesmo bloco de diferentes direções. Em situações como essa, uma solução ideal seria que um agente esperasse o outro passar:

Além disso, se não houver corredor norte, a busca de caminhos falha.

Como eu poderia implementar esse algoritmo?

Você pode começar deixando a busca de caminho falhar. Em caso de falha, escolha um horário aleatório no futuro para tentar novamente a busca de caminhos. Alguns protocolos de rede de baixo nível funcionam dessa maneira e muito bem. O que você precisa fazer é criar caminhos um de cada vez e marcar como usados ​​todos os blocos que um agente passará. Quando outros caminhos falharem, o timer aleatório para reiniciar ajudará a espalhar as novas pesquisas de caminho e interromper as falhas de loop.

A segunda parte do seu problema pode ser tratada retornando dois caminhos. O primeiro caminho é o retorno regular, mesmo se falhar em um bloco. O segundo caminho é um caminho que ignora completamente todos os agentes. Em seguida, você pode usar o conhecimento adquirido nesses dois caminhos para decidir se seria melhor esperar ou percorrer o longo caminho. A heurística para essa decisão levará algum trabalho, mas é melhor do que não tentar nada.

No caso muito ruim em que seus agentes estão ficando muito bloqueados por corredores de largura única como essa, talvez seja necessário adicionar pontos seguros para ficar onde os agentes possam localizar rapidamente e esperar o caminho real se abrir (para que o agente não apenas espere e bloqueie um corredor).

Em vez de resolver o seu problema, aqui está uma maneira de pegar os limões e fazer limonada.

Muitos anos atrás, um amigo meu estava trabalhando em um FPS muito conhecido, que tinha precisamente o problema que você descreve: uma área restrita teria vários caracteres de IA que tinham determinadas posições desejadas, e o algoritmo de localização de caminhos os esbarrava constantemente. um no outro. Em particular, o jogador, por exemplo, jogaria uma granada em uma pequena sala cheia de inimigos, e os personagens da IA ​​na área tentariam correr para a saída, mas se chocariam e acabariam parando, virando, bater em alguém, dar a volta e assim por diante. Isso parece muito irreal.

Tentativas de criar um algoritmo melhor de busca de caminhos que pudesse ser executado com êxito, devido ao orçamento computacional apertado, falhou. Então, em vez de resolver o problema de busca de caminhos, meu amigo adicionou um cheque muito barato à IA: se uma IA colidiu com outra AI duas vezes em um curto período de tempo, pare de tentar encontrar a saída e se proteja. Então agora o que acontece é que o PC joga a granada e vê um monte de inimigos correndo pelas saídas. Aqueles que se batem, se viram, e parece que eles percebem que não podem sair, então eles abaixam e cobrem a cabeça antes de explodir. Isso é realista e altamente satisfatório para o jogador.

Existe alguma maneira semelhante de transformar a desvantagem do seu algoritmo de produção de colisões e transformá-lo em uma vantagem?

Normalmente, acho melhor aumentar o caminho A * com outras formas de encontrar caminhos para outros cenários localizados; a evasão de unidades é geralmente uma delas, especialmente em um mundo onde existem vários agentes se movendo simultaneamente e, assim, criando bloqueadores dinâmicos).

Geralmente, uma técnica de acompanhamento de borda pode funcionar para isso. Quando você segue um caminho e encontra um bloqueador que não fazia parte do cálculo do caminho original, basicamente escolhe uma direção (no sentido horário ou anti-horário) e tenta atravessar o bloqueador, percorrendo-o nessa direção. Se não puder, aguarde o bloqueador se resolver (embora isso possa resultar em um impasse).

Você também pode implementar a capacidade das unidades rastrearem cooperativamente; isto é, uma unidade pode solicitar que outra unidade se afaste levemente para que possa "espremer" a unidade de bloqueio. Isso não funciona bem em um jogo baseado em blocos, no qual você está restrito ao movimento baseado em blocos, porque ainda é possível travar em corredores de largura única como o seu exemplo. Nesse caso, você pode providenciar para que as unidades peçam uma à outra para "trocar de lugar", o que resulta em resolução na maioria das vezes. Ocasionalmente, isso leva a unidades pulando umas sobre as outras, no entanto.

"Evitar unidades" é um tópico bastante comum quando se discute a busca de caminhos em jogos; existem muitos hits por aí. Em particular, convém verificar esta pergunta no caminho do "campo de fluxo" usado no Supreme Commander 2. Os RTSs costumam enfrentar esse problema muito e resolvê-lo de várias maneiras interessantes.

Se você tiver um sistema de movimento baseado em turnos / tick, poderá criar um gráfico 3D em que cada transição move o agente para a aparência do mapa no futuro. Em seguida, peça a cada agente que reivindique os blocos em que eles estariam naquele ponto no futuro e marque-os como inacessíveis. Cada agente tem uma opção extra de "aguardar" para o próximo tick como uma terceira maneira de fazer a transição pelo gráfico. Isso será mais difícil para o seu sistema, mas deverá fornecer melhores resultados do que esperar aleatoriamente. Melhor ainda, se você permitir que dois agentes se comuniquem, e um deles envie uma mensagem de "Quero passar por você" se o caminho mais curto passar por esse agente,

Ao usar um algoritmo como A *, você tem a maior latitude em trabalhar com a heurística de custos.

Nesse caso específico, você pode ajustar a heurística para aumentar o custo dos movimentos que levam um agente a outro agente, o problema é que você provavelmente terminaria tentando seguir a rota superior e oscilaria indo e voltando entre os caminhos conforme eles se fecham, dependendo do tempo exato.

Outra possibilidade é rastrear as rotas pretendidas pelos agentes e ajustar os custos para cima ao longo dos caminhos pretendidos pelos outros agentes. Isso efetivamente permite que os agentes se coordenem entre si em uma extensão limitada. O principal problema aqui é se todas as rotas estão bloqueadas. A localização do caminho pode continuar falhando para o agente que se move por último.

No caso em que há apenas um caminho, a localização do caminho falhará ou eles avançarão um contra o outro até o impasse.

Se nenhum deles for bom o suficiente, você precisará começar a acompanhar o tempo ao calcular seu custo também. O custo para o segundo agente deve ser a quantidade de tempo que leva para o primeiro agente ficar claro, mais o custo de passagem normal, para que seu agente possa decidir corretamente quando esperar ou seguir o outro caminho.

Levar o tempo de acordo pode ser um esforço significativamente maior, então a maioria das pessoas decide ajustar o layout do nível e os valores de custo até que as coisas estejam boas o suficiente.

Normalmente, eu recomendaria que você usasse comportamentos de direção para resolver problemas como esse durante o caminho a seguir. E você ainda pode se esforçar muito para se inspirar no comportamento de agrupamento. Infelizmente, não é realmente diretamente aplicável a movimentos simples baseados em ladrilhos.

Como você já tem uma prevenção de colisão de trabalho na maioria das situações, vamos nos concentrar nessa em particular. Eu acho que você está refazendo o caminho sempre que um agente quer se mudar, ou então não consigo ver como eles reagem a outros se movendo durante a mudança. Em segundo lugar, acho que esses agentes são amigáveis ​​entre si.

Você sugere um agente esperando pelo outro e eu aconselho você a fazer exatamente isso. Dê aos agentes uma maneira de acessar os caminhos dos outros, procure o primeiro bloco do seu próprio caminho que não faz parte do outro caminho e vá para lá. Os problemas com esta técnica podem ser:

1. Como você decide se existe outra maneira aceitável de contornar o outro agente ou não? Você não quer esperar pelo outro agente, se houver espaço suficiente para contorná-lo. Uma falha na busca de caminhos ao considerar o outro agente é um sinal claro da situação que você deseja corrigir, mas no exemplo que você criou, não haverá uma falha na busca de caminhos. Mas você pode - com um pouco de cálculo - decidir se o caminho alternativo A * fornece apenas o outro agente em um pequeno círculo ou usa um caminho totalmente diferente, como o corredor norte.

2. Não sei até que ponto um agente pode viajar durante uma rodada / operação, mas se isso não for suficiente, ou se todos os agentes estiverem se movendo paralelamente, os dois agentes decidiriam esperar no outro extremo do caminho. Isso pode ser corrigido sinalizando ao outro agente que você libera o caminho dele.

Uma das soluções possíveis seria desativar a colisão de unidades em locais tão apertados.

Por exemplo, no jogo Starcraft, os trabalhadores (SCVs, Probes, Drones) não colidem uns com os outros ao minerar cristais.