淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2806201312190400
中文論文名稱 運用多代理人協同機制於 A* 最佳路徑之改良 - 以塔防遊戲為例
英文論文名稱 Using Multi-Agent Coordination Mechanism to Improve A* Pathfinding on Tower Defense Game
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士在職專班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 101
學期 2
出版年 102
研究生中文姓名 張家銘
研究生英文姓名 Chia-Ming Chang
學號 700410250
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2013-06-21
論文頁數 58頁
口試委員 指導教授-葛煥昭
委員-葛煥昭
委員-蔣璿東
委員-羅光志
中文關鍵字 多代理人  路徑搜尋  A* 
英文關鍵字 Multi-Agent  Pathfinding  A* 
學科別分類 學科別應用科學資訊工程
中文摘要 本研究主要將應用多代理人機制,透過實際開發塔防遊戲為例,改進遊戲的人工智能。過去傳統的塔防遊戲都是使用固定的敵方行走路徑,這樣的設計除了遊戲的挑戰性有限外,也缺少玩家運用策略的變化性。因此,此研究將改以使用 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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-07-17公開。
  • 同意授權瀏覽/列印電子全文服務,於2013-07-17起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信