【正文】 絡(luò) ? 提供建立不同現(xiàn)象之間內(nèi)在因果關(guān)系的工具，并利用概率理論處理未知的和不完全的知識(shí) ? 對(duì)當(dāng)前狀態(tài)作出判斷，并決定下一步可能的動(dòng)作以及其帶來(lái)的后果 GAME AI技術(shù)簡(jiǎn)介（ 8） ? GAME AI技術(shù)的分類(lèi) ? 確定型 ? 基于領(lǐng)域固定領(lǐng)域知識(shí)，模擬簡(jiǎn)單的固定行為 ? 行為型 ? 基于行為模式來(lái)模擬智能行為 ? 戰(zhàn)術(shù)型 ? 策略模擬 ? RTS（ real time strategy） ? 其他 確定型 AI算法 ? 確定性算法指預(yù)先編入代碼當(dāng)中的可預(yù)測(cè)的行為 ? 從最簡(jiǎn)單的算法開(kāi)始 ? 例如，系統(tǒng)中有一顆小行星，以某一速度作勻速直線運(yùn)動(dòng)，它在任意時(shí)刻的位置由下列公式?jīng)Q定： ? 某種程度上，它們是智能的，但是這種智能是確定的，可預(yù)測(cè)的 Tracking/Chasing AI ? 當(dāng)智能體找到目標(biāo)后，一心一意向其移動(dòng)，而不考慮任何其他的因素，例如障礙物、另外的目標(biāo)等 ? 非常機(jī)械化 ? 在每一幀中，智能體計(jì)算其到目標(biāo)的前進(jìn)方向，并根據(jù)其速度，前進(jìn)一段距離 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 Tracking/Chasing算法 ? Tracking算法還可以做的更為真實(shí)一點(diǎn)，就像紅外導(dǎo)彈一樣： ? 在每一幀中，智能體仍然首先計(jì)算其到目標(biāo)的前進(jìn)方向 ? 這時(shí)，智能體的速度允許發(fā)生變化，并根據(jù)更新后的速度，計(jì)算下一幀的位置 ? 速度有一個(gè)上限，超過(guò)這個(gè)上限，智能體的速度將減慢，直到重新加速為止 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 Evading算法 ? 與前面的 chasing算法基本相同，唯一區(qū)別是智能體沿著遠(yuǎn)離物體的方向移動(dòng) 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 追逐行為的模擬示例 ? 你追我趕 Game AI/chasing and avoiding demo 基于行為模式的 AI ? 在任一時(shí)間點(diǎn)，每一個(gè)智能體都按照預(yù)先設(shè)定的某種模式運(yùn)動(dòng) ? 決策系統(tǒng)根據(jù)系統(tǒng)當(dāng)前的狀態(tài)，為每一個(gè)智能體從模式集合中選擇適當(dāng)?shù)哪Ｊ? ? 模式描述了智能體將在下面幾幀中所采取的一系列動(dòng)作 ? 特例： scripted AI，當(dāng)系統(tǒng)到達(dá)某一特定狀態(tài)（例如，每個(gè)回合的結(jié)束），系統(tǒng)運(yùn)行的一段程序（用腳本寫(xiě)），決定系統(tǒng)下一步的動(dòng)作 典型的行為模式 ? 基本模式 ? 用一段指令定義模式 ? 寫(xiě)一個(gè)解釋器解釋這段指令，并用于控制智能體的行為 ? 條件邏輯模式 ? 更為靈活的控制 ? 可以通過(guò)條件邏輯選擇模式 ? 也可以選擇本身帶有條件邏輯轉(zhuǎn)移的模式 編程技巧 ? 非常直觀 ? Pattern是一列數(shù)組 ? 數(shù)組的每一項(xiàng)定義智能體在該幀的速度（方向＋大小） ? 在模擬過(guò)程中，智能體就按照預(yù)先設(shè)定的參數(shù)在每一幀之間運(yùn)動(dòng) ? 當(dāng)移動(dòng)到數(shù)組末尾時(shí)，重新選擇一個(gè)新的模式 行為型的 AI技術(shù)示例 ? Chasing behavior AI demo 策略性 AI與通用問(wèn)題求解 ? AI的研究人員試圖尋找一個(gè)通用的計(jì)算模型和方法，解決所有的問(wèn)題 ? 感知輸入系統(tǒng) ? 有一個(gè)記憶模擬存儲(chǔ)系統(tǒng) ? 推理機(jī) ? 行為輸出系統(tǒng) ? 博弈問(wèn)題 ? 有限狀態(tài)機(jī)（ FSM） ? 規(guī)劃和搜索 有限狀態(tài)機(jī) ? 狀態(tài)（要采取的行為） ? 追擊 ? 隨機(jī)走動(dòng) ? 巡邏 ? 吃 ? 轉(zhuǎn)移（發(fā)生轉(zhuǎn)移的原因） ? 時(shí)間片結(jié)束 ? 發(fā)生某個(gè)時(shí)間 ? 完成某個(gè)行為 伐木 將木頭運(yùn)往最近的倉(cāng)庫(kù) 足夠多木材 放下木頭 : 返回林場(chǎng) 到倉(cāng)庫(kù) 到林場(chǎng) 有限狀態(tài)機(jī) ? 機(jī)器 ? 所有部件的總稱(chēng) ? 狀態(tài) ? 對(duì)于層次有限狀態(tài)機(jī)而言，狀態(tài)包括各種子狀態(tài) ? 轉(zhuǎn)移 ? 系統(tǒng)從當(dāng)前活動(dòng)狀態(tài)出發(fā)，判斷下一個(gè)活動(dòng)狀態(tài)，改變系統(tǒng)當(dāng)前的格局，并執(zhí)行相應(yīng)的操作 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 有限狀態(tài)機(jī) ? 條件 ? 定義發(fā)生轉(zhuǎn)移的先決條件 ? 輸入和事件 ? 允許狀態(tài)機(jī)對(duì)環(huán)境變化作出反應(yīng) ? 動(dòng)作 ? 作為狀態(tài)的一部分，或者伴隨轉(zhuǎn)移出現(xiàn) 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 狀態(tài)空間圖 ? 有向圖 ? 每個(gè)結(jié)點(diǎn)表示系統(tǒng)狀態(tài)模型，每條弧表示狀態(tài)轉(zhuǎn)移所伴隨的動(dòng)作行為 ? 結(jié)點(diǎn)可以是無(wú)窮多個(gè) ? 有些結(jié)點(diǎn)之間可能沒(méi)有弧相連接 特定狀態(tài)的查找 ? 結(jié)點(diǎn) － 包含查找目標(biāo) ? 終點(diǎn) － 搜索路徑的結(jié)束 ? 查找空間 － 所有結(jié)點(diǎn)的集合 ? 目標(biāo) － 所要到達(dá)的結(jié)點(diǎn) ? 經(jīng)驗(yàn) － 在一定程度上提示下一步搜索的方向 ? 解答路徑 － 從起始結(jié)點(diǎn)開(kāi)始，到目標(biāo)的一條有向路徑 模糊的有限狀態(tài)機(jī) ? 將模糊邏輯和有限狀態(tài)機(jī)結(jié)合 ? 狀態(tài)之間的遷移不再是確定的 ? 同時(shí)有多個(gè)狀態(tài) 有限狀態(tài)機(jī)和模糊的有限狀態(tài)機(jī)示例 ? FSM/FuFSM ? 代碼示例 ? 隸屬度 ? 演示 規(guī)劃 Part of intelligence is the ability to plan Move to a goal State ? 將系統(tǒng)表示成一系列狀態(tài)的集合 ? 通過(guò)操作（ Operator）改變狀態(tài) 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 路徑規(guī)劃 ? 狀態(tài) ? 智能體在空間的位置 ? 其他離散空間 ? 體素 ? 室內(nèi)位置 ? 局部區(qū)塊（ tile） ? 操作 ? 從一個(gè)位置移動(dòng)到其他位置 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 路徑規(guī)劃算法 ? 必須對(duì)狀態(tài)空間進(jìn)行搜索，才能轉(zhuǎn)移至目標(biāo)狀態(tài) ? 完全性 ? 如果目標(biāo)狀態(tài)存在，算法是否能夠?qū)⑵湔业剑? ? 時(shí)間復(fù)雜度 ? 空間復(fù)雜度 ? 能夠找到最優(yōu)解 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 搜索策略 ? 如何評(píng)價(jià)搜索算法 ? 時(shí)間：多長(zhǎng)時(shí)間能夠找到解 ? 找到的解是最優(yōu)、次優(yōu)還是其他 ? 盲目搜索 ? 沒(méi)有先驗(yàn)知識(shí) ? 僅僅知道目標(biāo)狀態(tài)是什么 ? 經(jīng)驗(yàn)搜索 ? 用經(jīng)驗(yàn)公式表示擁有的先驗(yàn)知識(shí) ? “ 經(jīng)驗(yàn) ” 只能作相對(duì)簡(jiǎn)單、低級(jí)的決策 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 廣度優(yōu)先搜索 ? 根結(jié)點(diǎn) 兒子結(jié)點(diǎn) 孫子結(jié)點(diǎn) ? 缺點(diǎn)：內(nèi)存消耗大 浙江大學(xué) CADCG 國(guó)家重點(diǎn)實(shí)驗(yàn)室 Root Root Child1 Child2