Como encontrar um obstáculo?

Como representar a seguinte situação, o melhor agente ( @) precisa chegar ao objetivo ( $). O caminho está bloqueado por um fosso ( ~~~). Está disponível um ancinho (ou algum outro dispositivo, como botas de caminhada aquática), que permitirá atravessar o obstáculo.

.....~~~...   . ground
...=.~~~...   = rake
.....~~~.$.   ~ water
.@...~~~...   @ agent
.....~~~...   $ goal

Como localizar corretamente o caminho @para, $desde que não haja um caminho imediatamente disponível? Meu caminho deveria ter não apenas custo, mas também pré-requisitos?

UPD : O problema é que o objetivo não está acessível e o rake é apenas um dos muitos objetos possíveis no mapa. A pergunta então é "como fazer o agente entender que precisa do rake?"

Estou pensando em uma pilha de objetivos, o pathfinding terá que ser anotado :

• Comece com um objetivo get $
• Tente encontrar caminho a caminho $- com a capacidade de caminhada na água necessária.
• Empurre a meta get waterwalking.
• A pilha de objetivos está agora get waterwalking, get $
• De alguma forma, ache que o rake dá caminhadas na água, vamos renomeá-lo para barco.
• Caminho para varrer. O objetivo principal alcançado, retira-o da pilha, o objetivo é get $.
• Caminho para $- agora temos capacidade e podemos alcançar a meta.

Todo o caminho para encontrar coisas é apenas uma busca pelo caminho mais curto em um gráfico. Para resolver seu problema, a única alteração que você precisa aplicar é adicionar algumas arestas extras (representando o caminho que o barco pode seguir) e criar um algoritmo simples de localização de caminhos. não importa se você usa BFS, Dijkstra ou A *, basta implementar um algoritmo de localização de caminho normal com algumas arestas extras. para obter mais informações sobre localização de caminhos em uma página de wiki de verificação de gráfico

Eu faria isso com algum tipo de solução em árvore de comportamento - você encaminha para o objetivo e anota todos os obstáculos que estão bloqueando seu A *. Se você falhar, verifique se há objetos que possam ajudar a superar esses obstáculos, nesse caso, o caminho para esse objeto. Repetir. Isso significa que o agente precisa tentar encontrar o caminho para a meta e falhar antes de ter a idéia de usar ferramentas, o que pode levar tempo, especialmente se houver um mundo enorme de peças que precisam ser verificadas. Pode não parecer muito fora do lugar que o agente leva algum tempo para pensar em como resolver o problema.

Eu posso imaginar uma solução real e hardcore, no entanto. Adicione outra dimensão ao caminho que encontra a grade. Portanto, no caso de um mapa 2D, você cria a grade de localização 3D. Neste exemplo simples, essa nova dimensão teria apenas duas profundidades, mas em um jogo real ela aumentaria rapidamente.

Em z = 0, você mapeia o terreno em circunstâncias normais, o que significa que os ladrilhos de água são considerados intransitáveis.

Em z = 1, você mapeia o terreno como está durante o rake, o que significa que os ladrilhos de água são considerados acessíveis (mas se você tiver, por exemplo, ladrilhos de parede, eles podem permanecer sólidos).

A localização do caminho é um A * comum nas dimensões x e y, o que significa que todas as células da grade são consideradas como tendo acesso aos seus vizinhos. Na dimensão z, no entanto, o A * NÃO pode se espalhar.

Exceto onde está o ancinho. O objeto rake atua como uma abertura entre z = 0 e z = 1 na grade de localização de caminho.

Isso significa que o A * inundará o preenchimento externo em z = 0, atingirá a água e ficará sem opções - então ele se espalhará para z = 1 através do ladrilho de ancinho e em z = 1 (onde a água é passável) encontre o caminho para a meta. O efeito é que o NPC sem hesitação se move para o rake e depois move o caminho mais curto para o objetivo.