编程与软件工程journal.stuffwithstuff.com
房间与迷宫：程序化地牢生成器
Rooms and Mazes: A Procedural Dungeon Generator
2014 — 2022，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章详细讲解了一种程序化地牢生成算法：先随机放置房间，再把剩余空间挖成迷宫，最后移除部分死胡同并连接区域，并配有可交互的 JavaScript 演示。作者逐步展示每个阶段的生成效果，让读者直观理解算法的演进过程。
为什么经久不衰：它把算法讲解、可运行代码和可视化演示结合得恰到好处，是程序化生成领域的经典教程，多年后仍是学习地牢生成的入门范本。
HN 评论精选
赞文章用交互式演示讲解算法的形式
这篇文章是散文与可交互示例结合的绝佳范例。看着地牢从无到有被一点点开凿出来，真让人着迷。JavaScript 常被低估的一点，就是它能让那些有趣但枯燥的概念活起来。Mike Bostock 的算法页面是另一个好例子。
akanet查看英文原文
I think this article is a fantastic example of how you can blend prose with working interactive examples. The examples make you really trance out watching dungeons being carved out of nothing. I think an often-discounted aspect of JavaScript's appeal is its ability to breathe life into a bunch of fascinating but otherwise dry concepts. Another terrific example is this page by the prolific Mike Bostock: http://bost.ocks.org/mike/algorithms/
掌握领域不变量可以免去回溯，写出更简单高效的生成算法
我以前也写过迷宫生成器。理解迷宫的代数性质很有帮助：每面墙最多与其他墙相交一次。遵守这条规则，用任何随机过程都能生成迷宫，无需回溯或记录状态，可达性天然保证。用铅笔随手画只相交一次的随机线条，就能得到完全连通的迷宫。理解问题领域的不变量和规则，能帮你写出更快更简单的代码。
ralfn查看英文原文
A long time ago i also wrote a maze generator. It's helpfull to understand the algebra of (fully accessible) mazes: 1. Every wall may intersect with some other wall at most once. (this includes the outer wall) With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute. Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze. The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.
补充行走者算法及 Spelunky 等相关生成技术资源
另一种廉价有效的程序化关卡生成技术是用“行走者”：从某点出发沿直线走，随机间隔转向，沿途留下走廊和房间。Vlambeer 的 Nuclear Throne 就是这样生成关卡的。想更学术地了解，可以看关于 Spelunky 的研究论文；Derek Yu 开源了初代 Spelunky 代码，Darius Kazemi 对其关卡生成技术做了很好的拆解。
doomlaser查看英文原文
Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.vlambeer.com/2013/04/02/random-level-generation-in-wasteland-kings/ If you'd like a more academic look into procedural 2d game generation, there's a nice research paper here, that describes a method and talks about Spelunky a lot (the king of procedural 2d level generation, in my book): http://games.soe.ucsc.edu/sites/default/files/cig10_043CP2_115.pdf Additionally, Derek Yu open sourced the code to the original Spelunky, and Darius Kazemi created a great breakdown of its level generation techniques here, also with interactive examples: http://tinysubversions.com/spelunkyGen/index.html The action roguelike genre, particularly the roguelike FPS, is a vital new area being explored by indie game developers. It reminds me of the way 2D platformers were mined, explored, and iterated upon starting around 7 or 8 years ago. Right now, it doesn't take much to stand out from the herd, as many of the most popular games in the genre don't do much beyond generating a bunch of square rooms and connecting them with doors and short, straight corridors. In my opinion, developers in the genre should take more cues from Doom, and less from original Zelda dungeons moving forward. And, from a more holistic perspective, nobody really cares about mazes, room placement on a grid, and connective corridors when playing a game, beyond a brute mechanical level. A more useful framework for thinking of generating levels might be to go one level of abstraction higher. Think about a level as a story for your player, and generate setpieces or 'acts' that you want the player to experience as they play. Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced with breathers for rhythm and flow. Place those sets on a path in a map, then figure out a way to connect them together at the lower level with rooms, objects, enemies, and corridors.
D&D 规则书自带的地牢生成算法可在游玩中逐步使用
最近重拾第一版 D&D，才发现书后附有整套地牢生成“算法”。我用它来玩单人推演，生成的地牢非常疯狂：斜向通道、宽度不一的走廊、跨多层又折返的楼梯、要临时去其他层才能进入的房间等。有趣的是生成顺序取决于队伍选择探索哪扇门，本就设计为在游玩过程中逐步生成。
wintermutestwin查看英文原文
Interesting to have the explanations of how it is built and the code, but the end results pale in comparison to this amazing tool which I frequently use in my D&D campaigns: https://watabou.itch.io/one-page-dungeon Other interesting generators here as well: https://watabou.itch.io/ And this prior discussion is full of great links: https://news.ycombinator.com/item?id=30338074
历次讨论
同类还值得读
开源应用架构
The Architecture of Open Source Applications
《开源软件架构》（AOSA）是一本在线免费书，邀请知名开源项目的作者亲自剖析其内部设计，涵盖 SQLAlchemy、LLVM、Audacity、Apache、Bash 等系统。
编程与软件工程上首页 9 次 · 2011–2024aosabook.org编辑精选编程语言简史：简短、不完整且多半错误
A Brief, Incomplete, and Mostly Wrong History of Programming Languages
一篇以戏谑、故意不准确的方式回顾编程语言史的博客文章，用夸张轶事和讽刺定义串起 Lisp、C、C++、Java、JavaScript、PHP 等语言。
编程与软件工程上首页 8 次 · 2009–2021james-iry.blogspot.comSQLite 是如何测试的
How SQLite is tested
SQLite 官方文档页，系统介绍 SQLite 的测试体系：多种测试方法（TCL 测试、模糊测试、回归测试、静态分析等）和海量测试用例，展示了这个小型开源项目如何靠极致测试获得…
编程与软件工程上首页 8 次 · 2009–2025sqlite.org编辑精选高级编程语言（2009）
Advanced programming languages (2009)
Matt Might 的经典文章，按用途推荐“高级编程语言”：如果追求就业就选主流语言，如果追求表达力、学术研究或创业，则推荐 Haskell、OCaml、Scala 等函数式语…
编程与软件工程上首页 8 次 · 2009–2022matt.might.net我的 Forth 与栈机器经历
Yosefk - My history with Forth & stack machines
作者以亲身经历回顾了使用 Forth 语言和栈式机器的历程：既赞叹其简洁优雅、代码量小、可自举的优点，也坦率指出栈操作在实际编程中的痛苦，以及 Forth 社区文化中的问题。
编程与软件工程上首页 8 次 · 2010–2024yosefk.com编辑精选