AI入門初探-機(jī)器人自動尋路算法基礎(chǔ)

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

AI入門初探-機(jī)器人自動尋路算法基礎(chǔ)

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

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

游戲中的路徑探索問題

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

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

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

A＊ 算法具有以下特性

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

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

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

（4）如果需要，它可以對很多不同的方向展開搜索。

工作原理

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

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

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

節(jié)點

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

G 分?jǐn)?shù)

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

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

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

曼哈頓距離Manhattan distance

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

對角距離Diagonal distance

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

歐式距離

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

F分?jǐn)?shù)

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

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

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*算法后，我將它和自己編寫的小游戲進(jìn)行了結(jié)合，由于我編寫的游戲是一個2D網(wǎng)格型游戲，人物角色只有上下左右四個行走方向，所以使用G分?jǐn)?shù)剛好。這樣就編寫出了NPC自動尋路AI，使游戲變得更加豐富多彩。下面是游戲其中一個場景截圖：

小結(jié)

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

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