Como posso fazer o acabamento A * mais rápido quando o destino é intransitável?

31

Estou criando um simples jogo 2D baseado em blocos, que usa o algoritmo de busca de caminhos A * ("Uma estrela"). Tenho tudo certo, mas tenho um problema de desempenho com a pesquisa. Simplificando, quando clico em um bloco intransitável, o algoritmo aparentemente percorre todo o mapa para encontrar uma rota para o bloco intransponível - mesmo que eu esteja ao lado dele.

Como posso contornar isso? Acho que poderia reduzir o caminho para a área da tela, mas talvez esteja faltando algo óbvio aqui?

user2499946
fonte
2
Você sabe quais peças são intransitáveis ​​ou apenas como resultado do algoritmo AStar?
user000user
Como você está armazenando seu gráfico de navegação?
Anko
Se você estiver armazenando nós atravessados ​​em listas, convém usar pilhas binárias para melhorar a velocidade.
ChrisC
Se for simplesmente muito lento, tenho uma série de otimizações a sugerir - ou você está tentando evitar pesquisas por completo?
Steven
1
Essa pergunta provavelmente teria sido mais adequada para a Ciência da Computação .
Raphael

Respostas:

45

Algumas idéias sobre como evitar pesquisas que resultam em caminhos com falha:

ID da ilha

Uma das maneiras mais baratas de concluir efetivamente as pesquisas A * mais rapidamente é não fazer nenhuma pesquisa. Se as áreas forem realmente intransitáveis ​​por todos os agentes, encha cada área com um ID de ilha exclusivo em carga (ou na tubulação). Ao encontrar o caminho, verifique se o ID da Ilha da origem do caminho corresponde ao ID da Ilha do destino. Se eles não corresponderem, não faz sentido fazer a pesquisa - os dois pontos estão em ilhas distintas e não conectadas. Isso ajuda apenas se houver nós realmente intransponíveis para todos os agentes.

Limite do limite superior

Limito o limite superior do número máximo de nós que podem ser pesquisados. Isso ajuda as pesquisas intransitáveis ​​a serem executadas para sempre, mas significa que algumas pesquisas passáveis ​​que são muito longas podem ser perdidas. Esse número precisa ser ajustado e realmente não resolve o problema, mas atenua os custos associados a longas pesquisas.

Se o que você está descobrindo é que está demorando muito , as seguintes técnicas são úteis:

Tornar iterações assíncronas e de limite

Deixe a pesquisa ser executada em um segmento separado ou um pouco em cada quadro, para que o jogo não pare de esperar pela pesquisa. Exiba animação do personagem coçando a cabeça ou batendo os pés, ou o que for apropriado enquanto aguarda o término da pesquisa. Para fazer isso de forma eficaz, eu manteria o estado da pesquisa como um objeto separado e permitiria a existência de vários estados. Quando um caminho é solicitado, pegue um objeto de estado livre e adicione-o à fila de objetos de estado ativo. Na atualização do pathfinding, retire o item ativo da frente da fila e execute A * até que A. seja concluído ou B. algum limite de iterações seja executado. Se concluído, coloque o objeto de estado novamente na lista de objetos de estado livre. Se não tiver sido concluído, coloque-o no final das 'pesquisas ativas' e passe para a próxima.

Escolha as estruturas de dados corretas

Certifique-se de usar as estruturas de dados corretas. Veja como meu StateObject funciona. Todos os meus nós são pré-alocados para um número finito - digamos 1024 ou 2048 - por motivos de desempenho. Eu uso um pool de nós que acelera a alocação de nós e também me permite armazenar índices em vez de ponteiros em minhas estruturas de dados que são u16s (ou u8 se eu tiver 255 nós máximos, o que eu faço em alguns jogos). Para minha busca de caminho, uso uma fila de prioridade para a lista aberta, armazenando ponteiros para objetos Node. Ele é implementado como um heap binário e classifico os valores de ponto flutuante como números inteiros, pois eles sempre são positivos e minha plataforma tem comparações lentas de ponto flutuante. Eu uso uma tabela de hashtags para o meu mapa fechado para acompanhar os nós que visitei. Ele armazena IDs de nó, não nós, para economizar em tamanhos de cache.

Coloque em cache o que você pode

Quando você visita um nó pela primeira vez e calcula a distância até o destino, armazene em cache no nó armazenado no Objeto de Estado. Se você revisitar o nó, use o resultado em cache em vez de calculá-lo novamente. No meu caso, ajuda não ter que fazer uma raiz quadrada nos nós revisitados. Você pode encontrar outros valores que podem ser pré-calculados e armazenados em cache.

Outras áreas que você pode investigar: use o pathfinding bidirecional para pesquisar em qualquer extremidade. Eu não fiz isso, mas como outros observaram, isso pode ajudar, mas não é sem suas ressalvas. A outra coisa na minha lista para tentar é encontrar o caminho hierárquico ou encontrar o caminho do cluster. Há uma descrição interessante na documentação da HavokAI Aqui, descrevendo seu conceito de cluster, que é diferente das implementações HPA * descritas aqui .

Boa sorte e deixe-nos saber o que você encontra.

Steven
fonte
Se houver agentes diferentes com regras diferentes, mas não muitos, isso ainda poderá ser generalizado com bastante eficiência usando um vetor de IDs, um por classe de agente.
MSalters
4
+1 por reconhecer que o problema é provavelmente áreas isoladas (não apenas ladrilhos intransponíveis) e que esse tipo de problema pode ser resolvido mais facilmente com cálculos iniciais do tempo de carregamento.
Slipp D. Thompson
Preenchimento de inundação ou BFS em cada área.
precisa saber é o seguinte
Os IDs de ilha não precisam ser estáticos. Existe um algoritmo simples que seria adequado caso houvesse necessidade de unir duas ilhas separadas, mas ele não pode dividir uma ilha posteriormente. Page 8 a 20 nestes slides explicar que algoritmo especial: cs.columbia.edu/~bert/courses/3137/Lecture22.pdf
kasperd
@kasperd é claro que nada impede que os IDs de ilha sejam recalculados, mesclados em tempo de execução. O ponto é que os IDs da ilha permitem confirmar se existe um caminho entre dois nós rapidamente, sem fazer uma pesquisa astar.
Steven Steven
26

O AStar é um algoritmo de planejamento completo , ou seja, se existe um caminho para o nó, o AStar é garantido para encontrá-lo. Conseqüentemente, ele deve verificar todos os caminhos fora do nó inicial para poder decidir que o nó do objetivo está inacessível. Isso é muito indesejável quando você tem muitos nós.

Maneiras de mitigar isso:

  • Se você sabe a priori que um nó está inacessível (por exemplo, não tem vizinhos ou está marcado UnPassable), retorne No Pathsem nunca chamar a AStar.

  • Limite o número de nós que o AStar irá expandir antes de terminar. Verifique o conjunto aberto. Se ficar muito grande, termine e retorne No Path. No entanto, isso limitará a integridade da AStar; portanto, ele pode planejar apenas caminhos de tamanho máximo.

  • Limite o tempo que o AStar leva para encontrar um caminho. Se o tempo acabar, saia e retorne No Path. Isso limita a integridade como a estratégia anterior, mas aumenta com a velocidade do computador. Observe que, para muitos jogos, isso é indesejável, porque jogadores com computadores mais rápidos ou lentos experimentam o jogo de maneira diferente.

mklingen
fonte
13
Gostaria de salientar que alterar a mecânica do seu jogo dependendo da velocidade da CPU (sim, encontrar rotas é um mecânico do jogo) pode se tornar uma má ideia, pois pode tornar o jogo bastante imprevisível e, em alguns casos, até impossível de jogar em computadores daqui a 10 anos. Por isso, prefiro limitar o A * limitando o conjunto aberto a tempo de CPU.
Philipp
@Philipp. Modificado a resposta para refletir isso.
mklingen
1
Observe que você pode determinar (razoavelmente eficiente, O (nós)) para um determinado gráfico a distância máxima entre dois nós. Esse é o problema do caminho mais longo e fornece um limite superior correto para o número de nós a serem verificados.
MSalters
2
@MSalters Como você faz isso em O (n)? E o que é 'razoavelmente eficiente'? Se isso é apenas para pares de nós, você não está apenas duplicando o trabalho?
Steven Steven
Segundo a Wikipedia, o problema do caminho mais longo é NP-hard, infelizmente.
Destino
21
  1. Execute uma pesquisa A * dupla a partir do nó de destino ao contrário e ao mesmo tempo no mesmo loop e aborte as duas pesquisas assim que uma for considerada insolúvel

Se o destino tiver apenas 6 blocos acessíveis ao seu redor e a origem tiver 1002 blocos acessíveis, a pesquisa será interrompida em 6 (duas) iterações.

Assim que uma pesquisa encontra os nós visitados da outra, você também pode limitar o escopo da pesquisa aos nós visitados da outra e terminar mais rapidamente.

Stephane Hockenhull
fonte
2
Há muito mais para implementar uma pesquisa bidirecional com uma estrela A do que está implícito na sua declaração, incluindo a verificação de que a heurística permanece admissível nessas circunstâncias. (Links: homepages.dcc.ufmg.br/~chaimo/public/ENIA11.pdf )
Pieter Geerkens
4
@StephaneHockenhull: Depois de implementar um A- * bidirecional em um mapa de terreno com custos assimétricos, garanto que ignorar o blá-blá acadêmico resultará na seleção de caminhos com falhas e cálculos incorretos de custos.
Pieter Geerkens
1
@MooingDuck: O número total de nós permanece inalterado, e cada nó ainda será visitado apenas uma vez; portanto, o pior caso de mapa dividido ao meio é idêntico ao A- * unidirecional.
Pieter Geerkens
1
@PieterGeerkens: No clássico A *, apenas metade dos nós é acessível e, portanto, é visitada. Se o mapa estiver dividido exatamente ao meio, quando você pesquisar bidirecionalmente, toque em (quase) todos os nós. Definitivamente um caso extremo
Mooing Duck
1
@MooingDuck: falei mal; os piores casos são gráficos diferentes, mas têm o mesmo comportamento - o pior caso para o unidirecional é um nó de objetivo completamente isolado, exigindo que todos os nós sejam visitados.
Pieter Geerkens
12

Supondo que o problema seja o destino inacessível. E que a malha de navegação não é dinâmica. A maneira mais fácil de fazer isso é ter um gráfico de navegação muito mais esparso (escasso o suficiente para que uma execução completa seja relativamente rápida) e use o gráfico detalhado apenas se o caminho for possível.

ClassicThunder
fonte
6
Isso é bom. Ao agrupar blocos em "regiões" e primeiro verificar se a região em que está o bloco pode ser conectada à região em que o outro bloco está, você pode jogar fora os negativos muito mais rapidamente.
precisa saber é o seguinte
2
Correto - geralmente se enquadra no HPA *
Steven
@ Steven Obrigado, eu tinha certeza de que não era a primeira pessoa a pensar em tal abordagem, mas não sabia como era chamada. Facilita muito o aproveitamento da pesquisa preexistente.
ClassicThunder
3

Use vários algoritmos com características diferentes

A * tem algumas características finas. Em particular, ele sempre encontra o caminho mais curto, se existir. Infelizmente, você também encontrou algumas características ruins. Nesse caso, ele deve procurar exaustivamente todos os caminhos possíveis antes de admitir que não existe solução.

A "falha" que você está descobrindo em A * é que ela não tem conhecimento da topologia. Você pode ter um mundo em 2-D, mas ele não sabe disso. Pelo que se sabe, no canto mais distante do seu mundo há uma escada que a leva diretamente ao mundo até o seu destino.

Considere criar um segundo algoritmo que esteja ciente da topologia. Como primeira passagem, você pode preencher o mundo com "nós" a cada 10 ou 100 espaços e, em seguida, manter um gráfico de conectividade entre esses nós. Esse algoritmo seria encontrado localizando nós acessíveis perto do início e no final e, em seguida, tentando encontrar um caminho entre eles no gráfico, se houver algum.

Uma maneira fácil de fazer isso seria atribuir cada bloco a um nó. É trivial mostrar que você só precisa atribuir um nó a cada bloco (você nunca pode ter acesso a dois nós que não estão conectados no gráfico). Em seguida, as arestas do gráfico são definidas para estar em qualquer lugar em que dois blocos com nós diferentes sejam adjacentes.

Este gráfico tem uma desvantagem: não encontra o caminho ideal. Apenas encontra um caminho. No entanto, agora ele mostra que A * pode encontrar um caminho ideal.

Ele também fornece uma heurística para melhorar suas subestimações necessárias para fazer o A * funcionar, porque agora você sabe mais sobre sua paisagem. É menos provável que você tenha que explorar completamente um beco sem saída antes de descobrir que precisava dar um passo atrás para avançar.

Cort Ammon - Restabelecer Monica
fonte
Tenho motivos para acreditar que algoritmos como os do Google Maps operam de maneira semelhante (embora mais avançada).
Cort Ammon - Restabelece Monica
Errado. A * está muito ciente da topologia, através da escolha da heurística admissível.
MSalters
No Google, no meu trabalho anterior, analisamos o desempenho do Google Maps e descobrimos que ele não poderia ter sido A *. Acreditamos que eles usam ArcFlags ou outros algoritmos semelhantes que dependem do pré-processamento de mapas.
MSalters
@MSalters: Essa é uma linha tênue interessante para desenhar. Argumento que A * desconhece a topologia porque se preocupa apenas com os vizinhos mais próximos. Eu diria que é mais justo dizer que o algoritmo que gera a heurística admissível está ciente da topologia, e não do próprio A *. Considere um caso em que há um diamante. A * segue um caminho um pouco, antes de voltar para tentar o outro lado do diamante. Não há como notificar A * que a única "saída" desse ramo é através de um nó já visitado (salvando a computação) com a heurística.
Cort Ammon - Restabelece Monica
1
Não é possível falar pelo Google Maps, mas o Bing Map usa uma estrela paralela bidirecional com pontos de referência e desigualdade de triângulo (ALT), com distâncias pré-calculadas de (e para) um pequeno número de pontos de referência e todos os nós.
Pieter Geerkens
2

Mais algumas idéias, além das respostas acima:

  1. Resultados de cache da pesquisa A *. Salve os dados do caminho da célula A na célula B e reutilize, se possível. Isso é mais aplicável em mapas estáticos e você precisará trabalhar mais com mapas dinâmicos.

  2. Coloque em cache os vizinhos de cada célula. Uma implementação * precisa expandir cada nó e adicionar seus vizinhos ao conjunto aberto a ser pesquisado. Se esses vizinhos forem calculados a cada vez, e não armazenados em cache, isso poderá diminuir drasticamente a pesquisa. E se você ainda não o fez, use uma fila de prioridade para A *.

user55564
fonte
1

Se o seu mapa for estático, basta que cada seção separada tenha um código próprio e verifique isso primeiro antes de executar o A *. Isso pode ser feito na criação do mapa ou mesmo codificado no mapa.

Ladrilhos intransitáveis ​​devem ter uma bandeira e, ao passar para um ladrilho como esse, você pode optar por não executar A * ou escolher um ladrilho ao lado que seja acessível.

Se você tem mapas dinâmicos que mudam com frequência, está sem sorte. Você precisa impedir que seu algoritmo pare antes da conclusão ou as verificações das seções são fechadas com frequência.

Madmenyo
fonte
Isso é exatamente o que eu estava sugerindo com um ID de área na minha resposta.
Steven
Você também pode reduzir a quantidade de CPU / tempo usada se o seu mapa for dinâmico, mas não mudar com frequência. Ou seja, você pode recalcular os IDs de área sempre que uma porta trancada for destrancada ou trancada. Como isso geralmente acontece em resposta às ações de um jogador, você excluiria pelo menos as áreas bloqueadas de uma masmorra.
uliwitness
1

Como posso fazer com que o A * conclua mais rapidamente que um nó é intransitável?

Faça um perfil de sua Node.IsPassable()função, descubra as partes mais lentas, acelere-as.

Ao decidir se um nó é passável, coloque as situações mais prováveis ​​no topo, para que na maioria das vezes a função retorne imediatamente sem se preocupar em verificar as possibilidades mais obscuras.

Mas isso é para acelerar a verificação de um único nó. Você pode criar um perfil para ver quanto tempo é gasto na consulta de nós, mas parece que seu problema é que muitos nós estão sendo verificados.

quando clico em um bloco intransitável, o algoritmo aparentemente percorre todo o mapa para encontrar uma rota para o bloco intransitável

Se o bloco de destino em si for intransitável, o algoritmo não deve verificar nenhum bloco. Antes mesmo de começar a encontrar o caminho, ele deve consultar o bloco de destino para verificar se é possível e, se não, retornar um resultado sem caminho.

Se você quer dizer que o destino em si é aceitável, mas é cercado por blocos intransitáveis, de modo que não há caminho, é normal que A * verifique o mapa inteiro. De que outra forma ele saberia que não há caminho?

Se este for o caso, você pode acelerar fazendo uma pesquisa bidirecional - dessa forma, a pesquisa iniciada no destino pode descobrir rapidamente que não há caminho e interromper a pesquisa. Veja este exemplo , envolva o destino com paredes e compare a direção bidirecional com a única.

Superbest
fonte
0

Faça o caminho para trás.

Se apenas o seu mapa não tiver grandes áreas contínuas de blocos inacessíveis, isso funcionará. Em vez de pesquisar em todo o mapa acessível, a localização do caminho pesquisará apenas a área inacessível fechada.

aaaaaaaaaaaa
fonte
Isto é ainda mais lento se os azulejos inacessíveis superam as telhas alcançáveis
Mooing Duck
1
@MooingDuck Os blocos inacessíveis conectados que você quer dizer. Esta é uma solução que funciona com praticamente qualquer design de mapa sensato e é muito fácil de implementar. Não vou sugerir nada mais sofisticado sem um melhor conhecimento do problema exato, como a implementação do A * pode ser tão lenta que visitar todos os blocos é realmente um problema.
Aaaaaaaaaaaa
0

Se as áreas que o jogador está conectado (sem teleporte, etc.) e as áreas inacessíveis geralmente não estão muito bem conectadas, você pode simplesmente fazer o A * a partir do nó que deseja alcançar. Dessa forma, você ainda pode encontrar qualquer rota possível para o destino e o A * para de procurar rapidamente áreas inacessíveis.

ent
fonte
O objetivo era ser mais rápido que o normal A *.
Heckel
0

quando clico em um bloco intransitável , o algoritmo aparentemente percorre todo o mapa para encontrar uma rota para o bloco intransponível - mesmo que eu esteja ao lado dele.

Outras respostas são ótimas, mas eu tenho que apontar para o óbvio - você não deve executar o caminho para um mosaico intransitável.

Esta deve ser uma saída antecipada do algo:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');
Kromster diz apoio Monica
fonte
0

Para verificar a maior distância em um gráfico entre dois nós:

(supondo que todas as arestas tenham o mesmo peso)

  1. Execute o BFS a partir de qualquer vértice v.
  2. Use os resultados para selecionar um vértice mais distante v, como o chamaremos d.
  3. Execute o BFS a partir de u.
  4. Encontre o vértice mais distante u, como o chamaremos w.
  5. A distância entre ue wé a maior distância no gráfico.

Prova:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)
  • Vamos dizer que a distância entre ye xé maior!
  • Então de acordo com isso D2 + R < D3
  • Então D2 < R + D3
  • Então a distância entre ve xé maior que a de ve u?
  • Então unão teria sido escolhido na primeira fase.

Crédito ao prof. Shlomi Rubinstein

Se você estiver usando arestas ponderadas, poderá realizar a mesma coisa em tempo polinomial executando Dijkstra em vez de BFS para encontrar o vértice mais distante.

Observe que estou assumindo que é um gráfico conectado. Também estou assumindo que não é direcionado.


A * não é realmente útil para um jogo simples baseado em blocos 2D, porque se eu entendi corretamente, assumindo que as criaturas se movem em 4 direções, o BFS alcançará os mesmos resultados. Mesmo que as criaturas possam se mover em 8 direções, o BFS preguiçoso que prefere os nós mais próximos do alvo ainda alcançará os mesmos resultados. A * é uma modificação Dijkstra que é muito mais cara em termos de computação que o BFS.

BFS = O (| V |) supostamente O (| V | + | E |), mas não realmente no caso de um mapa de cima para baixo. A * = O (| V | log | V |)

Se tivermos um mapa com apenas 32 x 32 blocos, o BFS custará no máximo 1024 e um A * verdadeiro poderá custar 10.000. Essa é a diferença entre 0,5 e 5 segundos, possivelmente mais se você levar em consideração o cache. Portanto, verifique se o seu A * se comporta como um BFS preguiçoso que prefere blocos mais próximos do destino desejado.

A * é útil para mapas de navegação onde o custo das bordas é importante no processo de tomada de decisão. Em um simples jogo aéreo baseado em blocos, o custo das arestas provavelmente não é uma consideração importante. Evento, se for, (blocos diferentes custam de maneira diferente), você pode executar uma versão modificada do BFS que adia e penaliza caminhos que passam por blocos que retardam o caractere.

Então sim BFS> A * em muitos casos quando se trata de blocos.

wolfdawn
fonte
Não sei se entendi esta parte "Se tivermos um mapa com apenas 32 x 32 blocos, o BFS custará no máximo 1024 e um A * verdadeiro poderá custar 10.000" Você pode explicar como chegou ao 10k número por favor?
Kromster diz apoio Monica
O que exatamente você quer dizer com "BFS preguiçoso que prefere nós mais próximos do destino"? Você quer dizer Dijkstra, BFS simples ou um com uma heurística (bem, você recriou A * aqui, ou como você seleciona o próximo melhor nó de um conjunto aberto)? Isso log|V|na complexidade do A * realmente vem da manutenção do conjunto aberto, ou do tamanho da margem, e para os mapas de grade é extremamente pequeno - sobre log (sqrt (| V |)) usando sua notação. O log | V | aparece apenas em gráficos hiperconectados. Este é um exemplo em que a aplicação ingênua da pior complexidade do caso fornece uma conclusão incorreta.
congusbongus
@congusbongus É exatamente isso que eu quero dizer. Não use uma implementação de baunilha de A *
wolfdawn
@KromStern Supondo que você use a implementação baunilha de A * para um jogo baseado em blocos, você obtém a complexidade V * logV, V sendo o número de blocos, para uma grade de 32 por 32 é 1024. logV, sendo bem aproximadamente o número de bits necessário para representar 1024, que é 10. Portanto, você acaba executando por um longo tempo desnecessariamente. Claro, se você se especializar a implementação de tirar proveito do fato de que você está executando em uma grade de telhas, você superar essa limitação, que é exatamente o que eu estava me referindo
wolfdawn