0

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

经典的 D&D 电脑游戏由地牢（迷宫）组成，游戏的目的是穿过地牢，从迷宫的“入口”进入并在“出口”退出。为了使事情更具挑战性，地牢的布局是先验未知的，并且必须通过使用沿线发现的物体（车费、梯子和钥匙）来克服障碍（僵尸、沥青坑和门）。方式。

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

4

2 回答 2

1

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

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

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

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

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

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

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

诀窍实际上是在你去的时候建立这个图，并使用股票图遍历算法（其中有很多，而且它们并不难）从一个节点导航到另一个节点。

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

附加物：

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

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

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

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

考虑这个微不足道的迷宫：

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

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

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

你的堆栈看起来像：

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

7 下，1 左，1 上。

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

于 2011-09-24T21:35:07.010 回答
0

我个人会尝试使用递归来查找路径。您可以使用 if 语句来处理陷阱，而不是使用 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
    }
  }

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

于 2011-09-25T03:16:16.480 回答