跳到主要內容

臺灣博碩士論文加值系統

(44.200.77.92) 您好!臺灣時間:2024/03/01 08:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:鄭程元
研究生(外文):Cheng-Yuan Cheng
論文名稱:Pac-Man遊戲之關卡自動生成與難易度評估
論文名稱(外文):Automatic Maze Generation and Difficulty Evaluation for Pac-Man
指導教授:戴文凱戴文凱引用關係
指導教授(外文):Wen-Kai Tai
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
論文頁數:57
中文關鍵詞:自動生成迷宮難易度評估Pac-Man
外文關鍵詞:Procedural Content GenerationPac-ManMazeDifficulty Evaluation
相關次數:
  • 被引用被引用:3
  • 點閱點閱:335
  • 評分評分:
  • 下載下載:36
  • 收藏至我的研究室書目清單書目收藏:0
隨著Procedural Content Generation (PCG)的發展,越來越多的遊戲採用PCG的方式來生成遊戲內容,透過每次遊戲都略有不同的體驗(gameplay),來保持玩家對遊戲的新鮮感,並且也降低了手動製作關卡所需耗費的人工成本,並壓縮遊戲的硬碟容量需求,甚至能夠根據玩家的遊玩狀況調整內容,讓玩家玩起來更有挑戰性。
Pac-Man遊戲是1980年以來的經典遊戲之一,至今仍有不少人著迷於他簡單的操作與驚險刺激的遊戲體驗。然而Pac-Man遊戲的迷宮變化性一直都不大,即使是最近幾年推出的版本也只有固定幾個迷宮配置在變化。因此我們希望能透過自動生成的方法來增加Pac-Man遊戲的樂趣,讓玩家在每次遊戲時都能得到略為不同的體驗。在本論文中,將以自動生成Pac-Man遊戲的迷宮為目標,並且提出評斷所生成之迷宮的難易度的方法。
我們提出利用Recursive Branching的方式來生成迷宮的方法,並將不必要的Square及死路去除,以符合Pac-Man迷宮的特性。接著在迷宮中配置Pills和Power Pills,以及玩家和鬼的起始位置與鬼的巢穴。如此一來就可以生成一個適用於Pac-Man遊戲的迷宮。 再者,為了驗證生成的迷宮關卡具有一定的挑戰性,我們提出了一個評估迷宮難度的方法。透過對迷宮大小、叉路數量、走廊風險等三個項目評估出不同的難度等級,進而得出迷宮的整體難度。
我們生成的迷宮每10000組有8451組是可以直接遊玩的,約為84.51%。並且每組迷宮生成時間平均只需要53ms,適合在遊戲中進行即時生成。評估出來的迷宮難易度也有足夠的代表性,玩家在較困難的迷宮表現較差,而在較容易的迷宮表現較好。生成的迷宮分部狀況呈現常態分布,大部分生成的迷宮難度較Pac-Man遊戲的經典迷宮略低,而難易度與經典迷宮相差較大的迷宮數量則較少。
關鍵
With the development of procedural content generation (PCG), more and more games are using PCG to generate the content of a game. The technique brings some fresh experience every time players play the game. It can also lower the cost to design game levels, reduce storage requirement, or even adjust the content according to player habits and allow the players to enjoy the game with more challenges.
Pac-Man has been one of the classic games since 1980. The excitement and the simple playing style of the game is still favored by people in present days. However, even in the recent versions, the variety of the mazes in the game is never sufficient enough. Bringing different gameplay experience with respect to more variant mazes while playing the game would have players more fun. In this paper, our goal is to propose a method to generate Pac-Man mazes automatically, and propose a method to evaluate the difficulty of mazes.
A method called Recursive Branching is proposed to generate mazes, which is then refined by removing square patterns and dead ends to comply with the style of Pac-Man mazes. Also, the important game items such as pills, power pills, player start position, ghost start position, and ghost lair are placed in the maze to complete a maze as a whole. Moreover, to ensure the generated mazes have certain challenge for players, we propose a method to evaluate the difficulty of mazes. On the basis of feature parameters maze size, number of intersections, and corridor risk of a maze.
For every 10,000 mazes we generate, there are 84.51 percent of (8,451) mazes viable. The average time of generating a maze requires only 53ms, capable of generating mazes in real time. Based on the fact that players can perform better in easier mazes than more difficult mazes, it shows our difficulty evaluation is effective. Furthermore, the probability distribution of all difficulty levels of the generated mazes is in normal distribution. That is, the generated mazes conform to the skill of players.
Chapter 1. Introduction
1.1 Introduction to Pac-Man
1.1.1 History Of Pac-Man
1.1.2 How To Play
1.1.3 Basic Strategies
1.2 Motivation
1.3 Goals
1.4 Method
1.5 Contribution and Limitations
Chapter 2. Related Work
2.1 Methods For Maze Generation
2.2 Ghosts AI
Chapter 3. Method
3.1 Overview
3.2 Maze Generation
3.2.1 Maze Representation
3.2.2 Ghost House Setup
3.2.3 Recursive Branching
3.2.4 Square Removal
3.2.5 Dead End Removal
3.2.6 Setup of Pills and Power Pills
3.2.7 Setup of Important Locations
3.3 Quality Assurance
3.3.1 Quality Check
3.3.2 Difficulty Function
3.4 Maze Output
Chapter 4. Result
4.1 Effect of Input Parameters
4.1.1 Effect of Branching Number
4.1.2 Effect of Distance Between Branches
4.1.3 Effect of Branching Range
4.2 Efficiency of Difficulty Evaluation
4.3 Statistics of Generated Mazes
Chapter 5. Conclusion
5.1 Contribution
5.2 Limitations and Future Work
References
[ALM, May 2011] D. Ashlock, C. Lee, and C. McGuinness. Simultaneous Dual Level Creation For Games. IEEE Computational Intelleigence Magazine, May 2011
[ALM, September 2011] D. Ashlock, C. Lee, and C. McGuinness. Search-Based Procedural Generation of Maze-Like Levels. IEEE Transactions on Computational Intellegence and AI in Games, Vol. 3, No. 3, September 2011
[BB, 1984] D. Barben, I. Bell. Elite. 1984. Retrieved May 6, 2014, from http://www.eliteforever.co.uk/downloads.html
[BLL, 1992] J. Barraquand, B. Langlois, and J. Latombe. Numerical Potential Field Techniques for Robot Path Planning. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 22, No. 2, Match/April 1992
[Blizzard, 1996] Blizzard. (December 31, 1996). Diablo. Retrieved May 6, 2014, from Blizzard official Site: http://us.blizzard.com/en-us/games/legacy/
[Bethesda, 2006] Bethesda. The Elder Scrolls IV: Oblivion. 2006. Retrieved May 6, 2014, from The Elder Scrolls Official Site: http://www.elderscrolls.com/oblivion/
[Birch, 2010] C. Birch. Understanding Pac-Man Ghost Behavior. GameInternals.com, 2010
[Foltin, 2011] M. Foltin. Automated Maze Generation and Human Interaction. Masaryk University Faculty of Informatics Diploma Thesis, 2011
[GSC, 2007] GSC Game World. S.T.A.L.K.E.R.: Shadow of Chernobyl. 2007. Retrieved May 6, 2014, from S.T.A.L.K.E.R. Official Site: http://soc.stalker-game.com/
[Google, 2010] Google. Google 30th Anniversary of Pac-Man. May 21, 2010. Retrieved May 6, 2014, from https://www.google.com/doodles/30th-anniversary-of-pac-man
[Kruskal, 1956] J. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50
[Krause, 1986] Eugene F. Krause. Taxicab Geometry. Courier Dover Publications, 1986
[LYT, 2013] A. Liapis, G. N. Yannakakis, J. Togelius. Designer Modeling for Personalized Game Content Creation Tools. AIIDE Workshop, 2013.
[Lucas, 2014] S.M. Lucas. Ms. Pac-Man Competition. Retrieved May 6, 2014, from http://dces.essex.ac.uk/staff/sml/pacman/PacManContest.html
[Mossmouth, 2008] Mossmouth. Spelunky. 2008. Retrieved May 6, 2014, from http://spelunkyworld.com/
[Namco, 1980] Namco. Pac-Man. May, 1980. Retrieved May 6, 2014, from Pac-Man Official Site: http://pacman.com/ja/index.html
[Namco, 2007] Namco. (June, 2007). Pac-Man Championship Edition. Retrieved May 6, 2014, from Pac-Man Official Site: http://pacman.com/en/pac-man-games/pac-man-championship-edition-dx.html,
[Prim, 1957] R. C. Prim. Shortest connection networks and some generalizations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
[Pearson, 1895] Karl Pearson. Notes on regression and inheritance in the case of two parents. Proceedings of the Royal Society of London, 1895.
[Pullen, 2013] W. Pullen, Think Labyrinth. October 11, 2013. Retrieved May 6, 2014, from http://www.astrolog.org/labyrnth.htm
[PCGWiki] Procedural Content Generation Wiki. Retrieved May 6, 2014, from http://pcg.wikidot.com/what-pcg-is
[Reynolds, 2010] A. M. Reynolds. Maze-solving by Chemotaxis. Physical Review E 81, 2010
[RRL, 2014] P. Rohlfshagen, D. Robles, S. M. Lucas. Ms. Pac-Man V.S. Ghosts, Retrieved May 6, 2014, from http://www.pacman-vs-ghosts.net/
[Spore, 2008] Spore. September, 2008. Retrieved May 6, 2014, from Spore Official
Site: http://www.spore.com/
[STN, 2014] N. Shaker, J. Togelius, M. J. Nelson. PCG in Games. 2014. Retrieved May 6, 2014, from http://pcgbook.com/
[TWAL, 1983] M. Toy, G. Wichman, K. Amold, J. Lane. Rogue. 1983. Retrieved May 6, 2014, from http://www.dosgamesarchive.com/download/rogue/
[Webpacman, 2014] Webpacman. Retrieved May 6, 2014, from http://www.webpacman.com/
[Wiki, Pac-Man] Pac-Man. In Wikipedia. Retrieved May 6, 2014, from http://en.wikipedia.org/wiki/Pac-Man
[Wiki, Ms. Pac-Man] Ms. Pac-Man. In Wikipedia. Retrieved May 6, 2014, from http://en.wikipedia.org/wiki/Ms._Pac-Man
[ZFR, 2014] A. Zook, E. Fruchter, M. O. Riedl. Automatic Playtesting for Game Parameter Tuning via Active Learning. International Conference
on the Foundations of Digital Games, 2014
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top