初始化地图
- 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 算法生成迷宫
生成 2 * k + 1 的迷宫, 1 表示墙, 0 表示路
随机选一个顶点, 在该顶点上下左右随机抽取一个位置, 如果没有访问过而且没有越界就选这个点生成迷宫
重复第 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))
- }
来源: http://www.bubuko.com/infodetail-3061495.html