一顆星星搜尋演算法 (A Star Search Algorithm)真是個有趣的名字，那有沒有兩顆星星搜尋演算法？倒是沒有～其實正確應該翻譯成A星搜尋演算法(A* Search Algorithm)，至於為何要這麼命名，這我就不曉得了，去問天才作者吧！
A星搜尋演算法(A* Search Algorithm)在電腦資訊演算法中廣泛用在pathfinding和graph traversal，它有優異的效能和精確。1968年發展出來，是由Edsger Dijkstra’s 1959 algorithm擴展的演算法，有著更好的效果。
早在大三時我去上阿哲的人工智慧，印象最深刻的演算法就是A星搜尋演算法，當時覺得它有趣易懂，只是當時的我還沒有對寫遊戲非常熱衷，所以並沒有趣實做它。然而昨日遊戲設計主題Game AI，提到pathfinding其中之一個演算法就是A*，剛好喚起我沉睡已久的腦袋。
有一次跟研究生同學聊到A*，原來早就用在online game上，因為她有參與開發仙劍online，所以知道人物「自動」去找NPC就是用到A星搜尋演算法。至此我對A*更為感興趣了！
A星搜尋演算法有一個cost function，是這樣定義的：
- Goal: 計算一條從起點S到終點G的路徑
- 在n點的cost:
- f(n) = g(n) + h(n)
- g(n): 從起點S到目前點n的距離
- h(n): 從目前點n到終點G估計的距離
- f(n): 點n目前估計的距離
直接來看一個例子更容易理解：
各個點n的h(n)如表：
終點為Bucharest，各點到終點的直線距離。亮藍色為起點，亮紅色為終點。
此圖描述A*從起點到終點的過程。空心點為open set，實心點為close set，顏色越接近綠色表示越靠近終點。
此圖描述Dijkstra's algorithm從起點到終點的過程。空心點為open set，實心點為close set，顏色越接近綠色表示越靠近終點。
參考：WiKi – A* search algorithm、WiKi – Dijkstra’s algorithm、遊戲設計Game AI投影片。
逍遙文工作室 
Comments on: "A星搜尋演算法 (A* Search Algorithm)" (7)
請問~如果要將紅外線讀入的值使用A*演算法的化，該怎麼做比較好？
（二進制0101值，使用TCRT5000)
讚Liked by 1 person
你好，資訊太少，TCRT5000是什麼？
讚讚
TCRT5000是我選用的紅外線型號
我是使用五顆紅外線燈號偵測黑線，走棋盤方格的地圖
原本單純使用case的方式撰寫，但容易有誤判（例如該轉彎不轉或者該直走卻轉彎）
所以想改用演算法的方式讓它正確判斷動作。
不知道在這部分適不適用A*~~~
因為研究有牽扯到編隊系統的部分，
要找出最路徑並且讓每台自走車彼此協調走位
所以我選用A*來做為主要演算的部分
但是不清楚該如何將紅外線的值帶入演算法內運用….
五顆紅外線分別是 SL2.SL1.SM.SR1.SR2
當燈號讀取為1時，代表的值分別是1 , 2 ,4 ,8 ,16
原本使用case方式撰寫是指：
case 7 >> 代表SL2.SL1.SM這三顆紅外線偵測到黑線
那在case 7 當中就會放入讓車子左轉的副程式
不過這種方式容易誤判…..想請問這總合上述形容，適用A*嗎?
還是只能用在最佳路徑的部分，關於誤判要是別的演算法比較好呢？
讚Liked by 1 person
嗯～感謝你如此詳細的描述，才知道這玩意兒這麼複雜ＸＤ～我只能跟你說A*是用來找最短路徑，若同時要考慮多台車輛，就得配合其它演算法，這可要花時間研究呢！ 😀
讚讚
如果遊戲的人物可以360度移動
那A*和直接偵測目標的方位
哪個比較好
讚Liked by 2 people
謝謝你的整理跟介紹，讓原本對很怕演算法的我有興趣去研究，很詳細很實用: )
讚Liked by 1 person
很開心對你有幫助！就是因為演算法相當有趣，若用圖解來學習會更有意思，要是時間允許的話，我真想整理所有演算法，像這篇A星搜尋演算法一樣，讓更多有心學習的人可以樂在其中！ 😀
讚讚