const m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

// maze.js

function getPoint(m, x, y) {
  if (x >= 0 && y >= 0 && x < m.length && y < m[x].length) {
    return m[x][y]
  } else {
    return 0
  }
}

function getNextPoint(m, current, lastPoint) {
  let [x, y] = current
  let nextPoint = [
    [x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]
  ].find(p => {
    let r1 = getPoint(m, p[0], p[1]) > 0
    let r2 = !isSamePoint(p, lastPoint)
    return r1 && r2
  })
  return nextPoint
}

function isSamePoint (p1, p2) {
  return p1[0] === p2[0] && p1[1] === p2[1]
}

function solveMaze (matrix, begin, end) {
  let path = []

  // 當(dāng)前點
  let current = begin
  path.push(current)

  // 上次走過的路
  let lastPoint = begin

  // 隨便挑一個可以走的點
  while (1) {
    if (isSamePoint(current, end)) {
      break
    }

    let validPoint = getNextPoint(matrix, current, lastPoint)

    path.push(validPoint)
    lastPoint = current
    current = validPoint
  }
  return path
}

const m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

console.log(
  solveMaze(m, [0, 0], [3, 4])
)

// maze.js
// ...

// 導(dǎo)出 solveMaze 函數(shù)，讓vue組件調(diào)用
export {
  solveMaze
}

<template>
  <div>
    <div class="div-matrix">
      <div v-for="(row, x) in matrix" :key="x">
        <div class="cell" 
          :class="{ black: p <= 0, path: isPath(x, y) }"
          v-for="(p, y) in row" :key="y" :style="{ left: `${y * 2.5}em`, top: `${x * 2.5}em` }">
          {{ begin[0] === x && begin[1] === y ? 'B' : '' }}
          {{ end[0] === x && end[1] === y ? 'E' : '' }}
        </div>
      </div>
    </div>
  </div>
</template>

<script>
import { solveMaze } from './maze'

export default {
  data () {
    return {
      begin: [0, 0],
      end: [3, 4],
      matrix: [],
      paths: []
    }
  },
  methods: {
    isPath (x, y) {
      const p = this.paths.find(path => path[0] === x && path[1] === y)
      return p
    }
  },
  created () {
    const m = this.matrix = [
      [1, 1, 0, 0, 0],
      [0, 1, 1, 1, 0],
      [0, 0, 0, 1, 0],
      [0, 0, 0, 1, 1]
    ]
    this.paths = solveMaze(m, this.begin, this.end)
  }
}
</script>

<style>
.top {
  margin-bottom: 1em;
}
.div-matrix {
  position: relative;
}
.cell {
  border: 1px black solid;
  width: 2em;
  height: 2em;
  position:absolute;
  text-align: center;
}
.cell.path {
  border: 1px red solid;
}
.black {
  background: black;
}
</style>

const m = this.matrix = [
  [1, 1, 0, 0, 0],
  [1, 1, 1, 1, 1],
  [0, 1, 0, 1, 0],
  [0, 1, 0, 1, 1]
]

const m = [
  1, 1, 0, 0, 0,
  1, 1, 1, 1, 1,
  0, 1, 0, 1, 0,
  0, 1, 0, 1, 1
]

class Node {
  constructor (x, y, value) {
    this.x = x
    this.y = y
    this.value = value
    this.checked = false
    this.nearNodes = []
  }
}

class NodeGraph {
  constructor (matrix, width, height) {
    this.nodes = []
    this.matrix = matrix
    this.width = width
    this.height = height
  }

  buildNodeGraph () {
    let { width, height } = this
    
    for (let y = 0; y < height; y++) {
      for (let x = 0; x < width; x++) {
        let node = this.getNode(x, y)
  
        let up = this.getNode(x, y - 1)
        let down = this.getNode(x, y + 1)
        let left = this.getNode(x - 1, y)
        let right = this.getNode(x + 1, y)
        node.nearNodes = [ up, down, left, right].filter(node => node && node.value === 1)
      }
    }
  }

  getNode (x, y) {
    let { nodes, width, matrix } = this
    if (x >= 0 && y >= 0) {
      let node = nodes[y * width + x]
      if (!node) {
        let value = matrix[y * width + x]
        if (value !== undefined) {
          node = new Node(x, y, value)
          nodes[y * width + x] = node
        }
      }
      return node
    } else {
      return null
    }
  }
}

// ...
for (let node of current.nearNodes) {
  if (node.checked === false) {
	node.parent = current
	queue.push(node)
  }
}
// ...

function buildPath (endNode) {
  let path = []
  let node = endNode

  while (node) {
    path.push(node)
    node = node.parent
  }

  return path
}

// ...

    if (equalsNode(current, nodeGraph.endNode)) {
      while (equalsNode(current, nodeGraph.endNode)) {
        await sleep(1000)
      }
      continue
    }
// ...

class Node {
  constructor (x, y, value) {
    this.x = x
    this.y = y
    this.value = value
    this.endDistance = 0 // 與終點的距離，忽略中間的障礙
    this.checked = false
    this.parent = null
    this.nearNodes = []
  }
}

function getDistance (nodeA, nodeB) {
  const x = Math.abs(nodeB.x - nodeA.x)
  const y = Math.abs(nodeB.y - nodeA.y)
  return (x + y)
}

class NodeGraph {
// ...

  popBestNextNode () {
    let { queue } = this
    let bestNode = queue[0]
    let bestNodeIndex = 0
    let { length } = queue

    for (let i = 0; i < length; i++) {
      let node = queue[i]
      if (node.endDistance < bestNode.endDistance) {
        bestNode = node
        bestNodeIndex = i
      }
    }

    queue.splice(bestNodeIndex, 1)
    return bestNode
  }
// ...
}

// ...
for (let node of current.nearNodes) {
  if (node.checked === false && node.value) {
	node.parent = current
	node.checked = true
	node.endDistance = getDistance(node, nodeGraph.endNode)
	node.beginDistance = current.beginDistance + 1
	node.cost = node.endDistance + node.beginDistance
	nodeGraph.queue.push(node)
  }
}
// ...

/**
 * 獲取 Node 的 RGB 值
 * @param {Node} node 
 * @returns 
 */
function getNodeRGB (node) {
  let { value } = node
  let r = value & 0xFF
  let g = value >> 8 & 0xFF
  let b = value >> 16 & 0xFF
  return [ r, g, b ]
}

  getNearNodes (node) {
    let { x, y } = node
    let up = this.getNode(x, y - 1)
    let down = this.getNode(x, y + 1)
    let left = this.getNode(x - 1, y)
    let right = this.getNode(x + 1, y)
    return [ up, down, left, right ].filter(node => node !== null)
  }

let nearNodes = nodeGraph.getNearNodes(current)
for (let i = nearNodes.length - 1; i >= 0; i--) {
  let node = nearNodes[i]
  if (node.checked === false) {
	node.checked = true

	let colordiff = getNodeColorDiff(node, current)
	const colorDiffThreshold = 2 // 容許通過的顏色差異，范圍 0~100

	node.parent = current
	node.endDistance = getDistance(node, nodeGraph.endNode)
	node.beginDistance = current.beginDistance + 1

	if (mode === "1") { // 嚴(yán)格
	  node.cost = node.endDistance + node.beginDistance

	  if (colordiff < colorDiffThreshold) {
		nodeGraph.queue.push(node)
	  }
	} else if (mode === "2") { // 模糊
	  node.cost = node.endDistance + node.beginDistance + (colordiff * width * height)
	  nodeGraph.queue.push(node)
	}
  }
}