帮助使用 Java 解决 D&D 迷宫问题

Question

我一直在阅读 stackoverflow 上发布的其他一些问题，我对搜索算法的数量感到有点不知所措。我不是在寻找代码和更多涉及算法背景的页面，也许还有一些 sudo 代码。我知道有像 A* 这样的算法，但由于缺乏时间，我不知道我是否能够用这个算法完成程序。迷宫是使用服务器程序生成的，解算器连接到服务器以便向更多玩家发送命令。我无权访问服务器程序中的方法。我必须解决一个像 D&D 迷宫一样的迷宫。以下是游戏的基本概述：

经典的 D&D 电脑游戏由一个地牢（迷宫）组成，其中 游戏的目的是穿过地牢，进入 在迷宫的“入口”，在迷宫的“出口”离开。使 事情更具挑战性，地牢的布局未知 先验并且存在障碍（僵尸、焦油坑和门） 必须通过使用以下物体（票价、梯子和钥匙）来克服 一路上发现的。

我注意到许多其他帖子不必担心完成迷宫的障碍，这会是调整算法来补偿障碍的主要问题吗？我想知道像右手定则这样的东西是否可以很好地解决迷宫，如果不是，那么什么是尽可能简单的算法来解决迷宫（因为我必须尽快完成程序）。任何其他链接都会很棒，因为我知道我必须在 Objective-C 中再次完成这个程序，并且当发生这种情况时，我想实现比右手规则更强大的东西。感谢您的任何帮助。

Answer 1

对于简单的迷宫来说，您基本上沿着一条路径“行走”，直到到达十字路口。那时你记录下所有的选择。然后你选择一个（使用你喜欢的任何启发式，对于你的右手技术，你总是“向右走”）。一旦您记录了选项，您就可以将其填充到堆栈中。然后你继续前进。

当你读到一个死胡同时，你要么“走回去”，或者如果可能的话，简单地弹出堆栈，选择另一个选项并从那里继续。要往回走，您只需将每次移动记录在堆栈上，然后开始展开堆栈，直到到达最后一个交叉点。

你可以简单地继续这样做，注意怪物以及诸如你可以通过的东西，或者你错过的物品，作为“死胡同”。然后，您可以在十字路口记录这些可通行的死胡同，这样，如果您回到十字路口仍在寻找出口，您可以检查您的库存中是否有“钥匙”或“剑”或通过它所需的任何东西。当你回来后，检查未探索路径的选项，以及被你可以打败的东西阻挡的路径。如果你有可以打败怪物的物品，你可以重走那条路，打败怪物然后继续前进。

我不记得这种技术是否适用于有循环的迷宫。因为您应该始终能够判断您以前是否去过某个地点，所以应该在您身后留下一条“面包屑”痕迹或记录您所见过的位置。

它当然不会告诉你最佳路径或最佳得分路径，它只会在你偶然发现它时带你到达出口。

当您发现交叉点时，您还可以将地下城表示为内存中的连通图，图中的每个节点都是交叉点，每个节点之间的路径长度（步数）是图中的转换。您还可以将此图中的障碍物表示为节点。

因此，如果你遇到吸血鬼，它将是大厅尽头没有出口的节点。之后，当你拿到十字架和木桩时，你就会“知道”吸血鬼在哪里，并且能够遍历图表回到吸血鬼（当然假设它没有移动）。

诀窍是真正构建这个图，并使用股票图遍历算法（其中有很多，而且并不那么困难）从一个节点导航到另一个节点。

但对于穿越一个简单的迷宫，堆栈技术非常有效。

附录：

对于简单的迷宫，单个堆栈就足够了。我不知道你的地图是如何布局的，也不知道你是如何导航的，等等。

但你可以做的是每次移动时，只需将移动放在堆栈上即可。然后，当您想要原路返回时，您开始弹出堆栈并朝移动的相反方向前进，直到回到交叉点，然后从那里开始。

这只是对您还不知道其布局的树进行“深度优先”搜索。但同样重要的是，您还可以通过其他方式跟踪您去过的地方。例如，如果您的迷宫表示为大量地板和墙块，则您可以捕获在简单列表中输入的每个地板块的坐标。

这样做的原因是，如果迷宫中有循环，您就不想“向前走”到已经走过的空间。显然你需要在回溯时这样做。但探索的时候，你需要知道你见过什么，没见过什么。如何跟踪取决于地图的数据结构。

考虑这个简单的迷宫：

# ########
# ########
# # #    #
# # #### #
# #a    b#
# # #### #
#   #    #
##### ####
#    c   #
# ########

您可以看到，您只需要在位置 a、b 和 c 处压入堆栈。如果您能够标记您去过的楼层，您的地图在第一个十字路口处可能会如下所示：

#.########
#.########
#.# #    #
#.# #### #
#.#a    b#
#.#.#### #
#. .#    #
##### ####
#    c   #
# ########

并且您的堆栈将如下所示：

{d,d,d,d,d,d,d,l,u}

7 次向下，一次向左，一次向上。

如果您无法标记地图，您可以改为跟踪坐标。这一切都取决于。

Answer 2

我个人会尝试使用递归来查找路径。您可以使用 if 语句来处理陷阱，而 not 则可以使用 return 语句来告诉您路径。

  public static int recursion(int x, int y) {
    if (location == end) {
      return 0; //found the end
    }
    if (deadEnd) {
      //backtrack
    }
    if (trapName) {
      //put whatever you need to do to get around it
    }
    if (x+1 <= edge) {
      recursion(x+1,y); //Moves right
    }
  }

这或多或少是伪代码。希望它有帮助！