本篇將嘗使用canvas + wasm畫一個(gè)迷宮迅箩，生成算法主要用到連通集算法，使用wasm主要是為了提升運(yùn)行效率处铛。然后再用一個(gè)最短路徑算法找到迷宮的出路饲趋，最后的效果如下：
1. 用連通集算法生成迷宮
生成迷宮的算法其實(shí)很簡單，假設(shè)迷宮的大小是10 * 10撤蟆，即這個(gè)迷宮有100個(gè)格子奕塑，通過不斷地隨機(jī)拆掉這100個(gè)格子中間的墻，直到可以從第一個(gè)格子走到最后一個(gè)格子枫疆，也就是說第一個(gè)格子和最后一個(gè)格子處于同一個(gè)連通集爵川。具體如下操作：
生成100個(gè)格子，每個(gè)格子都不相通
隨機(jī)選取相鄰的兩個(gè)格子息楔，可以是左右相鄰或者是上下相鄰寝贡，判斷這兩個(gè)格子是不是處于同一個(gè)連通集扒披，即能否從其中一個(gè)格子走到另外一個(gè)格子，如果不能圃泡，就拆掉它們中間的墻碟案，讓它們相連，處于同一個(gè)連通集颇蜡。
重復(fù)第二步价说，直到第一個(gè)格子和最后一個(gè)格子相連。
那這個(gè)連通集應(yīng)該怎么表示呢风秤？我們用一個(gè)一維數(shù)組來表示不同的已連通的集合鳖目，初始化的時(shí)候每個(gè)格子的值都為-1，如下圖所示缤弦，假設(shè)迷宮為3 * 3领迈，即有9個(gè)格子：
每個(gè)索引在迷宮的位置：
負(fù)數(shù)表示它們是不同的連通集，因?yàn)槲覀冞€沒開始拆墻碍沐，所以一開始它們都是獨(dú)立的狸捅。
現(xiàn)在把3、4中間的墻拆掉累提，也就是說讓3和4連通尘喝，把4的值置成3，表示4在3這個(gè)連通集斋陪，3是它們的根朽褪，如下圖所示：
再把5、8給拆了
再把4鳍贾、5給拆了：
這個(gè)時(shí)候3鞍匾、4、5骑科、8就處于同一個(gè)連通集了橡淑，但是0和8依舊是兩個(gè)不同的連通集，這個(gè)時(shí)候再把3和0中間的墻給拆了：
由于0的連通集是3咆爽，而8的連通集也是3梁棠，即它們處于同一個(gè)連通集，因此這個(gè)時(shí)候從第一個(gè)格子到最后一個(gè)格子的路是相通的斗埂，就生成了一個(gè)迷宮符糊。
我們用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行代碼就實(shí)現(xiàn)了一個(gè)連通集呛凶。上面的代碼應(yīng)該比較好理解男娄，對照上面的示意圖。如findSet函數(shù)得到某個(gè)元素所在的set的根元素，而根元素存放的是負(fù)數(shù)模闲，只要存放的值是正數(shù)那么它就是指向另一個(gè)結(jié)點(diǎn)建瘫，通過while循環(huán)一層層的往上找直到負(fù)數(shù)。unionElement可以連通兩個(gè)元素尸折，先找到它們所在的set，然后把它們的set union一下變成同一個(gè)連通集实夹。
現(xiàn)在寫一個(gè)Maze亮航，用來控制畫迷宮的操作，它組合一個(gè)UnionSet的實(shí)例泪勒，如下代碼所示：
class Maze{
constructor(columns, rows, cavans){
this.columns = columns;
this.rows = rows;
this.cells = columns * rows;
//存放是連通的格子宴猾，{1: [2, 11]}表示第1個(gè)格子和第2仇哆、11個(gè)格子是相通的
this.linkedMap = {};
this.unionSets = new UnionSet(this.cells);
this.canvas = canvas;
}
}
Maze構(gòu)造函數(shù)傳三個(gè)參數(shù)，前兩個(gè)是迷宮的列數(shù)和行數(shù)夫植，最后一個(gè)是canvas元素讹剔。在構(gòu)造函數(shù)里面初始化一個(gè)連通集，作為這個(gè)Maze的核心模型详民，還初始化了一個(gè)linkedMap延欠，用來存放拆掉的墻，進(jìn)而提供給canvas繪圖沈跨。
Maze類再添加一個(gè)生成迷宮的函數(shù)由捎，如下代碼所示：
//生成迷宮
generate(){
//每次任意取兩個(gè)相鄰的格子，如果它們不在同一個(gè)連通集饿凛，
//則拆掉中間的墻狞玛，讓它們連在一起成為一個(gè)連通集
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循環(huán)里面判斷第一個(gè)是否與最后一個(gè)格子連通涧窒，如果不是的話心肪，則每次隨機(jī)選取兩個(gè)相鄰的格子，如果它們不在同一個(gè)連通集纠吴，則把它們連通一下硬鞍，同時(shí)記錄一下拆掉的墻到linkedMap里面。
怎么隨機(jī)選取兩個(gè)相鄰的格子呢？這個(gè)雖然沒什么技術(shù)難點(diǎn)固该，但是實(shí)現(xiàn)起來需要?jiǎng)右环X筋锅减，因?yàn)樵谶吷系母褡記]有完整的上下左右四個(gè)相鄰格子，有些只有兩個(gè)蹬音，有些有三個(gè)上煤。筆者是這么實(shí)現(xiàn)的劫狠，相對來說比較簡單：
//取出隨機(jī)的兩個(gè)挨著的格子
pickRandomCellPairs(){
var cell = (Math.random() * this.cells) >> 0;
//再取一個(gè)相鄰格子，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]];
}
首先隨機(jī)選一個(gè)格子，然后得到它的行數(shù)和列數(shù)腹暖，接著依次判斷它的邊界情況。如果它不是處于第一排以蕴，那么它就有上面一排的相鄰格子，如果不是最后一排則有下面一排的相鄰格子宝与，同理咆瘟，如果不是在第一列則有左邊的，不是最后一列則有右邊的灸眼。把符合條件的格子放到一個(gè)數(shù)組里面，然后再隨機(jī)取這個(gè)數(shù)組里的一個(gè)元素。這樣就得到了兩個(gè)隨機(jī)的相鄰元素闪唆。
另一個(gè)addLinkedMap函數(shù)的實(shí)現(xiàn)較為簡單，如下代碼所示：
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);
}
}
這樣生成迷宮的核心邏輯基本完成，但是上面連通集的代碼可以優(yōu)化霸旗， 一個(gè)是findSet函數(shù)，可以在findSet的時(shí)候把當(dāng)前連通集里的元素的存放值直接改成根元素精居，這樣就不用形成一條很長的查找鏈，或者說形成一棵很高的樹佛吓，可直接一步到位淤刃，如下代碼所示：
findSet(x){
if(this.set[x] < 0) return x;
return this.set[x] = this.findSet(this.set[x]);
}
這段代碼使用了一個(gè)遞歸，在查找的同時(shí)改變值铝侵。
union函數(shù)也可以做一個(gè)優(yōu)化，findSet可以把樹的高度改小嗜诀，但是在沒有改小前的union操作也可以做優(yōu)化隆敢，如下代碼所示：
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;
}
}
這段代碼的目的也是為了減少查找鏈的長度或者說減少樹的高度，方法是把一棵比較矮的連通集成為另外一棵比較高的連通集的子樹温自，這樣兩個(gè)連通集，合并起來的高度還是那棵高的馆里。如果兩個(gè)連通集的高度一樣，則選取其中一個(gè)作為根营密，另外一棵樹的結(jié)點(diǎn)在查找的時(shí)候無疑這些結(jié)點(diǎn)的查找長度要加上1 滥沫，因?yàn)槎嗔艘粋€(gè)新的root，也就是說樹的高度要加1缀辩，由于存放的是負(fù)數(shù)，所以進(jìn)行減減操作健无。在判斷樹高度的時(shí)候也是一樣的，越小就說明越高臼膏。
經(jīng)驗(yàn)證，這樣改過之后始鱼，代碼執(zhí)行效率快了一半以上。
迷宮生成好之后，現(xiàn)在開始來畫双泪。
2. 用Canvas畫迷宮
先寫一個(gè)canvas的html元素，如下代碼所示：
<canvas id="maze" width="800" height="600"></canvas>
注意canvas的寬高要用width和height的屬性寫村斟，如果用style的話就是拉伸了孩灯，會(huì)出現(xiàn)模糊的情況。
怎么用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個(gè)基礎(chǔ)的api怎爵。
上面已經(jīng)得到了一個(gè)linkedMap，對于一個(gè)3 * 3的表格，把linkedMap打印一下灌侣，可得到以下表格。
通過上面的表格可知道，0和3中間是沒有墻哪审，所以在畫的時(shí)候0和3中間就不要畫橫線了滴须，3和4也是相連的，它們中間就不要畫豎線了叽奥。對每個(gè)普通的格子都畫它右邊的豎線和下面的橫線扔水，而對于被拆掉的就不要畫，所以得到以下代碼：
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個(gè)像素而线，避免模糊
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);
}
上面的代碼也比較好理解，在畫右邊的豎線的時(shí)候膀篮，先判斷它和右邊的格子是否相通筷屡，即linkMap[i]里面有沒有i + 1元素，如果沒有纠拔，并且它不是最后一列匹耕，就畫右邊的豎線。因?yàn)槊詫m的邊框放到后面再畫龄恋，它比較特殊乘碑，最后一個(gè)格子的豎線是不要畫的，因?yàn)樗敲詫m的出口宛官。每次moveTo和lineTo的位置需要計(jì)算一下费变。
注意上面的代碼做了兩個(gè)優(yōu)化，一個(gè)是先translate 0.5個(gè)像素哼转，為了讓canvas畫線的位置剛好在像素上面，因?yàn)槲覀兊膌ineWidth是1基显，如果不translate，那么它畫的位置如下圖中間所示挨队，相鄰兩個(gè)像素占了半個(gè)像素，顯示器顯示的時(shí)候變會(huì)變虛如输，而translate 0.5個(gè)像素之后，它就會(huì)剛好畫在像在像素點(diǎn)上。詳見：HTML5 Canvas – Crisp lines every time。
第二個(gè)優(yōu)化是所有的moveTo和lineTo都完成之后再stroke，這樣它就是一條線锥累，可以極大地提高畫圖的效率。這個(gè)很重要桃熄，剛開始的時(shí)候沒這么做先口，導(dǎo)致格子數(shù)稍多的時(shí)候就畫不了了，改成這樣之后瞳收，繪制的效率提升很多池充。
我們還可以再做一個(gè)優(yōu)化，就是使用雙緩存技術(shù)缎讼，在畫的時(shí)候別直接畫到屏幕上，而是先在內(nèi)存的畫布里面完成繪制坑匠，最后再一次性地Paint繪制到屏幕上血崭，這樣也可以提高性能诞外。如下代碼所示：
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);
}
先動(dòng)態(tài)創(chuàng)建一個(gè)canvas節(jié)點(diǎn)屑墨，獲取它的context，在上面畫圖崔挖，畫好之后再用原先的canvas的context的drawImage把它畫到屏幕上去设凹。
然后就可以寫驅(qū)動(dòng)代碼了舰讹，如下畫一個(gè)50 * 50的迷宮，并統(tǒng)計(jì)一下時(shí)間：
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");
畫出的迷宮：
運(yùn)行時(shí)間：
可以看到畫一個(gè)2500規(guī)模的迷宮闪朱，draw的時(shí)間還是很少的月匣，而生成的時(shí)間也不長，但是我們發(fā)現(xiàn)一個(gè)問題奋姿，就是迷宮的有些格子是封閉的：
這些不能夠進(jìn)去的格子就沒用了锄开，這不太符合迷宮的特點(diǎn)。所以不能存在自我封閉的格子称诗，由于生成的時(shí)候是判斷第一個(gè)格子有沒有和最后一個(gè)連通萍悴，現(xiàn)在改成第一個(gè)格子和所有的格子都是連通的，也就是說可以從第一個(gè)格子到達(dá)任意一個(gè)格子寓免，這樣迷宮的誤導(dǎo)性才比較強(qiáng)癣诱，如下代碼所示：
linkedToFirstCell(){
for(var i = 1; i < this.cells; i++){
if(!this.unionSets.sameSet(0, i))
return false;
}
return true;
}
把while的判斷也改一下，這樣改完之后袜香，生成的迷宮變成了這樣：
這樣生成的迷宮看起來就正常多了撕予，生成迷宮的時(shí)間也相應(yīng)地變長：
但是我們發(fā)現(xiàn)還是有一些比較奇怪的格子布局，如下圖所示:
因?yàn)檫@樣布局的其實(shí)沒太大的意義困鸥，如果讓你手動(dòng)設(shè)計(jì)一個(gè)迷宮嗅蔬，你肯定也不會(huì)設(shè)計(jì)這樣的布局剑按。所以我們的算法還可以再改進(jìn)，由于上面是隨機(jī)選取兩個(gè)相鄰格子澜术，可以把它改成隨機(jī)選取4個(gè)相鄰的格子艺蝴，這樣生成的迷宮通道就會(huì)比較長，像上圖這種比較奇芭的情況就會(huì)比較少鸟废。讀者可以親自動(dòng)手試驗(yàn)一下猜敢。
3. 用最短路徑算法找到迷宮的出路
這個(gè)模型更為常見的場景是，現(xiàn)在我在A城鎮(zhèn)盒延，準(zhǔn)備去Z城鎮(zhèn)缩擂，中間要繞道B、C添寺、D等城鎮(zhèn)胯盯，并且有多條路線可選，并且知道每個(gè)城鎮(zhèn)和它連通的城鎮(zhèn)以及兩兩之間距離计露，現(xiàn)在要求解一條A到Z的最短的路博脑，如下圖所示：
在迷宮的模型里面也是類似的，要求解從第一個(gè)格子到最后一個(gè)格子的最短路徑票罐，并且已經(jīng)知道格子之間的連通情況叉趣。不一樣的是相鄰格子之間的距離是無權(quán)的，都為1该押，所以這個(gè)處理起來會(huì)更加簡單疗杉。
用一個(gè)貪婪算法可以解決這個(gè)問題，假設(shè)從A到Z的最短路徑為A->C->G->Z蚕礼，那么這條路徑也是A到G烟具、A到C的最短路徑，因?yàn)槿绻鸄到G還有更短的路徑奠蹬，那么A到Z的距離就還可以更短了净赴，即這條路徑不是最短的。因此我們從A開始延伸罩润，一步步地確定A到其它地點(diǎn)的最短路徑玖翅，直到擴(kuò)散到Z。
在無權(quán)的情況下割以，如上面任意相鄰城鎮(zhèn)的距離相等金度，和A直接相連的節(jié)點(diǎn)必定是A到這個(gè)節(jié)點(diǎn)的最短路徑，如上圖A到B严沥、C猜极、F的最短路徑為A->B、A->C消玄、A->F跟伏，這三個(gè)點(diǎn)的最短路徑可標(biāo)記為已知丢胚。和C直接相鄰的是G和D，C是最短的受扳，所以A->C-G和A->C->D也是最短的携龟，再往下一層，和G勘高、D直接相連的分別是E和Z峡蟋，所以A->C->G->Z和A->C->D->E是到Z和E的一條最短路徑，到此就找到了A->Z的最短路線华望。E也可以到Z蕊蝗，但是由于Z已經(jīng)被標(biāo)為已知最短了，所以通過E的這條路徑就被放棄了赖舟。
和A直接相連的做為第一層蓬戚，而和第一層直接相連的做為第二層，由第一層到第二層一直延伸目標(biāo)結(jié)點(diǎn)宾抓，先被找到的節(jié)點(diǎn)就會(huì)被標(biāo)記為已知碌更。這是一個(gè)廣度優(yōu)先搜索。
而在有權(quán)的情況下洞慎，剛開始的時(shí)候A被標(biāo)記為已知，由于A和C是最短的嘿棘，所以C也被標(biāo)記為已知劲腿，B和F不會(huì)標(biāo)記，但是它們和A的距離會(huì)受到更新鸟妙，由初始化的無窮大更新為A->B和A->F的距離焦人。在已查找到但未標(biāo)記的兩個(gè)點(diǎn)里面，A->F的距離是最短的重父，所以F被標(biāo)記為已知花椭，這是因?yàn)槿绻嬖诹硗庖粭l更短的未知的路到F，它必定得先經(jīng)過已經(jīng)查找到的點(diǎn)（因?yàn)橐呀?jīng)查找過的點(diǎn)是A的必經(jīng)之路）房午，這里面已經(jīng)是最短的了矿辽，所以不可能還有更短的了。F被標(biāo)記為已知之后和F直接相連的E的距離得到更新郭厌，同樣地袋倔，在已查找到但未標(biāo)記的點(diǎn)里面B的距離最短，所以B被標(biāo)記為已知折柠，然后再更新和B相連的點(diǎn)的距離宾娜。重復(fù)這個(gè)過程，直到Z被標(biāo)記為已知扇售。
標(biāo)記起始點(diǎn)為已知前塔，更新表的距離嚣艇，再標(biāo)記表里最短的距離為已知，再更新表的距離华弓，重復(fù)直到目的點(diǎn)被標(biāo)記食零，這個(gè)算法也叫Dijkstra算法。
現(xiàn)在來實(shí)現(xiàn)一個(gè)無權(quán)的最短路徑该抒，如下代碼所示：
calPath(){
var pathTable = new Array(this.cells);
for(var i = 0; i < pathTable.length; i++){
pathTable[i] = {known: false, prevCell: -1};
}
pathTable[0].known = true;
var map = this.linkedMap;
//用一個(gè)隊(duì)列存儲(chǔ)當(dāng)前層的節(jié)點(diǎn)慌洪，先進(jìn)隊(duì)列的結(jié)點(diǎn)優(yōu)先處理
var unSearchCells = [0];
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;
}
這個(gè)算法實(shí)現(xiàn)的關(guān)鍵在于用一個(gè)隊(duì)列存儲(chǔ)未處理的結(jié)點(diǎn)，每處理一個(gè)結(jié)點(diǎn)時(shí)凑保，就把和這個(gè)結(jié)點(diǎn)相連的點(diǎn)入隊(duì)冈爹，這樣新入隊(duì)的結(jié)點(diǎn)就會(huì)排到當(dāng)前層的結(jié)點(diǎn)的后面，當(dāng)把第一層的結(jié)點(diǎn)處理完了欧引，就會(huì)把第二層的結(jié)點(diǎn)都push到隊(duì)尾频伤，同理當(dāng)把第二層的結(jié)點(diǎn)都出隊(duì)了，就會(huì)把第三層的結(jié)點(diǎn)推到隊(duì)尾芝此。這樣就實(shí)現(xiàn)了一個(gè)廣度優(yōu)先搜索憋肖。
在處理每個(gè)結(jié)點(diǎn)需要需要先判斷一下當(dāng)前結(jié)點(diǎn)是否已被標(biāo)記為known，如果是的話就不用處理了婚苹。
在pathTable表格里面用一個(gè)prevCell記錄到這個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)是哪個(gè)岸更，為了能夠從目的結(jié)點(diǎn)一直往前找到到達(dá)第一個(gè)結(jié)點(diǎn)的路徑。最后找到這個(gè)path返回膊升。
只要有這個(gè)path怎炊，就能夠計(jì)算位置畫出路徑的圖，如下圖所示：
這個(gè)算法的速度還是很快的廓译，如下圖所示：
當(dāng)把迷宮的規(guī)模提高到200 * 200時(shí)：
生成迷宮的時(shí)間就很耗時(shí)了评肆，花費(fèi)了10秒：
于是想著用WASM提高生成迷宮的效率，看看能提升多少非区。我在《WebAssembly與程序編譯》這篇里已經(jīng)介紹了WASM的一些基礎(chǔ)知識(shí)瓜挽，本篇我將用它來生成迷宮。
4. 用WASM生成迷宮
我在《WebAssembly與程序編譯》提過用JS寫很難編譯征绸，所以本篇也直接用C來寫久橙。上面是用的class，但是WASM用C寫沒有class的類型管怠，只支持基本的操作剥汤。但是可以用一個(gè)struct存放數(shù)據(jù)，函數(shù)名也相應(yīng)地做修改排惨，如下代碼所示：
struct Data{
int *set;
int columns;
int rows;
int cells;
int **linkedMap;
} 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]);
}
數(shù)據(jù)類型都是強(qiáng)類型的吭敢，函數(shù)名以類名Set_開頭，類的數(shù)據(jù)放在一個(gè)struct結(jié)構(gòu)里面暮芭。主要導(dǎo)出函數(shù)為：
#include <emscripten.h>
EMSCRIPTEN_KEEPALIVE //這個(gè)宏表示這個(gè)函數(shù)要作為導(dǎo)出的函數(shù)
int **Maze_generate(int columns, int rows){
Maze_init(columns, rows);
Maze_doGenerate();
return data.linkedMap;
//return Maze_getJSONStr();
}
傳進(jìn)來列數(shù)和行數(shù)鹿驼，返回一個(gè)二維數(shù)組欲低。其它代碼相應(yīng)地改成C代碼，這里不再放出來畜晰。需要注意的是砾莱，由于這里用到了一些C內(nèi)置的庫，如使用隨機(jī)數(shù)函數(shù)rand()凄鼻，所以不能用上文提到的生成wasm的方法腊瑟，不然會(huì)報(bào)rand等庫函數(shù)沒有定義。
把生成wasm的命令改成：
emcc maze.c -Os -s WASM=1 -o maze-wasm.html
這樣它會(huì)生成一個(gè)maze-wasm.js和maze-wasm.wasm（生成的html文件不需要用到）块蚌，生成的JS文件是用來自動(dòng)加載和導(dǎo)入wasm文件的闰非，在html里面引入這個(gè)JS：
<script src="maze-wasm.js"></script>
<script src="maze.js"></script>
它就會(huì)自動(dòng)去加載maze-wasm.wasm文件，同時(shí)會(huì)定義一個(gè)全局的Module對象峭范，在wasm文件加載好之后會(huì)觸發(fā)onInit财松，所以調(diào)它的api添加一個(gè)監(jiān)聽函數(shù)，如下代碼所示：
var maze = new Maze(column, row, canvas);
Module.addOnInit(function(){
var ptr = Module._Maze_generate(column, row);
maze.linkedMap = readInt32Array(ptr, column * row);
maze.draw();
});
有兩種方法可以得到導(dǎo)出的函數(shù)纱控，一種是在函數(shù)名前面加_辆毡，如Module._Maze_generate，第二種是使用它提供的ccall或cwrap函數(shù)甜害，如ccall：
var linkedMapPtr = Module.ccall("Maze_generate", "number",
["number", "number"], [column, row]);
第一個(gè)參數(shù)表示函數(shù)名舶掖，第二個(gè)返回類型，第三個(gè)參數(shù)類型尔店，第四個(gè)傳參眨攘，或者用cwrap：
var mazeGenerate = Module.cwrap("Maze_generate", "number",
["number", "number"]);
var linkedMapPtr = mazeGenerate(column, row);
三種方法都會(huì)返回linkedMap的指針地址，可通過Module.get得到地址里面的值闹获，如下代碼所示：
function readInt32Array(ptr, length) {
var linkedMap = new Array(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');
}
}
linkedMap[i] = neiborcells;
}
return linkedMap;
}
由于它是一個(gè)二維數(shù)組，所以數(shù)組里面存放的是指向數(shù)組的指針河哑，因此需要再對這些指針再做一次get操作避诽，就可以拿到具體的值了。如果取出的值是-1則表示不是有效的相鄰元素璃谨，因?yàn)镃里面數(shù)組的長度是固定的沙庐，無法隨便動(dòng)態(tài)push，因此我在C里面都初始化了4個(gè)佳吞，因?yàn)橄噜徳刈疃嘀挥?個(gè)拱雏，初始時(shí)用-1填充。取出非-1的值push到JS的數(shù)組里面底扳，得到一個(gè)用WASM計(jì)算的linkedMap. 然后再用同樣的方法去畫地圖铸抑。
最后再比較一下WASM和JS生成迷宮的時(shí)間。如下代碼所示衷模，運(yùn)行50次：
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");
Module.addOnInit(function(){
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);
var linkedMap = readInt32Array(ptr, column * row);
}
console.timeEnd("WASM generate maze");
})
迷宮的規(guī)模為50 * 50鹊汛，結(jié)果如下：
可以看到蒲赂，WASM的時(shí)間大概快了25%，并且有時(shí)候會(huì)觀察到WASM的時(shí)間甚至要比JS的時(shí)間要長刁憋，這時(shí)因?yàn)樗惴ㄊ请S機(jī)的滥嘴，有時(shí)候拆掉的墻可能會(huì)比較多，所以偏差會(huì)比較大至耻。但是大部份情況下的25%還是可信的若皱，因?yàn)槿绻央S機(jī)選取的墻保存起來，然后讓JS和WASM用同樣的數(shù)據(jù)尘颓，這個(gè)時(shí)間差就會(huì)固定在25%走触，如下圖所示：
這個(gè)時(shí)間要比上面的大，因?yàn)楸４媪艘粋€(gè)需要拆的墻比較多的數(shù)組泥耀。理論上不用產(chǎn)生隨機(jī)數(shù)饺汹，時(shí)間會(huì)更少，不過我們的重點(diǎn)是比較它們的時(shí)間差痰催，結(jié)果是不管運(yùn)行多少次兜辞，時(shí)間差都比較穩(wěn)定。
所以在這個(gè)例子里面WASM節(jié)省了25%的時(shí)間夸溶，雖然提升不是很明顯逸吵，但還是有效果，很多個(gè)25%累積起來還是挺長的缝裁。
綜上扫皱，本文用JS和WASM使用連通集算法生成迷宮，并用最短路徑算法求解迷宮的路徑捷绑。使用WASM在生成迷宮的例子里面可以提升25%的速度韩脑。
雖然迷宮小時(shí)候就已經(jīng)在玩了，不是什么高大上的東西粹污，但是通過這個(gè)例子討論到了一些算法，還用到了很出名的最短路徑算法壮吩，還把WASM實(shí)際地應(yīng)用了一遍进苍，作為學(xué)習(xí)的的模型還是挺好的。更多的算法可參考這篇《我接觸過的前端數(shù)據(jù)結(jié)構(gòu)與算法》鸭叙。
