Javascript結合Vue實現(xiàn)對任意迷宮圖片的自動尋路
可以直接體驗最終效果：https://maze-vite.vercel.app/
尋路前：
尋路后，自動在圖片上生成紅色路徑，藍色是探索過的區(qū)域：
這里我故意用手機斜著角度拍，就是為了展示程序完全可以處理手機從現(xiàn)實拍攝的迷宮圖片。
整個程序我準備用 Vue 3 + Vite 來寫，但其實用不用 Vue 都一樣，不會涉及復雜的界面，用別的框架甚至不用框架其實也完全可以。
二維數(shù)組，一本道說了要從零開始，所以先嘗試從非常簡單的迷宮入手吧
對于我們?nèi)祟悂碚f，這個迷宮十分簡單，顯而易見的只有一條路。但是計算機解決這樣的迷宮還是得稍微花費那么一點力氣的。
二維數(shù)組很適合用來表達這個迷宮：
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]。
那么應該有這么一個函數(shù)： function solveMaze (matrix, begin, end) {//...}，matrix是描述迷宮的二維數(shù)組，begin 是起點，end 是終點，最終返回值是一個有序集合，每一個元素是一個格子，代表正確的路線軌跡。
這里我們準備采用的策略十分簡單，從起點開始，看看周圍上下左右（不能斜著走）哪些是可以走的格子，然后移動到這個格子，接著循環(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 = [] // 當前點 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 獲取最終可行走的路徑，控制臺輸出：
這些坐標就是最終的行走軌跡，目測是正確的。
映射基礎界面為了方便測試觀察，得把我們的數(shù)據(jù)結構映射到網(wǎng)頁上面。
// maze.js// ...// 導出 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 生成對應 div，數(shù)組里面元素值決定黑白。paths 數(shù)組存儲結果路徑，把路徑用紅色邊框標記出來。這樣就方便以后測試結果的查看了。
廣度優(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]]
如果把他應用到上面的代碼，會發(fā)現(xiàn)頁面卡死了，這是因為這個迷宮含有岔路，導致算法一直在繞圈。我們需要一些手段，把走過的路記住，以后就不再走了，方法不難，只要把當前可以走的格子，放進一個隊列中，然后要做的，就是不斷對這個隊列里的格子，作出同樣處理，直到遇到終點格子。
為了方便我們用算法進行處理，需要使用新的數(shù)據(jù)結構來表達，它就是 圖(Graph) 結構。
圖結構和鏈表很像，最大不同是每個節(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]
雖然這樣訪問起來不那么直接，但是只需要一次尋址，復制傳輸也比二維數(shù)組方便得多。
然后創(chuàng)建一個 Node 類代表節(jié)點，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 } = 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ù)組轉換為圖結構，每個節(jié)點的 nearNodes 就相當于是下一步可以走的格子集合，checked 表示這個節(jié)點是否已經(jīng)探索過。
為了方便查看每一步狀態(tài)的變化，需要把當前所在格子和隊列中的格子，在畫面上標記出來，完整代碼我就不貼了，codesandbox 可以隨意看：
藍色邊框就是隊列中的格子，小人就是當前所在的格子，當它走到右下角時就會停下來。
目前做的，只是順利讓小人移動到終點而已，但是怎么得出我們要的路徑呢？方法就是在 Node 多加一個屬性 parent，記錄上一個 Node。當取出 nearNodes 時，把當前節(jié)點賦值到每一個 nearNode 的 parent 即可：
// ...for (let node of current.nearNodes) { if (node.checked === false) {node.parent = currentqueue.push(node) }}// ...
然后就是從當前節(jié)點，讀取 parent 一個一個回溯即可：
function buildPath (endNode) { let path = [] let node = endNode while (node) { path.push(node) node = node.parent } return path}
效果：
當小人到達終點時，紅色方格就是最短路徑了。
地圖編輯稍微改動下代碼，讓我們可以實時編輯迷宮，測試更加方便。
操作：點擊方格可以改變黑白狀態(tài)，按住alt點擊可以設置新的目標點。
逐漸把 solveMaze 里面的局部變量移到 NodeGraph 類里面，這樣外部訪問更加便利。注意當尋路結束的時候，不要結束函數(shù)，而是使用 while 循環(huán)一直等待新的目標點被設置：
// ... if (equalsNode(current, nodeGraph.endNode)) { while (equalsNode(current, nodeGraph.endNode)) {await sleep(1000) } continue }// ...優(yōu)化尋路算法
想象一下這種情形：
起點和終點一條直線，中間毫無阻擋，但是這個小人竟然到處跑，好一會才到終點，這樣下去不行的，必須要優(yōu)化。
在 Node 類加一個屬性 endDistance 記錄每個節(jié)點到終點的距離，getDistance 函數(shù)根據(jù)坐標可以直接計算出距離，這個距離是沒有考慮到中間可能出現(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ù)值不直接從坐標計算，而是隨著前進累加，這樣 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 屬性，用來表達 成本。目前 cost 就是 endDistance + beginDistance，cost 越小，優(yōu)先級越高。
像這樣的情況，小人一開始企圖從上方靠近，但是隨著不斷前進，經(jīng)過的步數(shù)越來越多，倒不如走下面了，于是就放棄的上面的路線。
現(xiàn)在，小人的行動變成更加靠譜了：
對圖片進行尋路拿這張我隨便畫的圖來作為參數(shù)：
目標是從 B 點到達 E 點，我們只需要讀取這張圖片的像素，根據(jù)黑白顏色，轉換成為一個數(shù)組，放到 solveMaze 函數(shù)即可。
為此，需要有一個 input 標簽，type='file'，用來選擇圖片，通過 URL.createObjectURL(File) 生成一個 URL，然后使用 new Image() 創(chuàng)建一個 img 標簽，它不需要添加進 body，把 url 給到 img.src。通過 CanvasRenderingContext2D.drawImage() 復制進 Canvas，再調(diào)用 CanvasRenderingContext2D.getImageData() 即可獲取像素數(shù)組。
這時不能再用 div 去渲染了，因為這張圖幾萬個像素，每個像素一個 div 的話，瀏覽器也吃不消，再加上將來圖片將會更大。
所以這里改用 Canvas 進行渲染，安排三個 Canvas，一個顯示迷宮的原圖，一個顯示探索過的節(jié)點，一個顯示當前最短路徑，也就是 path 數(shù)組里面的節(jié)點，然后把這三個 Canvas 疊在一起即可，最后就是在回調(diào)里面去更新后面兩個 Canvas 即可。
把我上面的圖片下載到自己電腦，點擊選擇文件按鈕選擇圖片，然后就能看到效果了，選別的圖片也可以，只是我的起點和終點坐標是寫死的，而且代碼沒有優(yōu)化過，太大的圖片恐怕難以處理。
注意：如果遇到跨域問題那就要自己上傳圖片了。
自定義起始點，以及隨時變更路線利用點擊事件中的 offsetX、offsetY 即可知道點擊坐標，把起點和終點的坐標保存起來，一旦有變化，則停止之前的尋路函數(shù)，重新執(zhí)行當前的尋路函數(shù)，因此需要在循環(huán)中作一個判斷來決定是否退出函數(shù)，這件事情適合在回調(diào)里面做。
然后提供一個輸入框，自由調(diào)整經(jīng)歷多少個循環(huán)才更新一次畫面，這樣能調(diào)整尋路的速度。
處理彩色圖片預覽：https://codesandbox.io/s/maze-vite-8-h845p?file=/src/App.vue (注意如果出現(xiàn)跨域錯誤，就自己上傳圖片吧)
不放iframe了，感覺放太多了，讓這個頁面已經(jīng)相當卡。
前面都是默認白色像素是可以行走的區(qū)域，現(xiàn)在嘗試把顏色相似的附近像素作為行走區(qū)域，這樣效果會更加好。
直接把 rgba 顏色數(shù)據(jù)傳入 solveMaze，然后在循環(huán)中計算出相鄰節(jié)點與當前節(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 顏色的相似度，最樸素的方法是把兩個顏色看成是兩個三維坐標的點，然后求其歐幾里得距離，但這不符合人眼的感知模型。詳細方法wiki已經(jīng)有了：https://zh.wikipedia.org/wiki/顏色差異
關于這方面的運算有點復雜，我都寫到了 color.js 里面了。
結果：
注意代碼里的 colorDiffThreshold，目前我用的 2.25，如果太高，會導致穿墻，太低則容易找不到路失敗。
性能優(yōu)化當點擊兩次畫面后，需要稍微等一會才會開始尋路，這里應該耗費了不少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ōu)化之后的代碼：
看起來稍微好一些。
在尋路途中進行性能監(jiān)測：
發(fā)現(xiàn) buildPath 相當?shù)暮馁M時間，這也是理所應當?shù)模吘姑看窝h(huán)都調(diào)用，并且完整遍歷整個鏈條。處理辦法也簡單，只在最后出結果時調(diào)用他即可，根據(jù)前面的經(jīng)驗，while (node) 改為 while (node !== null)。
現(xiàn)在他完全沒有存在感了。
然后是 for...of 語句，建議改為傳統(tǒng)的數(shù)組下標自減，這是最快的，當然日常使用 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)全部移除，不再預先初始化所有的 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é)點，這樣就大幅縮減了一開始的卡頓了。
最后，提供兩種策略：
嚴格：當相鄰像素顏色差距小于某個值，才加入隊列。適合行走區(qū)域的顏色變化不大的圖片，得出的結果幾乎就是最短的路徑。 模糊：相鄰像素無論顏色的差距，都加入隊列，其差距值乘以某些系數(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') { // 嚴格 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實現(xiàn)對任意迷宮圖片的自動尋路的文章就介紹到這了,更多相關Javascript結合Vue迷宮自動尋路內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持好吧啦網(wǎng)！
相關文章：
網(wǎng)公網(wǎng)安備