班級：四技系統三甲 組員： 葉家宏 黃致中 指導老師：黎靖

Presentation on theme: "班級：四技系統三甲 組員： 葉家宏 黃致中 指導老師：黎靖"— Presentation transcript:

1 班級：四技系統三甲 組員：49839033葉家宏 49839056黃致中 指導老師：黎靖
電腦鼠的迷宮演算法 班級：四技系統三甲 組員： 葉家宏 黃致中 指導老師：黎靖

2 摘要 區域性演算法 全域性演算法 又分為洪水演算法、A*演算法。
如果把電腦鼠比喻成人來看，那硬體就是四肢，而軟體就相當於電腦鼠的大腦。在此報告中討論兩種路徑演算，兩種皆可再細分很多種演算法。 區域性演算法 又分為右手法則、左手法則、中左法則、中右法則、向心法則。 全域性演算法 又分為洪水演算法、A*演算法。

3 區域性演算法 應用在探索迷宮的階段。 由於迷宮狀態未知，因此只能根據目前電腦鼠週遭的環境，試著尋找到達終點的路徑。
演算法有左手法則、右手法則、中左法則、中右法則及向心法則等。

4 全域性演算法 應用在已經部份或完全探索迷宮後，此時可以根據已探索的迷宮資料找到起點至終點的最短路徑。
演算法則有洪水填充法(Flood-Fill algorithm)及A*演算法與其諸多的變形演算法等。

5 選擇你想搜尋的演算法 右手法則 左手法則 區域性演算法 中左法則 中右法則 向心法則 全域性演算法 洪水填充法 A*演算法

6 右手法則 電腦鼠遇到岔路時，以右手為優先，其次直線、左手。

7 右手法則-迷宮範例

8 左手法則 電腦鼠遇到岔路時，以左手為優先，其次直線、右手。

9 左手法則-迷宮範例

10 中左法則 電腦鼠遇到岔路會以直線優先，其次左手，最後右手。

11 中左法則-迷宮範例

12 中右法則 電腦鼠遇到岔路會以直線優先，其次右手，最後左手。

13 中右法則-迷宮範例

14 向心法則 向心法則要先畫出其迷宮的座標，然後在遇到岔路時，依目前位置與中心點之間的距離來判斷下一步，再依向心權位值小的格子前進(中心點為0)

15 洪水演算法 洪水演算法是一種以距離為主的迷宮演算法，由終點開始填洪水值，先被洪水流過的方格其洪水值肯定比較晚流過之方格的洪水值小，所以依洪水值大小，由大到小即可找出最短路徑

16 A*演算法(1/15) G代表走到鄰近節點的移動代價。 H代表從所選的相鄰節點到終點的移動代價 路徑評估的公式F = G + H。
最廣泛被大家使用的演算法，用於一般的RPG遊戲、或是大型的戰略遊戲 A*演算法重點在於開啟列表及關閉列表的使用。 路徑評估的公式F = G + H。 G代表走到鄰近節點的移動代價。 H代表從所選的相鄰節點到終點的移動代價

17 A*演算法(2/15) 深綠色(A3) → 起始節點 粉紅色(E7) → 終點節點 棕色 → 父節點 藍色 → 設定為障礙物
棕色 → 父節點 藍色 → 設定為障礙物 青綠色 → 列入開啟列表 紫色 → 列入關閉列表 圖1

18 A*演算法(3/15) 將A3設定為父節點，並將鄰近節點(青綠色部分)列入開啟列表中，計算出節點的F值。
並將其各點指向父節點如圖2。 A2 → G=10 H=9*10 F=100 A4 → G=10 H=7*10 F=80 B2 → G=14 H=8*10 F=94 B3 → G=10 H=7*10 F=80 B4 → G=14 H=6*10 F=74 圖2 選擇F值最低做為下一點，因此選擇B4

19 A*演算法(4/15) 選擇F值較小的B3前進 將B4設為父節點(如圖3)，將A3從開始列表刪除，加入關閉列表。
B4的相鄰節點A4、B3已在開啟列表中， A5 → G=28 H=6*10 F=88 圖3 選擇F值較小的B3前進

20 選擇F值較小的C3而非B2，因C3比B2晚加入列表
A*演算法(5/15) 將B3設為父節點(如圖4)，將B4從開啟列表中刪除且加入關閉列表中。 B3的相鄰節點為A2、B2、A4已在開啟列表，Ｃ4為障礙物。 C2 → G=24 H=7*10 F=94 C3 → G=20 H=6*10 F=80並將其節點指向父節點 圖4 選擇F值較小的C3而非B2，因C3比B2晚加入列表

21 A*演算法(6/15) 設定C3為父節點(如圖5)，將B3從開啟列表中刪除且加入關閉列表中，D3為障礙物，D2為對角線都也不在此討論中使用。

22 A*演算法(7/15) 將C2設為父節點(如圖6)，將C3從開啟列表中刪除並加入關閉列表，計算C2相鄰節點的F值。
B1 → G=38 H=9*10 F=128 C1 → G=34 H=8*10 F=114 D1 → G=38 H=7*10 F=108 D2 → G=34 H=6*10 F=94 並將其節點指向父節點。 圖6 選擇F值較小的節點D2為下一步

23 A*演算法(8/15) 將D2設為父節點(如圖7)，將C2從開啟列表中刪除並加入關閉列表中，因為不考慮對角線，故E3不列入相鄰節點中。
E1 → G=48 H=6*10 F=108 E2 → G=44 H=5*10 F=94 並將其指向父節點。 圖7 選擇F值較小的E2為下一步

24 A*演算法(9/15) 將E2設定為父節點(如圖8)，並將D2從開啟列表中刪除且加入關閉列表中。計算E2相鄰節點的F值。
E3 → G=54 H=4*10 F=94 F1 → G=58 H=7*10 F=128 F2 → G=54 H=6*10 F=114 F3 → G=58 H=5*10 F=108並將其指向父節點。 圖8 選擇F值較小的E3為下一步

25 A*演算法(10/15) 將E3設為父節點(如圖9)，並將D2從開啟列表中刪除且加入關閉列表中。計算出E3相鄰節點的F值。
E4 → G=64 H=3*10 F=94 F4 → G=68 H=4*10 F=108 並將其指向父節點。 圖9 選擇F值較小的E4為下一步

26 A*演算法(11/15) 將E4設為父節點(如圖10)，並將E3從開啟列表中刪除且加入關閉列表中，計算E4相鄰節點的F值。
E5 → G=74 H=2*10 F=94 F5 → G=78 H=3*10 F=108並將其指向父節點。 圖10 選擇F較小的E5為下一步

27 A*演算法(12/15) 將E5設為父節點(如圖11)，並將E4從開啟列表中刪除且加入關閉列表中。計算E5相鄰節點的F值。
E6 → G=84 H=1*10 F=94 F6 → G=88 H=2*10 F=108並將其指向父節點。 圖11 選擇F值較小的E6為下一步

28 A*演算法(13/15) 將E6設為父節點(如圖12)，並將E5從開啟列表中刪除且加入關閉列表中，計算E6相鄰節點的F值。
E7 → G=94 H=0 F=94 F6 → G=78 H=2*10 F=108並將其指向父節點。 圖12 選擇F值較小的E7為下一步

29 A*演算法(14/15) 此時經發現終點E7，從E7反推回去至起始節點至終點的路徑為 E7→E6→E5→E4→E3→E2→D2→C2→C3→B3→A3(如圖13)。 圖13

30 A*演算法(15/15)

31 參考文獻 南台知識分享平台 標題:應用在電腦鼠迷宮搜尋問題上之修正的深先搜尋法 作者:黎靖,吳一德..等
南台知識分享平台 標題:應用在電腦鼠迷宮搜尋問題上之修正的深先搜尋法 作者:黎靖,吳一德..等 南台知識分享平台 標題:迷宮搜尋演算法 作者:黎靖 A* Algorithm A*路徑搜尋 迷宮演算法 電腦鼠-演算法 電腦鼠-向心法則 報告背景圖來源