Ajustando o AStar para encontrar o local mais próximo do destino inacessível

11

Eu implementei o AStar em Java e ele funciona bem para uma área com obstáculos onde o destino escolhido é acessível.

No entanto, quando o destino está inacessível, o "caminho" calculado não chega ao local mais próximo (ao local inacessível), mas é um caminho aleatório.

Existe uma maneira viável de ajustar o AStar para encontrar o caminho para o local mais próximo de um destino inacessível?

path-finding Shivan Dragon
fonte

Respostas:

20

Acompanhe o nó com o menor EstimatedDistanceToEnd(ou seja, o menor h(x)) e, se nenhum nó final estiver acessível para voltar atrás, volte para trás desse nó.

BlueRaja - Danny Pflughoeft
fonte
Simples. Eu amo isso!
30512 John McDonald
Eu apenas dei um tapa na cabeça e fiquei "doh" quando li sua resposta. Obrigado!
Shivan Dragon
1

Esta não é realmente uma pergunta A *. A * tem tudo a ver com encontrar um caminho do ponto A ao ponto B. Mesmo que possa ser estendido, os resultados podem ser facilmente confusos e imprevisíveis. Em vez disso, você precisa de um algoritmo que escolha o destino acessível mais próximo.

Aqui está uma maneira de fazer isso: Se A * retornar um caminho válido (nós de início / fim no caminho correspondem aos nós de entrada), retorne o caminho. De outra forma...

  • Iniciar pesquisa a partir do nó inicial
  • Atravessar todos os nós vinculados (lembre-se de sinalizar os visitados para evitar recursões infinitas)
  • Compare distâncias ao destino para encontrar o nó mais próximo
snake5
fonte
Algo como o Flood Fill parece apropriado pt.wikipedia.org/wiki/Flood_fill observe que você ainda precisa A * do nó inicial ao nó com a menor distância. Observe também que isso sempre envolve a inspeção de todos os nós conectados e, portanto, pode ser extremamente lento.
Roy T.
Sim, pode ser lento. Mas a lentidão provavelmente viria de ter os nós espalhados pela memória; isso pode ser facilmente consertado. Além disso, é possível acelerar isso sacrificando alguma precisão - basta pular links que estão muito distantes ou apontam na direção errada.
usar o seguinte comando
1
@Roy: A *, BFS, e todos os algoritmos pathfinding semelhantes será exatamente tão lento como inundação-fill, porque todos eles necessidade de inspecionar cada nó conectado para garantir que não é nenhum caminho até o fim. No entanto, existem maneiras de aliviar esse problema; veja aqui .
BlueRaja - Danny Pflughoeft 30/08/2012