Algorithm
：
??????
A*
在地圖中兩點(diǎn)間找出一條路徑，如果存在至少一條路徑，在各種不同的算法中
A*
將找到最短路徑，而且相比之下算法速度快。
A*
是一種可控的算法，是一種啟發(fā)式搜索算法，也就是說算法本身不會盲目的搜索路徑，而是估計(jì)一個(gè)最佳的考察方向，進(jìn)行搜索。
?
????
在
A*
尋路算法中，我們從起點(diǎn)開始，檢查相鄰方格的方式，向外擴(kuò)展直到找到目標(biāo)。
我們做如下操作開始搜索：
1.
從起點(diǎn)開始，并且把它作為待處理的第一個(gè)點(diǎn)存入一個(gè)
“
開啟列表
”
。開啟列表就像一張購物清單。盡管現(xiàn)在列表里只有一個(gè)元素，但以后就會多起來。你的路徑可能會通過它包含的方格，也可能不會。基本上，這是一個(gè)待檢查方格的列表。
2.
從開啟列表中取出一個(gè)代價(jià)最小的點(diǎn)
關(guān)于代價(jià)值的計(jì)算
F = G + H
這里：
??? * G =
從起點(diǎn)，沿著產(chǎn)生的路徑，移動到當(dāng)前節(jié)點(diǎn)的移動耗費(fèi)。
??? * H =
從網(wǎng)格上那個(gè)方格移動到終點(diǎn)的預(yù)估移動耗費(fèi)。這經(jīng)常被稱為啟發(fā)值
?
如果開啟列表為空則說明路徑?jīng)]有找到，結(jié)束搜索。如果取到這個(gè)節(jié)點(diǎn)，則將這個(gè)結(jié)點(diǎn)加入到
”
關(guān)閉列表
”
，如果這個(gè)點(diǎn)是終點(diǎn)，則結(jié)束搜索。如果不是終點(diǎn)就把這個(gè)點(diǎn)作為當(dāng)前點(diǎn)。
3.
按照八個(gè)方向查找與當(dāng)前點(diǎn)相鄰的節(jié)點(diǎn)，如果是可以移動的點(diǎn)（尋找起點(diǎn)周圍所有可到達(dá)或者可通過的方格，跳過有墻，水，或其他無法通過地形的方格）
a.
如果新考核的點(diǎn)在
”
關(guān)閉列表
”
中，并且從當(dāng)前點(diǎn)到達(dá)這個(gè)點(diǎn)的
G
值更小則
將這個(gè)點(diǎn)作為當(dāng)前點(diǎn)的孩子節(jié)點(diǎn)
更新這個(gè)點(diǎn)的
G
值
更新這個(gè)點(diǎn)所有孩子節(jié)點(diǎn)的父節(jié)點(diǎn)指針、
G
值、
F
值
b.
如果新考核的點(diǎn)在
”
開啟列表中
”
，并且從當(dāng)前點(diǎn)到達(dá)這個(gè)點(diǎn)的
G
值更小則
將這個(gè)點(diǎn)作為當(dāng)前點(diǎn)的孩子節(jié)點(diǎn)
更新這個(gè)點(diǎn)的
G
值
?c.
將這個(gè)點(diǎn)作為當(dāng)前點(diǎn)的孩子節(jié)點(diǎn)，計(jì)算這個(gè)點(diǎn)的
G
、
H
、
F
值，將這個(gè)節(jié)點(diǎn)加入到
”
開啟列表
”
中。
?
4
．跳回第二步周而復(fù)始，直到
”
開啟列表
”
為空，或者將終點(diǎn)加入到
”
關(guān)閉列表
”
?
流程圖:
算法優(yōu)化：
?
?
??
算法中消耗分析
1.????
節(jié)點(diǎn)的內(nèi)存分配與釋放
?
節(jié)點(diǎn)的內(nèi)存分配與釋放非常頻繁，大規(guī)模搜索的時(shí)候通常需要數(shù)千個(gè)節(jié)點(diǎn)乃至上萬個(gè)節(jié)點(diǎn)。所以很有必要做內(nèi)存管理。考慮用
placement new
來分配內(nèi)存減少分配與釋放的開銷，但是需要在程序運(yùn)行開始就事先分配好內(nèi)存。每個(gè)節(jié)點(diǎn)大約
20
字節(jié)左右，正常的情況下一張稍大的地圖有
1500x1500
大小
2,250,000
格，那么最壞情況下，需要內(nèi)存約
40,000k
，所以如果一開始就分配這么多內(nèi)存是不現(xiàn)實(shí)的，所以只能限制一個(gè)內(nèi)存分配極值，比如一次分配一兆，如果用完就結(jié)束搜索。但如果游戲一開始就分配
1
兆內(nèi)存用于尋路，實(shí)際上有可能一直都不需要大規(guī)模搜索，所以最好有增長方式的內(nèi)存管理。
另一個(gè)方案是每次分配一批節(jié)點(diǎn)所需內(nèi)存，用完了再增長，分配粒度越大命中效果也會更好些。
?
2.????
從開啟列表中取出一個(gè)代價(jià)最小的點(diǎn)
從開啟列表中取出一個(gè)代價(jià)最小的點(diǎn)需要比較并遍歷所有在開啟表中節(jié)點(diǎn)。優(yōu)化的做法是在每次插入開啟表的時(shí)候都將節(jié)點(diǎn)插入在表的最前端，這樣每次從前端取就可以避免遍歷的開銷，但是分析證明，每次節(jié)點(diǎn)的值改變都需要重新排序，一次大循環(huán)中可能需要多次排序，而每次大循環(huán)只會取一次代價(jià)最小節(jié)點(diǎn)，所以這一次的遍歷相比開銷要比排序小的多。
3.????
查找考核點(diǎn)是否在關(guān)閉列表
查找考察點(diǎn)是否在關(guān)閉或者開啟列表中都需要遍歷整張表，優(yōu)化的辦法是選擇合適的數(shù)據(jù)結(jié)構(gòu)。
相比使用
vector
插入和刪除的速度會很慢，但是訪問和遍歷的速度很快，但如果
vector
預(yù)先分配內(nèi)存，內(nèi)存命中會很高，訪問和遍歷也會更快，插入和刪除如果用
swap
也會相對較快。
使用
list
插入和刪除速度會很快，但是遍歷會很慢，內(nèi)存命中也會比較差。如果算法中對表的插入比遍歷頻繁，可以考慮使用
list
。
經(jīng)過測試發(fā)現(xiàn)，瓶頸在表的遍歷與搜索上，
vector
無論有多快搜索速度都是線性的而且隨著節(jié)點(diǎn)的增加，遍歷時(shí)間也隨之線性增長，而
map
的查找速度是常數(shù)級的，
Hash map
查找的時(shí)間復(fù)雜度為
O(1)
，即使用
STL
的
map
也會有
O(log (n))
比線性查找
O(n)
快很多，
map
永遠(yuǎn)是穩(wěn)定的。
?
4.????
如果已經(jīng)存在在列表中并且當(dāng)前
G
值最小則更新其
G
值和這個(gè)考核點(diǎn)所有的孩子節(jié)點(diǎn)的
G
值和父節(jié)點(diǎn)指針。
遍歷孩子節(jié)點(diǎn)需要遞規(guī)來完成搜索整棵樹，開銷在于函數(shù)調(diào)用，所以采用棧的方式來模擬遞規(guī)。
5.????
查找考核點(diǎn)是否在開啟列表，如果在開啟列表則更新這個(gè)節(jié)點(diǎn)。
6.????
函數(shù)調(diào)用帶來的開銷，所有檢測函數(shù)都做成內(nèi)聯(lián)函數(shù)，封裝后的
A*
需要對外開放一個(gè)檢測函數(shù)指針，可以實(shí)現(xiàn)函數(shù)對象來做檢測函數(shù)，函數(shù)對象的可以內(nèi)聯(lián)
operator
操作符。
?
A*
帶來的其他問題
A*
在最壞的情況下會廣度搜索地圖，花費(fèi)很多時(shí)間才能找到終點(diǎn)，尤其是目標(biāo)點(diǎn)為掩碼（即無論如何到達(dá)不了的終點(diǎn)），所以通常情況下要對尋路時(shí)間加以限制，但是限制時(shí)間短了可能找不到目標(biāo)點(diǎn)，限制時(shí)間長了又可能影響游戲幀率，比如在在游戲
Mouse Hold
的情況下，尋路是頻繁進(jìn)行的。一個(gè)經(jīng)驗(yàn)值是
20
毫秒，對有效的目標(biāo)點(diǎn)搜索超過
20
毫秒都沒有找到有效的路徑就放棄搜索，找一個(gè)離目標(biāo)最近的終點(diǎn)即可。
但是時(shí)間限制可能存在硬件不同而效果不同的問題，對于不同的
cpu
來說，相同的時(shí)間搜索的范圍會不一樣，另一個(gè)選擇是利用循環(huán)次數(shù)來限制。
對于目標(biāo)點(diǎn)為掩碼的處理，與其讓
A*
進(jìn)行超時(shí)搜索不如在開始設(shè)置目標(biāo)點(diǎn)的時(shí)候就計(jì)算一個(gè)離目標(biāo)點(diǎn)最近的可以到達(dá)的點(diǎn)。可以從目標(biāo)點(diǎn)為中心一圈一圈向外搜索，直到搜索到一個(gè)可以到達(dá)的點(diǎn)（非掩碼
…
）為止，這比起直接用
A*
消耗要小的多。
?
算法的進(jìn)一步改進(jìn)
1.??????
需要更快的速度
a.????
改進(jìn)數(shù)據(jù)結(jié)構(gòu)
??????
當(dāng)前使用的是
STL
的
map
，是使用紅黑樹來管理內(nèi)存的而不是真正的
Hash Map
，如果改為
HashMap
，效率可能會再有一些改進(jìn)。
???
b. ??
分時(shí)計(jì)算
如果需要更快速的得到路徑，需要分時(shí)計(jì)算。一開始就計(jì)算出一條快速路徑，可能只有幾步，只是一個(gè)大概的方向，然后讓角色開始按照這條路徑開始行進(jìn)，與此同時(shí)繼續(xù)計(jì)算完整路徑。
2. ??
需要更優(yōu)的路徑
??????
如果需要更優(yōu)的路徑，可以做進(jìn)一步對路徑進(jìn)行修正，也就是在搜索好的路徑上面選取一個(gè)點(diǎn)為目標(biāo)再次進(jìn)行搜索，找到更短路徑。這也意味著運(yùn)算時(shí)間更長，這時(shí)候就需要在性能和更好的效果上取一個(gè)平衡點(diǎn)。