A*找不到AI游戏中的路径

Question

我想问一个作业问题。我知道有些人在回答这类问题时犹豫不决，但相信我，我花了很多时间在这个任务上，我已经尽我所能了。所以如果可以的话请帮忙。

这个问题是一个网格格式的类似流氓的人工智能游戏，其中一个测试用例是如下所示的地图：

~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~
~~   g**   d *~~
~~   ** *   * ~~
~~   **  ***  ~~
~~   **  d    ~~
~~   **    <  ~~
~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~

g=gold，d=dynamite，~=water，*=wall，是我们的代理人，面向左。

规则是，代理人不得进入水中或墙壁。它只能移动到一个空的广场或一个d广场来捡起炸药。然后它可以用炸药炸墙。一旦使用了炸药，就不能再使用了。最终的目标是找到金子并捡起来。探员只能上下移动或左右移动。没有对角线移动。

由于文本格式的原因，墙壁之间在对角线方向上可能出现一些额外的空间，但没有任何空间。

到目前为止，我已经使用深度优先搜索来探索地图。(这个示例地图很小，有些很大)。我还使用了A*搜索来规划路径，以曼哈顿距离作为启发。

这张地图的棘手之处在于，A*搜索找不到通往目标的道路，唯一的解决办法是先拿起炸药，然后把第二堵墙炸到黄金的右边，然后右转，拿起第二个炸药，然后返回到黄金右边的最后一道墙，然后拿到金子。

我被困在以下问题上：

1. *搜索只给我一条通往目标的路，如果它找到了的话。它没有给出一条“几乎-那里”的道路。
2. 我可以用A*来寻找黄金或炸药的路径，但不能同时搜索两者。看来，在这种情况下，我需要寻找最好的途径，首先获得炸药，然后黄金，在一个例行。这听起来像hard..Please告诉我，如果这是错误的方向。

如果有人有任何建议或好建议，请指点我。我已经两天没睡觉了..。

感谢您的阅读。

编辑30/05好，我设法用一个技巧来解决上面的地图。基本上，从黄金中寻找，并假设第一层相邻的墙壁是干净的，看看代理人是否可以移动到那里，也可以从那里捡起任何炸药。如果两者兼而有之，那就是一条直通之路。

但是，看看下面的地图，我是speechless.....can，有人帮我吗？

一个。

~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~
~g***       *** ~~
~***         d**~~
~**           *d~~
~*      ^      *~~
~**           **~~
~d**         **d~~
~ d**       **d ~~
~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~

B.

~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~
~~                  ~~
~~     ^            ~~
~~    ***           ~~
~~   *****          ~~
~~  ***g***         ~~
~~  ********        ~~
~~   ***dd***       ~~
~~    *****d**      ~~
~~     ***d*d**     ~~
~~      ******d*    ~~
~~       ********   ~~
~~        ********  ~~
~~         d*d**d*  ~~
~~          **d**   ~~
~~           ***    ~~
~~            *     ~~
~~                  ~~
~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~

有人能说点什么吗？，谢谢.

Answer 1

这不仅仅是一个路径查找问题，但听起来你只是在尝试使用A*来查找路径。这就是它失败的原因。

您的A*搜索空间需要包括状态更改，这些状态更改涉及到拾取炸药并在墙上使用炸药(这会改变地图的连通性)。换句话说，您需要搜索由所有可能的代理动作生成的游戏状态的空间，而不仅仅是代理的移动。

详细说明一下: A*使用的游戏状态应该是当前地图、所有对象(包括代理)的位置以及代理的炸药库存。状态更改可以包括代理的移动和(如果该代理有炸药)炸毁该代理可能旁边的任何墙段。后一种行动将导致继承国拥有不同的地图(以及更少的炸药)。

您可能会喜欢节省空间(并使状态生成更有效)，方法是只在每个状态中存储由于使用炸药而引起的对映射的更改，而不是整个映射的副本。取决于您表示地图的方式，这可能就像存储额外的边缘一样简单，表示由于爆炸而产生的映射位置之间的额外连接。