迷宫程序设计

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

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

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

第一部分 基础

第 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