AI入門初探-機器人自動尋路算法基礎

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

AI入門初探-機器人自動尋路算法基礎

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

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

游戲中的路徑探索問題

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

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

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

A＊ 算法具有以下特性

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

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

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

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

工作原理

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

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

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

節點

一個節點的數據結構中包含了一組位置值（如x，y），一個指向其父節點的指針和三個與其相關的分數。這些分數決定了A*算法如何選擇優先考慮的節點。

G 分數

G分數是節點的基本分，它只是從起始節點出發到該節點的累積代價。

H 分數–啟發策略

這里的啟發策略是一種易于計算的，對從每個節點到目標節點距離的預估值。對H分數，易于計算非常重要，因為每個在節點的H分在到達目的地前都會被計算至少一遍。H分的選擇和待搜索的圖的具體特性相關，下面是一些最常用的啟發策略。

曼哈頓距離Manhattan distance

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

對角距離Diagonal distance

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

歐式距離

這個啟發策略可以用于任何角度的移動，標準的計算方程可能使得計算量太大，所以具體實現中往往使用計算量相對經濟的方程式。

F分數

F分數就是簡單的把G分數和H分數相加，用來表示通過當前節點的路徑的總代價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

算法應用DEMO

在研究學習了A*算法后，我將它和自己編寫的小游戲進行了結合，由于我編寫的游戲是一個2D網格型游戲，人物角色只有上下左右四個行走方向，所以使用G分數剛好。這樣就編寫出了NPC自動尋路AI，使游戲變得更加豐富多彩。下面是游戲其中一個場景截圖：

小結

在過去的10年里，游戲的AI發展很快，各種AI技術被引入到游戲中，如遺傳算法、人工神經網絡計算、地形分析技術、團隊尋徑算法、A*算法等，這些技術出色地解決了游戲中一些基本問題。我們有理由相信未來游戲的AI將會給玩家帶來更多的驚喜。

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