臺灣博碩士論文加值系統

隨著電腦遊戲蓬勃發展，現今有許多遊戲都採用Procedural Content Generation(PCG)的方式來產生遊戲內容，使用PCG方式能夠快速產生許多不同的關卡，節省在手動製作時所需的人工成本，而跟著其他領域的結合，也能取得更精準的結果。在本論文中，將以自動產生Dr.Truck遊戲的關卡為目標，我們藉由遊戲物件與勝利條件推導得出通關路徑之概念，利用基因演算法來取得最符合開發者需求的通關路徑，重新組合出新的關卡。此外，由於產生出來之關卡是由通關路徑重新生成，仍有太多空白區域，為了充分運用這些空白區域我們提供了一個關卡完整化系統，系統內針對現有遊戲物件制定其放置規則，根據這些規則來填滿這些空白區域，產生一個更完整的關卡。

在實驗結果中，證明了我們的基因演算法由於突變中擁有修正效果，使得其演算法能夠快速收斂。在完整化系統內，雖然完善度尚不理想，但也成功取得了完整與可玩之關卡。在系統運行時間上，我們調整挑選菁英之方法與使用排列組合來交配，使得系統運行能夠穩定在一個均值上。最後本論文也推導出一組方程式用來解決其斜坡地板轉換之問題，藉由實驗結果也得到一個可行的答案。

With the vigorous development of computer games, today there are many games have adopted Procedural Content Generation (PCG) to generate game content, use PCG to quickly produce many different levels, saving labor costs in the production of the desired manual, and follow in combination with other fields, can achieve more accurate results. In this paper, we will automatically generate Dr.Truck level as the goal, we triumph by game objects and conditions deduced concept clearance path(PassPath), the use of genetic algorithms to obtain clearance path that best meet the needs of developers, recombination a new level. Furthermore, due to the generation out of these level are regenerate by the clearance path(PassPath), there are still too many blank areas to make full use of these blank area we offer a complete system level, the development of the existing rules of the game place objects within the system, based on these guidelines to fill the blank area to produce a more complete level.

In experimental results prove that our algorithms due to mutations in the gene have a correcting effect, making it possible to fast convergence. In the complete system, although the degree of improvement is not yet over, but also successfully achieved a complete and playable level. On the system performance, we adjusted the selection of elite method using permutations of mating, so that the system can run in a stable on average. Finally, this paper also derive a set of equations to solve the problem of converting its ramp floor, with experimental results obtained a viable answer.

摘要 I
ABSTRACT III
目錄 V
圖目錄 VII
表目錄 IX
方程式目錄 XI
第1章 介紹 1
1.1 動機 1
1.2 目標 1
1.3 方法 2
1.4 貢獻 2
1.5 DR.TRUCK 3
1.5.1 遊戲玩法 4
第2章 相關文獻 5
2.1 關卡自動生成(PCG) 6
2.2 基因演算法(GA) 7
第3章 方法 9
3.1 概要 9
3.2 基因演算法 9
3.2.1 場景結構 9
3.2.2 系統參數設定 11
3.2.3 初始化 13
3.2.4 評估 17
3.2.5 選擇交配群 18
3.2.6 交配 18
3.2.7 突變 20
3.2.8 挑選精英 22
3.3 關卡完整性強化 23
3.3.1 通關路徑完整化 23
3.3.2 樓層地板填充 24
3.3.3 確保通關路徑 25
3.3.4 放置斜坡地板 26
3.3.5 放置陷阱球 29
3.3.6 開啟第二路徑 29
3.3.7 Candy陷阱設置 31
3.3.8 關卡地板修正 32
3.3.9 清除無意義Cell 34
3.4 輸出 35
第4章 實驗結果 37
4.1 系統架構 37
4.2 實驗結果 40
4.2.1 關卡產生驗證 41
4.2.2 系統運行時間 43
4.2.3 關卡完整化驗證 45
4.2.4 斜坡地板修正 46
第5章 結論 47
5.1 結論 47
5.2 限制與未來計畫 47
參考文獻 49

Angry Birds. (2017). Retrieved from Angry Birds: https://www.angrybirds.com/
Chen, G.-J., & Tai, W.-K. (2016). Pattern-Based Automatic Game Level Generation and Difficulty Evaluation. published master’s thesis, National Dong Hwa University. Hualien, Taiwan.
Dahlskog, S., & Togelius, J. (2014). A Multi-level Level Generator. Computational Intelligence and Games (CIG) 2016 IEEE Conference on, pp. 1-8.
Diablo. (2017). Retrieved from Diablo III Official Game Site: http://tw.battle.net/d3/zh/
DOULL, A. (2008). Ascii Dreams: The Death of the Level Designer: Procedural Content Generation in Games. Retrieved from The Death of the Level Designer: Procedural Content Generation in Games - Part One: http://roguelikedeveloper.blogspot.tw/2008/01/death-of-level-designer-procedural.html
Ferreira, L., & Toledo, C. (2014). A Search-based Approach for Generating Angry Birds Levels. Computational Intelligence and Games (CIG), 2014 IEEE Conference on, pp. 1-8.
Genetic algorithm. (2017). Retrieved from Wiki: https://en.wikipedia.org/wiki/Genetic_algorithm
Horn, B., Dahlskog, S., Shaker, N., Smith, G., & Togelius, J. (2014). A Comparative Evaluation of Procedural Level Generators in the Mario AI Framework. International Conference on the Foundations of Digital Games, pp. 1-8.
Pacman. (2017). Retrieved from Pacman: http://www.gametop.com/download-free/pacman/
PCGWiki. (2014). What Pcg Is. Retrieved 6 29, 2016, from Procedural Content Generation Wiki: http://pcg.wikidot.com/what-pcg-is
Roberts, J., & Chen, K. (2015). Learning-Based Procedural Content Generation. IEEE Transactions on Computational Intelligence and AI in Games, Volume. 7(No.1), pp. 88 - 101.
Snodgrass, S., & Ontañón, S. (2014). Experiments in Map Generation using Markov Chains. International Conference on the Foundations of Digital Games.
Super Mario Bros. (2017). Retrieved from Super Mario Bros: http://www.supermariobrosx.org/
Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2010). Search-based Procedural Content Generation. EvoApplicatons'10 Proceedings of the 2010 international conference on Applications of Evolutionary Computation, Volume Part I, pp. 141-150.
Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011). Search-Based Procedural Content Generation:A Taxonomy and Survey. IEEE Transactions on Computational Intelligence and AI in Games, Volume. 3, pp. 172-186.