本研究主要將應用多代理人機制,透過實際開發塔防遊戲為例,改進遊戲的人工智能。過去傳統的塔防遊戲都是使用固定的敵方行走路徑,這樣的設計除了遊戲的挑戰性有限外,也缺少玩家運用策略的變化性。因此,此研究將改以使用 A* 最短路徑演算法來改善基本的路徑搜索方式,再透過多個遊戲物件代理人之間互相的溝通及協調藉以產生路徑的變化進一步改良路徑搜尋演算法,使敵方的路徑選擇和整體智能夠有大幅度的提昇。

This article uses the multi-agent system coordination mechanism and implements the characteristics of agents to construct and add intelligence to a computer program. By redesigning and developing a tower defense game as an example, this article presents models for coordination and message transmission between agents and creates two new methods to correct the path of the enemies and dynamically generate agents, which largely improves the intelligence of the enemies and towers in the game. Overall, the system changed traditional game rules and made a real-time strategy game more challenging.

目錄
第一章 緒論  1
1.1 研究背景及動機 1
1.2 研究目的    3
1.3 論文架構    4
第二章 文獻探討    5
2.1 代理人 5
2.2 路徑搜尋演算法 10
2.2.1 Dijkstra演算法   10
2.2.2 A*演算法 14
2.3 UML 19
2.4 Unity   23
2.5 塔防遊戲 26
第三章 系統分析與設計 27
3.1 系統架構    27
3.2 代理人和協調機制    31
3.2.1 管理者代理人    32
3.2.2 防禦塔和敵人代理人 32
3.2.3 路徑代理人 34
第四章 實作  36
4.1 A*路徑搜尋  36
4.2 執行結果    38
第五章 結論與未來方向 45
參考文獻    46
附錄-英文論文 49

圖目錄
圖2-1 DIJKSTRA和A*的搜尋結果 (資料來源WIKIPEDIA)   10
圖2-2 利用DIJKSTRA尋找S到各個節點的最短距離    12
圖2-3 A*演算法範例圖   16
圖2-4 計算相鄰F(N)值的結果   17
圖2-5 選擇下方F(N)值最低的方格 17
圖2-6 選擇左方F(N)值最低的方格 18
圖2-7 A*演算法的搜尋結果 18
圖2-8 UNITY的整合開發環境   23
圖2-9 預制(PREFABS)物件的屬性編輯 24
圖2-10 高動態範圍的渲染技術    25
圖2-11 第一款塔防遊戲RAPART 26
圖3-1 系統架構圖  27
圖3-2 防禦塔和敵人之使用範例圖   29
圖3-3 代理人類別圖 30
圖3-4 代理人間的合作模型  31
圖3-5 管理者和代理人間的訊息傳輸  33
圖3-6 攻擊模式的狀態圖   34
圖3-7 路徑修正示意圖    35
圖4-1 設定地圖節點 36
圖4-2 遊戲設定畫面 38
圖4-3 遊戲主畫面  39
圖4-4 防禦塔配置  40
圖4-5 防禦塔自動攻擊經過的敵人   41
圖4-6 玩家手動操控攻擊目標 42
圖4-7 第一回合的路徑選擇  42
圖4-8 第二回合的路徑選擇  43
圖4-9 第三回合的路徑選擇  44

表目錄
表2-1 DIJKSTRA演算法的虛擬程式碼  11
表2-2 各節點的初始狀態   13
表2-3 計算S節點的相鄰節點距離   13
表2-4 節點5的相鄰節點距離 13
表2-5 DIJKSTRA演算法的搜尋結果   13
表2-6 A*演算法的虛擬程式碼    14

[1] Zambonelli, Franco, Nicholas R. Jennings, and Michael Wooldridge. "Developing multiagent systems: The Gaia methodology." ACM Transactions on Software Engineering and Methodology (TOSEM) 12.3 (2003): 317-370.
[2] Horling, Bryan, et al. "The soft real-time agent control architecture." Autonomous Agents and Multi-Agent Systems 12.1 (2006): 35-91.
[3] Wooldridge, Michael. "Agent-based software engineering." IEE Proceedings-Software 144.1 (1997): 26-37.
[4] Bonabeau, Eric. "Agent-based modeling: Methods and techniques for simulating human systems." Proceedings of the National Academy of Sciences of the United States of America 99.Suppl 3 (2002): 7280-7287.
[5] Kinny, David, and Michael Georgeff. "Modelling and design of multi-agent systems." Intelligent Agents III Agent Theories, Architectures, and Languages. Springer Berlin Heidelberg, 1997. 1-20.
[6] Avery, Phillipa, et al. "Computational intelligence and tower defence games." Evolutionary Computation (CEC), 2011 IEEE Congress on. IEEE, 2011.
[7] Zhan, F. Benjamin. "Three fastest shortest path algorithms on real road networks: Data structures and procedures." Journal of geographic information and decision analysis 1.1 (1997): 69-82.
[8] Goldberg, Andrew V., Haim Kaplan, and Renato Werneck. "Reach for A*: Efficient point-to-point shortest path algorithms." Workshop on Algorithm Engineering & Experiments, Miami. 2006.
[9] Balaji, P. G., and D. Srinivasan. "An introduction to multi-agent systems." Innovations in Multi-Agent Systems and Applications-1. Springer Berlin Heidelberg, 2010. 1-27.
[10] Sycara, Katia, and Dajun Zeng. "Coordination of multiple intelligent software agents." International Journal of Cooperative Information Systems 5.02n03 (1996): 181-211.
[11] Ito, Nobuhiro, Tetsuya Esaki, and Naohiro Ishii. "A cooperative agent model by forming a group." Industrial Technology, 2002. IEEE ICIT'02. 2002 IEEE International Conference on. Vol. 2. IEEE, 2002.
[12] Cherkassky, Boris V., Andrew V. Goldberg, and Tomasz Radzik. "Shortest paths algorithms: theory and experimental evaluation." Mathematical programming 73.2 (1996): 129-174.
[13] Goldberg, Andrew V., and Chris Harrelson. "Computing the shortest path: A* search meets graph theory." Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005.
[14] Ferber, Jacques. Multi-agent systems: an introduction to distributed artificial intelligence. Vol. 1. Reading: Addison-Wesley, 1999.
[15] Sycara, Katia, and Dajun Zeng. "Coordination of multiple intelligent software agents." International Journal of Cooperative Information Systems 5.02n03 (1996): 181-211.
[16] Gallo, Giorgio, and Stefano Pallottino. "Shortest path algorithms." Annals of Operations Research 13.1 (1988): 1-79.
[17] Yershov, Dmitry S., and Steven M. LaValle. "Simplicial dijkstra and a* algorithms for optimal feedback planning." Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on. IEEE, 2011.
[18] Lo, Steven KC. "A collaborative multi-agent message transmission mechanism in intelligent transportation system–A smart freeway example." Information Sciences 184.1 (2012): 246-265.
[19] Robertson, David. "Multi-agent coordination as distributed logic programming." Logic programming. Springer Berlin Heidelberg, 2004. 416-430.
[20] De Weerdt, Mathijs, Adriaan Ter Mors, and Cees Witteveen. "Multi-agent planning: An introduction to planning and coordination." In: Handouts of the European Agent Summer. 2005.
[21] Tornero, Rafael, Javier Martinez, and Joaquin Castello. "Multi-Agent System." Highlights on Practical Applications of Agents and Multi-Agent Systems 156 (2012): 147.
[22] Patrick Lester 2003 A* Pathfinding for Beginners.