Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


DissertationDraft_PaulKim8.pdf (14.73 MB)

ETD Abstract Container

Abstract Header

Intelligent Maze Generation

Kim, Paul H
http://rave.ohiolink.edu/etdc/view?acc_num=osu1563286393237089

Abstract Details

2019, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
A maze is a puzzle in which a player finds a path from the starting point to the ending point. These days, maze is not only used as a puzzle but also adopted in many different fields. In the field of computer games, it can be used as a basic structure for a game level. In the field of robotics, it can be used as a platform to demonstrate the robot's learning ability. Also, in the field of architecture, its pattern can be used to decorate a building. Maze users in different fields may have different purposes to use a maze and need different properties of the maze. For example, a user may want a maze with numerous turns and branches in a robot contest, while others may want a maze with long straight passages and fewer dead-ends in building decoration. Thus, our research focuses on developing a method which can generate a maze based on the desired properties. Our research domain is perfect maze. Perfect maze is one type of a maze that has neither loops nor inaccessible areas. To generate a perfect maze satisfying given desired properties, our research applies a search-based procedural content generation (SBPCG) approach. SBPCG is one approach to procedurally generate game content like weapons and terrains via a searching mechanism. In our research domain, the perfect maze, SBPCG searches/generates perfect mazes until either a satisfactory maze is found or a termination criteria is met. Since a perfect maze has a structure of a spanning tree, spanning tree generation algorithms, such as Prim’s algorithm and Kruskal’s algorithm, can be used. This research aims to investigate whether these spanning tree generation algorithms are capable of generating the desired mazes using SBPCG approach. Since they search mazes randomly in the space of spanning trees, mazes with some desired properties could result in infinite searching. Thus, our research also provides new method, which applies intelligent searching mechanism in SBPCG approach. In this new method, from a space of spanning tree, we pre-build several representative vectors and use them in a SBPCG approach to find the desired mazes with very high probability. Our research demonstrates that any desired mazes can be found effectively with this representation-based method. Additionally, we also provide a method which can control the solution path topology on a maze so that users can manage game quality. To demonstrate how useful our intelligent maze generation is, this thesis provides several use-cases of building actual game levels and shows that the levels can be designed effectively using our method.
roger crawfis (Advisor)
matthew lewis (Committee Member)
jian chen (Committee Member)
249 p.
Computer Science
procedural content generation for games; maze generation; perfect maze; spanning tree; search-based procedural content generation

Recommended Citations

Citations

  • Kim, P. H. (2019). Intelligent Maze Generation [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1563286393237089

    APA Style (7th edition)

  • Kim, Paul. Intelligent Maze Generation. 2019. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1563286393237089.

    MLA Style (8th edition)

  • Kim, Paul. "Intelligent Maze Generation." Doctoral dissertation, Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1563286393237089

    Chicago Manual of Style (17th edition)

osu1563286393237089
2,999
© 2019, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.