運用多代理人協同機制於 A* 最佳路徑之改良 - 以塔防遊戲為例

Using Multi-Agent Coordination Mechanism to Improve A* Pathfinding on Tower Defense Game

張家銘(Chia-Ming Chang)

指導教授 ： 葛煥昭

淡江大學/工學院/資訊工程學系碩士在職專班/碩士(2013年)

https://doi.org/10.6846/TKU.2013.01173

摘要

本研究主要將應用多代理人機制,透過實際開發塔防遊戲為例,改進遊戲的人工智能。過去傳統的塔防遊戲都是使用固定的敵方行走路徑,這樣的設計除了遊戲的挑戰性有限外,也缺少玩家運用策略的變化性。因此,此研究將改以使用 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.

並列關鍵字

Multi-Agent ； Pathfinding ； A*

參考文獻

[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.

[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.