線上遊戲之戰術規畫

Abstract

隨著網際網路使用者數量的快速累積，網路這個虛擬世界對現實世界的影響力隨之變得具體而引人注目。其中，線上遊戲這個產業在近幾年爆發性的市場成長更讓我們看到未來無限的潛力，在這麼多種的線上遊戲裡面又以角色扮演的線上遊戲佔最大的比例，同時也是眾多遊戲廠商的主要收入來源。然而，對於如何有效率的排程打怪練功過程，以提高經驗值的研究卻顯得稀少。因此，我們在這篇論文中，提出一線上遊戲的戰術規劃問題。這個問題主要建立在一個在角色扮演的線上遊戲，遊戲角色可以透過打怪、完成任務等等方式獲取經驗值，而我們的目標就是在最少的時間下，排程打怪練功的過程，以達到特定目標經驗值。在這篇論文裡，我們先把這個題目描述成一個資源限制下的排程問題，並設計一個動態規劃演算法來求出最佳解，分析題目近似解，以及在幾個特殊情況下的求解方法。

As the population of the Internet users increases explosively, the market value of the virtual world becomes remarkable. In this thesis, we propose a mission planning problem arising from computer games to optimize the time required to reach a target experience level. The problem is formulated as a resource-constrained scheduling problem in which each job (task) has a processing time, requires an amount of resources for its processing and returns another amount of resources. We give a formal mathematical formulation through a binary integer program. A pseudo-polynomial time dynamic programming algorithm is developed to produce optimal schedules. A result of non-approximability about constant performance ratios is established and a 2-approximate greedy algorithm is given for a special case. We also proposed solution algorithms for two special cases: (1) jobs have the same processing time, and (2) jobs belong to K different types.