University of North Carolina Wilmington



2D Procedural Dungeon Generation AnalysisJessica Baron & Aurora SilverwoodUniversity of North Carolina WilmingtonAbstract2D dungeon maps consist of traversable rooms and corridors, represented by connected floors and bounded by untraversable walls. The algorithms used in creating such maps are divided as room-generating algorithms and corridor-generating algorithms. Each algorithm pair is written in Java using custom graphs, implemented with two-dimensional arrays. The efficiency of each algorithm pair is measured in Theta notation, which is reflected by the recorded time measurements taken in milliseconds in creating each map. Each algorithm has its strengths and weaknesses and can be used in combination for different desired results.Key Words: ?Procedural, dungeon, map, 2D Array , graph, goal specific constraints, Java1. IntroductionThe algorithms are subject to a standard set of rules. The graph representing the map can be set to dimensions between 30x30 vertices and 500x500 vertices, but for our testing purposes all algorithm pairs take place on a 60x60 Graph composed of “on”- and “off”-vertices. Each pair of algorithms produces a connected graph. Testing each pair produces standard deviation percentages that are each is no more than 10% from the desired percent from 40% “on” : 60% “off” ratio, and these deviations across the different algorithm pairs differ slightly from one another since each pair has its own unique pattern in creating the map’s rooms and corridors. The ultimate appeal of the composition of a map depends on the map’s purpose and the user’s own subjections; this is one reason why there are multiple approaches to generating dungeons and why we narrowed our focus to generating a particular kind of map for this project.2. Formal Problem StatementWith minimal computational iterations measured in Theta Notation, procedurally generate a 2D video game dungeon map, which is composed of rectangular “rooms” that are connected by narrower “corridors” as a graph of ?w × h vertices, with a width of w vertices and a height of h vertices. ?Each vertex is assigned a state that is either “on” or “off” (“on” forming the traversable rooms and corridors, and “off” forming untraversable boundaries, or, “walls”). ?One benchmark is that the “on” vertices of the graph are connected, meaning each “on” vertex is adjacent to at least one other “on” vertex, guaranteeing that all traversable vertices ultimately lead to one another and are therefore connected. The other benchmark is that the graph should reflect a desired sparsity ratio between “on”- and “off”-vertices, which is defined as approximately 40% of the graph vertices being “on” and 60% being “off,” the graph’s percentages being within a 10% deviation from that ratio.A “room” is a subset of the set of graph vertices, consisting of, “on”-vertices that are adjacent to one another, forming a subgraph of their own of a width and a height; the width and height are each constrained by certain minimum and maximum values that are fractions of the graph’s width and height values. A “corridor” is a subgraph of a width and a height, where either the width or the height has to be equal to one. ?Corridors are generated after rooms have been generated and connect two rooms at a time. A room cannot be connected to another room, but it must be connected to at least one corridor. ?A corridor must be connected to at least one other corridor or room, and if it is connected to a corridor, the corridor it is connected to must be connected to a room.3. ContextRogue (1980) (reference figure 3.1), developed by Michael Toy and Glenn Wichman is one of the first video games to use procedural dungeon generation in game. ?Many games following it have been considered “Rogue-like.” Due to the severely limited memory and disk space of early computers, storing large maps and artwork for a video game simply were not feasible. Today, computer memory and processing power are not so limited.Procedurally generated dungeon maps allows game developers to devote more time into creating complex story and gameplay. The early games used ASCII representation, similar to our implementation. However, increased computer processing power and memory have allowed more modern games to combine procedural generation with original artwork to create more appealing and organic maps such as in the games Blizzard’s Diablo (1996) (reference figure 3.2) and Minecraft (2009).4. The AlgorithmsWe implemented five algorithms that use and manipulate the base Graph class. ?Each algorithm is either a room-generating algorithm or a corridor-generating one, and these five algorithms are combined to create five unique, map generating algorithm pairs.5. The Base GraphThe base graph class is what all of the room and corridor algorithms modify and build upon. ?It is constructed as mainly a 2D array of “vertex” objects, which each hold a Boolean state value of “on” or “off” (the default state being “off”), and a String value that depicts which component of the graph the vertex belongs to: a “room,” “wall,” or “corridor.” Each vertex is then stored in the 2D array Graph class the graph is initialized as a blank dungeon map, represented by “off” vertices.6. Random Room Placement ?Random Room Placement is a brute force room-generating algorithm. It is implemented by randomly generating a room width and height (bounded by minimum and maximum dimension values), then randomly picking a vertex (x, y) on the graph that will be the top-left corner of the room to place. This potential room is then checked for overlapping with other “on”-vertices of the graph. If it will not overlap, the room is “drawn” in the graph, starting at the top-left corner vertex. Otherwise, try to place the same room again but at a different vertex location; there can be a maximum of only 100 tries of placing the same room in the graph. We have implemented a separate method that checks for overlapping other rooms or the borders of the graph plus a space of three vertices horizontally and vertically around those other rooms and borders. Once a room is created, it is added to an array-list. ?This algorithm continues to run in a main while loop until the percentage of the graph composed of “on” (or, specifically, “room”) vertices reaches a particular value, which is passed as a parameter. This value is different according to which corridor-generating algorithm this room-generating one is paired with. Efficiencies for Random Room Placement:In general: Θ (1)In our case: Θ (n+c+(w*h))(Reference figure 6.1 for full analysis)7. BSP Room PlacementThe BSP Room Placement algorithm is an implementation of binary space partitioning. ?It partitions the graph into “leaf” objects, each of which is stored in a tree data structure, starting with the entire graph as the “root” of the tree. ?The leaves are split until a split leaf has children of a defined minimum size (which is directly related to the graph’s dimensions as it is the maximum room size plus a certain modifier, which is a fraction of the graph’s dimensions, to prevent room overlapping). ?A bottom leaf has no children as it does not get split. ?The bottom childless leaves are assigned rooms (the maximum size of which is smaller than the minimum leaf size), and these rooms are added to an array-list in the order of which the leaf objects are created. Efficiencies for BSP Room Placement:In general: Θ(1)In our case: Θ(n+c+(w*h))(Reference figure 7.1 for full analysis)8. Random Point ConnectThis corridor-generating algorithm accesses the array-list created by one of the room-generating algorithms and connects two rooms at a time, which are two consecutive elements in the room list. ?The algorithm connects rooms of this array-list in a brute force manner, selecting a random vertex each bordering the two rooms and connecting them the entire horizontal distance and then the entire vertical distance (or vice versa; the algorithm randomly decides in which direction to start). ?Overlapping other corridors and rooms with these new corridors is ignored. ?Random Point Connect produces different results according to how the array-list of rooms is ordered. ?For example, ?a room list created by the Random Room Placement algorithm has no relation between consecutive elements in the list as randomly generated room are added as they are successfully placed, therefore connecting them with Random Point Connect will often have more overlapping of corridors. ?A room list created by BSP Room Placement is created according to bottommost leaf objects, whose order is reflected by how the BSP tree splits. ?Therefore, when these rooms are connected, the corridors produced are often shorter and do not overlap as much as with a room list form Random Room Placement.Efficiencies for Random Point Connect:In general: Θ(n)In our case: Θ(w*h)(Reference figure 8.1 for full analysis)9. Drunkard’s WalkOur Drunkard’s Walk algorithm is inspired by an original Drunkard’s Walk algorithm used in generating?maps with cave structures rather than rooms and corridors. Our implementation of the Walk is used as a winding room-connecting, corridor-generating algorithm. As with Random Point Connect, this algorithm accesses the array-list created by the one of the room-generating algorithms and connects pairs of rooms, at a time by randomly selecting a bordering vertex each of the two rooms. This algorithm varies from the previous corridor-generating one as it starts at the first room’s selected vertex and heads off in the appropriate x and y directions (whether positive or negative) towards the second chosen vertex, incrementing n vertices (n ∈ N = {2,3,4,5,6} ) horizontally or vertically with each iteration, which is randomly decided. ?Direction is negated if path reaches too closely to the graph’s borders. ?Drunkard’s Walk will keep iterating until it reaches the other point, or when too many steps have been taken. ?(The latter may happen if the Walk is trapped at a corner of the graph and may reach an infinite loop if unchecked. ?If the number of steps does exceed the certain defined limit, the Walk will continue from the current vertex to the destination vertex in a brute force manner to ensure connectedness.) This algorithm produces the most varying results, ranging from sparse maps where corridors found their destinations quickly, to cave-like maps where the algorithm carved winding corridors in taking many iterations to find the destination vertex.Efficiencies for Drunkard’s Walk:In general: Θ(n)In our case: Θ(m* w*h)(Reference figure 9.1 for full analysis)10. ?BSP CorridorsBSP Corridors must be paired with the BSP Room Placement algorithm as its functionality is within the classes that handle the binary space partitioning and relies on particular information gathered in BSP Room Placement. ?As with the previous corridor-generating algorithms, BSP Corridors connects room pairs from an array-list generated by a room-generating algorithms and, with each pair of rooms to connect, selects random border vertices each from the two rooms. ?BSP Corridors has a very similar implementation to Random Point Connect but varies slightly as it implements a possibility of one or two connections between a single pair of rooms. ?However, the largest difference between those two corridor-generating algorithms is how the pairs of rooms are determined. ?BSP Corridors connects rooms of bottommost leaf objects that share the same parent leaf. ?Each pair of?sibling leaves is also connected to one other pair of siblings. ?Consequently, the graph result often has very orderly and linear connections between rooms.Efficiencies for BSP Cooridors:In general: Θ(1)In our case: Θ(3c*w*h)(Reference 10.1 for full analysis)11. Random Room Placement and Random Point Connect AnalysisWhen paired with Random Point Connect, the maximum percentage parameter passed to Random Room Placement is 40% (meaning that the rooms produced by this algorithm pair should ?compose no more than 40% of the graph’s vertices), since the amount of vertices that compose the corridors of the graph when generated by Random Point Connect will not be too large.Efficiencies for Random Rooms and Random In general: Θ(w*h) + Θ(w*h) = Θ(2(w*h)) = ?Θ(w*h) ?In our case: Θ(n) + Θ(n) = Θ(2n) = Θ(n)12. Random Room Placement and Drunkard’s Walk AnalysisWhen paired with Drunkard’s Walk, the maximum percentage parameter passed to Random Room Placement is 15% (meaning that the rooms produced by this algorithm pair should ?compose no more than 15% of the graph’s vertices), anticipating a large amount of vertices to compose the corridors of the graph when generated by Drunkard’s Walk.Efficiencies for Random Rooms and Drunkard’s:In general: Θ(w*h) + ?Θ(m* w*h) = Θ(m* 2(w*h))= ?Θ(m*w*h)In our case:Θ(n) + Θ(n) = ?Θ(2n) = Θ(n)13. BSP Room Placement and Random Point Connect AnalysisWhen paired with Random Point Connect, the minimum leaf size modifier parameters passed to BSP Room Placement is 1/15 of the graph’s width and 1/15 of the graph’s height (meaning that more rooms can be placed in the graph due to being able to split more leaves), since the amount of vertices that compose the corridors of the graph when generated by Random Point Connect will not be too large.Efficiencies for BSP Rooms and Random:In general:Θ(n+c+(w*h)) + Θ(w*h) = Θ(n+c+(w*h)) = Θ(n+c+(w*h))In our case:Θ(1) + Θ(n) = Θ(n)14. BSP Room Placement and Drunkard’s Walk AnalysisWhen paired with Drunkard’s Walk, the minimum leaf size modifier parameters passed to BSP Room Placement is 1/8 of the graph’s width and 1/8 of the graph’s height (meaning that less rooms can be placed in the graph due to being able to split less leaves with the larger minimum leaf size), anticipating a large amount of vertices to compose the corridors of the graph when generated by Drunkard’s Walk.Efficiencies for BSP Rooms and Drunkard’s:In general:Θ(n+c+(w*h)) + Θ(m* w*h) = Θ(n+c+(w*h)(1+m))In our case:Θ(1) + Θ(n) ?= Θ(n)15. BSP Room Placement and BSP CorridorsWhen paired with BSP Corridors, as with Random Point Connect, the minimum leaf size modifier parameters passed to BSP Room Placement is 1/15 of the graph’s width and 1/15 of the graph’s height (meaning that more rooms can be placed in the graph due to being able to split more leaves), since the amount of vertices that compose the corridors of the graph when generated by BSP Corridors will not be too large.Efficiencies for BSP Rooms and BSP Corridors:In general: Θ(n+c+(w*h)) + Θ(3c*w*h) = Θ(n+c+(w*h)(1+3c))In our case: Θ(1) + ?Θ(1) = Θ(1)16. Figures3.1) Rouge Game displayed on Ascii terminal3.2) Diablo I, example of modern dungeon generation application.6.1) Random Room Placement 7.1) BSP Room Placement8.1) Random Point Connect9.1) Drunken Corridors10.1 BSP Corridors17. Map ExamplesRandom RoomsBSP RoomsRandom Rooms and Random Points ConnectRandom Rooms and Drunkard’s WalkBSP Rooms and BSP CorridorsBSP Rooms and Random Points ConnectBSP Rooms and Drunkard’s Walk18. Statistics ???????????17. Why 380????????????This set of algorithms and the stated problem relate to CSC 380 because the problem is a goal oriented problem for the comprehension of two dimensional arrays. While each algorithm successfully achieves vertex percentages being within 10% of our goal ratio of on-vertices to off-vertices and connects all rooms, they each differ in style, in the ideal ratio of rooms to corridors, and in the amount of iterations it takes to complete generating a dungeon map. Many of the algorithms share similar properties, such as using the sparsity ratio as a sentinel value, however each algorithm produces a uniquely different result. The implementation of these algorithms can not only be useful to the average game or level designer, but those who wish create original maps to use for a base or reference.18. Future Work???????????In the future, we plan on creating a method to form irregular rooms, and another to create a cave-like map with cellular automata. Another plan is to recode the project into C++ and integrate more polished GUI elements into the project with using Qt. Lastly we could to attempt a 3D implementation, especially after writing the code in C++ and being able to use it in Unreal Engine.19. Questions1) Which algorithm pair implements a brute force approach?2) Informally, how is overlapping checked differently in random-room placement and BSP-room placement algorithms?3) Which corridor-generating algorithm produces the greatest variation in the “on”-vertex : “off”-vertex ratio? ?Which trend does this algorithm produce for the room-vertex : corridor-vertex ratio when paired with either room-generating algorithm?4) What defines a “good” dungeon?5) Why do the five algorithm pairs have more efficient runtimes when considering that the dimensions of the graph are limited to be within a certain range (which is from 30x30 vertices to 500x500 vertices) versus the algorithm pair runtimes when disregarding any restraints on the graph dimensions?20. Answers1) Random room placement, random points connect2) Random-rooms checks for overlapping by checking the location of the room and its area plus three-vertex-wide border around the room, and makes sure the room will not touch any other existing room. The BSP-rooms algorithm handles overlapping prevention by partitioning space of the graph and fitting rooms into that space. ?The max room size is smaller than that partitioned space, so there would never be touching or overlapping of rooms.3) Drunkard’s walk. ?This algorithm can “walk” corridors sparsely through the dungeon, or it can take a long time finding destination rooms and wander all over. ?When paired with either random-rooms or ?BSP-rooms, this algorithm also tends to produce more corridors in respect to rooms.4) An average sparsity ratio of 40-60% (on-off), connectedness, non-linear, but ultimately subjective.5) With the graph dimensions limited to a range of certain values, many computations (such as drawing rooms and corridors) actually run in constant time at both worst and best cases rather than at, for example, width x height time. 21. SourcesGeneral: ??????????????Random:’s: of 2D dungeons:(play) (generate) 1.0 : Michael Toy & Glenn Wichman’s ?Rogue figure 1.1 : ?Blizzard’s Diablo I Dungeon maps ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download