¿Cómo encontrar un obstáculo?

Cómo representar mejor la siguiente situación: el agente ( @) necesita llegar a la meta ( $). El camino está bloqueado por un foso ( ~~~). Se encuentra disponible un rastrillo (o algún otro dispositivo, como botas para caminar) que permitirá cruzar el obstáculo.

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

¿Cómo encontrar correctamente la ruta desde @a $siempre que no haya una ruta inmediatamente disponible? ¿Debería mi camino no solo costar sino también requisitos previos?

UPD : El problema es que el objetivo no es accesible y el rastrillo es solo uno de los muchos objetos posibles en el mapa. La pregunta entonces es "¿cómo hacer que el agente entienda que necesita el rastrillo?"

Estoy pensando en una pila de objetivos, la búsqueda de caminos tendrá que ser anotada :

• Comience con un gol get $
• Trate de encontrar la ruta a $- la ruta existe con la capacidad de caminar necesaria.
• Empujar gol get waterwalking.
• La pila de objetivos es ahora get waterwalking, get $
• De alguna manera, descubra que el rastrillo le da un paseo por el agua, cambiemos el nombre de barco
• Camino al rastrillo. Se alcanzó el objetivo superior, sáquelo de la pila, el objetivo es get $.
• Camino a $- ahora tenemos capacidad y podemos alcanzar la meta.

Todo el camino para encontrar cosas es solo una búsqueda del camino más corto sobre un gráfico. Para resolver su problema, el único cambio que necesita aplicar es agregar algunos bordes adicionales (que representan el camino que puede tomar el barco) y hacer un algoritmo de búsqueda de camino simple. no importa si usa BFS, Dijkstra o A *, simplemente implemente un algoritmo de búsqueda de ruta normal con algunos bordes adicionales. Para obtener más información sobre la búsqueda de rutas en un gráfico, consulte la página wiki

Lo haría con algún tipo de solución de árbol de comportamiento: su camino hacia la meta y tomar nota de todos los obstáculos que han estado bloqueando su A *. Si falla, verifica si hay objetos que pueden ayudar a superar esos obstáculos, en ese caso, el camino hacia ese objeto. Repetir. Esto significa que el agente debe tratar de llegar al objetivo y fracasar antes de tener la idea de usar herramientas, lo que puede llevar tiempo, especialmente si hay un gran mundo de mosaicos que todos deben verificarse. Sin embargo, podría no parecer demasiado fuera de lugar que el agente se tome un tiempo para contemplar cómo resolver el problema.

Sin embargo, puedo imaginar una solución real y dura. Agregue otra dimensión a su cuadrícula de búsqueda de ruta. Por lo tanto, en el caso de un mapa 2D, hace que la cuadrícula de trazado de ruta sea 3D. En este ejemplo simple, esta nueva dimensión solo tendría una profundidad de dos, pero en un juego real se haría grande rápidamente.

En z = 0 mapeas el terreno durante circunstancias normales, lo que significa que las baldosas de agua se consideran intransitables.

En z = 1 mapeas el terreno tal como está mientras tienes el rastrillo, lo que significa que las baldosas de agua se consideran transitables (pero si tienes, por ejemplo, baldosas de pared, esas podrían permanecer sólidas).

El hallazgo de la ruta es un A * ordinario en las dimensiones xey, lo que significa que se considera que cada celda de la cuadrícula tiene acceso a sus vecinos. Sin embargo, en la dimensión z, NO se permite que A * se propague.

Excepto donde está el rastrillo. El objeto rastrillo actúa como una abertura entre z = 0 y z = 1 en la cuadrícula de búsqueda de ruta.

Esto significa que el A * se inundará en z = 0, golpeará el agua y se quedará sin opciones; luego se extenderá a z = 1 a través del mosaico de rastrillo y en z = 1 (donde el agua es transitable) encuentra su camino hacia la meta. El efecto es que el PNJ sin dudar se mueve hacia el rastrillo, y luego mueve el camino más corto hacia la meta.