Prim演算法生成迷宮

初始化地圖

function initMaze(r,c){
  let row = new Array(2 * r + 1)
  
  for(let i = 0; i < row.length; i++){
    let column = new Array(2 * c + 1)
    row[i] = column
    for(let j = 0; j < column.length; j++){
       row[i][j] = 1
    }
  }
  
  for(let i = 0; i < r; i++){
    for(let j = 0; j < c; j++){
      row[2 * i + 1][2 * j + 1] = 0
    }
  }
  
  console.log(row)
}

initMaze(3,3)

計算二維數組坐標位置

let arr = [
   [0,0,0],
   [0,0,0],
   [0,0,0]
]

for(let i = 0; i < 9; i++){
    let row = Math.floor(i / 3)
    let column = i % 3
    arr[row][column] = false
}

console.log(arr)

偏移量方向預製

let offset = [
    {
        x:-1,
        y:0
    },
    {
        x:1,
        y:0
    },
    {
        x:0,
        y:-1
    },
    {
        x:0,
        y:1
    }
]

let x = 0
let y = 0

for(let i = 0; i < offset.length; i++){
    x = x + offset[i].x
    y = y + offset[i].y

    console.log(x,y)
}

隨機數公式

1.　　0-x之間的隨機數：
Math.round(Math.random()*x);

2.　　x至y之間的隨機數
Math.round(Math.random()*(y-x)+x);

3.　　1-x之間的隨機數：
Math.ceil(Math.random()*x);

Prim演算法

const INF = Number.MAX_SAFE_INTEGER

function findMinKey(graph,key,visited){
    let min = INF
    let minIndex
    //找到候選邊中成本最小的節點
    for(let v = 0; v < graph.length; v++){
        if(!visited[v] && key[v] < min){
            min = key[v]
            minIndex = v
        }
    }
    return minIndex
}

const prim = (graph) => {
    const visited = [],
          key = [],
          parent = [];

    let {length} = graph;

    for(let v = 0; v < length; v++){
        visited[v] = false
        key[v] = INF
    }
    //把到第一個頂點的權值初始化為0
    key[0] = 0
    parent[0] = -1
    //根節點不需要比
    for(let i = 0; i < length - 1; i++){
        //找到成本最小邊的頂點
        let u = findMinKey(graph,key,visited)
        //標記下該頂點已被訪問
        visited[u] = true;
        //以及該頂點到對應其他頂點是不是成本最小的
        //如果是那麼就走到該頂點去
        for(let v = 0; v < length; v++){
            if(graph[u][v] && !visited[v] && graph[u][v] < key[v]) {
                parent[v] = u
                key[v] = graph[u][v]
            }
        }
    }
    return parent
}

const graph = [
    [0,2,4,0,0,0],
    [2,0,2,4,2,0],
    [4,2,0,0,3,0],
    [0,4,0,0,3,2],
    [0,2,3,3,0,2],
    [0,0,0,2,2,0]
]
const parent = prim(graph)
console.log('Edge    Weight')
for (let i = 1; i < graph.length; i++) {
    console.log(parent[i] + ' - ' + i + '   ' + graph[i][parent[i]]);
}

使用Prim演算法生成迷宮

1. 生成2 * k + 1的迷宮，1表示牆，0表示路
2. 隨機選一個頂點，在該頂點上下左右隨機抽取一個位置，如果沒有訪問過而且沒有越界就選這個點生成迷宮
3. 重覆第2步

function roadmap(r,c){
    let map = []
    let rLen = 2 * r + 1
    let cLen = 2 * c + 1

    for(let i = 0; i < rLen; i++){
        map[i] = []
        for(let j = 0; j < cLen; j++){
          //生成0101的格式
          if((i ^ (i - 1)) === 1 && (j ^ (j - 1)) === 1){
            map[i][j] = 0
          }else{
            map[i][j] = 1
          }
        }
    }

    map[1][0] = 0;
    map[2 * r - 1][2 * c] = 0;
 
    return map
}

const MathUtil = {
    randomInt(a = 0,b){
        if(typeof b === 'undefined'){
            return Math.floor(Math.random() * a)
        } else {
            return Math.floor(Math.random() * (b - a) + a) 
        }
    }
}

function maze(map){
    let row = map.length >> 1
    let col = map[0].length >> 1
    let size = row * col
    let notAccessed = new Array(size).fill(0)
    let accessed = []
    let cur = MathUtil.randomInt(0,size)
    let offsS = [-col,col,-1,1] //cur在notAccessed要走的偏移量
    let offsR = [-1,1,0,0] //cur在map中row要走的偏移量
    let offsC = [0,0,-1,1]//cur在map中col要走的偏移量

    accessed.push(cur)
    notAccessed[cur] = 1

    while(accessed.length < size){
        let tr = Math.floor(cur / row)
        let tc = cur % col
        let num = 0;
        let pos = -1

        //判斷四周格子是不是可以走
        while(num++ < 4){
            let dir = MathUtil.randomInt(0,4)
            nr = tr + offsR[dir]
            nc = tc + offsC[dir]

            if(nr >= 0 && nc >= 0 && nr < row && nc < col && notAccessed[cur + offsS[dir]] === 0){
                pos = dir
                break 
            }
        }

        if(pos < 0){
            //堵死的情況
            cur = accessed[MathUtil.randomInt(0,accessed.length)]
        }else{
            //可以走的情況
            tr = 2 * tr + 1
            tc = 2 * tc + 1
            
            map[tr + offsR[pos]][tc + offsC[pos]] = 0
            cur = cur + offsS[pos]
            notAccessed[cur] = 1

            accessed.push(cur)
        }
    }
    
    return map
}

function geMaze(r,c){
    return maze(roadmap(r,c))
}