創作內容

6 GP

人工智慧演算法~A*

作者:willyliu│2009-07-30 01:03:59│贊助:10│人氣:6773
A*(A-star)是遊戲界中極出名的演算法 有研究這個領域的都知道
A*是用來搜尋路徑的演算法,它保證每次都能找到成本最低的路徑

有幾個術語:
節點: 在地圖上佈滿了節點,角色可由一個節點經過另一個而達到目標結點
地形成本: 由某一節點走向另一個所花費的成本(也許是錢,也許是時間......)
啟發成本: 用來評估一個節點是否接近終點(可能是到終點的距離),一個有點抽象的概念...用來決定節點搜尋的優先順序
總成本: 由起點累積到當前結點的地形成本和 + 當前結點的啟發成本
擴展: 拜訪相鄰節點

概觀:
在一個地圖中,我們要搜尋從A點到B點的最低成本路徑,所得的最短路徑為一個節點陣列,為路徑通過的結點
在連續的空間環境中,可能較難建立節點,因為鄰近結點之間要能相通;在方塊世界比較容易

演算法:
宣告陣列 open,closed
建立起始節點
open.push(起始結點)
while open不為空
{
set 當前節點 = open中總成本小的節點
if 當前節點 == 終點
{
搜尋結束,回傳當前節點
}
else
{
//擴展當前節點
for each 相鄰節點
{
if 此相鄰節點未被拜訪過 or 此相鄰節點總成本 > 當前節點的總成本 + 地形成本
{
set 此相鄰節點.parent = 當前節點
set 此相鄰節點的總成本 + 地形成本
set 此相鄰節點.parent = 當前節點
set 此相鄰節點的總成本 + 地形成本
open.push(此相鄰節點)
if 此相鄰節點在closed中
{
把此相鄰節點從closed中移除
}
}
//擴展結束
把當前節點從open中移除
closed.push(當前節點)
}
}

open裡面放的是尚未拓展,而已經到訪的結點,裡面總成本(包含起發成本)最小的作為下次拓展對象
closed裡面放的是已經拓展過的結點
每一次while迴圈時, 從open中選出最小成本的結點進行拓展,直到終點
每一個節點,除了起始結點外都記錄一個parent,也就是前一步是哪個節點
如果將要到訪的節點之前已經被到訪過了,就檢查舊的成本是否大於此路線的成本,如果是,便設此節點的parent為當前節點,改變路徑

最後,到訪至終點後,回傳"終點"這個節點,我們的路徑可以藉由parent這項追溯到起點

至於啟發成本,比較不確定,可以簡略地設為到終點的直線距離
總地形成本才算是真正的成本,啟發成本只是用來決定拓展順序而已

在此簡介A*結束 的相關文章可以在許多遊戲書籍中找到
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=247966
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:|program|programming|程式設計|程式|AI|人工智慧|

留言共 1 篇留言

中出廷
好多字 = =
懶的看
畫說你把高中數學概念丟上來?!

送你個GP吃啦 = =

07-30 11:37

willyliu
高中數學嗎?...算是吧
雖然說領域是高中的,但是這個演算法我小學就看懂了啊

正確來說,應該算是離散數學中的圖形結構...但是根本不需要那麼深的概念

這一切都是這樣...有耐心就看得懂07-30 21:41
我要留言提醒:您尚未登入,請先登入再留言

6喜歡★a27268139 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:人工智慧演算法~類神經網... 後一篇:遊戲物理,數學~向量的功...

追蹤私訊

作品資料夾

ycro52眾紳士
我...我畫了萊莎肥腿魔 有興趣紳士可以路過看看 愛你...看更多我要大聲說7小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】