目錄前言二維數(shù)組，一本道映射基礎(chǔ)界面廣度優(yōu)先，地毯式搜索地圖編輯優(yōu)化尋路算法對圖片進(jìn)行尋路自定義起始點，以及隨時變更路線處理彩色圖片性能優(yōu)化前言

可以直接體驗最終效果：https://maze-vite.vercel.app/

尋路前：

尋路后，自動在圖片上生成紅色路徑，藍(lán)色是探索過的區(qū)域：

這里我故意用手機斜著角度拍，就是為了展示程序完全可以處理手機從現(xiàn)實拍攝的迷宮圖片。

整個程序我準(zhǔn)備用 Vue 3 + Vite 來寫，但其實用不用 Vue 都一樣，不會涉及復(fù)雜的界面，用別的框架甚至不用框架其實也完全可以。

二維數(shù)組，一本道

說了要從零開始，所以先嘗試從非常簡單的迷宮入手吧

對于我們?nèi)祟悂碚f，這個迷宮十分簡單，顯而易見的只有一條路。但是計算機解決這樣的迷宮還是得稍微花費那么一點力氣的。

二維數(shù)組很適合用來表達(dá)這個迷宮：

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]。

那么應(yīng)該有這么一個函數(shù)： function solveMaze (matrix, begin, end) {//...}，matrix是描述迷宮的二維數(shù)組，begin 是起點，end 是終點，最終返回值是一個有序集合，每一個元素是一個格子，代表正確的路線軌跡。

這里我們準(zhǔn)備采用的策略十分簡單，從起點開始，看看周圍上下左右（不能斜著走）哪些是可以走的格子，然后移動到這個格子，接著循環(huán)上面的步驟，直到遇到 end 格子，注意還需要記錄上一步的格子，把它排除，以免走回頭路。具體看以下代碼：

// maze.jsfunction 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]))

getNextPoint 獲取可以下一步通行的格子，solveMaze 獲取最終可行走的路徑，控制臺輸出：

這些坐標(biāo)就是最終的行走軌跡，目測是正確的。

映射基礎(chǔ)界面

為了方便測試觀察，得把我們的數(shù)據(jù)結(jié)構(gòu)映射到網(wǎng)頁上面。

// 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 : 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>

最終效果：

其實就是通過二維數(shù)組 matrix 生成對應(yīng) div，數(shù)組里面元素值決定黑白。paths 數(shù)組存儲結(jié)果路徑，把路徑用紅色邊框標(biāo)記出來。這樣就方便以后測試結(jié)果的查看了。

廣度優(yōu)先，地毯式搜索

看看下面這個迷宮：

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

如果把他應(yīng)用到上面的代碼，會發(fā)現(xiàn)頁面卡死了，這是因為這個迷宮含有岔路，導(dǎo)致算法一直在繞圈。我們需要一些手段，把走過的路記住，以后就不再走了，方法不難，只要把當(dāng)前可以走的格子，放進(jìn)一個隊列中，然后要做的，就是不斷對這個隊列里的格子，作出同樣處理，直到遇到終點格子。

為了方便我們用算法進(jìn)行處理，需要使用新的數(shù)據(jù)結(jié)構(gòu)來表達(dá)，它就是 圖(Graph) 結(jié)構(gòu)。

圖結(jié)構(gòu)和鏈表很像，最大不同是每個節(jié)點可以有多個指針指向不同的節(jié)點。

同時把二維數(shù)組給他降維打擊，變成一維：

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

雖然這樣訪問起來不那么直接，但是只需要一次尋址，復(fù)制傳輸也比二維數(shù)組方便得多。

然后創(chuàng)建一個 Node 類代表節(jié)點，NodeGraph 類代表整個圖結(jié)構(gòu)。

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 } = thisfor (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 數(shù)組轉(zhuǎn)換為圖結(jié)構(gòu)，每個節(jié)點的 nearNodes 就相當(dāng)于是下一步可以走的格子集合，checked 表示這個節(jié)點是否已經(jīng)探索過。

為了方便查看每一步狀態(tài)的變化，需要把當(dāng)前所在格子和隊列中的格子，在畫面上標(biāo)記出來，完整代碼我就不貼了，codesandbox 可以隨意看：

藍(lán)色邊框就是隊列中的格子，小人就是當(dāng)前所在的格子，當(dāng)它走到右下角時就會停下來。

目前做的，只是順利讓小人移動到終點而已，但是怎么得出我們要的路徑呢？方法就是在 Node 多加一個屬性 parent，記錄上一個 Node。當(dāng)取出 nearNodes 時，把當(dāng)前節(jié)點賦值到每一個 nearNode 的 parent 即可：

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

然后就是從當(dāng)前節(jié)點，讀取 parent 一個一個回溯即可：

function buildPath (endNode) { let path = [] let node = endNode while (node) { path.push(node) node = node.parent } return path}

效果：

當(dāng)小人到達(dá)終點時，紅色方格就是最短路徑了。

地圖編輯

稍微改動下代碼，讓我們可以實時編輯迷宮，測試更加方便。

操作：點擊方格可以改變黑白狀態(tài)，按住alt點擊可以設(shè)置新的目標(biāo)點。

逐漸把 solveMaze 里面的局部變量移到 NodeGraph 類里面，這樣外部訪問更加便利。注意當(dāng)尋路結(jié)束的時候，不要結(jié)束函數(shù)，而是使用 while 循環(huán)一直等待新的目標(biāo)點被設(shè)置：

// ... if (equalsNode(current, nodeGraph.endNode)) { while (equalsNode(current, nodeGraph.endNode)) {await sleep(1000) } continue }// ...優(yōu)化尋路算法

想象一下這種情形：

起點和終點一條直線，中間毫無阻擋，但是這個小人竟然到處跑，好一會才到終點，這樣下去不行的，必須要優(yōu)化。

在 Node 類加一個屬性 endDistance 記錄每個節(jié)點到終點的距離，getDistance 函數(shù)根據(jù)坐標(biāo)可以直接計算出距離，這個距離是沒有考慮到中間可能出現(xiàn)的障礙的，但對路線的評估也十分有用：

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 = nodebestNodeIndex = i } } queue.splice(bestNodeIndex, 1) return bestNode }// ...}

既然有 endDistance，那也要有 beginDistance，用來記錄從起點走過來的步數(shù)。這個數(shù)值不直接從坐標(biāo)計算，而是隨著前進(jìn)累加，這樣 beginDistance 就不是估算值了，而是實際值：

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

考慮到以后可能會有新的因素加入，所以直接添加一個 cost 屬性，用來表達(dá) 成本。目前 cost 就是 endDistance + beginDistance，cost 越小，優(yōu)先級越高。

像這樣的情況，小人一開始企圖從上方靠近，但是隨著不斷前進(jìn)，經(jīng)過的步數(shù)越來越多，倒不如走下面了，于是就放棄的上面的路線。

現(xiàn)在，小人的行動變成更加靠譜了：

對圖片進(jìn)行尋路

拿這張我隨便畫的圖來作為參數(shù)：

目標(biāo)是從 B 點到達(dá) E 點，我們只需要讀取這張圖片的像素，根據(jù)黑白顏色，轉(zhuǎn)換成為一個數(shù)組，放到 solveMaze 函數(shù)即可。

為此，需要有一個 input 標(biāo)簽，type='file'，用來選擇圖片，通過 URL.createObjectURL(File) 生成一個 URL，然后使用 new Image() 創(chuàng)建一個 img 標(biāo)簽，它不需要添加進(jìn) body，把 url 給到 img.src。通過 CanvasRenderingContext2D.drawImage() 復(fù)制進(jìn) Canvas，再調(diào)用 CanvasRenderingContext2D.getImageData() 即可獲取像素數(shù)組。

這時不能再用 div 去渲染了，因為這張圖幾萬個像素，每個像素一個 div 的話，瀏覽器也吃不消，再加上將來圖片將會更大。

所以這里改用 Canvas 進(jìn)行渲染，安排三個 Canvas，一個顯示迷宮的原圖，一個顯示探索過的節(jié)點，一個顯示當(dāng)前最短路徑，也就是 path 數(shù)組里面的節(jié)點，然后把這三個 Canvas 疊在一起即可，最后就是在回調(diào)里面去更新后面兩個 Canvas 即可。

把我上面的圖片下載到自己電腦，點擊選擇文件按鈕選擇圖片，然后就能看到效果了，選別的圖片也可以，只是我的起點和終點坐標(biāo)是寫死的，而且代碼沒有優(yōu)化過，太大的圖片恐怕難以處理。

注意：如果遇到跨域問題那就要自己上傳圖片了。

自定義起始點，以及隨時變更路線

利用點擊事件中的 offsetX、offsetY 即可知道點擊坐標(biāo)，把起點和終點的坐標(biāo)保存起來，一旦有變化，則停止之前的尋路函數(shù)，重新執(zhí)行當(dāng)前的尋路函數(shù)，因此需要在循環(huán)中作一個判斷來決定是否退出函數(shù)，這件事情適合在回調(diào)里面做。

然后提供一個輸入框，自由調(diào)整經(jīng)歷多少個循環(huán)才更新一次畫面，這樣能調(diào)整尋路的速度。

處理彩色圖片

預(yù)覽：https://codesandbox.io/s/maze-vite-8-h845p?file=/src/App.vue (注意如果出現(xiàn)跨域錯誤，就自己上傳圖片吧)

不放iframe了，感覺放太多了，讓這個頁面已經(jīng)相當(dāng)卡。

前面都是默認(rèn)白色像素是可以行走的區(qū)域，現(xiàn)在嘗試把顏色相似的附近像素作為行走區(qū)域，這樣效果會更加好。

直接把 rgba 顏色數(shù)據(jù)傳入 solveMaze，然后在循環(huán)中計算出相鄰節(jié)點與當(dāng)前節(jié)點的顏色差距，差距過大則不放入隊列。

把一個 rgba 整數(shù)的各個通道拆分開來可以這么寫：

/** * 獲取 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 顏色的相似度，最樸素的方法是把兩個顏色看成是兩個三維坐標(biāo)的點，然后求其歐幾里得距離，但這不符合人眼的感知模型。詳細(xì)方法wiki已經(jīng)有了：https://zh.wikipedia.org/wiki/顏色差異

關(guān)于這方面的運算有點復(fù)雜，我都寫到了 color.js 里面了。

結(jié)果：

注意代碼里的 colorDiffThreshold，目前我用的 2.25，如果太高，會導(dǎo)致穿墻，太低則容易找不到路失敗。

性能優(yōu)化

當(dāng)點擊兩次畫面后，需要稍微等一會才會開始尋路，這里應(yīng)該耗費了不少CPU。打開 DevTools 的性能分析器分析下到底是哪里消耗最多性能：

很明顯 solveMaze 函數(shù)占據(jù)了大多數(shù)時間，展開下面的 Call Tree：

buildNodeGraph 和 getNode 是優(yōu)化重點，打開代碼，可以直接看到每句話耗費的CPU時間：

57 行的 if (!node) {...} 明明是簡單的判斷，卻耗費了不少時間，試試看改成 node === undefined，并且 value 也不再需要判斷了。對 nodes 數(shù)組的訪問與讀取也耗費不少時間，嘗試一開始用 new Array(length) 初始化，應(yīng)該會好一些。優(yōu)化之后的代碼：

看起來稍微好一些。

在尋路途中進(jìn)行性能監(jiān)測：

發(fā)現(xiàn) buildPath 相當(dāng)?shù)暮馁M時間，這也是理所應(yīng)當(dāng)?shù)模吘姑看窝h(huán)都調(diào)用，并且完整遍歷整個鏈條。處理辦法也簡單，只在最后出結(jié)果時調(diào)用他即可，根據(jù)前面的經(jīng)驗，while (node) 改為 while (node !== null)。

現(xiàn)在他完全沒有存在感了。

然后是 for...of 語句，建議改為傳統(tǒng)的數(shù)組下標(biāo)自減，這是最快的，當(dāng)然日常使用 for...of 可讀性更強。

然后是 popBestNextNode：

這里每次都完整遍歷整個數(shù)組找出cost最小的節(jié)點，最后還有一個數(shù)組元素移除的操作。我真的很難判斷 JavaScript 的數(shù)組到底是存儲在連續(xù)內(nèi)存里面還是分散的，但是不管怎么樣，這里完全可以使用二叉堆替代來獲取更好的性能。具體就不自己實現(xiàn)了，直接用現(xiàn)成的：https://www.npmjs.com/package/heap-js。注意 new Heap() 的時候傳入自定義的比較器，然后把 popBestNextNode 的實現(xiàn)改為 return this.queue.pop() 即可。

最后，把 buildNodeGraph 的那兩層for循環(huán)全部移除，不再預(yù)先初始化所有的 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) }

在后面的尋路循環(huán)中再去調(diào)用 getNearNodes 來獲取相鄰的節(jié)點，這樣就大幅縮減了一開始的卡頓了。

最后，提供兩種策略：

嚴(yán)格：當(dāng)相鄰像素顏色差距小于某個值，才加入隊列。適合行走區(qū)域的顏色變化不大的圖片，得出的結(jié)果幾乎就是最短的路徑。 模糊：相鄰像素?zé)o論顏色的差距，都加入隊列，其差距值乘以某些系數(shù)，作為節(jié)點的 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 = truelet colordiff = getNodeColorDiff(node, current)const colorDiffThreshold = 2 // 容許通過的顏色差異，范圍 0~100node.parent = currentnode.endDistance = getDistance(node, nodeGraph.endNode)node.beginDistance = current.beginDistance + 1if (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)} }}

源代碼：https://gitee.com/judgeou/maze-vite

到此這篇關(guān)于Javascript結(jié)合Vue實現(xiàn)對任意迷宮圖片的自動尋路的文章就介紹到這了,更多相關(guān)Javascript結(jié)合Vue迷宮自動尋路內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！