a演算法在游戲中的應用

Ⅰ A*演算法介紹

姓名：車文揚 學號：16020199006

【嵌牛導讀】：A*演算法的逐步詳解

【嵌牛鼻子】：啟發式演算法

【嵌牛提問】：A*演算法的原理是什麼？

【嵌牛正文】：

A*演算法

路徑規劃是指的是機器人的最優路徑規劃問題，即依據某個或某些優化准則（如工作代價最小、行走路徑最短、行走時間最短等），在工作空間中找到一個從起始狀態到目標狀態能避開障礙物的最優路徑。機器人的路徑規劃應用場景極豐富，最常見如游戲中NPC及控制角色的位置移動，網路地圖等導航問題，小到家庭掃地機器人、無人機大到各公司正爭相開拓的無人駕駛汽車等。

目前路徑規劃演算法分為：

A*演算法原理：

在計算機科學中，A*演算法作為Dijkstra演算法的擴展，因其高效性而被廣泛應用於尋路及圖的遍歷，如星際爭霸等游戲中就大量使用。在理解演算法前，我們需要知道幾個概念：

搜索區域（The Search Area）：圖中的搜索區域被劃分為了簡單的二維數組，數組每個元素對應一個小方格，當然我們也可以將區域等分成是五角星，矩形等，通常將一個單位的中心點稱之為搜索區域節點（Node）。

開放列表(Open List)：我們將路徑規劃過程中待檢測的節點存放於Open List中，而已檢測過的格子則存放於Close List中。

父節點（parent）：在路徑規劃中用於回溯的節點，開發時可考慮為雙向鏈表結構中的父結點指針。

路徑排序（Path Sorting）：具體往哪個節點移動由以下公式確定：F(n) = G + H 。G代表的是從初始位置A沿著已生成的路徑到指定待檢測格子的移動開銷。H指定待測格子到目標節點B的估計移動開銷。

啟發函數（Heuristics Function）：H為啟發函數，也被認為是一種試探，由於在找到唯一路徑前，我們不確定在前面會出現什麼障礙物，因此用了一種計算H的演算法，具體根據實際場景決定。在我們簡化的模型中，H採用的是傳統的曼哈頓距離（Manhattan Distance），也就是橫縱向走的距離之和。

如下圖所示，綠色方塊為機器人起始位置A，紅色方塊為目標位置B，藍色為障礙物。

我們把要搜尋的區域劃分成了正方形的格子。這是尋路的第一步，簡化搜索區域。這個特殊的方法把我們的搜索區域簡化為了2 維數組。數組的每一項代表一個格子，它的狀態就是可走(walkalbe)或不可走(unwalkable) 。現用A*演算法尋找出一條自A到B的最短路徑，每個方格的邊長為10，即垂直水平方向移動開銷為10。因此沿對角移動開銷約等於14。具體步驟如下：

從起點 A 開始，把它加入到一個由方格組成的open list(開放列表) 中，這個open list像是一個購物清單。Open list里的格子是可能會是沿途經過的，也有可能不經過。因此可以將其看成一個待檢查的列表。查看與A相鄰的8個方格 ，把其中可走的 (walkable) 或可到達的(reachable) 方格加入到open list中。並把起點 A 設置為這些方格的父節點 (parent node) 。然後把 A 從open list中移除，加入到close list(封閉列表) 中，close list中的每個方格都是不需要再關注的。

如下圖所示，深綠色的方格為起點A，它的外框是亮藍色，表示該方格被加入到了close list 。與它相鄰的黑色方格是需要被檢查的，他們的外框是亮綠色。每個黑方格都有一個灰色的指針指向他們的父節點A。

下一步，我們需要從open list中選一個與起點A相鄰的方格。但是到底選擇哪個方格好呢？選F值最小的那個。我們看看下圖中的一些方格。在標有字母的方格中G = 10 。這是因為水平方向從起點到那裡只有一個方格的距離。與起點直接相鄰的上方，下方，左方的方格的G 值都是10 ，對角線的方格G 值都是14 。H值通過估算起點到終點( 紅色方格) 的Manhattan 距離得到，僅作橫向和縱向移動，並且忽略沿途的障礙。使用這種方式，起點右邊的方格到終點有3 個方格的距離，因此H = 30 。這個方格上方的方格到終點有4 個方格的距離( 注意只計算橫向和縱向距離) ，因此H = 40 。

比較open list中節點的F值後，發現起點A右側節點的F=40，值最小。選作當前處理節點，並將這個點從Open List刪除，移到Close List中。

對這個節點周圍的8個格子進行判斷，若是不可通過（比如牆，水，或是其他非法地形）或已經在Close List中，則忽略。否則執行以下步驟：

若當前處理節點的相鄰格子已經在Open List中，則檢查這條路徑是否更優，即計算經由當前處理節點到達那個方格是否具有更小的 G值。如果沒有，不做任何操作。相反，如果G值更小，則把那個方格的父節點設為當前處理節點 ( 我們選中的方格 ) ，然後重新計算那個方格的 F 值和 G 值。

若當前處理節點的相鄰格子不在Open List中，那麼把它加入，並將它的父節點設置為該節點。

按照上述規則我們繼續搜索，選擇起點右邊的方格作為當前處理節點。它的外框用藍線打亮，被放入了close list 中。然後我們檢查與它相鄰的方格。它右側的3個方格是牆壁，我們忽略。它左邊的方格是起點，在close list 中，我們也忽略。其他4個相鄰的方格均在open list 中，我們需要檢查經由當前節點到達那裡的路徑是否更好。我們看看上面的方格，它現在的G值為14 ，如果經由當前方格到達那裡，G值將會為20( 其中10為從起點到達當前方格的G值，此外還要加上從當前方格縱向移動到上面方格的G值10) ，因此這不是最優的路徑。看圖就會明白直接從起點沿對角線移動到那個方格比先橫向移動再縱向移動要好。

當把4個已經在open list 中的相鄰方格都檢查後，沒有發現經由當前節點的更好路徑，因此不做任何改變。接下來要選擇下一個待處理的節點。因此再次遍歷open list ，現在open list中只有7 個方格了，我們需要選擇F值最小的那個。這次有兩個方格的F值都是54，選哪個呢？沒什麼關系。從速度上考慮，選擇最後加入open list 的方格更快。因此選擇起點右下方的方格，如下圖所示。

接下來把起點右下角F值為54的方格作為當前處理節點，檢查其相鄰的方格。我們發現它右邊是牆（牆下面的一格也忽略掉，假定牆角不能直接穿越)，忽略之。這樣還剩下 5 個相鄰的方格。當前方格下面的 2 個方格還沒有加入 open list ，所以把它們加入，同時把當前方格設為他們的父親。在剩下的 3 個方格中，有 2 個已經在 close list 中 ( 一個是起點，一個是當前方格上面的方格，外框被加亮的 ) ，我們忽略它們。最後一個方格，也就是當前方格左邊的方格，檢查經由當前方格到達那裡是否具有更小的 G 值。沒有，因此我們准備從 open list 中選擇下一個待處理的方格。

不斷重復這個過程，直到把終點也加入到了open list 中，此時如下圖所示。注意在起點下方2 格處的方格的父親已經與前面不同了。之前它的G值是28並且指向它右上方的方格。現在它的G 值為20 ，並且指向它正上方的方格。這是由於在尋路過程中的某處使用新路徑時G值更小，因此父節點被重新設置，G和F值被重新計算。

那麼我們怎樣得到實際路徑呢？很簡單，如下圖所示，從終點開始，沿著箭頭向父節點移動，直至回到起點，這就是你的路徑。

A*演算法總結：

1. 把起點加入 open list 。

2. 重復如下過程：

a. 遍歷open list ，查找F值最小的節點，把它作為當前要處理的節點，然後移到close list中

b. 對當前方格的 8 個相鄰方格一一進行檢查，如果它是不可抵達的或者它在close list中，忽略它。否則，做如下操作：

□  如果它不在open list中，把它加入open list，並且把當前方格設置為它的父親

□  如果它已經在open list中，檢查這條路徑 ( 即經由當前方格到達它那裡 ) 是否更近。如果更近，把它的父親設置為當前方格，並重新計算它的G和F值。如果你的open list是按F值排序的話，改變後你可能需要重新排序。

c. 遇到下面情況停止搜索：

□  把終點加入到了 open list 中，此時路徑已經找到了，或者

□  查找終點失敗，並且open list 是空的，此時沒有路徑。

3. 從終點開始，每個方格沿著父節點移動直至起點，形成路徑。

Ⅱ 什麼是A搜索演算法

A*搜索演算法，俗稱A星演算法，作為啟發式搜索演算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Ⅲ 人工智慧在游戲中的應用有什麼

1. 現代電腦游戲簡介
電子游戲從1971年誕生以來，越來越受到人們的喜愛。隨著現代計算機、網路、虛擬現實、人工智慧等技術的發展，游戲的擬人化越來越逼真。高度的擬人化使得現代電腦游戲能夠模仿人類社會中的各種情形，並把這些情形通過視覺、聽覺、甚至觸覺等多種感官反映到人的大腦，從而對人們的現實生活產生巨大沖擊。基於游戲中的這些反映人類社會的情形不同和游戲表示的方式不同，可以把電子游戲分為幾大類別：縱向卷軸和橫向卷軸類、棋牌邏輯類、文字冒險類、圖形冒險類、模擬類、戰略類、第一或第三人稱射擊類和角色扮演類。
無論游戲屬於何種類別，游戲玩家都希望在游戲中能夠體驗到現實中無法體驗到的刺激，得到現實中無法得到的滿足。這些刺激和滿足主要表現在特定的挑戰、社會化、吹噓與幻想、情感等方面。實際上，大部分的玩家並不能預先知道他們想要什麼樣的游戲，但是他們往往在看到了一個精美的游戲後說，「嗯，我要的就是這個！」
要使得玩家喜歡游戲，游戲的開發過程必須得到重視。一般來說，游戲的開發過程主要分為四個階段：構想階段、總體設計階段、細節設計階段和建設階段。[1]
萬事開頭難，構想階段是游戲開發中最為重要的階段。一個好的游戲背景故事是整個游戲成功的一半。在准備好游戲故事之後，就需要考慮游戲採用何種游戲類型，並把游戲故事分割成幕(Act)，改編為游戲劇本(Gameplay)。
在總體設計階段，要考慮每個幕中的角色和規則，同時也要考慮相關的技術問題。比如，游戲將採用何種技術、准備運行在什麼平台上等。
在細節設計階段，要對每一幕中的焦點(Focus)進行設計，對每一幕的效果產生效果圖，選擇合適的音樂匹配到各個場景，設計各個角色和場景的細節。
最後是建設階段。開發者要採用選定的技術對游戲進行開發。游戲製作包括編程和觸發器的製作。最後要進行游戲測試。2. 基於電腦游戲的圖靈實驗
人們在娛樂電腦游戲的時候，往往希望游戲中的其他角色能夠擁有某些程度上的智能。這些智能可以使得人們能夠在游戲的同時得到滿足。然而，這種智能必須得到控制。如果游戲中的機器角色的智能明顯高於玩家的能力，使得玩家對勝利喪失信心，那麼玩家會放棄這樣的游戲。所以，人工愚蠢(Artificial Stupidity)技術也是必不可少的。在游戲中，太強或太弱的人工智慧都是不合適的。
那何種程度的人工智慧才是合適的呢？回答這個問題首先要考慮怎樣的機器可以算作智能機器。圖靈曾經提出了「圖靈實驗」的概念。他認為能夠通過圖靈實驗的機器是具有智能的。其實，在游戲中也是一樣的。「圖靈實驗」在游戲中可以這樣描述：當玩家和其他玩家同諸多機器在同時游戲時，如果這個玩家通過游戲規則中的任何方式都無法分辨游戲中的其他角色哪個是其他玩家，哪個是機器的線程，那麼我們可以說這個游戲通過了「游戲中的圖靈測試」。[2]一般來說，通過了「游戲中的圖靈測試」的游戲是最適合玩家娛樂的。3. 游戲中的人工智慧技術
人工智慧在游戲中的目標主要有五個：一是為玩家提供適合的挑戰；二是使玩家處於亢奮狀態；三是提供不可預知性結果；四是幫助完成游戲的故事情節；五是創造一個生動的世界。這個生動的世界可以是類似現實生活中的世界，也可以是與現實世界完全不同的世界。但不管何種世界都要求有一整套能夠自圓其說的游戲規則。
在游戲製作過程中，實現人工智慧的關鍵主要有：虛擬現實與擬人化、動畫效果與機器角色場景感知[3]、機器角色的機器學習和進化、玩家與機器角色之間的平衡性、人工愚蠢技術、確定性人工智慧技術與非確定性人工智慧技術的互補。
游戲中的人工智慧的主要技術主要有：有限狀態自動機(Finite State Machines)、模糊邏輯(Fuzzy Logic)、A*演算法與有效尋徑(A* Algorithm for Efficient Pathfinding)、腳本設計(Scripting)、基於規則的人工智慧和系統(Rules-based AI and Systems)、人工生命(Artificial life)、貝葉斯推論(Bayesian Inference)和非確定性貝葉斯網路(Bayesian Networks for Uncertainty Decisions)、神經網路(Neural Networks)和遺傳演算法(Genetic Algorithms)等。4. 目前的局限與前景展望
就目前來說，技術上的困難主要來源於兩個方面：一是游戲中的非確定狀態實在太多；二是現有的硬體和計算機網路對於高級人工智慧還說，速度還達不到要求。[4]
目前要解決這些困難，在技術上來說還是不成熟的。對於數量極多的非確定狀態來說，盡可能地提高硬體和計算機網路的速度，可能是一個解決方法。但是要提高硬體和計算機網路的速度也並非易事。這可能要等到全息光學計算機和光互聯網誕生之後才能徹底解決。但目前有效的辦法是提高軟體的執行速度。比如使用更有效的演算法或神經網路等新技術。

Ⅳ 游戲中為什麼用啟發式a星演算法

首先，A* 是啟發式演算法，在尋路過程中搜索的范圍相比 Dijsktra 一般要小得多（當然，有時也可能一樣）
其次，A* 演算法的搜索速度和效率可控，可以通過控制代價函數來權衡搜索的速度和精度之間的關系

Ⅳ A*演算法的好處

其實A*演算法也是一種最好優先的演算法
只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到節點n的最短路徑值，h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。