摘要：整個思路十分簡單首先我們將迷宮視為一個行列的單元格組合，每一個單元格便可以表示為。用來儲存我們已訪問過的單元格，則記錄我們的訪問路徑。我們通過將單元格的，，，屬性設置為或來標識這個方向是否應該有邊框，同時該方向是否可走。

這個系列分為兩部分，第一部分為迷宮的生成及操作，第二部分為自動尋路算法。

我們先看效果：點擊查看

我們直入正題，先說一說生成迷宮的思路。
整個思路十分簡單：

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

我們假定從左上角開始出發，遍歷每一個單元格，如果該單元格未被訪問過，則查看其相鄰元素（上，下，左，右）是否有未訪問的單元格，如果有則隨機取出一個相鄰元素并打通他們之間的重合線，如果沒有則回退到上一個單元格。

上代碼：
首先我們創建一個構造函數：

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

在這個構造函數中，我們接收三個參數，分別為canvas元素，迷宮的行數與列數，并直接調用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方法中，我們首先根據傳入的列數col來計算單元格的寬度，然后構建一個maze_cells對象，其中每一行為一個數組，每個單元格包含的值分別代表x,y坐標，上下左右4個方向是否可以通行，是否訪問過，還有該單元格的g，h，f值。我們假定迷宮的開口位于整個迷宮的左上角，出口位于右下角。visitRooms用來儲存我們已訪問過的單元格，roomLine則記錄我們的訪問路徑。我們將迷宮的入口處和出口處的top，bottom分別設為true后再設置為false是為了在繪制的過程中不出現邊框，繪制完成后保證不能向上（下）移動。

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

接下來我們需要遍歷每一個單元格，如下通過遞歸的形式訪問每一個單元格，當某一個單元格的相鄰元素全部被訪問過并且roomLine數組為空時就意味著我們已經訪問了所有的單元格，具體原因自行腦補。

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){ //相鄰房間有未訪問房間
        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)
        }
    }
},

我們看到如果當前單元格的相鄰單元格有未訪問的，則執行breakWall方法，即打通當前單元格與相鄰單元格中間的墻，當然我們應該隨機選擇一個未訪問的相鄰單元格。我們通過將單元格的top，bottom，left，right屬性設置為true或false來標識這個方向是否應該有邊框，同時該方向是否可走。

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

進行完上面的兩步，我們的一個完整數組已經構成了，接下來便可以開始繪制了，top，left，right，bottom為false時則有邊框，true時無邊框。這一步比較簡單，我們在結尾調用了一個drawOffset方法，該方法將創建一個離屏對象，這樣我們在動態修改迷宮的時候可以直接將離屏的圖像繪制到當前畫布中。

drawCells : function(){
    var ctx = this.canvas,   //canvas對象
        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"
},

綁定事件比較簡單，我們為window監聽keydown事件，根據不同的keyCode來判斷我們應該行走的方向。

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("到達終點了")
    }
});

drawRect便是我們移動的目標。

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();
},

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