1-heuristic尋路簡(jiǎn)介

heuristic是啟發(fā)式的意思，因此heuristic尋路就是啟發(fā)式尋路，其所用的算法是貪心算法。

啟發(fā)式尋路之所以是啟發(fā)式的，是因?yàn)樵趯ぢ返倪^程中，我們會(huì)給它一個(gè)提示，比如你每邁出一步的時(shí)候，要朝離目標(biāo)點(diǎn)最近的位置邁出。

在上圖中，從start節(jié)點(diǎn)向end節(jié)點(diǎn)尋路的時(shí)候，它所邁出的每一步都是離end最近的。

可是每一步最近不代表整條路就是最近的，比如它從上面越過障礙物會(huì)更近。

這種只在乎眼前的利益，不考慮全局得失的算法，就是貪心算法。

啟發(fā)式尋路雖然有很大的缺陷，但它是尋路的基礎(chǔ)算法之一，以后我們可以以此為基礎(chǔ)進(jìn)行不斷優(yōu)化。

2-ts代碼實(shí)現(xiàn)

以下代碼是尋路邏輯的實(shí)現(xiàn)。至于效果的顯示，我是用canvas做的，不算重點(diǎn)，我就不貼出來了，想要的可以微信我(1051904257)。

解釋一下上面的代碼。

mapSize是地圖尺寸，它沒有單位的概念，不要將其理解為像素。

start起點(diǎn)、end終點(diǎn)的概念無需多說，其值是其在地圖中的索引位。

我們可以通過getPos(n: number)方法獲取索引位所對(duì)應(yīng)的行列位。

obstruction 是障礙物，其內(nèi)元素是構(gòu)成障礙物的節(jié)點(diǎn)的索引位。

road 是探索出的道路，其內(nèi)元素是構(gòu)成道路的節(jié)點(diǎn)的索引位。

basic 是探索基點(diǎn)，比如一開始的探索基點(diǎn)是起點(diǎn)，從起點(diǎn)邁出離終點(diǎn)最近的一步后，我們會(huì)以這一步的節(jié)點(diǎn)為基點(diǎn)，繼續(xù)往前探索。

state 是探索狀態(tài)，finding探索中、fail探索失敗、success探索成功。

explorer() 是尋路方法，它會(huì)遍歷基點(diǎn)周邊的8個(gè)節(jié)點(diǎn)，然后找到離終點(diǎn)最近的點(diǎn)，并記下探索狀態(tài)state。state為finding時(shí)，會(huì)繼續(xù)探索，否則停止探索。

當(dāng)然，為了便于查看尋路的過程，我們也可以逐步尋路。

整體的heuristic尋路邏輯便是如此，不過它還有一個(gè)嚴(yán)重的bug，那就是可能會(huì)被死胡同堵死。

在數(shù)字為8的黑色格子處，已經(jīng)無路可走了，便認(rèn)為探索失敗了。

在這種情況下，我可以嘗試讓它回頭，回到上一個(gè)路口4，不再走這條死路，而是走離終點(diǎn)較近的另一條路。

接下來，我們就解決一下這個(gè)Bug。

3-回頭是岸

突然想起一句話：學(xué)海無涯，回頭是岸。人生路漫漫哪有一帆風(fēng)順的，遇到過不去的可以繞道試試。

言歸正傳，繼續(xù)說一下heuristic遇到死胡同時(shí)，如何回頭是岸，繞道而行。

整體代碼如下：

效果如下：

說一下我們添加了哪些代碼。

explored 是探索過的基點(diǎn)集合，其中元素的key就是節(jié)點(diǎn)的索引位，value 是其前面的點(diǎn)。

explored 可以讓我們記住來路，以便回頭。

explorer(extrude?: number) 方法中有了一個(gè)extrude參數(shù)，表示要在遍歷周圍8點(diǎn)時(shí)，排除的點(diǎn)。此點(diǎn)用于在會(huì)回頭時(shí)，不再走過去被堵死的老路，而是走一條新路。

其排除邏輯如下

被堵時(shí)的回頭邏輯如下：

走出死胡同時(shí)，需要把死胡同里的路刪掉。

關(guān)于heuristic尋路咱們就說到這，下一章我們會(huì)再說更優(yōu)良的尋路方法。