问题标签 [maze]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
3 回答
3742 浏览

java - 设置已访问房间的迷宫求解回溯算法问题

我寻求是否有人可以帮助我解决我的房间搜索算法
我正在尝试实现一个回溯算法来解决迷宫问题。我被困在我应该记住我已经访问过的房间的地方。
迷宫由房间组成,每个房间有 4 个面——北、东、南和西。每个房间都通过在所需一侧制作一扇门连接到下一个房间,即room1.createNorth(roomName) 在北边创建一个新房间,一个新房间有南门连接回第一个房间,正如您在我的 Room 课程中看到的那样。

这是我切碎的房间类,它代表迷宫中的每个房间。我删除了与我处理北侧的方法相同的南、西和东方向。

迷宫看起来像这样:http: //i.stack.imgur.com/2KePs.jpg其中 S 是起点

我的迷宫课

这是我的主要课程 public class Main {

问题出在我的findPathTo(roomName)方法中,它找到了通往房间的路线。如果我进入房间 D4,那么我的算法只会从“A4”向东移动一次到“B4”房间,然后它会无限循环,堆栈只会随着房间“B4”而增长。为什么它不前进到下一个房间“B3”或“C4”?

编辑:这是工作代码

0 投票
1 回答
786 浏览

recursion - 回溯迷宫算法似乎并没有一路回溯

基本上,我有这个:首先,一堆代码生成一个不可穿越的迷宫。它根据一些参数在二维数组的某些空间中随机设置墙壁。然后我有一个回溯算法通过它来敲掉墙壁,直到整个东西都可以遍历。问题是,程序似乎并没有回到堆栈中。

这是非常标准的回溯代码。该算法从一个随机位置开始,然后以伪代码进行:

move(x, y){
如果你可以往上走但还没到过:
move (x, y - 1)
如果你可以往右走但还没到过:
move (x + 1, y)
。 ..
}

其他方向依此类推。每次移动时,都会在坐标处设置两个单独的 2D 布尔数组(一个是临时的,一个是永久的),以表明您已经在某个元素中。一旦它不能继续前进,它就会检查永久二维数组,看看它是否无处不在。如果不是,它会随机选择一个在已访问空间和未访问空间之间的墙(根据临时数组)并将其移除。这整个过程是在一个while循环中调用的,所以一旦它遍历了迷宫的一大块,临时二维数组就会被重置,而另一个则保留,它会在另一个随机位置再次遍历,直到永久二维数组显示整个迷宫已经被遍历。move 方法中的检查与临时二维数组进行比较,而不是永久数组。

这几乎可行,但我一直在最终生成的迷宫中找到一些无法到达的区域。否则,它会按照我想要的方式生成迷宫。问题是,我发现这样做的原因是它不会一直回到堆栈中。

如果我将其更改为检查临时二维数组是否完成而不是永久数组(从而使其在一次运行中进行一次完整遍历以将其标记为完成,而不是在多次迭代中进行完整运行),它将继续下去等等。我必须设置一个计数器来打破它。结果是一个“迷宫”,移除了太多太多的墙壁。检查算法采用的路线,我发现它没有正确回溯,并且没有回到堆栈中足够远的距离,并且经常只是在一个元素上卡住了几十次递归,然后无缘无故地宣布自己完成根本没有拆除零的墙需要拆除。

我尝试过两次运行前面的那个,但它一直在敲掉不需要敲掉的墙壁并使迷宫变得太稀疏。我不知道为什么会发生这种情况。

0 投票
3 回答
449 浏览

java - 国王的迷宫

我正在为一场编程比赛做准备,我正在解决一些我过去无法回答的难题。其中之一是国王的迷宫。-50<x<50本质上,您会得到一个代表“令牌”的 NxN 数字数组。您必须从位置 1,1(我假设数组索引中的 0,0)开始并在 N,N 处结束。您必须在您访问的单元格上拾取令牌,并且您不能踩没有令牌的单元格(由 0 表示)。如果你被 0 包围,你就输了。如果迷宫没有解决方案,则输出“无解决方案”。否则,您会输出通过将您拾取的代币相加可以获得的最高数字。

我不知道如何解决这个问题。我想你可以写一个迷宫算法来解决它,但这需要时间,而且在编程比赛中你只有两个小时来解决多个问题。我猜我缺少某种模式。任何人都知道我应该如何处理这个问题?

另外,提到这个问题是针对高中生的,这可能会有所帮助。

0 投票
2 回答
3407 浏览

algorithm - 迷宫求解最优不左转算法

我正在做一个项目,我需要使用最少的右转和不左转来解决迷宫。

只要右转最小化,行进的距离是无关紧要的。我们被要求使用回溯算法和最佳(时间)算法来实现我们的程序。

对于回溯算法,我将使用堆栈。我的算法是这样的:

  • 将所有四个可能的起始方向压入堆栈。
  • 走一条路,尽可能直走。
  • 如果我们到达迷宫的尽头,则返回当前路径长度为最佳。
  • 如果我们到达死胡同,回到最后可能的右转并采取它。
  • 如果当前路径长度大于当前最佳路径长度,则返回最后可能的右转并采取它。

我想知道是否有人可以指出我的最佳算法方向。

我很难想出比回溯更好的东西。

0 投票
2 回答
370 浏览

depth-first-search - Java:随机化 DFS 运行以构建迷宫的麻烦

我在随机访问从一个节点到它的邻居时遇到了麻烦,很少访问整个图(一个 MxN 数组,在这个测试 4x4 中),我不明白我在这里做错了什么。

这段代码给了我这样的输出:

即使我正在验证下一步的位置(通过布尔值 southValid、eastValid 等)

0 投票
3 回答
186 浏览

java - Java:随机化方法递归调用的顺序

对于 Java 中的 DFS 迷宫生成,我想随机化 DFS 的递归调用的顺序:

我怎样才能做到这一点?

0 投票
1 回答
728 浏览

wpf - WPF 布局/地图/迷宫生成器

我正在尝试为用户提供用于在 WPF 中生成框布局的控件。我希望能够添加/删除行和列,并将每个框设置为 0 或 45 度旋转。结果将是一种正方形的蜂窝。我正在考虑使用 ListBox 和 WrapPanel 来解决这个问题,但在考虑之后,我认为 Canvas 可能会更好。有什么简单的方法我可以遵循,还是只是在画布位置上反复试验?

0 投票
1 回答
3096 浏览

algorithm - 用块代替墙的深度优先搜索迷宫生成算法

我正在尝试在我的游戏中实现深度优先搜索算法。我一直在研究这个网页: http: //www.mazeworks.com/mazegen/mazetut/index.htm,却发现我无法将它与块而不是墙一起使用。我所说的块是指覆盖整个单元格的正方形,而不仅仅是边缘。我认为这样做会更容易,但现在我不太确定。有人做过吗?如果是这样,怎么做?(伪代码很好)。或者,如果它更容易,我应该只使用墙壁方法吗?

0 投票
3 回答
2542 浏览

java - 从文本文件创建迷宫图:Java

我需要从包含表示为邻接列表的多个“迷宫”的文本文件中制作图表。名单如下:

每个“迷宫”的第一行包含迷宫的起始节点(第一个字母)和迷宫的结束节点(第二个字母)。

我已将文本文件解析为所有行(包括空白行)的 ArrayList,然后解析为行 ArrayLists 的 ArrayList(单独的迷宫列表)。我通过在空白行上拆分完整的文本来做到这一点。我现在的问题是我无法弄清楚如何使用我的节点类从这些“迷宫”中构造一个图表。这是我的节点类:

有人可以指出我正确的方向吗?

0 投票
1 回答
1007 浏览

prolog - Visual Prolog - 迷宫问题

我已经定义了房间门的列表:

还有一些谓词:

我正在寻找从一个房间到另一个房间的方法:

此谓词有效并返回:

Jest droga:feba

Jest droga:fedcba

这是房间列表,我必须将其从 a 传递到 f。run():- stdio::write("\nDroga zf do a"), R_list=["f"], go("f", "a", R_list), 失败。但是这个,一无所获。而且您可能会注意到,这与前一种情况正好相反。