Optimization of NPC Assignment for Attack Strategy in the Game Using Ant Colony System

In a fighting game, especially Real Time Strategy (RTS), generally there were two or more teams fighting each other. Each team in the game certainly played by a lot of NPCs (Non Player Character) that moved autonomous. Thus, it taken a special intelligence for NPCs in terms of the assignment which was a guideline for each NPC to behave. Assignment would affected almost all the NPCs behavior, such as where NPC will move, when the NPC will carry out attacks, the nearest enemy who should be attacked first, who the team member will be assisted comrades nearby, and others. Besides optimal assignment can make the game became more realistic, it also serves as a strategy of NPC in an attempt to defeat the opponent effectively. Assignment was calculated based on the distance parameter between the NPC unit team with each unit of NPC opponent. In this paper was used the optimization algorithm Ant Colony System (ACS) which is one optimization method of shortest path finding. The goal of optimization was to generate a list of assignments for each unit of NPC to attack each opponent, then the total mileage in battle to be shorter, effective and efficient. Moreover, in this paper also discussed about the effect of using the optimization algorithms to the assignment of opponent. There were three different results on the total mileage of NPC in battle in some cases. The three different results were, first, if both of team used the optimization algorithm, the second when only one team used optimization algorithms, and third if there was no team that used optimization algorithm. The results of this paper were if there was no team used optimization algorithm (Non Optimization vs Non Optimization), then the total mileage NPC achieved 444.39. Then if just one team that used optimization algorithm (ACS vs Non Optimization), the total mileage NPC achieved 433.65. And if both of team used optimization algorithm (ACS vs ACS), total mileage NPC achieved 402.95. These results indicated that the differences optimization NPC on a team assignment would affected the assignment of NPC opponents. Moreover, the differences in these results proved that using optimization Ant Colony System (ACS) was suitable solution in the assignment problem of NPC.