Javascript結合Vue實現對任意迷宮圖片的自動尋路
前言
可以直接體驗最終效果：https://maze-vite.vercel.app/
尋路前：
尋路後，自動在圖片上生成紅色路徑，藍色是探索過的區域：
這裡我故意用手機斜著角度拍，就是為瞭展示程序完全可以處理手機從現實拍攝的迷宮圖片。
整個程序我準備用 Vue 3 + Vite 來寫，但其實用不用 Vue 都一樣，不會涉及復雜的界面，用別的框架甚至不用框架其實也完全可以。
二維數組，一本道
說瞭要從零開始，所以先嘗試從非常簡單的迷宮入手吧
對於我們人類來說，這個迷宮十分簡單，顯而易見的隻有一條路。但是計算機解決這樣的迷宮還是得稍微花費那麼一點力氣的。
二維數組很適合用來表達這個迷宮：
const m = [ [1, 1, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 1, 0], [0, 0, 0, 1, 1] ]
1 代表可以走的格子，0 代表不能走的格子。每個格子可以使用 [x, y] 來表示，比如這裡起點是 [0, 0]，終點是 [3, 4]。
那麼應該有這麼一個函數： function solveMaze (matrix, begin, end) {//...}，matrix是描述迷宮的二維數組，begin 是起點，end 是終點，最終返回值是一個有序集合，每一個元素是一個格子，代表正確的路線軌跡。
這裡我們準備采用的策略十分簡單，從起點開始，看看周圍上下左右（不能斜著走）哪些是可以走的格子，然後移動到這個格子，接著循環上面的步驟，直到遇到 end 格子，註意還需要記錄上一步的格子，把它排除，以免走回頭路。具體看以下代碼：
// 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 = []
// 當前點
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])
)
getNextPoint 獲取可以下一步通行的格子，solveMaze 獲取最終可行走的路徑，控制臺輸出：
這些坐標就是最終的行走軌跡，目測是正確的。
映射基礎界面
為瞭方便測試觀察，得把我們的數據結構映射到網頁上面。
// maze.js
// ...
// 導出 solveMaze 函數，讓vue組件調用
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>
最終效果：
其實就是通過二維數組 matrix 生成對應 div，數組裡面元素值決定黑白。paths 數組存儲結果路徑，把路徑用紅色邊框標記出來。這樣就方便以後測試結果的查看瞭。
廣度優先，地毯式搜索
看看下面這個迷宮：
const m = this.matrix = [ [1, 1, 0, 0, 0], [1, 1, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 0, 1, 1] ]
如果把他應用到上面的代碼，會發現頁面卡死瞭，這是因為這個迷宮含有岔路，導致算法一直在繞圈。我們需要一些手段，把走過的路記住，以後就不再走瞭，方法不難，隻要把當前可以走的格子，放進一個隊列中，然後要做的，就是不斷對這個隊列裡的格子，作出同樣處理，直到遇到終點格子。
為瞭方便我們用算法進行處理，需要使用新的數據結構來表達，它就是 圖(Graph) 結構。
圖結構和鏈表很像，最大不同是每個節點可以有多個指針指向不同的節點。
同時把二維數組給他降維打擊，變成一維：
const m = [ 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1 ]
雖然這樣訪問起來不那麼直接，但是隻需要一次尋址，復制傳輸也比二維數組方便得多。
然後創建一個 Node 類代表節點，NodeGraph 類代表整個圖結構。
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
}
}
}
buildNodeGraph 把 matrix 數組轉換為圖結構，每個節點的 nearNodes 就相當於是下一步可以走的格子集合，checked 表示這個節點是否已經探索過。
為瞭方便查看每一步狀態的變化，需要把當前所在格子和隊列中的格子，在畫面上標記出來，完整代碼我就不貼瞭，codesandbox 可以隨意看：
藍色邊框就是隊列中的格子，小人就是當前所在的格子，當它走到右下角時就會停下來。
目前做的，隻是順利讓小人移動到終點而已，但是怎麼得出我們要的路徑呢？方法就是在 Node 多加一個屬性 parent，記錄上一個 Node。當取出 nearNodes 時，把當前節點賦值到每一個 nearNode 的 parent 即可：
// ...
for (let node of current.nearNodes) {
if (node.checked === false) {
node.parent = current
queue.push(node)
}
}
// ...
然後就是從當前節點，讀取 parent 一個一個回溯即可：
function buildPath (endNode) {
let path = []
let node = endNode
while (node) {
path.push(node)
node = node.parent
}
return path
}
效果：
當小人到達終點時，紅色方格就是最短路徑瞭。
地圖編輯
稍微改動下代碼，讓我們可以實時編輯迷宮，測試更加方便。
操作：點擊方格可以改變黑白狀態，按住alt點擊可以設置新的目標點。
逐漸把 solveMaze 裡面的局部變量移到 NodeGraph 類裡面，這樣外部訪問更加便利。註意當尋路結束的時候，不要結束函數，而是使用 while 循環一直等待新的目標點被設置：
// ...
if (equalsNode(current, nodeGraph.endNode)) {
while (equalsNode(current, nodeGraph.endNode)) {
await sleep(1000)
}
continue
}
// ...
優化尋路算法
想象一下這種情形：
起點和終點一條直線，中間毫無阻擋，但是這個小人竟然到處跑，好一會才到終點，這樣下去不行的，必須要優化。
在 Node 類加一個屬性 endDistance 記錄每個節點到終點的距離，getDistance 函數根據坐標可以直接計算出距離，這個距離是沒有考慮到中間可能出現的障礙的，但對路線的評估也十分有用：
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)
}
每次通過 popBestNextNode 方法從隊列取出 endDistance 最小的 Node：
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
}
// ...
}
既然有 endDistance，那也要有 beginDistance，用來記錄從起點走過來的步數。這個數值不直接從坐標計算，而是隨著前進累加，這樣 beginDistance 就不是估算值瞭，而是實際值：
// ...
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)
}
}
// ...
考慮到以後可能會有新的因素加入，所以直接添加一個 cost 屬性，用來表達 成本。目前 cost 就是 endDistance + beginDistance，cost 越小，優先級越高。
像這樣的情況，小人一開始企圖從上方靠近，但是隨著不斷前進，經過的步數越來越多，倒不如走下面瞭，於是就放棄的上面的路線。
現在，小人的行動變成更加靠譜瞭：
對圖片進行尋路
拿這張我隨便畫的圖來作為參數：
目標是從 B 點到達 E 點，我們隻需要讀取這張圖片的像素，根據黑白顏色，轉換成為一個數組，放到 solveMaze 函數即可。
為此，需要有一個 input 標簽，type=”file”，用來選擇圖片，通過 URL.createObjectURL(File) 生成一個 URL，然後使用 new Image() 創建一個 img 標簽，它不需要添加進 body，把 url 給到 img.src。通過 CanvasRenderingContext2D.drawImage() 復制進 Canvas，再調用 CanvasRenderingContext2D.getImageData() 即可獲取像素數組。
這時不能再用 div 去渲染瞭，因為這張圖幾萬個像素，每個像素一個 div 的話，瀏覽器也吃不消，再加上將來圖片將會更大。
所以這裡改用 Canvas 進行渲染，安排三個 Canvas，一個顯示迷宮的原圖，一個顯示探索過的節點，一個顯示當前最短路徑，也就是 path 數組裡面的節點，然後把這三個 Canvas 疊在一起即可，最後就是在回調裡面去更新後面兩個 Canvas 即可。
把我上面的圖片下載到自己電腦，點擊選擇文件按鈕選擇圖片，然後就能看到效果瞭，選別的圖片也可以，隻是我的起點和終點坐標是寫死的，而且代碼沒有優化過，太大的圖片恐怕難以處理。
註意：如果遇到跨域問題那就要自己上傳圖片瞭。
自定義起始點，以及隨時變更路線
利用點擊事件中的 offsetX、offsetY 即可知道點擊坐標，把起點和終點的坐標保存起來，一旦有變化，則停止之前的尋路函數，重新執行當前的尋路函數，因此需要在循環中作一個判斷來決定是否退出函數，這件事情適合在回調裡面做。
然後提供一個輸入框，自由調整經歷多少個循環才更新一次畫面，這樣能調整尋路的速度。
處理彩色圖片
預覽：https://codesandbox.io/s/maze-vite-8-h845p?file=/src/App.vue (註意如果出現跨域錯誤，就自己上傳圖片吧)
不放iframe瞭，感覺放太多瞭，讓這個頁面已經相當卡。
前面都是默認白色像素是可以行走的區域，現在嘗試把顏色相似的附近像素作為行走區域，這樣效果會更加好。
直接把 rgba 顏色數據傳入 solveMaze，然後在循環中計算出相鄰節點與當前節點的顏色差距，差距過大則不放入隊列。
把一個 rgba 整數的各個通道拆分開來可以這麼寫：
/**
* 獲取 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 ]
}
求 rgb 顏色的相似度，最樸素的方法是把兩個顏色看成是兩個三維坐標的點，然後求其歐幾裡得距離，但這不符合人眼的感知模型。詳細方法wiki已經有瞭：https://zh.wikipedia.org/wiki/顏色差異
關於這方面的運算有點復雜，我都寫到瞭 color.js 裡面瞭。
結果：
註意代碼裡的 colorDiffThreshold，目前我用的 2.25，如果太高，會導致穿墻，太低則容易找不到路失敗。
性能優化
當點擊兩次畫面後，需要稍微等一會才會開始尋路，這裡應該耗費瞭不少CPU。打開 DevTools 的性能分析器分析下到底是哪裡消耗最多性能：
很明顯 solveMaze 函數占據瞭大多數時間，展開下面的 Call Tree：
buildNodeGraph 和 getNode 是優化重點，打開代碼，可以直接看到每句話耗費的CPU時間：
57 行的 if (!node) {...} 明明是簡單的判斷，卻耗費瞭不少時間，試試看改成 node === undefined，並且 value 也不再需要判斷瞭。對 nodes 數組的訪問與讀取也耗費不少時間，嘗試一開始用 new Array(length) 初始化，應該會好一些。優化之後的代碼：
看起來稍微好一些。
在尋路途中進行性能監測：
發現 buildPath 相當的耗費時間，這也是理所應當的，畢竟每次循環都調用，並且完整遍歷整個鏈條。處理辦法也簡單，隻在最後出結果時調用他即可，根據前面的經驗，while (node) 改為 while (node !== null)。
現在他完全沒有存在感瞭。
然後是 for…of 語句，建議改為傳統的數組下標自減，這是最快的，當然日常使用 for…of 可讀性更強。
然後是 popBestNextNode：
這裡每次都完整遍歷整個數組找出cost最小的節點，最後還有一個數組元素移除的操作。我真的很難判斷 JavaScript 的數組到底是存儲在連續內存裡面還是分散的，但是不管怎麼樣，這裡完全可以使用二叉堆替代來獲取更好的性能。具體就不自己實現瞭，直接用現成的：https://www.npmjs.com/package/heap-js。註意 new Heap() 的時候傳入自定義的比較器，然後把 popBestNextNode 的實現改為 return this.queue.pop() 即可。
最後，把 buildNodeGraph 的那兩層for循環全部移除，不再預先初始化所有的 Node，給 NodeGraph 添加一個新方法：
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)
}
在後面的尋路循環中再去調用 getNearNodes 來獲取相鄰的節點，這樣就大幅縮減瞭一開始的卡頓瞭。
最後，提供兩種策略：
- 嚴格：當相鄰像素顏色差距小於某個值，才加入隊列。適合行走區域的顏色變化不大的圖片，得出的結果幾乎就是最短的路徑。
- 模糊：相鄰像素無論顏色的差距，都加入隊列，其差距值乘以某些系數，作為節點的 cost。適合任何圖片，最終總是能找到一條路。。。
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") { // 嚴格
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)
}
}
}
源代碼：https://gitee.com/judgeou/maze-vite
到此這篇關於Javascript結合Vue實現對任意迷宮圖片的自動尋路的文章就介紹到這瞭,更多相關Javascript結合Vue迷宮自動尋路內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- C++ 雙向循環鏈表類模版實例詳解
- C++圖解單向鏈表類模板和iterator迭代器類模版詳解
- 一文教你用python編寫Dijkstra算法進行機器人路徑規劃
- JavaScript實現二叉搜索樹
- element-ui tree 手動展開功能實現(異步樹也可以)