我發現了一些關於遊戲中人工智慧的有趣材料。 透過簡單的例子解釋了人工智慧的基本知識，裡面有很多有用的工具和方法，可以輕鬆地進行開發和設計。 如何、在何處以及何時使用它們也在那裡。
大多數範例都是用偽代碼編寫的，因此不需要高級程式設計知識。 剪輯下方有 35 張帶有圖片和 gif 的文字，所以請做好準備。
UPD。 抱歉，我已經翻譯了這篇關於哈布雷的文章 。 你可以閱讀他的版本 ，但由於某種原因，這篇文章與我擦肩而過（我使用了搜索，但出現了問題）。 由於我正在一個致力於遊戲開發的部落格上寫作，因此我決定將我的翻譯版本留給訂閱者（有些要點的格式不同，有些根據開發人員的建議故意省略）。
什麼是人工智能？
遊戲人工智慧重點在於物件應根據其所處的條件執行哪些操作。 這通常被稱為「智慧代理」管理，其中代理是玩家角色、車輛、機器人，或有時更抽象的東西：整個實體組甚至是文明。 在每種情況下，它都必須看到它的環境，根據它做出決定，並按照它採取行動。 這稱為感知/思考/行動循環：
- 感知：代理人發現或接收有關其環境中可能影響其行為的事物的資訊（附近的威脅、要收集的物品、要探索的有趣地方）。
- 思考：特工決定如何反應（考慮是否足夠安全來收集物品或他是否應該先戰鬥/隱藏）。
- 行動：代理人執行行動以實施先前的決定（開始向敵人或物體移動）。
- ……現在情況由於角色的行為而發生了變化，因此循環會用新數據重複。
人工智慧傾向於關注循環的感知部分。 例如，自動駕駛汽車拍攝道路照片，將其與雷達和光達數據結合，並進行解釋。 這通常是透過機器學習來完成的，機器學習處理傳入的數據並賦予其含義，提取語義訊息，例如「在你前面 20 碼處有另一輛車」。 這些就是所謂的分類問題。
遊戲不需要複雜的系統來提取訊息，因為大多數數據已經是遊戲不可或缺的一部分。 無需運行圖像識別演算法來確定前方是否有敵人——遊戲已經知道並將資訊直接輸入決策過程。 因此，週期的「感知」部分通常比「思考和行動」部分簡單得多。
遊戲人工智慧的局限性
人工智慧有許多必須遵守的限制：
- AI不需要事先訓練，就好像它是一種機器學習演算法一樣。 在開發過程中編寫一個神經網路來監控數以萬計的玩家並學習與他們對抗的最佳方式是沒有意義的。 為什麼？ 因為遊戲還沒發售，還沒有玩家。
- 遊戲應該有趣且具有挑戰性，因此特工不應該找到對抗人類的最佳方法。
- 特工需要看起來很真實，這樣玩家才會感覺自己在與真人對戰。 AlphaGo 程式的表現優於人類，但所選的步驟與傳統的遊戲理解相去甚遠。 如果遊戲模擬的是人類對手，這種感覺就不應該存在。 需要更改演算法，以便做出合理的決策，而不是理想的決策。
- 人工智慧必須即時工作。 這意味著演算法無法長時間獨佔CPU使用率來做出決策。 即使 10 毫秒也太長了，因為大多數遊戲只需要 16 到 33 毫秒即可完成所有處理並進入下一個圖形幀。
- 理想情況下，系統的至少一部分應該是資料驅動的，以便非編碼人員可以更快地進行更改和調整。
讓我們看看涵蓋整個感知/思考/行動週期的人工智慧方法。
做出基本決定
讓我們從最簡單的遊戲開始—乒乓球。 目標：移動球拍，使球從球拍上彈開，而不是飛過球拍。 就像網球一樣，如果你不擊球，你就輸了。 這裡人工智慧有一個相對簡單的任務──決定平台往哪個方向移動。
條件語句
對於 Pong 中的 AI，最明顯的解決方案是始終嘗試將平台放置在球下方。
一個簡單的演算法，用偽代碼寫：
遊戲運行時的每一幀/更新：
如果球位於球拍左側：
向左移動槳
否則，如果球位於球拍右側：
向右移動槳
如果平台以球的速度移動，那麼這就是 Pong 中 AI 的理想演算法。 如果代理程式沒有太多資料和可能的操作，則無需使任何事情複雜化。
這種方法非常簡單，以至於整個感知/思考/行動週期幾乎不易被注意到。 但它就在那裡：
- Sense 部分位於兩個 if 語句中。 遊戲知道球在哪裡以及平台在哪裡，因此人工智慧會向它尋找這些資訊。
- Think 部分也包含在兩個 if 語句中。 它們體現了兩種解決方案，在這種情況下，這兩種解決方案是相互排斥的。 結果，選擇三個操作之一 - 將平台向左移動、向右移動，或如果平台已經正確定位，則不執行任何操作。
- Act 部分位於 Move Paddle Left 和 Move Paddle Right 語句中。 根據遊戲設計，他們可以立即或以特定速度移動平台。
這種方法稱為反應式 - 有一組簡單的規則（在本例中是程式碼中的 if 語句），可以對世界的當前狀態做出反應並採取行動。
決策樹
Pong 的例子其實相當於一個正式的人工智慧概念，稱為決策樹。 演算法透過它到達「葉子」——關於採取什麼行動的決定。
讓我們為我們平台的演算法製作一個決策樹框圖：
樹的每個部分都稱為節點 - AI 使用圖論來描述此類結構。 有兩種類型的節點：
- 決策節點：根據測試某些條件在兩個備選方案之間進行選擇，其中每個備選方案都表示為一個單獨的節點。
- 結束節點：代表最終決策的要執行的操作。
演算法從第一個節點（樹的“根”）開始。 它要么決定轉到哪個子節點，要么執行儲存在節點中的操作並退出。
讓決策樹執行與上一節的 if 語句相同的工作有什麼好處？ 這裡有一個通用系統，其中每個決策只有一個條件和兩種可能的結果。 這使得開發人員可以根據代表樹中決策的資料創建人工智慧，而無需對其進行硬編碼。 我們用表格的形式來展示：
在程式碼方面，您將獲得一個用於讀取字串的系統。 為每個節點建立一個節點，根據第二列連接決策邏輯，根據第三列和第四列連接子節點。 您仍然需要對條件和動作進行編程，但現在遊戲的結構將更加複雜。 您可以在此處新增其他決策和操作，然後透過簡單地編輯樹訂文字檔案來自訂整個 AI。 接下來，您將檔案傳輸給遊戲設計者，他們可以更改行為，而無需重新編譯遊戲或更改程式碼。
當決策樹是根據大量範例自動建置時（例如，使用 ID3 演算法），它非常有用。 這使得它們成為根據所獲得的數據對情況進行分類的有效且高效能的工具。 然而，我們超越了一個供代理選擇操作的簡單系統。
情境
我們分析了使用預先建立的條件和操作的決策樹系統。 設計人工智慧的人可以隨心所欲地組織這棵樹，但他仍然必須依賴編寫這一切的程式設計師。 如果我們可以為設計師提供工具來創造自己的條件或行動呢？
這樣程式設計師就不必為條件「球在球拍左側」和「球在球拍右側嗎」編寫程式碼，他可以創建一個系統，設計人員將在其中編寫條件來檢查這些值。 那麼決策樹資料將如下所示：
這本質上與第一個表中的相同，但解決方案本身有自己的程式碼，有點像 if 語句的條件部分。 在程式碼方面，這將在第二列中讀取決策節點，但不是尋找要執行的特定條件（球是否位於球拍左側），而是評估條件表達式並相應地傳回 true 或 false。 這是使用 Lua 或 Angelscript 腳本語言完成的。 使用它們，開發人員可以在遊戲中獲取物件（球和球拍）並創建腳本中可用的變數（ball.position）。 而且，腳本語言比 C++ 更簡單。 它不需要完整的編譯階段，因此非常適合快速調整遊戲邏輯，並允許「非編碼人員」自行創建必要的功能。
在上面的範例中，腳本語言僅用於評估條件表達式，但也可用於操作。 例如，資料 Move Paddle Right 可以成為腳本語句 (ball.position.x += 10)。 這樣動作也可以在劇本中定義，而不需要對 Move Paddle Right 進行程式設計。
您可以更進一步，用腳本語言編寫整個決策樹。 這將是硬編碼條件語句形式的程式碼，但它們將位於外部腳本檔案中，也就是說，可以更改它們而無需重新編譯整個程式。 您通常可以在遊戲過程中編輯腳本文件，以快速測試不同的 AI 回應。
事件回應
上面的例子非常適合 Pong。 他們不斷地運行感知/思考/行動循環，並根據世界的最新狀態採取行動。 但在更複雜的遊戲中，您需要對個別事件做出反應，而不是立即評估所有事情。 在這種情況下，Pong 已經是一個壞例子了。 讓我們選擇另一個。
想像在射擊遊戲中，敵人一動也不動，直到他們發現玩家，然後他們根據自己的“專長”採取行動：有人會跑去“衝”，有人會從遠處攻擊。 它仍然是一個基本的反應系統 - “如果發現玩家，請做某事” - 但它可以在邏輯上分解為玩家看到事件和反應（選擇響應並執行它）。
這讓我們回到了感知/思考/行動循環。 我們可以編寫一個 Sense 部分來檢查每一幀 AI 是否看到玩家。 如果沒有，則不會發生任何事情，但如果它看到了，則會建立 Player Seen 事件。 該程式碼將有一個單獨的部分，其中顯示“當發生 Player Seen 事件時，執行操作”，其中是解決思考和行動部分所需的回應。 因此，您將設定對 Player Seen 事件的反應：對於「衝鋒」角色 - ChargeAndAttack，對於狙擊手 - HideAndSnipe。 可以在資料檔案中建立這些關係，以便快速編輯，而無需重新編譯。 這裡也可以使用腳本語言。
做出艱難的決定
雖然簡單的反應系統非常強大，但在許多情況下它們還不夠。 有時你需要根據代理商目前正在做的事情做出不同的決定，但很難想像這是一個條件。 有時條件太多，無法在決策樹或腳本中有效地表示它們。 有時您需要提前評估情況將如何變化，然後再決定下一步。 需要更複雜的方法來解決這些問題。
有限狀態機
有限狀態機或 FSM（有限狀態機）是一種表示我們的代理目前處於幾種可能狀態之一的方式，並且它可以從一種狀態轉換到另一種狀態。 這樣的狀態有一定數量──因此得名。 生活中最好的例子就是交通燈。 不同的地方有不同的燈光序列，但原理是相同的－每種狀態代表某種東西（停止、行走等）。 交通號誌在任何給定時間僅處於一種狀態，並根據簡單的規則從一種狀態移動到另一種狀態。
遊戲中的 NPC 也有類似的故事。 例如，讓我們來看看具有以下狀態的守衛：
- 巡邏。
- 進攻。
- 逃跑。
以及改變其狀態的這些條件：
- 如果守衛看到敵人，他就會攻擊。
- 如果守衛攻擊但不再看到敵人，他就會返回巡邏。
- 如果一名警衛發動攻擊但受了重傷，他就會逃跑。
您也可以編寫帶有守護者狀態變數和各種檢查的 if 語句：附近是否有敵人、NPC 的健康程度是多少等。讓我們加入更多狀態：
- 閒置——巡邏之間。
- 搜索 - 當發現的敵人消失時。
- 尋求幫助 - 當發現敵人但其力量太強大而無法單獨作戰時。
他們每個人的選擇都是有限的 - 例如，如果守衛的生命值較低，他就不會去尋找隱藏的敵人。
畢竟，有一大堆“如果” ， 那「可能會變得太麻煩，因此我們需要形式化一種方法，使我們能夠記住狀態和狀態之間的轉換。 為此，我們考慮所有狀態，並在每個狀態下，在清單中寫下所有到其他狀態的轉換，以及它們所需的條件。
這是一個狀態轉換表格－一種表示 FSM 的綜合方式。 讓我們畫一張圖，全面了解 NPC 行為如何改變。
該圖反映了該代理人根據當前情況做出決策的本質。 此外，如果旁邊的條件為真，每個箭頭都會顯示狀態之間的轉換。
每次更新時，我們都會檢查代理程式的當前狀態，查看轉換列表，如果滿足轉換條件，則它接受新狀態。 例如，每一幀都會檢查 10 秒定時器是否已到期，如果已到期，則警衛從空閒狀態進入巡邏狀態。 同樣，攻擊狀態會檢查代理的健康狀況 - 如果健康狀況較低，則進入逃跑狀態。
這是處理狀態之間的轉換，但是與狀態本身相關的行為又是如何呢？ 在實現特定狀態的實際行為方面，通常有兩種類型的“掛鉤”，我們可以在其中將操作指派給 FSM：
- 我們針對目前狀態定期執行的操作。
- 從一種狀態過渡到另一種狀態時我們採取的行動。
第一種類型的範例。 巡邏狀態將在每個畫面中沿著巡邏路線移動代理。 攻擊狀態將嘗試每幀發動攻擊或轉換到可能的狀態。
對於第二種類型，請考慮過渡「如果敵人可見且敵人太強大，則進入尋求幫助狀態。 代理必須選擇去哪裡尋求幫助並存儲此信息，以便“尋找幫助”狀態知道去哪裡。 一旦找到幫助，代理就會回到攻擊狀態。 此時，他將想要告訴盟友有關威脅的訊息，因此可能會發生 NotifyFriendOfThreat 操作。
我們可以再次透過感知/思考/行動循環的視角來看這個系統。 意義體現在轉換邏輯所使用的資料。 思考 - 每個狀態都可以轉換。 Act 是透過在一個狀態內或在狀態之間的轉換時定期執行的動作來執行的。
有時，連續輪詢轉換條件的成本可能很高。 例如，如果每個代理程式每幀都執行複雜的計算來確定它是否可以看到敵人並了解它是否可以從巡邏狀態轉換到攻擊狀態，這將花費大量的CPU時間。
世界狀況的重要變化可以被視為將在發生時處理的事件。 FSM 無需每幀檢查轉換條件“我的代理可以看到玩家嗎？”，而是可以配置一個單獨的系統來降低檢查頻率（例如每秒 5 次）。 結果是在檢查通過時發出 Player Seen。
該資訊被傳遞給 FSM，FSM 現在應該轉到 Player Seen 事件接收條件並做出相應回應。 除了回應之前幾乎察覺不到的延遲之外，最終的行為是相同的。 但由於將 Sense 部分分離為程式的單獨部分，性能得到了提高。
分層有限狀態機
然而，使用大型 FSM 並不總是很方便。 如果我們想要將攻擊狀態擴展為單獨的近戰攻擊和遠程攻擊，我們將必須更改導致攻擊狀態（當前和未來）的所有其他狀態的轉換。
您可能注意到，在我們的範例中存在許多重複的轉換。 大多數空閒狀態的轉換與巡邏狀態的轉換相同。 最好不要重複自己，特別是如果我們添加更多類似的狀態。 將閒置和巡邏歸類為「非戰鬥」的一般標籤是有意義的，其中只有一組常見的到戰鬥狀態的轉換。 如果我們將此標籤視為一個狀態，那麼 Idling 和 Patrolling 就會變成子狀態。 為新的非戰鬥子狀態使用單獨的轉換表的範例：
主要狀態：
脫離戰鬥狀態：
並以圖表形式：
這是相同的系統，但具有新的非戰鬥狀態，包括空閒和巡邏。 每個狀態都包含一個帶有子狀態的FSM（這些子狀態又包含它們自己的FSM - 等等，只要您需要），我們就得到了一個分層有限狀態機或HFSM（分層有限狀態機） 。 透過對非戰鬥狀態進行分組，我們刪除了一堆冗餘的轉換。 我們可以對任何具有共同轉換的新狀態執行相同的操作。 例如，如果將來我們將攻擊狀態擴展到近戰攻擊和飛彈攻擊狀態，它們將是根據與敵人的距離和彈藥可用性在彼此之間轉換的子狀態。 因此，可以用最少的重複轉換來表示複雜的行為和子行為。
行為樹
透過 HFSM，可以以簡單的方式創建複雜的行為組合。 然而，有一點困難，即以過渡規則的形式做出的決策與當前狀態密切相關。 在許多遊戲中這正是所需要的。 仔細使用狀態層次結構可以減少轉換重複次數。 但有時您需要無論您處於哪個州都適用的規則，或幾乎適用於任何州的規則。 例如，如果一個特工的生命值下降到 25%，你會希望他逃跑，無論他是在戰鬥、閒置還是說話 - 你必須將這個條件添加到每個狀態。 如果您的設計師稍後想要將低健康閾值從 25% 更改為 10%，則必須再次執行此操作。
理想情況下，這種情況需要一個系統，其中關於「處於什麼狀態」的決策是在狀態本身之外的，以便僅在一個地方進行更改而不觸及轉換條件。 行為樹出現在這裡。
實現它們的方法有多種，但本質大致相同，並且類似於決策樹：演算法從「根」節點開始，樹包含代表決策或動作的節點。 但有一些關鍵的差異：
- 節點現在會傳回三個值之一：成功（如果作業已完成）、失敗（如果無法啟動）或正在運行（如果仍在運行並且沒有最終結果）。
- 沒有更多的決策節點可以在兩個選項之間進行選擇。 相反，它們是裝飾器節點，具有一個子節點。 如果他們成功，他們就會執行他們唯一的子節點。
- 執行操作的節點傳回一個 Running 值來表示正在執行的操作。
這一小組節點可以組合起來創造大量複雜的行為。 讓我們將前面範例中的 HFSM 防護想像為行為樹：
透過這種結構，從空閒/巡邏狀態到攻擊或任何其他狀態不應有明顯的轉換。 如果敵人可見且角色的生命值較低，則執行將在「逃跑」節點處停止，無論之前執行的是哪個節點 - 巡邏、閒置、攻擊或任何其他節點。
行為樹很複雜——有很多方法可以組成它們，找到裝飾器和複合節點的正確組合可能具有挑戰性。 還有關於多久檢查一次樹的問題 - 我們想要檢查它的每個部分還是僅當其中一個條件發生變化時？ 我們如何儲存與節點相關的狀態 - 我們如何知道我們何時空閒了 10 秒，或者我們如何知道哪些節點上次執行，以便我們可以正確處理序列？
這就是為什麼有很多實現的原因。 例如，一些系統用內聯裝飾器替換了裝飾器節點。 當裝飾器條件發生變化時，它們會重新評估樹，幫助連接節點並提供定期更新。
基於實用程式的系統
有些遊戲有許多不同的機制。 希望它們能夠獲得簡單且通用的轉換規則的所有好處，但不一定以完整的行為樹的形式。 與擁有一組明確的選擇或可能的操作樹相比，檢查所有操作並選擇當前最合適的操作會更容易。
基於實用程式的系統將有助於解決此問題。 在這個系統中，代理具有多種操作，並根據每個操作的相對效用選擇要執行的操作。 其中效用是對代理執行此操作的重要性或期望程度的任意度量。
根據當前狀態和環境計算出某個動作的效用，智能體可以隨時檢查並選擇最合適的其他狀態。 這與 FSM 類似，不同之處在於轉換是由對每個潛在狀態（包括當前狀態）的估計來確定的。 請注意，我們會選擇最有用的操作繼續（如果我們已經完成，則留下）。 對於更多種類，這可以是從一個小列表中平衡但隨機的選擇。
系統分配任意範圍的效用值，例如，從 0（完全不需要）到 100（完全需要）。 每個操作都有許多影響該值計算的參數。 回到我們的監護人範例：
動作之間的轉換是不明確的－任何狀態都可以跟隨任何其他狀態。 操作優先權可在傳回的效用值中找到。 如果敵人可見，且該敵人很強，且角色的生命值較低，則 Fleeing 和 FindHelp 都會傳回較高的非零值。 在這種情況下，FindingHelp 總是會更高。 同樣，非戰鬥活動的返回值永遠不會超過 50，因此它們總是低於戰鬥活動。 在創建操作併計算其效用時需要考慮到這一點。
在我們的範例中，操作會傳回固定常數值或兩個固定值之一。 更現實的系統會傳回連續值範圍的估計值。 例如，如果代理人的生命值較低，則「逃跑」動作會回傳較高的效用值；如果敵人太強，「攻擊」動作會回傳較低的效用值。 因此，在特工認為自己沒有足夠的生命值來擊敗敵人的任何情況下，逃跑行動優先於攻擊行動。 這允許根據任意數量的標準對操作進行優先排序，從而使這種方法比行為樹或 FSM 更加靈活和可變。
每個動作都有很多程式計算的條件。 它們可以用腳本語言編寫，也可以編寫為一系列數學公式。 《模擬市民》模擬了角色的日常生活，增加了額外的計算層——代理商收到一系列影響效用評級的「動機」。 如果角色感到飢餓，隨著時間的推移，他們會變得更加飢餓，而 EatFood 動作的效用值將會增加，直到角色執行該操作，從而降低飢餓程度並將 EatFood 值返回到零。
基於評級系統選擇行動的想法非常簡單，因此基於效用的系統可以用作人工智慧決策過程的一部分，而不是完全取代它們。 決策樹可能會詢問兩個子節點的效用評級並選擇較高的一個。 類似地，行為樹可以有一個複合效用節點來評估操作的效用，以決定執行哪個子層級。
運動和導航
在前面的範例中，我們有一個可以向左或向右移動的平台，以及一個巡邏或攻擊的守衛。 但我們究竟該如何處理代理人在一段時間內的移動呢？ 當到達目的地比直線移動更困難時，我們如何設定速度，如何避開障礙物，以及如何規劃路線？ 讓我們看看這個。
Управление
在初始階段，我們假設每個智能體都有一個速度值，包括它移動的速度和方向。 它可以以米每秒、公里每小時、像素每秒等為單位進行測量。回想一下 Sense/Think/Act 循環，我們可以想像 Think 部分選擇一個速度，Act 部分將該速度應用於代理。 通常，遊戲都有一個實體系統來為您完成此任務，了解每個物件的速度值並進行調整。 因此，你可以留給人工智慧一項任務——決定代理應該有什麼速度。 如果您知道代理應該在哪裡，那麼您需要以設定的速度將其移動到正確的方向。 一個非常簡單的方程式：
desired_travel = 目的地位置 – 代理位置
想像一個 2D 世界。 智能體位於點 (-2,-2)，目的地位於東北方某處的點 (30, 20)，智能體到達那裡所需的路徑是 (32, 22)。 假設這些位置以米為單位測量 - 如果我們將代理的速度設為每秒 5 米，那麼我們將縮放位移向量並獲得大約 (4.12, 2.83) 的速度。 有了這些參數，代理將在近 8 秒內到達目的地。
您可以隨時重新計算這些值。 如果智能體已到達目標的一半，則移動長度將是一半，但由於智能體的最大速度為 5 m/s（我們在上面決定），因此速度將相同。 這也適用於移動目標，允許代理在移動時進行微小的更改。
但我們想要更多的變化 - 例如，緩慢增加速度來模擬角色從站立到奔跑的移動。 最後停止前也可以做同樣的事情。 這些功能被稱為轉向行為，每個行為都有特定的名稱：尋找、逃離、到達等。其想法是，基於將代理的位置和當前速度與目的地進行比較，可以將加速力應用於代理的速度。為了使用不同的方法來實現目標。
每個行為的目的都略有不同。 尋找和到達是將代理商移動到目的地的方法。 避障和分離調整代理的運動，以避開到達目標途中的障礙物。 一致性和凝聚力使代理人能夠齊心協力。 考慮到所有因素，可以將任意數量的不同轉向行為相加，以產生單一路徑向量。 使用「到達」、「分離」和「避障」行為來遠離牆壁和其他代理的代理。 這種方法在開放位置效果很好，沒有不必要的細節。
在更困難的條件下，添加不同的行為效果會更糟 - 例如，代理可能會因為到達和避障之間的衝突而卡在牆上。 因此，您需要考慮比簡單添加所有值更複雜的選項。 方法是這樣的：你可以考慮不同方向的移動並選擇最佳選項，而不是將每個行為的結果加起來。
然而，在一個充滿死胡同和選擇走哪條路的複雜環境中，我們將需要更先進的東西。
找路
轉向行為非常適合在開放區域（足球場或競技場）中進行簡單移動，其中從 A 到 B 是一條直線路徑，僅繞障礙物很少繞道。 對於複雜的路線，我們需要尋路，這是一種探索世界並決定穿越世界的路線的方式。
最簡單的方法是將網格應用於代理旁邊的每個方格，並評估其中哪些方格可以移動。 如果其中一個是目的地，則沿著從每個方格到前一個方格的路線，直到到達起點。 這就是路線。 否則，請對附近的其他方塊重複此過程，直到找到目的地或用完方塊（意味著沒有可能的路線）。 這就是所謂的廣度優先搜尋或 BFS（廣度優先搜尋演算法）。 每走一步，他都會向各個方向看（因此是寬度，「寬度」）。 搜尋空間就像一個波前，移動直到到達所需位置 - 搜尋空間每一步都會擴展，直到包含終點，之後可以追溯到起點。
結果，您將收到一個方塊列表，沿著這些方塊編輯所需的路線。 這就是路徑（因此稱為尋路）——代理在跟隨目的地時將訪問的地點的清單。
鑑於我們知道世界上每個方塊的位置，我們可以使用轉向行為沿著路徑移動 - 從節點 1 到節點 2，然後從節點 2 到節點 3，依此類推。 最簡單的選擇是前往下一個方塊的中心，但更好的選擇是停在當前方塊和下一個方塊之間的邊緣中間。 因此，代理商將能夠在急轉彎處走捷徑。
BFS 演算法也有缺點——它在「錯誤」方向上探索的方塊數量與在「正確」方向上探索的方塊數量一樣多。 這就是稱為 A*（A 星）的更複雜演算法發揮作用的地方。 它的工作方式相同，但不是盲目地檢查相鄰方塊（然後是鄰居的鄰居，然後是鄰居的鄰居的鄰居，等等），而是將節點收集到一個列表中並對它們進行排序，以便檢查的下一個節點始終是一條通往最短路線的路徑。 節點根據啟發式進行排序，該啟發式考慮了兩件事：到所需廣場的假設路線的“成本”（包括任何旅行成本）以及對該廣場距目的地有多遠的估計（使搜索偏向於正確的方向）。
此範例表明，智能體一次探索一個方格，每次都會選擇最有希望的相鄰方格。 生成的路徑與 BFS 相同，但在此過程中考慮的方塊更少 - 這對遊戲性能有很大影響。
無網格運動
但大多數遊戲並不是在網格上佈局的，而且通常不可能在不犧牲真實性的情況下做到這一點。 需要做出妥協。 正方形的大小應該是多少？ 太大，他們將無法正確表示小走廊或轉彎，太小，將有太多的方塊需要搜索，這最終將花費大量時間。
首先要理解的是，網格為我們提供了連接節點的圖。 A* 和 BFS 演算法實際上適用於圖，根本不關心我們的網格。 我們可以將節點放置在遊戲世界中的任何位置：只要任意兩個連接的節點之間以及起點和終點與至少一個節點之間存在連接，演算法就會像以前一樣運作。 這通常稱為航路點系統，因為每個節點代表世界上的一個重要位置，可以是任意數量的假設路徑的一部分。
範例 1：每個方格中有一個結。 搜尋從智能體所在的節點開始，到所需方格的節點結束。
範例 2：較小的一組節點（航路點）。 搜尋從代理的方格開始，經過所需數量的節點，然後繼續到達目的地。
這是一個完全靈活且功能強大的系統。 但在決定在何處以及如何放置路徑點時需要小心，否則代理可能根本看不到最近的點並且無法啟動路徑。 如果我們能夠根據世界的幾何形狀自動放置路徑點，那就更容易了。
這是導航網格或 navmesh（導航網格）出現的位置。 這通常是覆蓋在世界幾何形狀上的三角形的 2D 網格 - 無論智能體允許在哪裡行走。 網格中的每個三角形都成為圖中的一個節點，最多有三個相鄰三角形成為圖中的相鄰節點。
這張圖片是來自 Unity 引擎的範例 - 它分析了世界中的幾何形狀並創建了一個導航網格（在淺藍色的螢幕截圖中）。 導航網格中的每個多邊形都是代理可以站立或從一個多邊形移動到另一個多邊形的區域。 在此範例中，多邊形小於它們所在的樓層 - 這樣做是為了考慮代理的大小，該代理將超出其標稱位置。
我們可以再次使用 A* 演算法來搜尋穿過該網格的路線。 這將為我們提供一條幾乎完美的世界路線，它考慮了所有幾何形狀，並且不需要不必要的節點和創建航路點。
探路這個主題太廣泛，一篇文章的一節是不夠的。 如果您想更詳細地研究它，那麼這會有所幫助 .
Планирование
我們透過尋路了解到，有時僅僅選擇一個方向並移動是不夠的 - 我們必須選擇一條路線並轉幾個彎才能到達我們想要的目的地。 我們可以概括這個想法：實現目標不只是下一步，而是一個完整的序列，有時你需要向前看幾個步驟才能找出第一步應該是什麼。 這就是所謂的計劃。 尋路可以被認為是規劃的幾個擴展之一。 就我們的感知/思考/行動週期而言，這是思考部分為未來規劃多個行動部分的地方。
讓我們來看看棋盤遊戲《萬智牌》的例子。 我們首先手上有以下一組牌：
- 沼澤 - 提供 1 點黑色法力（地牌）。
- 森林 - 提供 1 點綠色法力（土地卡）。
- 逃亡巫師 - 需要 1 點藍色法力召喚。
- 精靈秘法師 - 需要 1 點綠色法力才能召喚。
我們忽略剩下的三張牌以使其更容易。 根據規則，玩家每回合允許打出一張地牌，他可以「橫置」這張牌以從中提取法力，然後根據法力的數量施展法術（包括召喚生物）。 在這種情況下，人類玩家知道要玩森林，點擊 1 個綠色法術力，然後召喚精靈秘法師。 但遊戲人工智慧如何解決這個問題呢？
輕鬆規劃
最簡單的方法是依序嘗試每個動作，直到沒有合適的動作。 透過查看牌，AI 可以了解 Swamp 可以玩什麼。 他演奏了它。 本回合還有其他行動嗎？ 它不能召喚精靈秘法師或逃亡法師，因為它們分別需要綠色和藍色法力來召喚它們，而沼澤只提供黑色法力。 而且他將不再能夠玩森林，因為他已經玩過沼澤了。 因此，遊戲AI雖然遵守了規則，但卻做得很糟糕。 可以改進。
規劃可以找到使遊戲達到所需狀態的一系列操作。 就像路徑上的每個方格都有鄰居（在尋路中）一樣，計劃中的每個動作也有鄰居或後繼者。 我們可以尋找這些動作和後續動作，直到達到所需的狀態。
在我們的例子中，期望的結果是「如果可能的話，召喚一個生物」。 在回合開始時，我們只看到遊戲規則允許的兩種可能的行動：
1.玩Swamp（結果：遊戲中的Swamp）
2.玩Forest（結果：遊戲中的Forest）
採取的每項行動都可能導致進一步的行動並關閉其他行動，這同樣取決於遊戲規則。 想像我們玩了沼澤 - 這將刪除沼澤作為下一步（我們已經玩過它），這也將刪除森林（因為根據規則，你每回合可以打一張地牌）。 在此之後，AI 會加入獲得 1 點黑色法力作為下一步，因為沒有其他選擇。 如果他繼續選擇點擊沼澤，他將收到 1 單位黑色法力，並且無法用它做任何事情。
1.玩Swamp（結果：遊戲中的Swamp）
1.1“點擊”沼澤（結果：沼澤被“點擊”，+1單位黑色法力）
沒有可用的操作 - 結束
2.玩Forest（結果：遊戲中的Forest）
行動清單很短，我們走進了死胡同。 我們在下一步中重複這個過程。 我們玩森林，打開「獲得 1 點綠色法力」動作，這又會打開第三個動作——召喚精靈秘法師。
1.玩Swamp（結果：遊戲中的Swamp）
1.1“點擊”沼澤（結果：沼澤被“點擊”，+1單位黑色法力）
沒有可用的操作 - 結束
2.玩Forest（結果：遊戲中的Forest）
2.1“點擊”森林（結果：森林被“點擊”，+1單位綠色魔法值）
2.1.1 召喚精靈秘法師（結果：精靈秘法師在場，-1 綠色法力）
沒有可用的操作 - 結束
最後，我們探索了所有可能的行動，並找到了召喚生物的計畫。
這是一個非常簡單的例子。 建議選擇最佳的計劃，而不是僅僅選擇滿足某些標準的任何計劃。 通常可以根據實施的結果或整體效益來評估潛在的計劃。 你可以為自己打出一張地牌得 1 分，召喚一個生物得 3 分。 打沼澤將是一個 1 點計劃。 玩森林→點擊森林→召喚精靈秘法師將立即獲得4分。
這就是《萬智牌》中計畫的運作方式，但同樣的邏輯也適用於其他情況。 例如，在西洋棋中移動棋子為象移動騰出空間。 或像這樣在 XCOM 中躲在牆後安全射擊。 一般來說，你明白了。
改善規劃
有時，潛在的行動太多，無法考慮每一個可能的選擇。 回到萬智牌的例子：假設在遊戲中和你的手中有幾張地牌和生物牌 - 可能的移動組合數量可能有數十種。 該問題有多種解決方案。
第一種方法是向後連結。 與其嘗試所有組合，不如從最終結果開始，嘗試找到一條直接的路線。 我們不是從樹根到特定的葉子，而是沿著相反的方向移動——從葉子到根。 這種方法更簡單、更快。
如果敵人有 1 個生命值，您可以找到「造成 1 或更多傷害」計畫。 為了實現這一目標，必須滿足許多條件：
1. 法術可以造成傷害 - 法術必須在手上。
2. 要施展法術，你需要法力。
3. 要獲得法力，您需要打出地牌。
4. 要打出地牌，您需要擁有它在手上。
另一種方法是最佳優先搜尋。 我們不會嘗試所有路徑，而是選擇最適合的一條。 大多數情況下，此方法會給出最佳計劃，而無需不必要的搜尋成本。 A* 是最佳優先搜尋的一種形式 - 從一開始就檢查最有希望的路線，它已經可以找到最佳路徑，而無需檢查其他選項。
蒙特卡羅樹搜尋是一個有趣且越來越流行的最佳優先搜尋選項。 該演算法在選擇每個後續行動時不會猜測哪些計劃比其他計劃更好，而是在每一步中隨機選擇後繼者，直到到達終點（當計劃導致勝利或失敗時）。 然後使用最終結果來增加或減少先前選項的權重。 透過連續多次重複這個過程，即使情況發生變化（如果敵人採取行動幹擾玩家），演算法也能很好地估計下一步的最佳行動是什麼。
如果沒有目標導向的行動計畫或 GOAP（目標導向的行動計畫），遊戲中的計畫故事就不完整。 這是一種廣泛使用和討論的方法，但除了一些區別細節之外，它本質上是我們之前討論的向後連結方法。 如果目標是「摧毀玩家」並且玩家位於掩體後面，則計劃可能是：用手榴彈摧毀→拿到它→扔掉它。
通常有幾個目標，每個目標都有自己的優先順序。 如果最高優先級的目標無法完成（由於玩家不可見，因此任何行動組合都不會創建「殺死玩家」計劃），AI 將回退到較低優先順序的目標。
培訓和適應
我們已經說過，遊戲人工智慧通常不使用機器學習，因為它不適合即時管理代理。 但這並不意味著你不能從這個領域借東西。 我們希望在射手中找到一個可以讓我們學習一些東西的對手。 例如，找出地圖上的最佳位置。 或者格鬥遊戲中的對手會阻止玩家常用的連擊動作，激勵他使用其他連擊動作。 因此，機器學習在這種情況下非常有用。
統計與機率
在我們討論複雜的例子之前，讓我們看看透過進行一些簡單的測量並使用它們來做出決策我們可以走多遠。 例如，即時戰略——我們如何判斷玩家在遊戲開始的幾分鐘內是否可以發動攻擊，以及準備什麼防禦？ 我們可以研究玩家過去的經驗來了解未來可能的反應。 首先，我們沒有這樣的原始數據，但我們可以收集它——每次人工智慧與人類對戰時，它都可以記錄第一次攻擊的時間。 經過幾次會話後，我們將得到玩家未來攻擊所需的平均時間。
平均值還有一個問題：如果一個玩家衝了 20 次，慢速玩了 20 次，那麼所需的值將位於中間的某個位置，這不會為我們帶來任何有用的東西。 一種解決方案是限制輸入資料 - 可以考慮最後 20 個資料。
當透過假設玩家過去的偏好在未來相同來估計某些行為的可能性時，可以使用類似的方法。 如果玩家用火球攻擊我們五次，用閃電攻擊兩次，用近戰攻擊一次，那麼很明顯他比較喜歡火球。 讓我們推斷一下使用不同武器的機率：火球=62,5%，閃電=25%，近戰=12,5%。 我們的遊戲人工智慧需要做好保護自己免受火災的準備。
另一個有趣的方法是使用樸素貝葉斯分類器來研究大量輸入資料並對情況進行分類，以便人工智慧以所需的方式做出反應。 貝葉斯分類器因其在電子郵件垃圾郵件過濾器中的使用而聞名。 他們在那裡檢查這些單詞，將它們與這些單詞之前出現的位置（是否在垃圾郵件中）進行比較，並對收到的電子郵件得出結論。 即使投入更少，我們也可以做同樣的事情。 基於AI看到的所有有用資訊（例如創建了哪些敵方單位，或者他們使用了哪些法術，或者他們研究了哪些技術），以及最終結果（戰爭還是和平，衝鋒還是防禦等） - 我們將選擇所需的人工智慧行為。
所有這些訓練方法都足夠了，但建議基於測試資料使用它們。 人工智慧將學習適應遊戲測試人員使用的不同策略。 發布後適應玩家的人工智慧可能會變得太可預測或太難擊敗。
基於價值的適應
給定我們遊戲世界的內容和規則，我們可以改變影響決策的一組值，而不是簡單地使用輸入資料。 我們這樣做：
- 讓AI收集遊戲過程中世界狀況和關鍵事件的數據（如上所述）。
- 讓我們根據這個數據改變幾個重要的值。
- 我們根據處理或評估這些值來實施我們的決策。
例如，特工在第一人稱射擊遊戲地圖上有多個房間可供選擇。 每個房間都有自己的價值，這決定了參觀的慾望。 AI會根據數值隨機選擇去哪個房間。 然後，特工會記住他在哪個房間被殺，並降低其價值（他返回那裡的機率）。 對於相反的情況也是如此 - 如果代理消滅了許多對手，那麼房間的價值就會增加。
馬可夫模型
如果我們使用收集到的資料進行預測會怎麼樣？ 如果我們記住一段時間內看到玩家所在的每個房間，我們就會預測玩家可能會去哪個房間。 透過追蹤和記錄玩家在房間中的移動（值），我們可以預測它們。
我們以三個房間為例：紅色、綠色和藍色。 還有我們在觀看比賽時記錄的觀察：
每個房間的觀察次數幾乎相等——我們仍然不知道在哪裡設置伏擊的好地方。 收集統計數據也因玩家的重生而變得複雜，這些玩家均勻地出現在整個地圖上。 但是他們出現在地圖上後進入的下一個房間的數據已經有用了。
可以看出，綠色房間適合玩家——大多數人從紅色房間搬到綠色房間，其中50%的人會繼續留在那裡。 相反，藍色的房間並不受歡迎，幾乎沒有人去，即使去了，也不會停留太久。
但數據告訴我們一些更重要的事情——當一個玩家在藍色的房間裡時，我們看到他所在的下一個房間將是紅色的，而不是綠色的。 儘管綠色房間比紅色房間更受歡迎，但如果玩家在藍色房間中，情況就會改變。 下一個狀態（即玩家將前往的房間）取決於先前的狀態（即玩家目前所在的房間）。 因為我們探索依賴關係，所以我們將比簡單地獨立計算觀測值做出更準確的預測。
根據過去狀態的資料預測未來狀態稱為馬可夫模型，此類範例（有房間）稱為馬可夫鏈。 由於模式代表連續狀態之間變化的機率，因此它們在視覺上顯示為 FSM，並帶有每個轉換周圍的機率。 之前，我們使用 FSM 來表示智能體所處的行為狀態，但這個概念可以擴展到任何狀態，無論它是否與智能體相關。 在本例中，狀態代表代理人佔用的房間：
這是一種表示狀態變化的相對可能性的簡單方法，使人工智慧具有預測下一個狀態的能力。 您可以預見未來的幾個步驟。
如果球員在綠色房間裡，那麼下次觀察他時，他有 50% 的次數會留在綠色房間裡。 但即便如此，他仍留在那裡的可能性有多高？ 不僅有可能該球員在兩次觀察後仍留在休息室，而且也有可能離開並返回。 這是考慮了新數據的新表：
它表明，經過兩次觀察後，在綠色房間中看到玩家的幾率將等於 51% - 21%，他將來自紅色房間，其中 5% 玩家將訪問他們之間的藍色房間，並且25% 的球員不會離開休息室。
該表只是一個可視化工具 - 該過程只需要在每一步乘以機率。 這意味著您可以展望遙遠的未來，但有一個警告：我們假設進入房間的機會完全取決於當前房間。 這稱為馬可夫性質 - 未來狀態僅取決於現在。 但這並不是百分百準確。 玩家可以根據其他因素改變決定：健康程度或彈藥數量。 由於我們不記錄這些值，因此我們的預測將不太準確。
N-克
格鬥遊戲和預測玩家的連擊動作的例子怎麼樣？ 相同！ 但我們將檢查構成組合攻擊的整個序列，而不是一個狀態或事件。
實現此目的的一種方法是將每個輸入（例如 Kick、Punch 或 Block）儲存在緩衝區中，並將整個緩衝區寫入為事件。 因此，玩家反覆按 Kick、Kick、Punch 來使用 SuperDeathFist 攻擊，AI 系統將所有輸入儲存在緩衝區中，並記住每一步中使用的最後三個輸入。
（粗體線是玩家發動 SuperDeathFist 攻擊的時間。）
當玩家選擇 Kick（踢），然後選擇另一個 Kick（踢）時，AI 將看到所有選項，然後注意到下一個輸入始終是 Punch（出拳）。 這將允許代理預測 SuperDeathFist 的組合動作並在可能的情況下阻止它。
這些事件序列稱為 N 元語法，其中 N 是儲存的元素數量。 在前面的範例中，它是 3-gram（三元組），這意味著：前兩個條目用於預測第三個條目。 因此，在 5-gram 中，前四個條目預測第五個條目，依此類推。
設計者需要仔細選擇 N-gram 的大小。 N 越小，需要的記憶體越少，但儲存的歷史記錄也越少。 例如，2-gram（bigram）將記錄 Kick、Kick 或 Kick、Punch，但無法儲存 Kick、Kick、Punch，因此 AI 不會對 SuperDeathFist 組合做出反應。
另一方面，更大的數字需要更多的內存，並且人工智慧將更難訓練，因為會有更多可能的選擇。 如果您有三種可能的輸入：踢、出拳或阻擋，而我們使用 10 克，那麼將有大約 60 個不同的選項。
二元模型是一個簡單的馬可夫鏈 - 每個過去狀態/當前狀態對都是一個二元模型，您可以根據第一個狀態預測第二個狀態。 3-gram 和更大的 N-gram 也可以被視為馬可夫鏈，其中所有元素（N-gram 中的最後一個除外）一起形成第一個狀態，最後一個元素形成第二個狀態。 格鬥遊戲範例顯示了從 Kick and Kick 狀態轉換到 Kick and Punch 狀態的機會。 透過將多個輸入歷史條目視為一個單元，我們實質上是將輸入序列轉換為整個狀態的一部分。 這給了我們馬可夫屬性，它允許我們使用馬可夫鏈來預測下一個輸入並猜測下一步將是什麼組合移動。
結論
我們討論了人工智慧開發中最常見的工具和方法。 我們也研究了需要使用它們的情況以及它們特別有用的情況。
這應該足以理解遊戲 AI 的基礎知識。 但是，當然，這些並不是所有方法。 不太受歡迎但同樣有效的包括：
- 最佳化演算法包括爬山演算法、梯度下降演算法和遺傳演算法
- 對抗性搜尋/調度演算法（極小極大和 alpha-beta 剪枝）
- 分類方法（感知器、神經網路和支援向量機）
- 處理代理的感知和記憶系統
- 人工智慧的架構方法（混合系統、子集架構和其他覆蓋人工智慧系統的方法）
- 動畫工具（規劃和運動協調）
- 效能因素（詳細程度、任何時間和時間切片演算法）
有關該主題的線上資源：
1.GameDev.net有 和 .
2. 包含許多與遊戲人工智慧開發相關的廣泛主題的簡報和文章。
3. 包括 GDC 人工智慧高峰會的主題，其中許多主題都是免費的。
4. 有用的資料也可以在網站上找到 .
5. 人工智慧研究員和遊戲開發者 Tommy Thompson 在 YouTube 上製作視頻 對商業遊戲中的人工智慧進行了解釋和研究。
有關該主題的書籍：
1. Game AI Pro書籍系列是解釋如何實現特定功能或如何解決特定問題的短文集合。
2.AI遊戲程式設計智慧系列是Game AI Pro系列的前身。 它包含較舊的方法，但幾乎所有方法即使在今天也是相關的。
3. 是每個想要了解人工智慧一般領域的人的基礎文本之一。 這不是一本關於遊戲開發的書——它教導人工智慧的基礎知識。
來源： www.habr.com