创建（真正的）随机迷宫的最佳逻辑
我一直在尝试制作一个简单的小游戏来测试我的逻辑，这是一个简单的迷宫，很丑陋，而且到目前为止很糟糕。
引擎工作得很好，考虑到迷宫已经存在（一个矩阵），它甚至可能很有趣，但我无意绘制一堆地图，这可能会在矩阵的 400 (20x20) 字段上设置值。不好笑。
然后我创建了一个函数来随机化它，为每个字段设置地板/墙壁，并且（我预计）并非每个地图都是可获胜的。然后我做了另一个函数来检查地图是否可玩（接收两个点，并检查它们之间是否有有效的路径，然后我只需传递开始和结束。非常漂亮）并且它起作用了。
如果您没有注意到，这是创建我的随机迷宫的一种非常愚蠢的方法，原因如下：
1 - 它可能非常容易（巨大的地板岛，或一堆墙在一起） ，只制作一条极其可见的路径，创建一个愚蠢的（尽管有效）迷宫
2 - 这可能是有史以来创建完美随机迷宫最快的方法，但同时它也可能是最慢的，需要长达......无限长的时间。当我将网格设置为 30x30 或更大时（当某些内容没有溢出时），这种差异会更加明显
3 - 这很愚蠢，而且违背了逻辑本身。
在我看来，我从一开始就没有打算这样做，正如所描述的那样，一件事导致了另一件事。
所以我开始思考如何制作一个美丽的（充满路径、棘手且可获胜的）迷宫，然后我考虑制作带有预先设计的入口的微小（比方说）5x5 块，并将它们安装在一起适合，但它会违背我的真实随机愿望，以及我不愿意手绘它。
然后我想到了一个创建随机路径的函数，运行一次到终点，然后运行几次到接近终点的地方，还有一些交叉点之类的东西，一些创建死胡同，这对我来说似乎更好，但我无法想象它会创造出一个像样的迷宫。
您可以在此链接中查看我到目前为止所做的操作。< /strong>
注意：我无意用任何东西伤害任何人的电脑。第一个打开它的人，请在这里评论说它是安全的。 - 完成（谢谢你，Jonno_FTW）
如果您仍然不信任它，请使用虚拟机。
OBS：我知道这不是开发任何东西的最佳方式。我应该得到一个像样的游戏引擎，bla bla bla，这对我自己来说是一种挑战。
I've been trying to make a little simple game just to test my logics, and it's a simple labyrinth, it's ugly, and so far sucky.
The engine works pretty well, given that the labyrinth already exists (a matrix), it could be even enjoyable, but I have no intention on drawing a bunch of maps, which might be setting values on 400 (20x20) fields of a matrix. not funny.
Then I've created a function to randomize it, setting floor/wall for each field, and (I expected that) not every map is winnable. then I've made another function which checks if the maps is playable (receives two points, and checks if there's a valid path between them, then I just pass the start and the end. Pretty nifty) and it worked.
If you haven't noticed, this is a VERY stupid way of creating my random labyrinth for the following reasons:
1 - It might come out really easy (giant isles of floor, or a bunch of walls together, making only one, extremely visible path, creating a stupit (though valid) labyrinth
2 - It is potentially the fastest way of creating a perfect random labyrinth EVER, but at the same time it's potentially the slowest too, taking as long as... infinite. This difference is noticed more when I set the grid for 30x30 or more (when something is not overflown)
3 - It's dumb and an offence to logic itself.
In my deffense, I didn't plan making it this way from the beginning, as described, one thing led to another.
So I've started thinking about ways to do a beautiful (full of paths, tricky and winnable) labyrinth, then I've thought about making tiny small (let's say) 5x5 blocks with predesigned entrances and mount them together in a way that it fits, but it would go against my true random desire, as well as my unwillingness to draw it by hand.
Then I've thought about a function to create a random path, run it once to the end, and run it several times to somewhere close to the end, and some crossings and stuff, some creating dead ends, which seemed better to me, but I just couldn't imagine it creating a decent labyrinth.
You can check what I've done so far in this link.
Note: I have no intentions in harming anyone's pc with anything.First one to open it, please comment here saying that it's safe. - Done (thank you, Jonno_FTW)
If you still don't trust it, use a Virtual Machine.
OBS: I know this is not the best way of developing anything. I should get a decent game engine, bla bla bla, it was some kind of challenge for myself.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
我已经完成了迷宫生成。您不想随机放置东西并进行验证。相反，您从一个起点生成它。
选择一个起点，向随机方向移动。有选择新方向的随机概率。永远不要进入一个被占领的广场，如果你撞到一个，当前的路线就结束了。如果当前路径结束，请选择一个您已经访问过的正方形，然后选择一个新方向，然后像第一个方向一样进行随机行走。重复此操作，直到迷宫达到您想要的程度。
方向改变的概率应该是一个输入参数，因为它会产生很大的差异。请注意，如果您正在玩 3D 迷宫，则垂直转弯的几率应该比水平移动的几率低很多。
I've done maze generation. You don't want to place stuff randomly and validate. Instead, you generate it out from a starting point.
Pick a starting point, move in a random direction. Have a random probability of picking a new direction. Never move into an occupied square, if you bump into one the current trail ends. If the current trail ends pick a square you have already visited and pick a new direction and do a random walk like you did for the first one. Repeat until the maze is as full as you want it to be.
The probability of the direction change should be an input parameter as it makes quite a difference. Note that if you are doing a 3D maze the odds of a vertical turn should be a lot lower than the odds of a horizontal move.
这是一个专门介绍迷宫的大型网站：
http://www.astrolog.org/labyrnth/algrithm.htm
解释什么类型里面有很多迷宫，回顾了生成算法和解决算法，有很多很酷的图片。
Here's an expansive website dedicated to labyrinths:
http://www.astrolog.org/labyrnth/algrithm.htm
Explains what types of labyrinths there are, goes over the generation algorithms and the solution algorithms, has a lot of cool pictures.
看一下我的 Roguelike 游戏 Tyrant 的源代码：
Dungeon.java 代码
有许多不同的地图生成技术用于生成不同的关卡类型。但最基本的模式是迭代以下内容：
这是一个屏幕截图你得到的东西类型（从迷宫结构看小地图）：
暴君截图http://www.freeimagehosting.net/uploads/af45502c9c.png
Have a look at the source code in my Roguelike game, Tyrant:
Code for Dungeon.java
There are a lot of diferent map generation techniques used to produce the different level types. But the most basic pattern is to iterate the following:
Here's a screenshot of the type of thing you get (Look at the mini-map from the maze structure):
Tyrant screenshot http://www.freeimagehosting.net/uploads/af45502c9c.png
你的问题让我想起了XScreensaver Maze程序。查看其屏幕截图，看看这是否是所需的效果。
看起来它的迷宫生成算法来自维基百科。
Your question makes me think of the XScreensaver Maze program. Look at its screenshots to see if that's the desired effect.
It looks like it took its maze generation algorithm from Wikipedia.
维基百科有一篇关于迷宫生成算法的精彩文章
Wikipedia has a great article on Maze generation algorithms
如何创建随机迷宫取决于您想要它的外观。如果您正在创建一些设计有很多死胡同的东西，那么您可以“随机”追踪从起点到终点的路径，然后随机填充空白区域，本质上是从固体材料块。例如，想象你有一块石碑。第一步是开辟“解决方案”路径。然后你就进去并走完所有的死胡同。
如果你想要一些比“益智”更“游戏”的东西，那么创建一堆以不同方式组合在一起的图块可能是正确的选择。据我所知，《暗黑破坏神》游戏就是这么做的。一些预先设计的“集合”以及关于它们如何组合在一起的规则。您可以用“三个开放空间，然后两个封闭空间”之类的内容来标记块的四个侧面，然后如果另一块也有匹配的描述，则可以将它们放在一起。
之后，您所要做的就是弄清楚如何一致地呈现“随机”行为。
How you create a random labyrinth will depend on what you want it to look like. If you're creating something that's designed to have a lot of dead ends, then you can just "randomly" trace a path from the start point to the end point, and then randomly fill in the empty spaces, essentially carving the path out of a solid block of material. E.g. imagine you had a stone tablet. First step would be to carve the "solution" path. Then you'd go in and make all of the dead ends.
If you want something that's more "play" than "puzzle", then creating a bunch of tile pieces that fit together in different ways is probably the way to go. That's how the Diablo games did it as far as I can tell; a number of predesigned "sets" and rules about how they fit together. You'd mark the four sides of the block with things like "three open spaces followed by two closed," and then if another piece also has a matching description, they can be put together.
After that, all you have to do is figure out how you can consistently render "random" behavior.
实际上，Al Lowe 在他的一款《Leisure Suit Larry》游戏（我相信是 LSL 3）中使用了一个技巧，可能会有所帮助。
基本上，他制作了一个玩家必须穿过的竹林“迷宫”。然而，他并没有为每个屏幕创建一个单独的“方形”迷宫，而是简单地“翻转”他已经创建的一个屏幕，并通过用单个“竹墙”图形阻塞各个入口来形成死胡同。
也许您可以这样做：让生成器雕刻一个有效的迷宫，然后告诉它沿着某些路径放置死胡同块。这将确保至少有一条有效、开放的路径到达“终点线”，并防止玩家只是在超级简单的布局中漫步。
它还将使 30x30 的迷宫更加可行，因为计算机不必测试 900 方格网格中的每个方格的有效性。
There's actually a trick that Al Lowe used for one of his Leisure Suit Larry games (LSL 3, I believe) that might be helpful.
Basically, he made a bamboo forest 'maze' that the player had to navigate. Rather than creating a separate 'square' of maze for each screen, however, he simply 'flipped' the one screen he had already created and made dead ends by blocking various entrances with a single 'bamboo wall' graphic.
Perhaps you could do the same: have the generator carve a valid maze, and then tell it to place dead-end blocks along some of the paths. That would ensure that there's always at least one valid, open path to the 'finish line', as well as preventing players from just strolling through a super-easy layout.
It'll also make a 30x30 maze more workable, since the computer won't have to test every square of a 900-square grid for validity.