问题标签 [maze]

假设你想要一个 N x M 网格上的简单迷宫，有一条路径，有很多死角，但这看起来“正确”（即，就像有人手工制作的那样，没有太多小的死角等等）。有没有已知的方法可以做到这一点？

向前穿过迷宫很容易，但我似乎无法弄清楚一旦你遇到死胡同而不会返回太远，如何在迷宫中倒退以尝试新路线？

我正在开发一个简单的多人游戏，其中 2-4 名玩家被放置在迷宫中的不同入口点，需要到达一个目标点。生成迷宫一般来说很容易，但在这种情况下，游戏的目标是在其他人之前达到目标，我不希望生成算法过于偏爱一个玩家。

因此，我正在寻找一种迷宫生成算法，其中每个玩家从起点到目标的最佳路径不超过平均路径的 10%。通过这种方式，玩家或多或少处于平等的竞争环境中。谁能想出这样的算法？

（我有一个想法，但它没有经过深思熟虑，而且似乎远不是最佳的——我会把它作为答案发布。）

我正在尝试在 C++ 中创建一个随机迷宫，但我无法开始，因为我不知道如何创建网格或单元格。我怎么能创造它？而且我还想使用 ASCII 字符来创建它。我怎样才能将它存储在数组中？（任何人都可以提供示例代码和一些解释，以便我更好地理解它）

另一个问题：我需要学习和使用哪些数据结构？我打算使用 Eller 算法或 Kruskal 算法。

谢谢你们帮助我！我是一个初学者程序员，我想了解这个，因为这是我项目的一部分，谢谢你变化很大！

我正在尝试制作一个数据结构来表示 C++ 中的迷宫。

我需要保存的关于迷宫的所有数据都可以使用按位运算存储在 16 位整数中（以表示迷宫的每个单元格）：（_{来源：mazeworks.com）}16 位无符号整数

所以，我想出了一个 16 位整数的二维数组，我很适合我的 Maze 数据结构。我想保持数据结构的大小，以便我可以轻松创建非常密集的迷宫。

因此，我需要能够在运行时动态创建一个 16 位 n*m 大小的整数的二维数组。在某处，我读到 C++ 中的 2d 数组只是 [n *m] 大小的 1d 数组的语法糖，您可以通过 [row + col * width] 访问元素。

这是我的工作尝试：

有一些 C++ 知识的人对我的 Maze 课程有什么建议吗？我对 C++ 很陌生，所以这对我来说都是一次学习经历。

所以我正在用 Java 构建 pacman 游戏来自学游戏编程。

我有基本的游戏窗口，里面有 pacman sprite 和 ghost sprites，pacman 用箭头键移动，不会超出窗口的墙壁等。现在我正在尝试构建迷宫，就像在这个图片：

如果没有给我直接/完整的解决方案，有人可以指导我如何构建它吗？我在这里只谈论边界和管道（'T' 标记），你不能通过它们，你必须四处走动。不是吃豆人吃的那些点。

以下是我的问题：

1）创建这个迷宫最有效的算法/方法是什么？每次调用paint()方法时都必须绘制它，还是有办法只在游戏开始时绘制它而不再绘制？

2）这将如何实际绘制到屏幕上？我假设fillRect()将被使用？

3) 任何有关碰撞检测的提示（因此 pacman/ghosts 无法穿过墙壁）都会有所帮助。

4）关于如何计算管道之间的空白空间以便在它们之间填充点的任何提示也将非常有帮助。

谢谢

我在设计用于解决迷宫的算法时遇到问题。

我从这里使用了一个算法。http://www.cs.bu.edu/teaching/alg/maze/

查找路径（x，y）

1. 如果 (x,y 在迷宫外) 返回 false
2. 如果 (x,y 是目标) 返回 true
3. 如果 (x,y 未打开) 返回 false
4. 将 x,y 标记为解决方案路径的一部分
5. if (FIND-PATH(x,y 以北) == true) 返回 true
6. if (FIND-PATH(x,y 以东) == true) 返回 true
7. if (FIND-PATH(x,y 以南) == true) 返回 true
8. if (FIND-PATH(West of x,y) == true) 返回 true
9. 取消将 x,y 标记为解决方案路径的一部分
   10. 返回假

这是一个递归解决方案，我对其进行了修改，使其即使在找到退出后也会继续，以便它也可以找到其他解决方案。它似乎有效，只是它似乎找到了我所知道的可能解决方案总数的一半。

2. if (x,y is goal) return true 改为 return false。

任何人都知道这种算法可能会导致什么问题导致可能解决方案总数的一半？我也很难找到死胡同的总数，对此有什么建议吗？

这是一个用最少的代码解决的有趣问题。我预计递归解决方案将最受欢迎。

我们有一个迷宫，它被定义为一张人物地图，其中=是一堵墙，一个空间是一条路径，+是你的起点，#也是你的终点。一个非常简单的例子是这样的：

你能用尽可能少的代码编写一个程序来找到解决这种风格的迷宫的最短路径吗？

如果它适用于所有迷宫输入，例如那些具有跨越自身的路径或具有大量分支的迷宫输入，则可以加分。该程序应该能够适用于大型迷宫（例如，1024x1024 - 1 MB），并且如何将迷宫传递给程序并不重要。

“玩家”可以沿对角线移动。输入迷宫永远不会有对角线通道，因此您的基本动作集将是上、下、左、右。对角线运动只是向前看一点，以确定是否可以合并上/下和左/右。

输出必须是迷宫本身，其中最短路径使用星号字符 ( *) 突出显示。

我正在尝试编写一个程序，该程序有一个迷宫并试图找到出路。M 是入口，E 是出口，1 是墙壁，0 是路径。它应该找到每条路径并将 P 放入路径中。它应该找到所有可用的路径。现在它找到了路径的一部分。

这是代码：

这是测试仪：

这是当前的输出：

编辑：我添加了 if( board[x][y].equals("P") ) board[x][y] = "1"; 在 findIndex 的开头。我还修复了 x <= 0 问题。我将输出更新为我现在得到的（实际上是打印 348 个类似的板）。

我正在编写代码以读取代表“迷宫”的文件中的 7x15 文本块。

这是我的原始草稿，但由于它不断返回，所以这不起作用？对于它读取的每个字符。这是我正在测试的迷宫：

编辑： cout 正在打印：

我不是在逃避 \n 的吗？

我已经编码了几个小时，所以我认为这是一个我没有发现的简单错误，这让我现在绊倒了。谢谢！