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

Question

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

问题是一个网格格式的类 rogue-like AI 游戏，其中一个测试用例是如下 map :

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

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

规则是代理不能进入水中或墙壁。它只能移动到一个空方格或一个d格来捡起炸药。然后它可以用炸药炸开一堵墙。炸药一旦使用，就不能再次使用。最终目标是找到黄金并捡起来。代理只能上下或左右移动。没有对角线移动。

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

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

这张 map 的难点在于，A*搜索找不到通往目标的路径，唯一的解决办法是先捡起agent附近的炸药，然后炸掉金币右边的第二堵墙，然后向右去捡第二个炸药，然后回去炸掉金币右边的最后一堵墙，然后拿到金币。

我被以下问题困住了:

A* 搜索只会在找到目标时为我提供一条通往目标的路径。它没有给出“几乎在那里”的路径。

我可以使用 A* 来搜索黄金或炸药的路径，但不能同时搜索两者。看来，在这种情况下，我需要在一个例程中寻找先获得炸药然后获得黄金的最佳途径。这听起来太难了..请告诉我这是不是错误的方向。

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

谢谢阅读。

[编辑 30/05]
好吧，我设法使用了一个技巧来解决上面的 map 。基本上从黄金向后搜索，并假设第一层相邻的墙壁是否畅通无阻，看看代理是否可以移动到那里，也可以从那里捡起任何炸药。如果两者都有，那么它是一条直通路径。

但是，看着下面的 map ，我无语了.....有人可以帮忙吗？

一种。

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

B.

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

任何人都可以透露一些信息吗？，赞赏...

Answer 1

这不仅仅是一个寻路问题，但听起来您正试图将 A* 仅用于寻路。这就是它失败的原因。

您的 A* 搜索空间需要包括涉及拿起炸药和在墙上使用炸药(这会改变 map 的连接性)的状态变化。换句话说，您需要搜索所有可能的代理 Action 生成的游戏状态空间，而不仅仅是代理移动。

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

您可能会喜欢通过在每个状态中仅存储因使用炸药而导致的 map 更改而不是整个 map 的副本来节省空间(并使状态生成更高效)。根据您表示 map 的方式，这可能就像存储表示爆炸产生的 map 位置之间的附加连接的附加边一样简单。