怎么随机选取两个相邻的格子呢？这个虽然没什么技术难点，但是实现起来需要动一番脑筋，因为在边上的格子没有完整的上下左右四个相邻格子，有些只有两个，有些有三个。笔者是这么实现的，相对来说比较简单：

//取出随机的两个挨着的格子 pickRandomCellPairs(){ var cell = (Math.random() * this.cells) >> 0; //再取一个相邻格子，0 = 上，1 = 右，2 = 下，3 = 左 var neiborCells = []; var row = (cell / this.columns) >> 0, column = cell % this.rows; //不是第一排的有上方的相邻元素 if(row !== 0){ neiborCells.push(cell - this.columns); } //不是最后一排的有下面的相邻元素 if(row !== this.rows - 1){ neiborCells.push(cell + this.columns); } if(column !== 0){ neiborCells.push(cell - 1); } if(column !== this.columns - 1){ neiborCells.push(cell + 1); } var index = (Math.random() * neiborCells.length) >> 0; return [cell, neiborCells[index]]; }

首先随机选一个格子，然后得到它的行数和列数，接着依次判断它的边界情况。如果它不是处于第一排，那么它就有上面一排的相邻格子，如果不是最后一排则有下面一排的相邻格子，同理，如果不是在第一列则有左边的，不是最后一列则有右边的。把符合条件的格子放到一个数组里面，然后再随机取这个数组里的一个元素。这样就得到了两个随机的相邻元素。

另一个addLinkedMap函数的实现较为简单，如下代码所示：

addLinkedMap(x, y){ if(!this.linkedMap[x]) this.linkedMap[x] = []; if(!this.linkedMap[y]) this.linkedMap[y] = []; if(this.linkedMap[x].indexOf(y) < 0){ this.linkedMap[x].push(y); } if(this.linkedMap[y].indexOf(x) < 0){ this.linkedMap[y].push(x); } }

这样生成迷宫的核心逻辑基本完成，但是上面连通集的代码可以优化， 一个是findSet函数，可以在findSet的时候把当前连通集里的元素的存放值直接改成根元素，这样就不用形成一条很长的查找链，或者说形成一棵很高的树，可直接一步到位，如下代码所示：

findSet(x){ if(this.set[x] < 0) return x; return this.set[x] = this.findSet(this.set[x]); }

这段代码使用了一个递归，在查找的同时改变值。
union函数也可以做一个优化，findSet可以把树的高度改小，但是在没有改小前的union操作也可以做优化，如下代码所示：

union(root1, root2){ if(this.set[root1] < this.set[root2]){ this.set[root2] = root1; } else { if(this.set[root1] === this.set[root2]){ this.set[root2]--; } this.set[root1] = root2; } }

这段代码的目的也是为了减少查找链的长度或者说减少树的高度，方法是把一棵比较矮的连通集成为另外一棵比较高的连通集的子树，这样两个连通集，合并起来的高度还是那棵高的。如果两个连通集的高度一样，则选取其中一个作为根，另外一棵树的结点在查找的时候无疑这些结点的查找长度要加上1 ，因为多了一个新的root，也就是说树的高度要加1，由于存放的是负数，所以进行减减操作。在判断树高度的时候也是一样的，越小就说明越高。

经验证，这样改过之后，代码执行效率快了一半以上。

迷宫生成好之后，现在开始来画。

2. 用Canvas画迷宫

先写一个canvas的html元素，如下代码所示：

<canvas></canvas>

注意canvas的宽高要用width和height的属性写，如果用style的话就是拉伸了，会出现模糊的情况。

怎么用canvas画线呢？如下代码所示：

var canvas = document.getElementById("maze"); var ctx = canvas.getContext("2d"); ctx.moveTo(0, 0); ctx.lineTo(100, 100); ctx.stroke();

这段代码画了一条线，从(0, 0)到(100, 100)，这也是本篇将用到的canvas的3个基础的api。

上面已经得到了一个linkedMap，对于一个3 * 3的表格，把linkedMap打印一下，可得到以下表格。

通过上面的表格可知道，0和3中间是没有墙，所以在画的时候0和3中间就不要画横线了，3和4也是相连的，它们中间就不要画竖线了。对每个普通的格子都画它右边的竖线和下面的横线，而对于被拆掉的就不要画，所以得到以下代码：

draw(){ var linkedMap = this.linkedMap; var cellWidth = this.canvas.width / this.columns, cellHeight = this.canvas.height / this.rows; var ctx = this.canvas.getContext("2d"); //translate 0.5个像素，避免模糊 ctx.translate(0.5, 0.5); for(var i = 0; i < this.cells; i++){ var row = i / this.columns >> 0, column = i % this.columns; //画右边的竖线 if(column !== this.columns - 1 && (!linkedMap[i] || linkedMap[i].indexOf(i + 1) < 0)){ ctx.moveTo((column + 1) * cellWidth >> 0, row * cellHeight >> 0); ctx.lineTo((column + 1) * cellWidth >> 0, (row + 1) * cellHeight >> 0); } //画下面的横线 if(row !== this.rows - 1 && (!linkedMap[i] || linkedMap[i].indexOf(i + this.columns) < 0)){ ctx.moveTo(column * cellWidth >> 0, (row + 1) * cellHeight >> 0); ctx.lineTo((column + 1) * cellWidth >> 0, (row + 1) * cellHeight >> 0); } } //最后再一次性stroke，提高性能 ctx.stroke(); //画迷宫的四条边框 this.drawBorder(ctx, cellWidth, cellHeight); }

上面的代码也比较好理解，在画右边的竖线的时候，先判断它和右边的格子是否相通，即linkMap[i]里面有没有i + 1元素，如果没有，并且它不是最后一列，就画右边的竖线。因为迷宫的边框放到后面再画，它比较特殊，最后一个格子的竖线是不要画的，因为它是迷宫的出口。每次moveTo和lineTo的位置需要计算一下。
注意上面的代码做了两个优化，一个是先translate 0.5个像素，为了让canvas画线的位置刚好在像素上面，因为我们的lineWidth是1，如果不translate，那么它画的位置如下图中间所示，相邻两个像素占了半个像素，显示器显示的时候变会变虚，而translate 0.5个像素之后，它就会刚好画在像在像素点上。详见：HTML5 Canvas – Crisp lines every time。