近年來，地城探索(Dungeon Crawler)類型遊戲之相關研究愈加受到關注。遊戲當中的許多要素，如：流暢的故事情節、緊湊刺激的操作、身歷其境的遊戲步調、以及多種不同走向的遊戲結局，讓這些動作冒險類型遊戲替玩家帶來了十分多元的遊戲體驗。在本篇論文中，我們將專注於，如何根據遊戲設計師所期望之遊戲步調，來生成地下城關卡。

我們提出了一套名為「步調導向地下城關卡生成器」的半自主式工具，可根據遊戲設計師預期的遊戲步調來生成地下城關卡。首先，我們需要一個透過“Mission and Space framework”手動製作出的遊戲關卡，來做為我們系統的輸入。“Mission and Space framework”是將遊戲關卡的建構過程，區分為任務和空間兩個不同層次的一種抽象概念。其次，遊戲步調參數，如：威脅性、推動力、以及節奏性等等，將透過視覺化曲線的方式，讓遊戲設計師能夠進行調整。接下來，遊戲設計者可以設定基因演算法的各項參數與限制條件，例如：允許的關卡類型、對玩家角色造成傷害之期望值、敵人數量等等，使其能夠生成出符合需求的候選關卡。我們的基因演算法透過兩種手段來修改關卡房間內遊戲物件的類型及位置：一為突變——隨機改變遊戲物件類型、或是將遊戲物件位置互換；二為交配——將兩個關卡個體之組成圖塊各取一部分進行組合。這有助於遊戲設計者根據自己的喜好，為玩家創造出一個有意義的地下城關卡。

本論文所提出的方法，可以最小化開發遊戲時耗費在創作關卡階段的時間及成本，並且，它可以被遊戲設計者用來做為，一種程序化地制定遊戲步調的正式方法。此外，這套系統可以透過不斷地提供各式各樣符合遊戲設計師期望的候選關卡，來保持玩家持續前進、同時維持遊玩體驗。由於在我們的方法中，關卡房間出口數量、玩家路徑長度、以及房間大小等等參數，皆受到約束、不允許改變，因此所生成出的遊戲關卡其步調與設計者期望目標的相似性，很大程度取決於一開始所輸入的關卡空間。系統生成新房間的靈敏度，取決於遊戲設計者所設置的限制條件；而生成預期中之遊戲步調模式所需的計算時間，則取決於房間大小。

The studies on the Dungeon Crawler games are getting even more attention these days. Many factors such as intense actions, immersive game pacing, and multi-alternative endings of the game, are allowing this action-adventure genre game to give various interesting experiences to the player. In this study, we focus on how to generate dungeon level with the intended game pacing designed by the game designer.

We proposed a mixed-initiative tool called “Pacing-based Dungeon Generator” to generate a game level, which corresponds to the game designer's expected game pacing. First, a game level space which we handcrafted by borrowing the mission and space framework is needed as an input for our system. The mission and space framework is an abstraction to distinguish the construction of a level into mission and space structure. Secondly, the designer can adjust the values of the intended pacing aspects, namely threat, impetus, and tempo, which are visualized by pacing curves. Thirdly, the designer can set up the constraints and configurations for the genetic algorithm to drive the generation process to produce level candidates, e.g., the allowed type, the expected damage, and the number of enemies. Our genetic algorithm generates rooms with modified objects' type and position by changing the type of the object randomly and/or swapping the object positions in mutation phase, and combining part of tiles from two individuals in crossover phase. This facilitates the game designer to create a meaningful dungeon level for the player based on the game designer's preferences.

The proposed approach minimizes both, the time and expenses used to create a game level, and it can be used as a formal approach for the game designer to procedurally tailor the game pacing. Moreover, the system can keep the players' progression and experience by providing various level candidates that follow the game designer's expectation. The closeness of pacing patterns to the designer's target is highly dependent on the level space since we do not allow the number of exit connections, the number of tiles in the player's path, and the room size to change. The sensitivity of the system to generate the new room is dependent on the constraints set by the designer, whereas the computation time to generate the expected pacing patterns is dependent on the room size.

[1] N. Shaker, J. Togelius, and M. J. Nelson, Procedural Content Generation in Games. Springer, 2016.
[2] G. Smith, J. Whitehead, M. Mateas, M. Treanor, J. March, and M. Cha, “Launchpad: A rhythm-based level generator for 2-d platformers,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 3, pp. 1–16, March 2011.
[3] G. R. Wichman, “A brief history of ‘rogue’.” http://web.archive.org/web/20150217024917/http://www.wichman.org/roguehistory.html archived from the original http://wichman.org/ on 2015-02-17. Accessed: 2017-11-22.
[4] G. N. Yannakakis and A. Paiva, “Emotion in games,” Handbook on affective computing, pp. 459–471, 2014.
[5] G. Wallner and S. Kriglstein, “Plato: A visual analytics system for gameplay data,” Computers & Graphics, vol. 38, pp. 341–356, 2014.
[6] A. Baldwin, S. Dahlskog, J. M. Font, and J. Holmberg, “Mixed-initiative procedural generation of dungeons using game design patterns,” in 2017 IEEE Conference on Computational Intelligence and Games (CIG), pp. 25–32, IEEE, 2017.
[7] J. Dormans, “Adventures in level design: Generating missions and spaces for action adventure games,” in Proceedings of the 2010 Workshop on Procedural Content Generation in Games, pp. 1:1–1:8, ACM, 2010.
[8] Z.-H. Wang, “Game design goal oriented approach for procedural content generation,” Master’s thesis, National Taiwan University of Science and Technology, Republic of China, 2017.
[9] R. van der Linden, R. Lopes, and R. Bidarra, “Procedural generation of dungeons,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 6, no. 1, pp. 78–89, 2014.
[10] N. Chomsky, Language and Mind (enlarged edition). Harcourt Brace Jovanovich, New York, 1968/72.
[11] J. Golding, “Building blocks: Artist driven procedural buildings,” in Game Developers Conference 2010, 2010.
[12] D. Adams et al., “Automatic generation of dungeons for computer games,” Bachelor thesis, University of Sheffield, UK. DOI= http://www. dcs. shef. ac. uk/intranet/ teaching/projects/archive/ug2002/pdf/u9da. pdf, 2002.
[13] J. Rekers and A. Schurr, “A graph grammar approach to graphical parsing,” in Proceedings of 11th IEEE International Symposium on Visual Languages, pp. 195–202,
IEEE, 1995.
[14] G. Stiny and J. Gips, “Shape grammars and the generative specification of painting and sculpture.,” in International Federation for Information Processing (IFIP) Congress, vol. 2, pp. 1460–1465, 1971.
[15] G. Gygax and D. Arneson, Dungeons and Dragons, vol. 19. Tactical Studies Rules Lake Geneva, WI, 1974.
[16] B. Lavender and T. Thompson, “A generative grammar approach for action-adventure map generation in the legend of zelda,” in Artificial Intelligence Simulation and Behaviour, 2016.
[17] C. Alexander, S. Ishikawa, and M. Silverstein, A Pattern Language: Towns, Buildings, Construction. New York: Oxford University Press, August 1977.
[18] B. Kreimeier, “The case for game design patterns.” https://www.gamasutra.
com/view/feature/132649/the_case_for_game_design_patterns.php/,
2002. Accessed: 2017-11-22.
[19] S. Dahlskog, S. Björk, and J. Togelius, “Patterns, dungeons and generators,” in 10th Conference on the Foundations of Digital Games, Foundations of Digital Games,
2015.
[20] S. Dahlskog and J. Togelius, “Procedural content generation using patterns as objectives,” in European Conference on the Applications of Evolutionary Computation,
pp. 325–336, Springer, 2014.
[21] A. Baldwin, S. Dahlskog, J. M. Font, and J. Holmberg, “Towards pattern-based mixed-initiative dungeon generation,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, pp. 74:1–74:10, ACM, 2017.
[22] J. M. Font, R. Izquierdo, D. Manrique, and J. Togelius, “Constrained level generation through grammar-based evolutionary algorithms,” in European Conference on the Applications of Evolutionary Computation, pp. 558–573, Springer, 2016.
[23] J. Wesolowski, “Beyond pacing: Games aren’t hollywood.” https : / / www . gamasutra.com/view/feature/132423/beyond_pacing_games_arent_.php, 2009. Accessed: 2017-04-23.
[24] M. Davies, “Examining game pace: How single-player levels tick.” https://www. gamasutra.com/view/feature/132415/examining_game_pace_how_.php, 2009. Accessed: 2017-04-23.
[25] B. Patatas, “The dungeon crawler recipe.” https://www.gamasutra.com/blogs/ BrunoPatatas/20130119/185096/The_Dungeon_Crawler_Recipe.php, 2013. Accessed: 2017-04-23.
[26] A. Canossa and G. Smith, “Towards a procedural evaluation technique: Metrics for level design,” in The 10th International Conference on the Foundations of Digital Games, vol. 7, pp. 8–14, 2015.
[27] G. Smith and J. Whitehead, “Analyzing the expressive range of a level generator,” in Proceedings of the 2010 Workshop on Procedural Content Generation in Games, pp. 4:1–4:7, ACM, 2010.
[28] D. Karavolos, A. Bouwer, and R. Bidarra, “Mixed-initiative design of game levels: Integrating mission and space into level generation.,” in FDG, 2015.
[29] J. Dormans and S. Leijnen, “Combinatorial and exploratory creativity in procedural content generation,” in Proceedings of the fourth workshop on Procedural Content
Generation for Games at the Foundations of Digital Games Conference, pp. 1–4, FDG, 2013.
[30] D.-Y. Gu, “A study on automatically optimizing gameplay based on the expectation of game designer,” Master’s thesis, National Dong Hwa University, Republic of China, 2016.
[31] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. Cambridge, MA, USA: MIT Press, 1992.
[32] A. Liapis, G. N. Yannakakis, and J. Togelius, “Generating map sketches for strategy games,” in European Conference on the Applications of Evolutionary Computation, pp. 264–273, Springer, 2013.
[33] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
[34] D. Whitley, “The genitor algorithm and selection pressure: Why rank-based allocation of reproductive trials is best,” in Proceedings of the Third International Conference on Genetic Algorithms, (San Francisco, CA, USA), pp. 116–121, Morgan
Kaufmann Publishers Inc., 1989.