canvas——路徑搜索

在前一篇博客中隨機生成迷宮，現在就以隨機生成的迷宮為地圖，開始尋找路徑。

迷宮尋路也可以使用DFS，BFS，但常見的是A*演算法，它是啟發式搜索演算法的一種，效率相比前兩者也更高。接下來以A*演算法為例，迷宮是一個連通圖，因此可以尋找到地圖上可通行的任意兩點間的路徑。

A*演算法

A*演算法的目的是求出最低通過成本，利用它來尋找最優路徑。

A*演算法的核心在於它的估值函數：f(n)=g(n)+h(n);

f(n)表示第n點的估值；

g(n)表示起始點到頂點n的代價，這裡代表起始點到頂點n距離；

h(n)表示頂點n到終點的代價，這裡代表頂點n到終點的距離。

對於h(n)採用曼哈頓距離計算。

|r1-r2| + |y1 - y2|

當然也可以使用其他的評估函數，如歐幾里得距離、切比雪夫距離；

實現

每個頂點除了保存自身的坐標位置r、c和通行狀態flag外，還需要保存各自的f、g、h值（初始化均為0，通過A*演算法計算得出），parent指向經過頂點n的前一頂點，state表示頂點n的狀態。

class Point {
constructor(r, c, flag=1) {
this.r = r;
this.c = c;
this.flag = flag; // 0 可以通過 1不能通過
this.state = -1; // 0 在openList 1 在closeList -1 未處理

this.f = 0;
this.g = 0;
this.h = 0;
this.parent = null;
}
}

需要兩個數組，openList保存已計算 f 值得頂點，closeList保存最有路徑的頂點。

（1）初始狀態下，openList包含起點，closeList為空。

（2）從openList中取出第一個頂點curPoint，放入closeList中，將curPoint的state設置為1，表示該頂點在closeList數組中

（3）遍歷curPoint上下左右的頂點tp，對tp做處理：

tp沒有超出邊界，flag==0，且state！=1（不在closeList）的，判斷tp是否為終點；

是則將tp的parent指向curPoint，返回true，結束函數執行；

如果不是，計算或更新tp的估值等。

（4）從openList中選擇估值最小的頂點，循環步驟3。

/*
* start 起點
* end 終點
* distPoint 計算兩點間曼哈頓距離
* processPoint 處理四周頂點
*/
findPath(start, end) { let curPoint = start;
// 上下左右頂點偏移量 let near = [{ r: -1, c: 0 }, { r: 1, c: 0 }, { r: 0, c: -1 }, { r: 0, c: 1 }]; let finded = false; start.f = start.h = this.distPoint(start, end); this.openList.push(start); while(this.openList.length > 0) { curPoint = this.openList.pop; curPoint.state = 1; this.closeList.push(curPoint); finded = this.processPoint(near, curPoint, end); if(finded) { break; } } }

/*
* near 需要遍歷的頂點偏移量
* curPoint 當前頂點
* pathArr 包含路和牆的二位數組
* end 終點
* between 計算數值是否在所給範圍內
* addArrSort 添加頂點到指定數組並排序
* quickSort 快速排序
* comPonitF 指定排序方法 — — 比較 f 值
*/
processPoint(near, curPoint, end) { let len = near.length, i = 0; while(i < len) { let tr = curPoint.r + near[i].r, tc = curPoint.c + near[i].c; if(this.between(tr, 0, this.r - 1) && this.between(tc, 0, this.c - 1)) { let tp = this.pathArr[tr][tc]; if(tp.flag === 0 && tp.state !== 1) {
// 判斷 tp 是否為終點 if(this.isEqual(tp, end)) { tp.parent = curPoint; return true; }
// tp不在openList（估值未計算） if(tp.state === -1) { tp.parent = curPoint; tp.g = curPoint.g + 1; tp.h = this.distPoint(tp, end); tp.f = tp.g + tp.h; this.addArrSort(this.openList, tp, this.comPonitF); }else { let g = curPoint + 1; if(g < tp.g) { tp.g = g; tp.f = tp.g + tp.h; this.quickSort(this.openList, 0, this.openList.length, this.comPonitF); } } } } ++i; } return false; }

最終，可以通過終點 parent 往回找到路徑。

確定起點、終點

為了探尋任意兩點間路徑，這裡為canvas添加了點擊事件，以確定起點和終點，然後描繪出兩點間的路線。

/*
* removeEvent 移除點擊事件
*/
addEvent(e) { if(this.start && this.end) { this.removeEvent; return; } let c = ~~(e.offsetX / 10), // 取整 r = ~~(e.offsetY / 10); if(this.pathArr[r][c].flag === 0) { if(!this.start) { this.start = this.pathArr[r][c]; this.renderPer(this.start, "yellow"); }else { this.end = this.pathArr[r][c]; this.findPath(this.start, this.end); this.render(this.end); } } }

路徑搜索就到這裡啦。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！