人工智能與游戲的基礎(chǔ)知識(shí)-資料下載頁(yè)
2025-02-20 15:20本頁(yè)面
【正文】 ， A點(diǎn)可以通過不同的路徑到達(dá) B點(diǎn)和 C點(diǎn)，但是代價(jià)不同。 Page ? 20 尋徑算法 A*算法 在 A*算法的處理過程中，每個(gè)貼磚都被稱為一個(gè)節(jié)點(diǎn)， A*算法在計(jì)算過程中為每個(gè)非障礙物節(jié)點(diǎn)都計(jì)算一個(gè)通過這個(gè)節(jié)點(diǎn)到達(dá)目標(biāo)地點(diǎn)的代價(jià)函數(shù)，記為f(n)。在計(jì)算過程中， f(n)為一個(gè)估算值，隨著計(jì)算的進(jìn)行每個(gè)節(jié)點(diǎn)的 f(n)值都有可能改變。 A*算法定義： f(n)=g(n)+h(n)。 g(n)表示從起始點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)耗費(fèi)的代價(jià)，根據(jù)之前的條件，垂直和水平方向代價(jià)為 10，對(duì)角線方向?yàn)?14。 h(n)表示當(dāng)前點(diǎn)到目標(biāo)點(diǎn)估計(jì)代價(jià)，一般設(shè)定這個(gè)估計(jì)代價(jià)值為：當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的水平和垂直方格的總數(shù)，然后乘以 10。 A*算法在計(jì)算過程中使用到兩個(gè)鏈表，一個(gè)叫做 open表，另一個(gè)叫做 closed表。 closed表中的節(jié)點(diǎn)是其所有相鄰節(jié)點(diǎn)的 f(n)值全部計(jì)算過的節(jié)點(diǎn)， open表中的節(jié)點(diǎn)是計(jì)算過 f(n)值，但是其所有相鄰節(jié)點(diǎn)的 f(n)值沒有全部計(jì)算的節(jié)點(diǎn)。 Page ? 21 尋徑算法 A*算法的具體步驟 （ 1）將起始點(diǎn)添加到 open表中。 （ 2）重復(fù)以下步驟： ① 尋找 open表中 f(n)值最低的點(diǎn)作為當(dāng)前點(diǎn)，并將它放入 closed表中。 ② 遍歷當(dāng)前節(jié)點(diǎn)相鄰的所有 8個(gè)節(jié)點(diǎn)，如果不可通過或已經(jīng)在 closed表中，則略過。如果不在 open表中，則將其添加進(jìn) open表中，并把當(dāng)前節(jié)點(diǎn)作為其父節(jié)點(diǎn)，記錄這個(gè)節(jié)點(diǎn)的 f(n)、 g(n)、 h(n)值；如果已經(jīng)在 open表中，則檢查 g(n)值，看是否存在更好的路徑，如果存在，則把這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)改為當(dāng)前點(diǎn)，并重新計(jì)算這個(gè)節(jié)點(diǎn)的 g(n)和 f(n)值，對(duì) open表按 f(n)值排序。 ③ 當(dāng)目標(biāo)點(diǎn)被放入 closed表中時(shí)，路徑被找到。另一種情況是，沒有找到目標(biāo)點(diǎn)， open表已空，也就是說，路徑不存在。 （ 3）如果找到路徑，則從目標(biāo)點(diǎn)開始，按父節(jié)點(diǎn)返回起始點(diǎn)，這就是我們需要的路徑。 Page ? 22 尋徑算法 A*算法 A*算法在計(jì)算過程中的每步都會(huì)對(duì)所有 open表里的節(jié)點(diǎn)按照 f(n)值的大小進(jìn)行排序，選擇 f(n)值最小的節(jié)點(diǎn)將其移動(dòng)到 closed表中，并考慮其所有相鄰節(jié)點(diǎn)。具體步驟如下。 ① 如果某個(gè)相鄰節(jié)點(diǎn)不在 open表中，則將其加入 open表，并將當(dāng)前節(jié)點(diǎn)作為這個(gè)相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)，計(jì)算其 f(n)、 g(n)和 h(n)值。 ② 如果這個(gè)相鄰節(jié)點(diǎn)已經(jīng)在 open表中，則比較其 g(n)值與通過本節(jié)點(diǎn)到達(dá)此相鄰節(jié)點(diǎn)的總代價(jià)值，如果通過本節(jié)點(diǎn)到達(dá)這個(gè)相鄰節(jié)點(diǎn)的總代價(jià)值更小，則更新這個(gè)相鄰節(jié)點(diǎn)的 g(n)值，將其父節(jié)點(diǎn)設(shè)為本節(jié)點(diǎn)，并根據(jù)新的 g(n)值重新計(jì)算f(n)值；否則，不改變這個(gè)相鄰節(jié)點(diǎn)的任何屬性，同時(shí)將這些相鄰節(jié)點(diǎn)加入open表中，并對(duì)這些相鄰的節(jié)點(diǎn)計(jì)算 f(n)、 g(n)、 h(n)值。 Page ? 23 尋徑算法 A*算法的具體步驟 A*算法不斷重復(fù)上述過程，最終將找到一條從起始點(diǎn)到目標(biāo)點(diǎn)的代價(jià)最小的路徑，如圖所示。 Page ? 24 演講完畢，謝謝觀看！
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1