結合蟻群與A*演算法應用在遊戲人工智慧路徑搜尋之研究－以塔防遊戲為例

Combine ACO and A* Algorithm in game ai pathfinding - As sample with Tower Defense Game

徐嘉琦(Chia-Chi Hsu)；巴白山(Pai-Shan Pa)；莊淇銘(Chi-Ming Chung)

路徑搜尋 ； A*演算法 ； 蟻群演算法 ； 心流曲線 ； 遊戲 ； Pathfinding ； A star algorithm ； Ant Co algorithm ； flow ； game

數位媒體設計國際研討會論文集

第十二屆（2019 / 06 / 14）

104 - 122

繁體中文;英文

路徑搜尋（Pathfinding）是眾多遊戲中常見的人工智慧系統（Artificial Intelligence，AI）。其應用層面為無論是玩家或是非玩家角色，在對應其設定上或是點選某個地圖上的座標點時，角色將會越過障礙，抵達目的地。而路徑搜尋的重心，都是用來尋找座標與座標之間的最短路徑，而學者們針對最短路徑撰寫了許多不同的演算法來解決問題，如搜尋樹、廣度優先演算法、戴克斯特拉演算法、A*演算法、蟻群演算法等。本研究主要探討「使用A*路徑搜尋演算法（A Star Algorithm）尋求最佳路徑解後，並透過蟻群演算法中的費洛蒙原理應用在敵人角色上，隨著玩家戰力的提升，敵人角色的攻擊路徑將有所改變，找出玩家最弱的路徑進行攻擊」。因此，我們將會建置一款塔防遊戲，並使用A*路徑搜尋演算法於敵人角色身上進行路徑搜尋，為了能夠輕易的分辨出差別，將會在使用者介面（UserInterface，UI）上建置一個按鈕，用於切換是否增加費洛蒙原理在敵人角色身上，藉此提升遊戲的困難度與遊戲性。之後將會配合問卷調查作心流曲線分析，遊戲主體將會以Unity3D開發平台與C#程式語言進行製作。

Pathfinding is the most popular artificial intelligence system in multiple games, In application level, player or non-character player, according system's settings or point the coordinate on map, character will cross the obstacle, and arrived where you want they go. Pathfinding's center is looking for the shortest path between coordinate, and a lot of scholars developer many defferent algorithm to solve the problems, such like search-tree, Breach-First Search, Dijkstra's Algorithm, A Star Algorithm and Ant Colony Algorithm. The purpose of the present is 「Using A*algorithm to find the best pathfinding, then combine Ant Colony algorithm's pheromone theory on enemies, when player promote power, enemy path will changing, find out the week path on player」. Therefore, We will build up a tower defense game, and use A* algorithm on enemies for pathfinding, We will build a button to switch whether add pheromone on enemies, to promote the game's difficulty and gameplay. And will cooperate questionnaire with flow analysis. Game will develop by Unity3D and C# program language.