本篇将尝使用canvas + wasm画一个迷宫，生成算法主要用到连通集算法，使用wasm主要是为了提升运行效率。然后再用一个最短路径算法找到迷宫的出路，最后的效果如下：

1. 用连通集算法生成迷宫

生成迷宫的算法其实很简单，假设迷宫的大小是10 * 10，即这个迷宫有100个格子，通过不断地随机拆掉这100个格子中间的墙，直到可以从第一个格子走到最后一个格子，也就是说第一个格子和最后一个格子处于同一个连通集。具体如下操作：

那这个连通集应该怎么表示呢？我们用一个一维数组来表示不同的已连通的集合，初始化的时候每个格子的值都为-1，如下图所示，假设迷宫为3 * 3，即有9个格子：

每个索引在迷宫的位置：

负数表示它们是不同的连通集，因为我们还没开始拆墙，所以一开始它们都是独立的。

现在把3、4中间的墙拆掉，也就是说让3和4连通，把4的值置成3，表示4在3这个连通集，3是它们的根，如下图所示：

再把5、8给拆了

再把4、5给拆了：

这个时候3、4、5、8就处于同一个连通集了，但是0和8依旧是两个不同的连通集，这个时候再把3和0中间的墙给拆了：

由于0的连通集是3，而8的连通集也是3，即它们处于同一个连通集，因此这个时候从第一个格子到最后一个格子的路是相通的，就生成了一个迷宫。

我们用UnionSet的类表示连通集，如下代码所示：

class UnionSet{ constructor(size){ this.set = new Array(size); for(var i = this.set.length - 1; i >= 0; i--){ this.set[i] = -1; } } union(root1, root2){ this.set[root1] = root2; } findSet(x){ while(this.set[x] >= 0){ x = this.set[x]; } return x; } sameSet(x, y){ return this.findSet(x) === this.findSet(y); } unionElement(x, y){ this.union(this.findSet(x), this.findSet(y)); } }

我们总共用了22行代码就实现了一个连通集。上面的代码应该比较好理解，对照上面的示意图。如findSet函数得到某个元素所在的set的根元素，而根元素存放的是负数，只要存放的值是正数那么它就是指向另一个结点，通过while循环一层层的往上找直到负数。unionElement可以连通两个元素，先找到它们所在的set，然后把它们的set union一下变成同一个连通集。

现在写一个Maze，用来控制画迷宫的操作，它组合一个UnionSet的实例，如下代码所示：

class Maze{ constructor(columns, rows, cavans){ this.columns = columns; this.rows = rows; this.cells = columns * rows; //存放是连通的格子，{1: [2, 11]}表示第1个格子和第2、11个格子是相通的 this.linkedMap = {}; this.unionSets = new UnionSet(this.cells); this.canvas = canvas; } }

Maze构造函数传三个参数，前两个是迷宫的列数和行数，最后一个是canvas元素。在构造函数里面初始化一个连通集，作为这个Maze的核心模型，还初始化了一个linkedMap，用来存放拆掉的墙，进而提供给canvas绘图。

Maze类再添加一个生成迷宫的函数，如下代码所示：

//生成迷宫 generate(){ //每次任意取两个相邻的格子，如果它们不在同一个连通集， //则拆掉中间的墙，让它们连在一起成为一个连通集 while(!this.firstLastLinked()){ var cellPairs = this.pickRandomCellPairs(); if(!this.unionSets.sameSet(cellPairs[0], cellPairs[1])){ this.unionSets.unionElement(cellPairs[0], cellPairs[1]); this.addLinkedMap(cellPairs[0], cellPairs[1]); } } }

生成迷宫的核心逻辑很简单，在while循环里面判断第一个是否与最后一个格子连通，如果不是的话，则每次随机选取两个相邻的格子，如果它们不在同一个连通集，则把它们连通一下，同时记录一下拆掉的墙到linkedMap里面。