HTML 迷宫
今天补个遗，将很久以前研究 HTML5 的时候写的生成迷宫、迷宫寻路程序整理出来。
下载链接在文章最后。
简介
为什么要做这个 HTML5 迷宫程序？因为我喜欢、我愿意。也是向老程序员学习（见第5节）。
里面都有什么？包括生成迷宫，以及，走出迷宫的 Javascript 程序，绘制迷宫使用了 Canvas。
怎么做的？主要参考了这几篇文章：
这个网站提供在线的 Java Applet 示例，很直观。
然后代码自己写，因为没有可以照搬的，照搬的也不是按照我希望的方式去工作的。看明白原理之后，就开始设计自己的迷宫程序了。
原理
这是此次补遗最难的部分，因为我真的不记得是怎么做到的了！唯一有点儿印象的，是A*搜索算法，即包含当前探索节点与目标节点距离的估值函数的改进型A搜索算法，相当于对A搜索算法剪枝吧。我是这么认为的 
在网页上生成迷宫，主要解决下面几个问题：
- 生成迷宫
- 挑选迷宫起点和终点
- 探索迷宫
- 绘制迷宫和探索结果（路径）
前面3个问题，和 HTML 一毛钱关系都没有。完全依靠数据结构和算法。你把数据结构和算法搬到 C# 里面去，用 WPF 画迷宫也是可以的。
迷宫（尤其是矩形的）可以看作是很多个小格子，叫做 Cell，每个小格子都被墙（Wall）环绕，组合在一起。所以一开始，迷宫如果绘制出来，看上去应该是这样的：
然后，从选定的起点开始，从周围相邻的 Cell 里面随便挑选一个，打破这2个 Cell 之间的墙。接着，继续，直到所有的 Cell 都被访问过了。迷宫的生成大概就是这么个原理，当然，圆形、六角形的迷宫会有区别，这个方面，参考上面列出的 Wiki 上面的解释最清楚了。
探索迷宫的话，需要先知道起点和终点（目标点）的 Cell 的坐标。在我的程序里面，起点 Cell （start_cell）是随机挑选的，终点 Cell （goal_cell）则是指定的一个位置，这样做只是为了让出来的迷宫图形比较好看，否则可能出现起点和终点太靠近，迷宫画出来没有“好复杂！”的感觉
为了避免盲目探索，每次从当前 Cell 开始挑选下一个邻近的可以走通的 Cell 时，都会计算一个 g 值，也就是下一个 Cell 和目标 Cell 的距离值，这个值用来剪枝，距离小的，优先走。在我的程序里面，这个值是用 init_g_h_value 函数来计算的。为了提高迷宫处理速度，已经预先将所有节点的 g 值计算完毕，存在迷宫数组里面了，即用“空间换时间”是也。
有兴趣的话，可以修改程序里面的 maze_g_value、maze_h_value 两个参数变量的值，看看不同的效果，你会发现路径会从松散到紧凑变化。
程序
先看网页布局。虽然写程序是从生成迷宫到探索到显示的顺序，但是，实现起来，要反过来，先把最终呈现效果给设计出来。
顺便插一句：做软件，可以没有测试，可以没有文档，甚至可以没有需求，但，你不能没有设计。说得“极端”了点儿，但这只是为了强调“设计”的重要性。
界面上有一个 canvas，一个 div。Canvas 用来绘制迷宫，div 用来输出调试信息，将程序中 _debug_ 变量设置为 true 即可开启。（_debug_ 作为全局变量，命名方式和其它全局变量不同，这是因为这个调试变量是我今天写这篇博客时临时加的，反映了我最近对于全局变量命名的口味。以前写的，则是另外一种口味，人总是会变的嘛。）
下面是程序设计，
这个迷宫程序需要 jQuery，1.7 以后的版本应该都可以，默认用的是 jquery-1.9.1.js。如果你是用 IE 9 以前的版本来运行这个网页程序，你还需要一个 excanvas.js 文件。这些 js 文件都和程序网页放在一层目录里面就可以了。
打开网页以后，程序立即运行：
- $(document).ready 调用 generate_maze 函数；
- generate_maze 将迷宫每个 cell 的数据填入 maze_cells 数组；
- 接着 solve_maze；
- solve_maze 将探索过程记录进入 parsed_cells 数组；
- 接着 reformate_path；
- reformate_path 将 parsed_cells 中的实际路径挑选出来，塞入 final_path 数组，这样，绘制迷宫的时候就比较简单了；
- 最后是 draw_maze，在 canvas 上面绘图。只有在这里，这个迷宫程序才和 HTML5 搭上了点儿边。
这里有个技术细节。
由于生成和探索迷宫的过程中，需要不停的记录当前状态、取出上一个状态的堆栈入栈和出栈操作，因此，当迷宫尺寸比较大的时候，会出现“堆栈溢出”的消息。为此，我自己用 cell_stack 数组实现了一个堆栈来保存探索过程中的状态信息。
效果
网页打开就是这样，每F5一次就刷一个新的迷宫给你。红色的点是起点，蓝色的点是终点（目标点），紫色的点是探索过的路径，绿色的点是最终走通的路径。
下载
到这里下载，只有一个 HTML 文件。另外还需要 jQuery（文件名是 jQuery-1.9.1.js，如果你用了其它版本的 jQuery，请到 maze.html 里面对应修改） 和 excanvas 文件，和我的迷宫程序网页放在一个目录即可。
最新文章
- 自定义cell自适应高度
- css3动画简介以及动画库animate.css的使用
- 如何应对ISP乱插广告（案例分析）
- 利用PHP的register_shutdown_function来记录PHP的输出日志，模拟析构函数
- PHP基础班初学心得：关于网页创作
- this的使用
- docker的四种网络模式
- ****JFinal 部署在 Tomcat 下推荐方法
- python多线程，多进程
- 去除MyEclipse频繁弹出的Update Progress窗口
- 关于viewports 设备像素比 密度
- Java Socket通信实现私聊、群聊
- nginx高级用法汇总
- [转]使用Git Submodule管理子模块
- Linux终端命令全面介绍
- e3.7.2-MyEclipse-10.7安装SVN插件
- day04 --class --homework
- HAL库定时器
- 开发发布npm module包
- Halcon学习之边缘检测函数