迷宫程序设计

《迷宫程序设计》不但教你生成迷宫，更能提高你的编程和思维水平。

《迷宫程序设计》是一本专门探讨用编程的方式设计与实现迷宫的书，从*简单的方格迷宫讲起，介绍迷宫程序设计的基本方法和技巧，然后讲解如何设计形状各异的二维迷宫，比如把迷宫放到立方体表面、球面，甚至莫比乌斯环上去。*后讲解多维迷宫，让迷宫在不同的层次上穿行。书中的所有迷宫都附有代码。本书内容由浅入深，只需掌握*基本的编程概念即可以开始学习，尤其适合程序员和游戏爱好者阅读。

Jamis Buck是Ruby On Rails开发团队的核心成员，拥有多年的开源软件开发经验，曾在37Signal工作。他的写作风格平实易懂，尤其擅长将复杂的问题用简单的方式讲解清楚。

这本书让我找到了*纯粹的编程乐趣，推荐给所有对迷宫感兴趣的程序员！
——Corey Haines
Curious Nation公司首席技术官

阅读《迷宫程序设计》就像一次有趣的穿越迷宫之旅。本书将简明解释和实现代码巧妙结合起来，并借助每章末尾的想法来鼓励读者拓展所学内容。
Walter Pullen，迷宫思考网站作者

《迷宫程序设计》充满了极客算法的乐趣，是一本真正有趣的书！
Bruce Williams，CargoSense公司CTO

同类技术书籍的典范，一次令人印象深刻的算法和编程技术之旅。
David A. Black，《The Well-Grounded Rubyist》作者

以全新陌生的方式激发自己，这是我作为一个程序员提高编程水平的*佳方法。《迷宫程序设计》不但教你生成迷宫，更能提高你的编程和思维水平。
Chad Fowler，Wunderlist CTO

一本有趣、好玩的书，讲解生成和求解迷宫的所有概念和算法。要是我写《Maze Crusade》的时候有这本书就好了！
Amanda Wixted，Meteor Grove软件公司老板

这本书让我记起了一个有时会忘记的简单事实：编程很有趣。
Jeff Hardy，Basecamp程序员

第一部分 基础

第 1 章 学画随机迷宫 1

11 准备网格 2

12 二叉树算法 4

13 Sidewinder 算法 13

14 小试身手 17

第 2 章 自动处理和呈现迷宫 19

21 引入基本网格 19

22 实现二叉树算法 25

23 在终端上显示迷宫 27

24 实现 Sidewinder 算法 31

25 将迷宫渲染成图像 33

26 小试身手 36

第 3 章 勇闯迷宫 39

31 Dijkstra 算法 40

32 实现 Dijkstra 算法 43

33 查找最短路径 48

34 制作更具挑战性的迷宫 51

35 为迷宫着色 55

36 小试身手 59

第 4 章 通过随机游走避免偏差 61

41 理解偏差 61

42 Aldous-Broder 算法 64

43 实现 Aldous-Broder 算法 66

44 Wilson 算法 70

45 实现 Wilson 算法 74

46 小试身手 76

第 5 章 为随机游走添加约束条件 79

51 猎杀算法 79

52 实现猎杀算法 82

53 死角计数 85

54 递归回溯算法 88

55 实现递归回溯算法 92

56 小试身手 94

第二部分 进阶

第 6 章 设计不同形状的迷宫 97

61 介绍遮蔽 98

62 实现遮罩 102

63 ASCII 文本的遮罩 106

64 图像遮罩 109

65 小试身手 111

第 7 章 圆形迷宫 113

71 理解极坐标网格 114

72 绘制极坐标网格 118

73 自适应细分网格 121

74 实现极坐标网格 123

75 小试身手 131

第 8 章 探索其他网格 133

81 实现六边形网格 134

82 显示六边形网格 137

83 制作六边形迷宫 141

84 实现三角形网格 143

85 显示三角形网格 145

86 制作三角形迷宫 148

87 小试身手 149

第 9 章 编排和交织迷宫 153

91 编排迷宫 154

92 成本与距离 157

93 实现成本敏感的 Dikstra 算法 161

94 介绍交织和嵌入 166

95 生成交织型迷宫 173

96 小试身手 183

第三部分 更多的算法

第 10 章 增强交织型迷宫 187

101 Kruskal 算法 188

102 实现随机 Kruskal 算法 196

103 用 Kruskal 算法更好地交织迷宫 200

104 实现更好的交织型迷宫 202

105 小试身手 206

第 11 章 Prim 算法之旅 209

111 Prim 算法介绍 210

112 简化版 Prim 算法 214

113 真正的 Prim 算法 218

114 生长树算法 220

115 小试身手 224

第 12 章 组合与分割 227

121 Eller 算法 227

122 实现 Eller 算法 232

123 递归分割算法 237

124 实现递归分割算法 240

125 小试身手 245

第四部分 形状与表面

第 13 将迷宫扩展到更高维度 247

131 理解维度 248

132 介绍 3D 迷宫 250

133 添加第三个维度 252

134 展示 3D 迷宫 256

135 描述四维网格 259

136 小试身手 262

第 14 章 弯折迷宫 265

141 圆柱体迷宫 266

142 莫比乌斯环迷宫 268

143 立方体迷宫 272

144 球体迷宫 281

145 小试身手 291

附录 A 回顾迷宫算法 293

附录 B 比较迷宫算法 303

迷宫无处不在。从老鼠四处寻觅奶酪的心理学实验，到机器人演示，再到电影（《迷宫》）和电子游戏（《吃豆人》《塞尔达传说》《毁灭战士》），乃至你用手指和铅笔玩的书里的迷宫，几乎可以肯定你一定遇到过迷宫。
本书不是解决迷宫的大全，而是更加令人兴奋的东西。这是一部赋予你灵感的思想秘籍。
你将学习生成自己的迷宫——随机的迷宫，独一无二，每一个都与众不同。阅读本书将是一次发现之旅，在登上山峰前，你永远不知道会发现什么。
本书利用现有软件工程知识生成各种形状和大小的迷宫。我们将制作正方形、圆形、三角形和六边形迷宫，将迷宫放在圆柱体、立方体、球体甚至莫比乌斯环上。还会把迷宫延展到其他维度、挤压成任意形状，并对迷宫进行交织、编排、打印和折叠等各种处理。
阅读本书，你会发现自己时刻都能迸发出思想的火花，这也许是解决程序员迟钝、倦怠、沮丧的*有效方法。
如果你以前写过软件，那么这本书就适合你。你不需要拥有计算机科学学位，甚至不需要发布过任何大型软件项目——你只需要熟悉简单的编程概念。
也许你是一名游戏设计师。无论你的游戏复杂还是简单，迷宫都可以在其中发挥作用。任天堂的《塞尔达传说》，id Software的《毁灭战士》都隐式地使用了迷宫。其他游戏，例如南梦宫的《吃豆人》，其中的迷宫是完全可见的，它的作用与其说是谜题，不如说是障碍。Will Crowther的《巨洞冒险》使用迷宫发明了完整的互动文字游戏类型。
如果你是程序员——无论是业余爱好者还是专业人士，通常都非常喜欢学习和实现随机迷宫这样的算法。理解这些算法并将其变为现实是一个巨大挑战，沉浸其中，你会获得大量的满足感。
即使你不属于上述任何一种角色，也有可能发现迷宫算法的价值。我发现，适度的挑战和视觉上的吸引力可以非常有效地对抗倦怠和“程序员躺平症”。每天花点时间来摆弄一些不同算法，可以让头脑保持清新和灵活。这是很棒的大脑锻炼！

本书分为四个部分，介绍了十几种迷宫生成方法，涉及许多有趣的内容。
第一部分介绍一些基本技术，以及实现网格的基础知识。你将了解Dijkstra算法，用它来生成迷宫、深入了解隐藏在迷宫中的结构和模式。到第5章结束时，我们将学到六种生成弯曲小通道的方法。
第二部分将展示一些令人兴奋的方法来改变前五章的迷宫，将迷宫放入任意轮廓，将迷宫径向构建成圆形。同时将探索六边形和三角形等网格样式，甚至通过构建相互交织的通道来尝试3D迷宫。
第三部分介绍其余六种迷宫生成方法，包括一些改变算法的技巧，以生成交织密集的通道、房间，甚至无限长的迷宫。
*后，第四部分展示如何构建多维迷宫。我们将看到如何在迷宫的不同层之间添加上下移动的通道，甚至学习在3D对象（如立方体和球体）的表面生成迷宫的方法。
本书的示例代码都是用Ruby写的，但也完全可以用Python、C、Java、C#或任何其他语言实现。我希望这些示例写得足够清楚，即使大家不熟悉Ruby，也能一目了然。无论Ruby是否适合你，这本书都有足够的试验空间。
如果你打算使用Ruby，请用2.1或更高的版本Ruby，因为这些示例不能完全在早期Ruby版本上运行。
本书所有示例代码都可以从本书网站 下载。如果你不想重新实现整个网格框架，可以下载现成的代码，不过逐行编写代码无疑是*有效的学习方式！