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

（1）生成100个格子，每个格子都不相通

（2）随机选取相邻的两个格子，可以是左右相邻或者是上下相邻，判断这两个格子是不是处于同一个连通集，即能否从其中一个格子走到另外一个格子，如果不能，就拆掉它们中间的墙，让它们相连，处于同一个连通集。

（3）重复第二步，直到第一个格子和最后一个格子相连。

``````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));
}
}
``````

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

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

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

``````//取出随机的两个挨着的格子
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(x, y){
}
}
}
``````

``````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;
}
}
``````

## 2. 用Canvas画迷宫

``<canvas id="maze" width="800" height="600"></canvas>``

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

``````draw(){
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);
}
``````

``````draw(){
var canvasBuffer = document.createElement("canvas");
canvasBuffer.width = this.canvas.width;
canvasBuffer.height = this.canvas.height;
var ctx = canvasBuffer.getContext("2d");
ctx.translate(0.5, 0.5);
for(var i = 0; i < this.cells; i++){

}
ctx.stroke();
this.drawBorder(ctx, cellWidth, cellHeight);
console.log("draw");
this.canvas.getContext("2d").drawImage(canvasBuffer, 0, 0);
}
``````

``````const column = 50,
row = 50;
var canvas = document.getElementById("maze");
var maze = new Maze(column, row, canvas);

console.time("generate maze");
maze.generate();
console.timeEnd("generate maze");
console.time("draw maze");
maze.draw();
console.timeEnd("draw maze");
``````

``````linkedToFirstCell(){
for(var i = 1; i < this.cells; i++){
if(!this.unionSets.sameSet(0, i))
return false;
}
return true;
}
``````

## 3. 用最短路径算法找到迷宫的出路

``````calPath(){
var pathTable = new Array(this.cells);
for(var i = 0; i < pathTable.length; i++){
pathTable[i] = {known: false, prevCell: -1};
}
pathTable.known = true;
//用一个队列存储当前层的节点，先进队列的结点优先处理
var unSearchCells = ;
var j = 0;
while(!pathTable[pathTable.length - 1].known){
while(unSearchCells.length){
var cell = unSearchCells.pop();
for(var i = 0; i < map[cell].length; i++){
if(pathTable[map[cell][i]].known) continue;
pathTable[map[cell][i]].known = true;
pathTable[map[cell][i]].prevCell = cell;
unSearchCells.unshift(map[cell][i]);
if(pathTable[pathTable.length - 1].known) break;
}
}
}
var cell = this.cells - 1;
var path = [cell];
while(cell !== 0){
var cell = pathTable[cell].prevCell;
path.push(cell);
}
return path;
}
``````

## 4. 用WASM生成迷宫

``````struct Data{
int *set;
int columns;
int rows;
int cells;
} data;

void Set_union(int root1, int root2){
int *set = data.set;
if(set[root1] < set[root2]){
set[root2] = root1;
} else {
if(set[root1] == set[root2]){
set[root2]--;
}
set[root1] = root2;
}
}

int Set_findSet(int x){
if(data.set[x] < 0) return x;
else return data.set[x] = Set_findSet(data.set[x]);
}``````

``````#include <emscripten.h>

EMSCRIPTEN_KEEPALIVE //这个宏表示这个函数要作为导出的函数
int **Maze_generate(int columns, int rows){
Maze_init(columns, rows);
Maze_doGenerate();
//return Maze_getJSONStr();
}``````

emcc maze.c -Os -s WASM=1 -o maze-wasm.html

``````<script src="maze-wasm.js"></script>
<script src="maze.js"></script>``````

``````var maze = new Maze(column, row, canvas);
var ptr = Module._Maze_generate(column, row);
maze.draw();
});
``````

``````var linkedMapPtr = Module.ccall("Maze_generate", "number",
["number", "number"], [column, row]);
``````

``````var mazeGenerate = Module.cwrap("Maze_generate", "number",
["number", "number"]);
``````

``````function readInt32Array(ptr, length) {
for(var i = 0; i < length; i++) {
var subptr = Module.getValue(ptr + (i * 4), 'i32');
var neiborcells = [];
for(var j = 0; j < 4; j++){
var value = Module.getValue(subptr + (j * 4), 'i32');
if(value !== -1){
neiborcells.push(value, 'i32');
}
}
}
}
``````

``````var count = 50;
console.time("JS generate maze");
for(var i = 0; i < count; i++){
var maze = new Maze(column, row, canvas);
maze.generate();
}
console.timeEnd("JS generate maze");

console.time("WASM generate maze");
for(var i = 0; i < count; i++){
var maze = new Maze(column, row, canvas);
var ptr = Module._Maze_generate(column, row);
}
console.timeEnd("WASM generate maze");
})
``````
{"ft_lang_label":"__label__zh","ft_lang_prob":0.78394115,"math_prob":0.9932256,"size":12922,"snap":"2020-24-2020-29","text_gpt3_token_len":7986,"char_repetition_ratio":0.115575165,"word_repetition_ratio":0.11099138,"special_character_ratio":0.25290203,"punctuation_ratio":0.2179009,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9876858,"pos_list":[0,1,2],"im_url_duplicate_count":[null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-06T17:54:57Z\",\"WARC-Record-ID\":\"<urn:uuid:ba56029a-88d1-4df7-8a71-449b1f52af50>\",\"Content-Length\":\"291998\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a184f973-15e3-4c69-aa44-259101564234>\",\"WARC-Concurrent-To\":\"<urn:uuid:f54f66d0-e0b0-4d11-892b-a12ece314d15>\",\"WARC-IP-Address\":\"211.152.148.73\",\"WARC-Target-URI\":\"https://zhuanlan.zhihu.com/p/28203300\",\"WARC-Payload-Digest\":\"sha1:TNYQVE56VOCRW7FAAQJLRAZTMNY2KZC5\",\"WARC-Block-Digest\":\"sha1:P74XWSROIDXSOFSA247DYJ4B6F2PM5F4\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593655881763.20_warc_CC-MAIN-20200706160424-20200706190424-00088.warc.gz\"}"}