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

Question

我想问一个作业问题.我知道有些人对这类问题的答案犹豫不决,但请相信我,我花了很多时间完成这项工作,并尽我所能.如果可以,请帮忙.

问题是网格格式的流氓式AI游戏,其中一个测试用例是如下地图:

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

g =金,d =炸药,〜=水,*=墙,<是我们的代理人,朝左.

规则是代理人不能进入水中,也不能进入隔离墙.它只能移动到空方格或广场上以拾取炸药.然后它可以用炸药炸开墙壁.一旦使用炸药,就不能再使用它.最终目标是找到黄金并捡起它.代理只能上下或左右移动.没有对角线移动.

由于文本格式化,在对角线方向的墙壁之间可能会出现一些额外的空格,但没有任何空格.

到目前为止,我已经使用Depth First Search来探索地图.(这个示例地图非常小,有一些很大).我还使用A*搜索计划路径,曼哈顿距离作为启发式.

这张地图有点棘手的是,A*搜索无法找到通往目标的路径,唯一的解决方案是首先拿起代理附近的炸药,然后将第二堵墙炸到金的右边,然后向右走,拿起第二个炸药,然后回去炸掉金矿右边的最后一道墙,然后拿出金币.

我遇到了以下问题:

1. 如果找到一个,*搜索只会给我一条通往目标的路径.它没有给出"几乎在那里"的路径.
2. 我可以使用A*搜索黄金或炸药的路径,但不能同时搜索两者.看来,在这种情况下,我需要在一个例程中搜索获得炸药的最佳路径,然后是黄金.这听起来太难了.请告诉我,如果这是错误的方向.

如果有人有任何建议或好建议,请赐教.我已经睡了两天了......

谢谢阅读.

[编辑30/05]好吧,我设法使用一个技巧来解决上面的地图.基本上从黄金向后搜索,并假设第一层邻近墙壁是否清晰,看看代理商是否可以移动到那里,也可以从那里拿起任何炸药.如果两者都是,那么这是一条通路.

但是,看下面的地图,我无言以对.....有人能帮忙吗？

一个.

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

B.

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

任何人都能摆脱一些光明吗？赞赏......

Answer 1

这不仅仅是一个寻路问题,但听起来你正试图用A*来寻找路径.这就是它失败的原因.

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

详细说明:A*使用的游戏状态应该是当前地图,所有对象(包括代理人)的位置以及代理商的炸药库存.状态变化可以包括代理人移动和(如果代理人有炸药)炸毁代理可能在旁边的任何墙段.后面的动作将导致后继状态具有不同的地图(以及少一个炸药).

您可以通过在每个状态中仅存储使用炸药而不是整个地图的副本对地图所做的更改来节省空间(并使状态生成更有效).根据您表示地图的方式,这可能非常简单,只需存储表示爆炸产生的地图位置之间的其他连接的附加边.