Javascript結(jié)合Vue實現(xiàn)對任意迷宮圖片的自動尋路
前言
可以直接體驗最終效果：https://maze-vite.vercel.app/
尋路前：
尋路后，自動在圖片上生成紅色路徑，藍(lán)色是探索過的區(qū)域：
這里我故意用手機(jī)斜著角度拍，就是為了展示程序完全可以處理手機(jī)從現(xiàn)實拍攝的迷宮圖片。
整個程序我準(zhǔn)備用 Vue 3 + Vite 來寫，但其實用不用 Vue 都一樣，不會涉及復(fù)雜的界面，用別的框架甚至不用框架其實也完全可以。
二維數(shù)組，一本道
說了要從零開始，所以先嘗試從非常簡單的迷宮入手吧
對于我們?nèi)祟悂碚f，這個迷宮十分簡單，顯而易見的只有一條路。但是計算機(jī)解決這樣的迷宮還是得稍微花費那么一點力氣的。
二維數(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.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])
)
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 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>
最終效果：
其實就是通過二維數(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 } = 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 數(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 = current
queue.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 = node
bestNodeIndex = 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 = 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 屬性，用來表達(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 可讀性更強(qiáng)。
然后是 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 = 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)
}
}
}
源代碼：https://gitee.com/judgeou/maze-vite
到此這篇關(guān)于Javascript結(jié)合Vue實現(xiàn)對任意迷宮圖片的自動尋路的文章就介紹到這了,更多相關(guān)Javascript結(jié)合Vue迷宮自動尋路內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了vue彈窗父子組件調(diào)用問題，本文通過示例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-08-08
vue如何使用element-ui 實現(xiàn)自定義分頁
這篇文章主要介紹了vue如何使用element-ui 實現(xiàn)自定義分頁,可以通過插槽實現(xiàn)自定義的分頁,本文通過實例圖文相結(jié)合給大家介紹的非常詳細(xì),感興趣的朋友一起看看吧2024-07-07
vue輪播圖插件vue-awesome-swiper的使用代碼實例
本篇文章主要介紹了vue輪播圖插件vue-awesome-swiper的使用代碼實例，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-07-07
mpvue小程序循環(huán)動畫開啟暫停的實現(xiàn)方法
這篇文章主要介紹了mpvue小程序循環(huán)動畫開啟暫停的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
Luckysheet?在vue中離線使用及引入報錯的解決方案(推薦)
這篇文章主要介紹了Luckysheet?在vue中離線使用方法及引入報錯的解決方案,將dist離線包在項目創(chuàng)建個文件夾放著，然后根據(jù)放置的位置在?index.html里面引入，下面通過案例給大家介紹我的項目里面放置的位置，需要的朋友可以參考下2022-10-10
這篇文章主要介紹了關(guān)于element-ui 側(cè)邊欄的router問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
本文主要介紹了Element-plus側(cè)邊欄踩坑的問題解決,主要解決了el-menu直接嵌套el-menu-item菜單,折疊時不會出現(xiàn)文字顯示和小箭頭無法隱藏的問題,具有一定的參考價值,感興趣的可以了解一下2023-08-08
仿照e簽寶,實現(xiàn)pdf電子簽章?=>?拿到pdf鏈接,移動章的位置,獲取章的坐標(biāo),怎么實現(xiàn)呢,下面小編給大家介紹vue2實現(xiàn)pdf電子簽章問題記錄,感興趣的朋友一起看看吧2023-12-12
這篇文章主要介紹了如何刪除vue項目下的node_modules文件夾，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-09-09
由于狀態(tài)零散地分布在許多組件和組件之間的交互中,大型應(yīng)用復(fù)雜度也經(jīng)常逐漸增長,為了解決這個問題,Vue 提供 vuex,這篇文章主要給大家介紹了關(guān)于vuex項目中登錄狀態(tài)管理的相關(guān)資料,需要的朋友可以參考下2021-09-09