摘要：整個(gè)思路十分簡(jiǎn)單首先我們將迷宮視為一個(gè)行列的單元格組合，每一個(gè)單元格便可以表示為。用來(lái)儲(chǔ)存我們已訪問(wèn)過(guò)的單元格，則記錄我們的訪問(wèn)路徑。我們通過(guò)將單元格的，，，屬性設(shè)置為或來(lái)標(biāo)識(shí)這個(gè)方向是否應(yīng)該有邊框，同時(shí)該方向是否可走。

這個(gè)系列分為兩部分，第一部分為迷宮的生成及操作，第二部分為自動(dòng)尋路算法。

我們先看效果：點(diǎn)擊查看

我們直入正題，先說(shuō)一說(shuō)生成迷宮的思路。
整個(gè)思路十分簡(jiǎn)單：

首先我們將迷宮視為一個(gè)m行n列的單元格組合，每一個(gè)單元格便可以表示為 maze[i][j] 。接下來(lái)迷宮與m*n單元格的區(qū)別是什么呢？對(duì)，迷宮就是相當(dāng)于不同單元格以某種規(guī)律相互連通，也就相當(dāng)于我們把相鄰的兩個(gè)單元格之間的重合線給去掉，然后按照某種規(guī)律循環(huán)，便可生成一個(gè)迷宮。

我們假定從左上角開(kāi)始出發(fā)，遍歷每一個(gè)單元格，如果該單元格未被訪問(wèn)過(guò)，則查看其相鄰元素（上，下，左，右）是否有未訪問(wèn)的單元格，如果有則隨機(jī)取出一個(gè)相鄰元素并打通他們之間的重合線，如果沒(méi)有則回退到上一個(gè)單元格。

上代碼：
首先我們創(chuàng)建一個(gè)構(gòu)造函數(shù)：

function Maze(obj,col,row){
     this.col = col || 10;
     this.row = row || 10;
     this.canvas = obj.getContext("2d");
     this.init();
}

在這個(gè)構(gòu)造函數(shù)中，我們接收三個(gè)參數(shù)，分別為canvas元素，迷宮的行數(shù)與列數(shù)，并直接調(diào)用Maze的init方法。

init : function(){
  this.cell = (width - 2) / this.col;
  for(var i = 0 ; i < this.row ; i++){
      maze_cells[i] = [];
      for(var j = 0; j < this.col ; j++){
          maze_cells[i].push({
              "x" : j,  
              "y" : i,
              "top" : false,
              "bottom" : false,
              "left" : false,
              "right" : false,
              "isVisited" : false,
              "g" : 0,
              "h" : 0,
              "f" : 0
          })
      }
  }
  start_cell = {"x" : 0, "y" : 0 };
  start_row = start_cell.x;
  start_col = start_cell.y;
  visitRooms.push(start_cell)
  roomsLine.push(start_cell)
  maze_cells[0][0].isVisited = true;
  maze_cells[0][0].top = true;
  maze_cells[this.row-1][this.col-1].bottom = true;
  this.calcCells(0,0,maze_cells);
  this.drawCells();
  maze_cells[0][0].top = false;
  maze_cells[this.row-1][this.col-1].bottom = false;
  this.drawRect(start_col,start_row);
  this.bindEvent();
  
},

在init方法中，我們首先根據(jù)傳入的列數(shù)col來(lái)計(jì)算單元格的寬度，然后構(gòu)建一個(gè)maze_cells對(duì)象，其中每一行為一個(gè)數(shù)組，每個(gè)單元格包含的值分別代表x,y坐標(biāo)，上下左右4個(gè)方向是否可以通行，是否訪問(wèn)過(guò)，還有該單元格的g，h，f值。我們假定迷宮的開(kāi)口位于整個(gè)迷宮的左上角，出口位于右下角。visitRooms用來(lái)儲(chǔ)存我們已訪問(wèn)過(guò)的單元格，roomLine則記錄我們的訪問(wèn)路徑。我們將迷宮的入口處和出口處的top，bottom分別設(shè)為true后再設(shè)置為false是為了在繪制的過(guò)程中不出現(xiàn)邊框，繪制完成后保證不能向上（下）移動(dòng)。

ps：canvas繪制線條是居中于我們坐標(biāo)的，即在（1,1）處繪制寬度為2的線條起始是從（0,1）開(kāi)始的，所以我們用整個(gè)canvas的寬度減去了線條的寬度2，當(dāng)然這里也可以設(shè)置為變量更方便修改。

接下來(lái)我們需要遍歷每一個(gè)單元格，如下通過(guò)遞歸的形式訪問(wèn)每一個(gè)單元格，當(dāng)某一個(gè)單元格的相鄰元素全部被訪問(wèn)過(guò)并且roomLine數(shù)組為空時(shí)就意味著我們已經(jīng)訪問(wèn)了所有的單元格，具體原因自行腦補(bǔ)。

calcCells : function(x,y,arr){
    var neighbors = [];
    if(x-1 >=0 && !maze_cells[x-1][y].isVisited){
        neighbors.push({"x" : x-1 ,"y" : y})
    }
    if(x+1 < this.row && !maze_cells[x+1][y].isVisited){
        neighbors.push({"x" : x+1 ,"y" : y})
    }
    if(y-1 >=0 && !maze_cells[x][y-1].isVisited){
        neighbors.push({"x" : x ,"y" : y-1})
    }
    if(y+1 0){ //相鄰房間有未訪問(wèn)房間
        var current = {"x" : x , "y" : y};
        var next = neighbors[Math.floor(Math.random() * neighbors.length)];
        maze_cells[next.x][next.y].isVisited = true;
        visitRooms.push({"x" : next.x , "y" : next.y})
        roomsLine.push({"x" : next.x , "y" : next.y});
        this.breakWall(current,next);
        this.calcCells(next.x,next.y,arr)
    }else{
        var next = roomsLine.pop();
        if(next != null){
            this.calcCells(next.x,next.y,arr)
        }
    }
},

我們看到如果當(dāng)前單元格的相鄰單元格有未訪問(wèn)的，則執(zhí)行breakWall方法，即打通當(dāng)前單元格與相鄰單元格中間的墻，當(dāng)然我們應(yīng)該隨機(jī)選擇一個(gè)未訪問(wèn)的相鄰單元格。我們通過(guò)將單元格的top，bottom，left，right屬性設(shè)置為true或false來(lái)標(biāo)識(shí)這個(gè)方向是否應(yīng)該有邊框，同時(shí)該方向是否可走。

breakWall : function(cur,next){
    if(cur.x < next.x){
        maze_cells[cur.x][cur.y].bottom = true;
        maze_cells[next.x][next.y].top = true;
    }
    if(cur.x > next.x){
        maze_cells[cur.x][cur.y].top = true;
        maze_cells[next.x][next.y].bottom = true;
    }
    if(cur.y < next.y){
        maze_cells[cur.x][cur.y].right = true;
        maze_cells[next.x][next.y].left = true;
    }
    if(cur.y > next.y){
        maze_cells[cur.x][cur.y].left = true;
        maze_cells[next.x][next.y].right = true;
    }
},

進(jìn)行完上面的兩步，我們的一個(gè)完整數(shù)組已經(jīng)構(gòu)成了，接下來(lái)便可以開(kāi)始繪制了，top，left，right，bottom為false時(shí)則有邊框，true時(shí)無(wú)邊框。這一步比較簡(jiǎn)單，我們?cè)诮Y(jié)尾調(diào)用了一個(gè)drawOffset方法，該方法將創(chuàng)建一個(gè)離屏對(duì)象，這樣我們?cè)趧?dòng)態(tài)修改迷宮的時(shí)候可以直接將離屏的圖像繪制到當(dāng)前畫(huà)布中。

drawCells : function(){
    var ctx = this.canvas,   //canvas對(duì)象
        w = this.cell;
    ctx.clearRect(0,0,$("canvas").width,$("canvas").height)
    ctx.beginPath();
    ctx.save();
    ctx.translate(1,1)
    ctx.strokeStyle = "#000000";
    ctx.lineWidth = 2;
    for(var i in maze_cells){ //i 為 row
        var len = maze_cells[i].length;
        for( var j = 0; j < len; j++){
            var cell = maze_cells[i][j];
            i = parseInt(i);    
            if(!cell.top){
                ctx.moveTo(j*w,i*w);
                ctx.lineTo((j+1)*w ,i*w);
            }
            if(!cell.bottom){
                ctx.moveTo(j*w,(i+1)*w);
                ctx.lineTo((j+1)*w ,(i+1)*w)
            }
            if(!cell.left){
                ctx.moveTo(j*w,i*w);
                ctx.lineTo(j*w,(i+1)*w )
            }
            if(!cell.right){
                ctx.moveTo((j+1)*w,i*w);
                ctx.lineTo((j+1)*w,(i+1)*w)
            }
        }
    }
    ctx.stroke();
    ctx.restore();
    this.drawOffset();
},

drawOffset : function(){
    var offsetCanvas = document.createElement("canvas");
    offsetCanvas.id = "offset";
    document.body.appendChild(offsetCanvas);
    offsetCanvas.width = $("canvas").width;
    offsetCanvas.height = $("canvas").height;
    var offset = $("offset").getContext("2d");
    offset.clearRect(0,0,$("canvas").width,$("canvas").height)
    offset.drawImage($("canvas"),0,0,offsetCanvas.width,offsetCanvas.height);
    $("offset").style.display ="none"
},

綁定事件比較簡(jiǎn)單，我們?yōu)閣indow監(jiān)聽(tīng)keydown事件，根據(jù)不同的keyCode來(lái)判斷我們應(yīng)該行走的方向。

var _self = this;
window.addEventListener("keydown",function(event){
    switch (event.keyCode) {
        case 37 : 
           event.preventDefault();
           if(maze_cells[start_row][start_col].left){
               start_col --;
           }
           break;
        case 38 :
           event.preventDefault();
           if(maze_cells[start_row][start_col].top){
               start_row --;
           }
           break;
        case 39 :
           event.preventDefault();
           if(maze_cells[start_row][start_col].right){
               start_col ++
           }
           break;
        case 40 :
           event.preventDefault();
           if(maze_cells[start_row][start_col].bottom){
               start_row ++;
           }
           break;
    }
    _self.drawRect(start_col,start_row);
    if(start_col == (_self.col - 1)  && start_row == ( _self.row - 1)){
        alert("到達(dá)終點(diǎn)了")
    }
});

drawRect便是我們移動(dòng)的目標(biāo)。

drawRect : function(col,row){
    var ctx = this.canvas;
    ctx.save();
    ctx.clearRect(0,0,canvas.width,canvas.height);
    ctx.drawImage($("offset"),0,0)
    ctx.translate(2,2)
    ctx.fillStyle = "#ff0000";
    ctx.fillRect(col*this.cell,row*this.cell,this.cell-2,this.cell-2);
    ctx.restore();
},

到這里我們的迷宮便完成了。

作者：易企秀——樊一