搞了N個(gè)小時(shí)，終于杯具的把A*算法寫出來了，這里只能弱弱的小結(jié)一下：
A*算法是一種啟發(fā)式算法：
即每次迭代都進(jìn)行啟發(fā)式思考，判斷F值：
我們維護(hù)兩個(gè)表，我這只用簡單的數(shù)組實(shí)現(xiàn)。
OPEN表和CLOSE表
OPEN表存儲(chǔ)我們待搜索的節(jié)點(diǎn)
CLOSE表存儲(chǔ)已經(jīng)搜索好的節(jié)點(diǎn)，這些節(jié)點(diǎn)都是每次啟發(fā)時(shí)F值最小的。
A為其點(diǎn)
B為終點(diǎn)
F = H + G
G = 從起點(diǎn)A，沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi)。G = 距離(A) * 偏移量
H = 從網(wǎng)格上那個(gè)方格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)耗費(fèi)。這經(jīng)常被稱為啟發(fā)式的，
??? 可能會(huì)讓你有點(diǎn)迷惑。這樣叫的原因是因?yàn)樗皇莻€(gè)猜測。
??? 我們沒辦法事先知道路徑的長度，因?yàn)槁飞峡赡艽嬖诟鞣N障礙(墻，水，等等)。
??? 雖然本文只提供了一種計(jì)算H的方法，但是你可以在網(wǎng)上找到很多其他的方法。
??? H = (列距離(B) + 行距離(B)) * 偏移量
我們選定上一次添加到CLOSE表的節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。
然后依次判斷當(dāng)前節(jié)點(diǎn)的四個(gè)或八個(gè)方向的節(jié)點(diǎn)。如果這些節(jié)點(diǎn)是障礙，或者已經(jīng)在CLOSE表中，
則不予考慮，否則將這些節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)，這些節(jié)點(diǎn)如果也沒有在OPEN表中，
則加入OPEN表，如果這些節(jié)點(diǎn)編號(hào)已經(jīng)出現(xiàn)在OPEN表中，則判斷他們的G值，G值小的留下，G值大的扔掉。
如果G值也相同，保留后出現(xiàn)的。
我們每次把OPEN表F值最小的節(jié)點(diǎn)刪去加入到CLOSE表中。
但是如果存在兩個(gè)節(jié)點(diǎn)的F值相同呢？隨機(jī)選一個(gè)。
如此反復(fù)，直到我們將B點(diǎn)加入CLOSE表。
如何得到我們的路徑呢？從B點(diǎn)依靠父節(jié)點(diǎn)向上遍歷就行了。
注意一點(diǎn)。我們要保持OPEN表的有序就對(duì)了，顯然我們這里是通過F值來維持OPEN表的次序。
而且每次添加新的節(jié)點(diǎn)到OPEN表時(shí)都要排序。當(dāng)然這里是用降序，這樣對(duì)于數(shù)組來說更好操作。
感謝，網(wǎng)上朋友提供的詳細(xì)的資料。