武漢市第二中學(xué)高三（五班） 何瑞豐

AI入門(mén)初探-機(jī)器人自動(dòng)尋路算法基礎(chǔ)

武漢市第二中學(xué)高三（五班） 何瑞豐

人工智能（Artificial Intelligence，簡(jiǎn)稱(chēng)AI）是最近的一個(gè)比較火的名詞，相信大家對(duì)于阿爾法狗和無(wú)人駕駛都不陌生吧？隨著人工智能技術(shù)的日益發(fā)達(dá)，我們的生活中也出現(xiàn)了越來(lái)越多的智能產(chǎn)品，比如掃地機(jī)器人，另外游戲中的人工智能，是指用來(lái)控制游戲中各種活動(dòng)對(duì)象行為的邏輯。大部分游戲（比如連連看，王者榮耀等），特別是角色扮演類(lèi)游戲都需要人工智能，在游戲中玩家是主要人物，而游戲中的其他人物由電腦AI操縱。游戲開(kāi)發(fā)領(lǐng)域中的AI設(shè)計(jì)越來(lái)越被游戲開(kāi)發(fā)者和玩家重視，因?yàn)樗芙o玩家提供更大的挑戰(zhàn)性，從而增加游戲的可玩性。

游戲中的路徑探索問(wèn)題

路徑探索問(wèn)題是游戲AI研究的一個(gè)重要方面，快速、準(zhǔn)確的路徑探索是游戲開(kāi)發(fā)者追求的目標(biāo)。計(jì)算出讓玩家或者角色從游戲地圖中的A點(diǎn)到達(dá)B點(diǎn)的一條路徑，是一件困難的事情。

當(dāng)我十四歲時(shí)候，我通過(guò)游戲開(kāi)發(fā)學(xué)習(xí)編程，并從此愛(ài)上了編程。我最早學(xué)習(xí)的正式算法之一就是A*，我非常享受這個(gè)學(xué)習(xí)的過(guò)程。這是最被廣泛使用的算法之一，也是接觸路徑搜索問(wèn)題的經(jīng)典算法。A*尋路算法一直以來(lái)被游戲界認(rèn)為是最好的尋路算法之一，因而被大量應(yīng)用。由于A*算法是按照尋找最低耗費(fèi)的路徑來(lái)設(shè)計(jì)，A*會(huì)找到最短，最直接的路徑。

我一直覺(jué)得最簡(jiǎn)單的路徑搜索的例子就是游戲中的2D網(wǎng)格，它可以被用來(lái)尋找任何圖中從A到B的路徑。比如，圖中黑色的網(wǎng)格是障礙物，白色是可供過(guò)部分,使用A*得到A到B的路徑。

A＊ 算法具有以下特性

（1）如果存在A到B的路徑的解存在，那么它一定可以求解。

（2）它可以通過(guò)啟發(fā)策略極大的提高求解過(guò)程。

（3）它可以設(shè)計(jì)行走點(diǎn)有不同的行走權(quán)重，比如，這可以描述游戲中的探險(xiǎn)者在巖石地貌的地圖行走更加緩慢，在草地行走更快。

（4）如果需要，它可以對(duì)很多不同的方向展開(kāi)搜索。

工作原理

（1）A*通過(guò)維持兩條列表來(lái)工作：一條開(kāi)放列表，一條封閉列表。開(kāi)放列表的目的是保存從起點(diǎn)出發(fā)的最優(yōu)路徑上可能包括但尚未被考慮的節(jié)點(diǎn)。如果開(kāi)放列表為空，那么意味著路徑不存在。封閉路徑初始為空，用來(lái)保存所有已經(jīng)被考察訪問(wèn)過(guò)的節(jié)點(diǎn)。

（2）在算法的核心循環(huán)中，反復(fù)從開(kāi)放列表中找出預(yù)估到目標(biāo)節(jié)點(diǎn)代價(jià)最小的節(jié)點(diǎn)，如果選中的節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，就將它的所有有效鄰接節(jié)點(diǎn)存入開(kāi)放列表。重復(fù)這個(gè)過(guò)程，直到循環(huán)終止。

（3）算法中的一個(gè)竅門(mén)在于，所有的創(chuàng)建的節(jié)點(diǎn)中需要保留一個(gè)指針，指向其父節(jié)點(diǎn)。這樣，我們就可以在算法中所創(chuàng)建的任意節(jié)點(diǎn)回溯起始節(jié)點(diǎn)。

節(jié)點(diǎn)

一個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中包含了一組位置值（如x，y），一個(gè)指向其父節(jié)點(diǎn)的指針和三個(gè)與其相關(guān)的分?jǐn)?shù)。這些分?jǐn)?shù)決定了A*算法如何選擇優(yōu)先考慮的節(jié)點(diǎn)。

G 分?jǐn)?shù)

G分?jǐn)?shù)是節(jié)點(diǎn)的基本分，它只是從起始節(jié)點(diǎn)出發(fā)到該節(jié)點(diǎn)的累積代價(jià)。

H 分?jǐn)?shù)–啟發(fā)策略

這里的啟發(fā)策略是一種易于計(jì)算的，對(duì)從每個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離的預(yù)估值。對(duì)H分?jǐn)?shù)，易于計(jì)算非常重要，因?yàn)槊總€(gè)在節(jié)點(diǎn)的H分在到達(dá)目的地前都會(huì)被計(jì)算至少一遍。H分的選擇和待搜索的圖的具體特性相關(guān)，下面是一些最常用的啟發(fā)策略。

曼哈頓距離Manhattan distance

這是最簡(jiǎn)單的啟發(fā)策略。對(duì)于允許在4個(gè)方向（上下左右）移動(dòng)的網(wǎng)格而言是最好的策略。

對(duì)角距離Diagonal distance

這個(gè)策略一般用于可以8個(gè)方向上的移動(dòng)，除了上下左右,在斜方向上的4個(gè)距離也可以移動(dòng)。

歐式距離

這個(gè)啟發(fā)策略可以用于任何角度的移動(dòng)，標(biāo)準(zhǔn)的計(jì)算方程可能使得計(jì)算量太大，所以具體實(shí)現(xiàn)中往往使用計(jì)算量相對(duì)經(jīng)濟(jì)的方程式。

F分?jǐn)?shù)

F分?jǐn)?shù)就是簡(jiǎn)單的把G分?jǐn)?shù)和H分?jǐn)?shù)相加，用來(lái)表示通過(guò)當(dāng)前節(jié)點(diǎn)的路徑的總代價(jià)f(n) = g(n) + h(n)

偽代碼 (下面是允許8向移動(dòng)的算法的偽碼)

function A*(start, goal)

open_list = set containing start

closed_list = empty set

start.g = 0

start.f = start.g + heuristic(start, goal)

while open_list isnot empty

current = open_list element with lowest f cost

if current = goal

return construct_path(goal) // path found

remove current from open_list

add current to closed_list

for each neighbor in neighbors(current)

if neighbor notin closed_list

neighbor.f = neighbor.g + heuristic(neighbor, goal)

if neighbor isnotin open_list

add neighbor to open_list

else

openneighbor = neighbor in open_list

if neighbor.g lt; openneighbor.g

openneighbor.g = neighbor.g

openneighbor.parent = neighbor.parent

returnfalse// no path exists

function neighbors(node)

neighbors = set of valid neighbors to node // check for obstacles here

for each neighbor in neighbors

if neighbor is diagonal

neighbor.g = node.g + diagonal_cost // eg. 1.414 (pythagoras)

else

neighbor.g = node.g + normal_cost // eg. 1

neighbor.parent = node

return neighbors

function construct_path(node)

path = set containing node

while node.parent exists

node = node.parent

add node to path

return path

算法應(yīng)用DEMO

在研究學(xué)習(xí)了A*算法后，我將它和自己編寫(xiě)的小游戲進(jìn)行了結(jié)合，由于我編寫(xiě)的游戲是一個(gè)2D網(wǎng)格型游戲，人物角色只有上下左右四個(gè)行走方向，所以使用G分?jǐn)?shù)剛好。這樣就編寫(xiě)出了NPC自動(dòng)尋路AI，使游戲變得更加豐富多彩。下面是游戲其中一個(gè)場(chǎng)景截圖：

小結(jié)

在過(guò)去的10年里，游戲的AI發(fā)展很快，各種AI技術(shù)被引入到游戲中，如遺傳算法、人工神經(jīng)網(wǎng)絡(luò)計(jì)算、地形分析技術(shù)、團(tuán)隊(duì)尋徑算法、A*算法等，這些技術(shù)出色地解決了游戲中一些基本問(wèn)題。我們有理由相信未來(lái)游戲的AI將會(huì)給玩家?guī)?lái)更多的驚喜。

[1]何國(guó)輝,陳家琪．游戲開(kāi)發(fā)中智能路徑搜索的算法研究[J],計(jì)算機(jī)工程與設(shè)計(jì),2006,27(13)：2334-2337．