動畫與遊戲設計 Data structure and artificial intelligent

Presentation on theme: "動畫與遊戲設計 Data structure and artificial intelligent"— Presentation transcript:

1 動畫與遊戲設計 Data structure and artificial intelligent
程于芳 老師

2 架構 6.1.1演算法 6.1.2線性串列 6.2.1堆疊 6.2.2佇列 6.3.1單向鏈結串列 6.3.2環狀鏈結串列
6.3.3雙向鏈結串列

3 資料結構簡介

4 資料結構簡介 資料結構(Data Structure:DS)為資料和程式結構的研究科學 在程設領域要求上，通常以執行速度為標準

5 演算法(Algorithm) 程式或專案是否能清楚而正確的解決問題，取決於演算法
遊戲Programmer要用最佳演算法以避免浪費與處理重複執行的部分 演算法的5個原則 1.有限性: 必須在有限的步驟內解決問題，不能無限制地執行 2.有效性: 每個步驟必須非常清楚，利用紙筆就能追蹤，在有限時間內就能達 成效果 3.明確性: 每個步驟必須清楚，不可含糊 4.輸入資料 外界要提供≧0個input 5.輸出資料 要產生≧1個output

6 五個原則例子 Algorithm GCD(m,n) procedure{ r<-m%n while r!=0 do m<-n
n<-r return n } 我們以逐步追蹤法（stepwise trace）一步一步執行敘述，來驗證這些敘述是否符合演算法的特性： 1. A=18, B=12 2. R=(18 MOD 12)=6 3. R≠0 4. A=12, B=6 5. R=(12 MOD 6)=0 6. R=0 7. B 即為GCD(GCD=6) 因此它符合明確性，能夠讓我們以紙筆來計算，並且不造成混淆。如果輸入改為： l. A=12, B=18 2. R=(l2 MOD 18)=12 4. A=18,B=l2 從第5 步開始又和前面的執行順序一樣。所以我們知道，只要A,B 是自然數（不為0）， 都能正確地執行下去，所以符合正確性。很明顯的，它也符合有限性和結果的描述與輸出

7 線性串列 如C++中的陣列就為一種線性串列 同一有序串列中每個元素必須為相同型態 (0,1,2,3,4,5,6,7,8,9) ex
口語化定義: 1.有序串列可以為null，或寫成(a1,a2,a3….an-1,an) 2.存在唯一第一個元素a1與存在唯一最後一個元素an 3.除了第一個元素a1外，每一個元素都有唯一的先行者，如,ai的先行者為ai-1 4.除最後一個元素an外，每一個元素都有唯一的後續者，如ai+1是ai的後續者 ex

8 堆疊與佇列

9 堆疊與佇列 堆疊和佇列為相當典型的抽象資料型態，主要特性是一群相同資料型態的集合 遊戲實做中常會用到這兩種資料結構來處理大量的資料

10 堆疊(stack) 為一群相同資料型態的組合，具資料先進後出(LIFO :Last in First Out)的特性 有五種工作定義
create 建立一個空堆疊 push 存放頂端資料，並傳回新堆疊 pop 刪除頂端資料，並傳回新堆疊 empty 判斷堆疊是否為空，是傳true，否傳false full 判斷是否已滿，是傳true，否傳false

11 堆疊(stack) push ：將資料存入堆疊。 pop ：將資料從堆疊中取出。
#define MaxSize /* 堆疊大小 */ int stack[MaxSize]; /* 全域陣列、堆疊 */ int sp=0; /* 全域變數、堆疊指標 */ 【push 的演算法】 push(int n) { if (sp<MaxSize) stack[sp]=n; sp++; return 0; } else return -1; 【pop 的演算法】 pop( ) { int k; if (sp>0) sp--; k=stack[sp]; return k;

12 佇列(queue) 資料先進先出的模式FIFO( First in First out)，加入和刪除發生在不同端，加入發生在尾端，刪除發生在前端 有五種工作定義 create 建立空佇列 add 將新資料加入尾端 delete 刪除前端的資料 front 傳回前端的值 empty 判斷是否為空，是傳true，否傳false

13 佇列(queue) inqueue ：將資料存入佇列中。 dequeue ：將資料從佇列中取出。
 #define MaxSize /* 佇列大小 */ int queue[MaxSize]; /* 全域陣列、佇列 */ int head=0; /* 全域變數、指向開頭資料的指標 */ int tail=0; /* 全域變數、指向尾端資料的指標 */ 【inqueue 的演算法】 inqueue(n) { if ((tail+1) % MaxSize != head) queue[tail] = n; tail++; tail = tail % MaxSize; return 0; } else return -1; 【dequeue 的演算法】 dequeue(int *n) if (tail != head) *n = queue[head]; head++; head = head % MaxSize;

14 鏈結串列(linked list)

15 鏈結串列(linked list) 由許多相同型態的項目，所組成的線性有序序列 有新資料加入就向系統要空間，資料刪除後，就把空間還給系統
以下介紹不同的類型簡介

16 單向串列鏈結 基本組成要件為node，在單向串列鏈結中第一個節點是串列指標首，最後一個是串列指標尾

17 環狀鏈結串列 而環狀連結串列跟單向連結串列僅有唯一不同點，就是環狀連結串列的最後一個節點指標指向的是第一個節點，好處為能從任一節點來追蹤其他節點

18 雙向鏈結串列 基本結構和單向鏈結串列類似，至少有一欄位存放資料。但有兩個欄位存放指標，其中一個指標指向後面的節點，另一個指向前面節點

19 樹狀(tree)結構

20 樹狀(tree)結構 為相當重要的非線性資料結構 如大型遊戲會用二元空間分割樹，四元樹，八元樹來分割場景資料 架構 6.4.1樹
6.4.2二元樹 6.4.3二元排序樹 6.4.4AVL TREE 6.4.5二元樹的走訪 6.4.6二元空間分割樹 6.4.7四元樹與八元樹

21 樹 串列(List)為線性之資料結構，而樹為非線性之資料結構，資料與資料之間藉由分支(Branch)組成階層式(Hierarchical)之關係。 樹之基本定義：樹狀結構為一個或多個節點所構成之有限集合，且 1. 有一個特定節點稱為樹根 (Root) 2. 其餘節點為分成n個獨立之集合，其中各個集合為一樹狀結構，而稱為樹根 (Root) 之子樹 (Sub-tree)

22 二元樹 最多只能有兩個子節點

23 二元搜尋樹 定義如下: 1.第一個輸入資料當作ROOT 2.小於ROOT的放左子樹，大於的放右子樹

24 二元搜尋樹 7 13 4 15 5 8 1 11 2 9 12

25 AVL樹(二元平衡樹) AVL樹也是一棵二元搜尋樹，當資料插入二元搜尋樹或自二元搜尋樹刪除資料時均要檢查二元樹是否平衡，如非平衡狀態就須設法將之調整為平衡狀態 AVL樹規定每一個節點上均記錄著該節點的平衡因子，平衡因子為左子樹之高度減右子樹之高度，當一個二元搜尋樹的每一個節點之平衡因子皆屬於-1、0、或1三者之一時即為AVL樹 分為四種型式

26 LL和LR 1.LL 2.LR 50 40 調整 1 40 30 50 不是一棵AVL-tree 30

27 RR和RL 1.RR 2.RL -2 調整 60 50 -1 50 70 60 70 不是一棵AVL-tree

28 樹的走訪 中序追蹤(Inorder Traversal):BAC
中序追蹤法是依左子樹，樹根節點，右子樹之順序來拜訪每一個節點，亦即以LDR之順序 後序追蹤(Postorder Traversal):BCA 由於我們規定先左子樹再右子樹，因此後序追蹤之次序為左子樹，右子樹，最後才是樹根節點   前序追蹤 (Preorder Traversal):ABC 拜訪節點之次序是樹根節點，左子樹，最後才是右子樹。

29 樹的走訪 7 4 16 5 8 1 11 2 9 12 15

30 二元空間分割樹 二元空間分割樹， Binary Space Partitioning Tree是一種空間分割的方法，簡稱「BSP Tree」。通常被使用在平面繪圖 BSP Tree在一開始將資料檔讀進來的時候，就將整個資料檔中的數據（即是牆的數值）先建成一個二元樹的資料結構。如下圖所示： 每個物體的多邊形當成一個平面，每個平面會有正反兩個面，就可把場景分為兩部分，每個平面都會有正反兩個面，再從這分出的兩部分各別再以同樣的方式細分。 所以當地形資料被讀進來時，BSP樹也會同時被建立

31 二元空間分割樹 例:雷神之鎚系列就是這種分式開發
通常， BSP 用來處理遊戲中室內場景模型的切割，不僅用來加速位於視錐中物體的搜尋，也可加速場景中的碰撞處理 例:雷神之鎚系列就是這種分式開發

32 四元樹 樹的每個節點擁有4個子節點，許多遊戲場景的地面就是用四元樹來做地劃分，以遞迴方式，軸心一致的將地形依四個象限分成4個子區域
四元樹示意圖

33 四元樹範例 一般來說，四元樹在2D平面與碰撞偵測相當有用，右圖可能對應的3D圖形，分割方式是以地面上的斜率(利用平面法向量來比較)做為依據
地形與四元樹的對應關係

34 八元樹 八元樹（octree）是一種用於描述三位空間的樹狀資料結構。八叉樹的每個節點表示一個正方體的體積元素，每個節點有八個子節點，這八個子節點所表示的體積元素加在一起就等於父節點的體積。通常用在3d空間的場景管理

35 八元樹演算法 建立八元樹的演算法如下： 1. 設定最大容量，即每個立方體最多只能裝多少單位元素(在電腦圖學中，單位元素就是一個三角型)
2. 找出場景的最大尺寸，並以此尺寸建立第一個立方體 3. 依序將單位元素丟入能被包含且沒有子節點的立方體 4. 若該立方體達到最大容量，就進行細分八等份，再將該立方體所裝的單位元素全部分擔給八個子立方體 5. 若發現子立方體所分配到的單位元素數量不為零且跟父立方體是一樣的，則該子立方體停止細分，因為跟據空間分割理論，細分的空間所得到的分配必定較少，若是一樣數目，則再怎麼切數目還是一樣，會造成無窮切割的情形。 6. 重覆3，直到所有單位元素都處理完畢。

36 八元樹演算法

37 圖形結構

38 圖形結構 討論兩個頂點之間是否相連與否關係 在遊戲中應用相當廣泛，包含人物的通行和路徑長短等 架構 6.5.1圖形的定義
6.5.2MST擴張樹 6.5.3路徑演算法的應用

39 圖形定義 圖形 G 包含兩個集合：一個是由頂點 ( vertices ) 所形成的有限的非空集合，另一個是由邊 ( edges ) 所形成有限非空集合 種類： 無向圖形 ( undirected  graph ) ：表示任一邊的兩個頂點是沒有方向性的。 　　 有向圖形 ( directed graph ) ：表示任一邊的兩個頂點是有方向性的。

40 MST擴張樹 如果圖形的每一個邊上含有權重 (Weight) 就形成具有實際意義的網路 (Network)。
權重可代表兩節點間以邊相連所須的花費 (Cost)，花費可能是指兩節點 (或城市) 間的實際距離，或連接兩節點之經費，或完成某一工作所須之工時。 網路的花費最少擴張樹 (Minimum Cost Spanning Tree) 就是網路中加權總值最少的擴張樹並不一定是任兩項點間的花費都是最少。 以下介紹Prim‘s 的Geedy Algorithm，來取得無向流通圖形的最小花費樹

41 Greedy Algorithm 含有權重圖形G=(V , E) ，設V={1,2,…,n}，P氏法 從集合U={1}起點開始擴張，每次從集合尋找最短 (少) 的邊 (u , v)，其中使得U和E相連，然後再將v 加入U，重覆上述到U=V為止。

42 Greedy Algorithm

43 路徑演算法的應用 為圖型應用的一種，在遊戲中相當重要 逼近法:以目前的座標漸朝目的座標移動，常用於沒有障礙物的環境
路徑1:先對Y軸逼近，再對X軸逼近 路徑2:先對X軸逼近，再對Y軸逼近 路徑3:比較X與Y的距離比例，由差異值最高的軸向最先逼近，

44 路徑演算法的應用 下圖中，在第14步時逼近法就已經失效了，不管是X軸或是Y軸都沒辦法照原來演算式計算
由此可知，逼近法只是計算路徑的簡單工具，無法應付複雜地形

45 搜尋與排序

46 搜尋與排序 排序即將一群資料造某特定規則重新排列，使具有遞增或遞減關係 遊戲中常會用到排序技巧 搜尋為從檔案中找出符合特定條件的紀錄 架構
6.6.1氣泡排序法 6.6.2二分搜尋法 6.6.3雜湊搜尋法

47 氣泡排序法 氣泡排序法(Bubble Sort) 將N筆記錄(編號0至N-1)按鍵值不遞減次序排序的氣泡排序法
為止。 2.比較陣列中相鄰兩元素之鍵值，若前面元素大於後面元素， 則立刻將兩元素值交換。 3. 每一回合會使其底層增加一個完全正確排序的元素。

48 二分搜尋法 二元搜尋法是在已排序完成的串列中搜尋某一個搜尋值，搜尋 方法是取中間值與搜尋值比對，若搜尋值較大，則捨棄小於中 間值的所有串列值(或中間值的左半部串列之值)，若搜尋值較 小，則捨棄大於中間值的所有串列值(或中間值的右半部串列 之值)，其次，再從剩餘的串列中取中間值與搜尋值比對，…， 如此下去，直到找到搜尋值為止 。

49 二分搜尋法 欲搜尋值為45 第一次比對： 中間值為a[(10+0)/2]=a[5]=36，因45大於36， 取大於36的串列。

50 雜湊搜尋法 雜湊搜尋法是將資料經過一個已經設計好的函數，將鍵值轉換成儲存位址，然後依搜尋鍵值所放的儲存位址，去尋找所要搜尋的值，即可尋找到搜尋值

51 人工智慧

52 人工智慧 人工智慧就是由電腦模擬或執行，具有類似人類智慧或思考的行為，如推理，規畫..等等 一些決策遊戲的人工智慧更是下足了功夫
6.7.1遊戲與人工智慧 6.7.2有限狀態機 6.7.3模糊邏輯 6.7.4基因演算法 6.7.5類神經網路 6.7.6決策樹

53 遊戲與人工智慧 通常有4種模式 1.以規則為基礎:如戰鬥遊戲(if…then…else) 2.以目標為基礎:會定義出角色目標和答案目標的方法
3.以代理人為基礎:代理人是遊戲中的虛擬人物，遊戲中會賦與代理人生命，給他們思考能力 4.以人工生命為基礎:所為人工生命是結合了生物學，演化理論等概念，讓NPC(Non-Player Character)具有反應、特色及合理行為

54 有限狀態機(FSM) 在有限的狀態集合中，從一開始的初始狀態，以及其他狀態間，可經由不同轉換函式轉變到另一狀態，轉換函式相當於各個狀態之間關係 包含兩樣要素: 1.代表AI的有限狀態機器 2.輸入條件，會由目前狀態轉換到另一狀態 通常FSM會依據狀態轉移函式來決定輸出狀態，並將目前狀態轉移為輸出狀態 例如下圖為利用FMS撰寫魔鬼海盜船在大海中追逐玩家的程式

55 有限狀態機(FSM) 一個簡易的有限狀態機 被玩家擊沉 指派任務 玩家死亡 被玩家擊沉 被玩家擊沉 看見玩家 重新指派 死亡 目地 戰鬥

56 有限狀態機(FSM) 在上圖中，魔鬼海盜船的主要任務是接受任務指派和前往目的地。所以魔鬼海盜船的第一種狀態是前往目的，另一種可能是出門後馬上被玩家擊沉，變成死亡狀態。如果遊戲進行中碰到玩家，就必須與玩家交戰，或者沒有看到玩家，就重新接受任務的指派。其他情形就是得戰勝玩家，才能獲得新的任務指派，如果沒有戰勝玩家，就會面臨死亡狀態

57 有限狀態機(加入子系統) 當程式設計師為了讓簡易有限狀態機擴大規模，提出平行處理的自動方式。將複雜行為區分為不同子系統或是階層。
例如要在魔鬼海盜船中加入射擊動作，面對玩家才會進入射擊狀態，以下圖表示 完成 射程內 沒有火藥 射程外 補充能量 射擊 閒置

58 模糊邏輯(Fuzzy Logic) 模仿人類思考方式，將研究對象以0到1之間的數值來表示模糊概念的程度
遊戲中可加入模糊邏輯的概念，讓NPC具有不可預測的AI行為，並對true和false間的模糊地帶做回應。

59 模糊邏輯(Fuzzy Logic) 例如: 魔鬼海盜船和玩家即使距離1.95公里，如果在2公里遇見玩家必須和玩家戰鬥，
此處就將2公里定義為距離很近，至於魔鬼海盜船與玩家相距1公里就定義為非常接近。假如魔鬼海盜船玩家相距1.98公里，若以布林值來處理，應該為危險區域範圍外，但不符合實際狀況，因為明明就快交戰了。所以依照實際狀況來傳回0~1之間的數值，利用歸屬度函數來表達模糊集合內的狀況。如果0表示不危險，1表示危險，而0.5表示有點危險。此時就能利用下圖定義一個危險區域的模糊集合:

60 模糊邏輯(Fuzzy Logic) 模糊規則： 如果與玩家相距3公里，表示距離遠，為警戒區域，快速離開。
如果與玩家相距2公里，表示距離近，為危險區域，維持速度。 如果與玩家相距1公里，表示距離很近，為戰鬥區域，減速慢行。 由於每條規則都會執行運算，並輸出歸屬程度，當將每個變數輸入後， 可能會得到以下結果: 變數輸入結果：提高戒護的歸屬程度0.3 變數輸入結果：開啟防護的歸屬程度0.7 變數輸入結果：全員備戰的歸屬程度0.4 if(非常近 AND 危險區域) AND NOT武器填裝 then 提高戒備 if(很近 AND 戰鬥區域) AND NOT火力全開 then 開啟防護 if(NOT 近 AND 警戒區域) OR (NOT 保持不變) then 全員備戰

61 基因演算法(Genetic Algorithm)
在真實世界裡，物種的演化是為了更適應大自然，而在演化過程中，某個基因的改變也能讓下一代繼承 例如遊戲中行走中的人物可用基因演算法，把重力和人物的肌肉結構都做好關聯後，讓人物走得非常自然 基本上來說，人工智慧是一種特殊的搜尋技巧，適合處理多變數和非線性的問題 如在遊戲中，玩家可以挑選自己喜歡的角色來扮演，不同的角色有不同的特質和挑戰性，設計師無法事先預告或了解玩家打算扮演的角色。這時為了回應不同的架構，可將某個場景分配給某個染色體，利用不同的染色體來儲存每種狀況的回應

62 類神經網路(Artifical Neural Network)
模仿生物神經網路的數學模式，使用大量而相連的人工神經原來模擬生物神經細胞受特定程度刺激來反應刺激的架構為基礎的研究 透過訓練方式，讓類神經網路反覆學習，經過一段時間的經驗值，才能有效將學習產生初步運作的模式 如在遊戲中，當主角不斷學習和經過關卡考驗，功力自然大增

63 決策樹(Decision Tree) 如在紙牌或象棋遊戲中，如何出下一張牌或是下一步棋
決策型人工智慧是一項挑戰，例如如何在所有可能狀況下選擇對自己最有利的一步棋 決策型人工智慧的基礎是搜尋，在所有狀況下，搜尋獲勝的方法

64 決策樹(Decision Tree)

65 決策樹(Decision Tree) 程式碼： Int win [ ] [ ] = new int [8] [3] ;
… //類推下去

66 移動型遊戲AI專題研究

67 架構 6.8.1追逐移動 6.8.2躲避移動 6.8.3移動模式

68 追逐移動 為了豐富遊戲內容，必須適時加入躲避和追逐等動作來改變角色的行為
如怪物追逐玩家的例子，做法是每次在進行視窗貼圖時，將怪物的所在座標與玩交角色的所在目標做比較，遞增或是遞減怪物的座標，使怪物每次進行貼圖時，漸漸朝玩家方向逼近，產生追逐行動的效果 if(怪物x>玩家x) 怪物x- -; else 怪物x++; if(怪物y>玩家y) 怪物y- - 怪物y++

69 追逐移動 以怪物HP為程式對象 If (怪物HP>200) //生命值大於 200 時才追 {
p = rand( )% //取亂數除以3的餘數 if(p!=1) //餘數不為1時進行追逐 if(怪物x>玩家x) 怪物x--; else 怪物x++; if(怪物y>玩家y) 怪物y-- 怪物y++ } Else 怪物HP+=5 ; //怪物不動，休息補血

70 一架飛機於循環背景上移動，另外加入三隻追逐飛機移動的小鳥的部份程式碼：
01 …………………………… 02 if(now x < x) { now x += 10; if(now x > x) now x = x; } else { now x -=10; if(now x < x) now x = x } 14 if(now y > y) { now y += 10; if(now y > y) now y = y; } else { now y -= 10; if(now y < y) now y = y }

71 27 …………….. 28 …………….. 29 for(i=0;i<3;i++) { if(rand()%3 != 1) { if(p[i] . Y > nowy-16) p[i] . Y -= 5; else p[i] . x += 5; 38 if(p[i] . x > nowx-25) p[i] . x -= 5; else p[i] . x += 5; } 44 45 if(p[i] . X > now x-25) { 47 BitBlt(mdc , p[i] . X , p[i] . Y , 61 , 61 , bufdc , 61 , 61 , SRCAND); 48 BitBlt(mdc , p[i] . X , p[i] . Y , 61 , 61 , bufdc , 61 , 61 , SRCPAINT); } else { 52 BitBlt(mdc , p[i] . X , p[i] . Y , 61 , 61 , bufdc , 61 , 0 , SRCAND); 53 BitBlt(mdc , p[i] . X , p[i] . Y , 61 , 61 , bufdc , 61 , 0 , SRCPAINT); } } 56 …………......

72

73 躲避移動 躲避移動目地為遠離目標 判斷式與追逐移動相同，不過每次重設怪物的貼圖目標時，則是會越來越遠離玩家的所在位置
if(怪物x>玩家x) 怪物x++; else 怪物x--; if(怪物y>玩家y) 怪物y++ 怪物y--

74 移動模式 遊戲開發人員在設計時，替角色定義出一組關的移動模式，機中包含多種移動方式，如追逐，躲避，隨機，固定移動。而角色會隨著遊戲情節而地翊不同的移動方式來進行移動，這便屬於模式移動

75 移動模式 RPG遊戲中的怪物有幾種行為1.普通攻擊2.施放魔法攻擊3.使盡全力攻擊4.補血5.逃跑
01 if(生命值>20) //生命值大於20 02 { if(rand()%10 != 1) //進行普通攻擊的機率9/10 普通攻擊 ; else 施放攻擊魔法 ; 07 } 08 else 09 { switch(rand()%5) { case 0: 普通攻擊 ; break ; case 1: 施放魔法攻擊 break ; case 2: 使盡全力攻擊 break ; case 3: 補血 ; break ; case 4: 逃跑 ; if(rand()%3 == 1) //逃跑成功機率為1/3 逃跑成功 ; else 逃跑失敗 ; break ; } 32 }

76 移動模式

77 移動模式

78 移動模式

79 移動模式

80 Thank You !