运用Union-Find 算法在生成迷宫(javascript)

生成的效果图

屏幕快照 2017-09-25 上午10.53.19.png

var canvas = document.getElementById("maze");
var path = document.getElementById("path");

class UF {
  constructor(size) {
    this.count = size;
    this.parent = new Array(size);
    this.size = new Array(size);
    for (var i = size-1; i >= 0; i--) {
      this.parent[i] = i;
      this.size[i] = 1;
    }
  }
  find(p) {
    if(p < 0 || p>= this.count) return;
    if(this.parent[p] !== p) {
      this.parent[p] = this.find(this.parent[p]);
    }
    return this.parent[p];
  }

  connected(p,q) {
    return this.find(p) === this.find(q);
  }

  union(p,q) {
    let rootP = this.find(p);
    let rootQ = this.find(q);
    if(rootP === rootQ) return;
    if(this.size[rootP] < this.size[rootQ]){
      this.parent[rootP] = rootQ;
      this.size[rootQ] += this.size[rootP];
    }else{
      this.parent[rootQ] = rootP;
      this.size[rootP] += this.size[rootQ];
    }
  }

}

class Maze {
  constructor(m,n,canvas) {
    this.rows = m;
    this.cols = n;
    this.size = m*n;
    this.canvas = canvas;
    this.UF = new UF(this.size);
    this.linkedMap = {};
    this.pathTo = [];
  }

  generate() {
    // 第0个和任意一个都要相同
    while(!this.firstConnectAll()) {
      let cellPair = this.pickRandomPair();
      if(!this.UF.connected(cellPair[0],cellPair[1])){
        this.UF.union(cellPair[0],cellPair[1]);
        this.addToLinkMap(cellPair[0],cellPair[1]);
      }
    }
  }

  // 用BFS, 无权图的Dijkstra 算法 0 -> this.size-1
  findPath() {

    // console.log(this.linkedMap)

    let queue = [0];
    let visited = new Set();
    while(queue.length > 0) {
      let cur = queue.shift();
      visited.add(cur);
      let that = this;
      this.linkedMap[cur].forEach(function(neighbor,i){
        if(!visited.has(neighbor)) {
          queue.push(neighbor);
          that.pathTo[neighbor] = cur;
          if(neighbor === that.size -1) {
            return;
          }
        }
      })
    }


  }

  drawPath() {
    var i = this.size-1;
    var cellWidth = this.canvas.width / this.cols,
        cellHeight = this.canvas.height / this.rows;

    var ctx = path.getContext("2d");
    //translate 0.5个像素，避免模糊
    ctx.translate(0.5, 0.5);
    ctx.strokeStyle = "red";
    
    while(i > 0){
      var row = i / this.cols >> 0,
          col = i % this.cols;

      var nextRow = this.pathTo[i] / this.cols >> 0,
          nextCol = this.pathTo[i] % this.cols;

      ctx.moveTo((col + 0.5) * cellWidth , (row + 0.5) * cellHeight );

      ctx.lineTo((nextCol + 0.5) * cellWidth , (nextRow + 0.5) * cellHeight);
      i = this.pathTo[i];
    }
    ctx.stroke();
  }

  draw(){ 
    var linkedMap = this.linkedMap;
    var cellWidth = this.canvas.width / this.cols,
        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.size; i++){
        var row = i / this.cols >> 0,
            col = i % this.cols;
        //画右边的竖线
        if(col !== this.cols - 1 && (!linkedMap[i] || linkedMap[i].indexOf(i + 1) < 0)){
            ctx.moveTo((col + 1) * cellWidth >> 0, row * cellHeight >> 0);
            ctx.lineTo((col + 1) * cellWidth >> 0, (row + 1) * cellHeight >> 0);
        }
        //画下面的横线
        if(row !== this.rows - 1 && (!linkedMap[i] || linkedMap[i].indexOf(i + this.cols) < 0)){
            ctx.moveTo(col * cellWidth >> 0, (row + 1) * cellHeight >> 0);
            ctx.lineTo((col + 1) * cellWidth >> 0, (row + 1) * cellHeight >> 0);
        }
    }
    //最后再一次性stroke，提高性能
    ctx.strokeStyle = "black";
    ctx.stroke();
    //画迷宫的四条边框
    this.drawBorder(ctx, cellWidth, cellHeight);
  }

  drawBorder(ctx,cellWidth,cellHeight) {
    ctx.moveTo(0,0);
    ctx.lineTo(this.cols*cellWidth,0);

    ctx.moveTo(this.cols*cellWidth-1,0);
    ctx.lineTo(this.cols*cellWidth-1,(this.rows-1)*cellHeight);

    ctx.moveTo(this.cols*cellWidth,this.rows*cellHeight-1);
    ctx.lineTo(0,this.rows*cellHeight-1);

    ctx.moveTo(0,this.rows*cellHeight);
    ctx.lineTo(0,cellHeight);
    ctx.stroke();
  }

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

  firstConnectAll(){
    for (var i = this.size - 1; i >= 0; i--) {
      if(!this.UF.connected(0,i)) return false;
    }
    return true;
  }

  pickRandomPair() {
    let num = (Math.random()*this.size)>>0;
    let neighborCells = [];
    let row = (num / this.cols)>>0;
    let col = num % this.cols;
    // 上下左右
    if(row > 0) {
      neighborCells.push((row-1)*this.cols+col);
    }
    if(row < this.rows-1) {
      neighborCells.push((row+1)*this.cols+col);
    }
    if(col > 0) {
      neighborCells.push(row*this.cols+col-1);
    }
    if(col < this.cols-1) {
      neighborCells.push(row*this.cols+col+1);
    }
    let index = (Math.random() * neighborCells.length) >> 0;
    return [num,neighborCells[index]];
  }
}

let maze = new Maze(50,50,canvas);

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

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

maze.findPath();
maze.drawPath();