IEEE TRANSACTIONS ON GAMES, VOL. 16, NO. 2, JUNE 2024 459 Hierarchically Composing Level Generators for the Creation of Complex Structures Michael Beukman , Manuel Fokam , Marcel Kruger , Guy Axelrod , Muhammad Nasir , Branden Ingram , Benjamin Rosman , and Steven James Abstract—Procedural content generation (PCG) is a growing field, with numerous applications in the video game industry and great potential to help create better games at a fraction of the cost of manual creation. However, much of the work in PCG is focused on generating relatively straightforward levels in simple games, as it is challenging to design an optimizable objective func- tion for complex settings. This limits the applicability of PCG to more complex and modern titles, hindering its adoption in the industry. Our work aims to address this limitation by introducing a compositional level generation method that recursively composes simple low-level generators to construct large and complex cre- ations. This approach allows for easily-optimizable objectives and the ability to design a complex structure in an interpretable way by referencing lower-level components. We empirically demonstrate that our method outperforms a noncompositional baseline by more accurately satisfying a designer’s functional requirements in sev- eral tasks. Finally, we provide a qualitative showcase (in Minecraft) illustrating the large and complex, but still coherent, structures that were generated using simple base generators. Index Terms—Evolutionary computation, genetic algorithms, procedural content generation. I. INTRODUCTION PROCEDURAL content generation (PCG) is a research field focused on automatically generating game content, such as levels, maps, and music [1]. PCG has several benefits: It is often cheaper than manually designing content [2], and it allows for significantly more content to be generated than would otherwise be possible through human creation [3], [4]. PCG has recently garnered more attention [5], leading to impressive results in numerous games [6], [7], [8]. However, much of the research done in the field of PCG focuses on simple, 2-D tilemap games, such as Super Mario Bros, The Legend of Zelda, and maze games [8], [9], [10], [11], [12]. While these are useful testbeds, they are often very simple and do not exhibit complex structures. This focus on simplicity Manuscript received 2 February 2023; revised 26 April 2023 and 11 July 2023; accepted 16 July 2023. Date of publication 21 July 2023; date of current version 18 June 2024. (Corresponding author: Michael Beukman.) The authors are with the School of Computer Science and Applied Mathematics, University of the Witwatersrand, Johannesburg 2050, South Africa (e-mail: mcbeukman@gmail.com; fokammanuel1@students.wits.ac.za; marcel.kruger1@students.wits.ac.za; guy.axelrod1@students.wits.ac.za; umair nasir1@students.wits.ac.za; branden.ingram@wits.ac.za; benjamin.rosman1@ wits.ac.za; steven.james@wits.ac.za). This article has supplementary material provided by the au- thors and color versions of one or more figures available at https://doi.org/10.1109/TG.2023.3297619. Digital Object Identifier 10.1109/TG.2023.3297619 makes it nontrivial to generalize these methods to more complex and modern games. Furthermore, few methods focus on, or excel at, generating large and complex levels, which is a necessary step for PCG to become more mainstream [13]. This has led to recent research that applies PCG to more com- plex titles [14], [15], [16], [17], particularly Minecraft. Minecraft is a 3-D, discrete voxel-based game, making it amenable to grid- based PCG methods originally developed for 2-D tilemaps. It is also more complex than these aforementioned games and, thus, provides a useful domain to bridge the gap between traditional and modern games. Despite progress in the field, there are still several shortcom- ings to current methods. Some rely on a developer manually designing level components [18], which can be costly [2] and difficult to transfer to new games [10]. Other approaches gener- ate levels that lack core functional requirements, such as being playable [14]. Finally, some methods generate relatively small and simple structures [16], [17], limiting their applicability to complex games. Our work aims to address these limitations by proposing an approach that decomposes the problem of generating a complex and large-scale level into smaller, but manageable pieces. For instance, it is simple to generate an abstract, high-level lay- out of a town (by considering houses, roads, and gardens as the individual building blocks) while ensuring all houses are reachable via roads. Similarly, it is relatively straightforward to learn to generate a single house, garden, or farm. Composed together, however, these simple generators can easily generate a fully-fledged, and functional, town. In our method, multiple generators are hierarchically com- posed to generate large and complex structures. This is inspired by hierarchical reinforcement learning [19], where a complex task is broken down into smaller components and an agent learns how to optimally perform each subcomponent. We break the construction of a high-level structure (e.g., a town) into sim- ple subtasks (e.g., houses, gardens, etc.) and train independent agents to generate these individual components. Furthermore, instead of manually designing level elements, our method allows a designer to specify an objective function, i.e., what constitutes a “good” component. This approach has the following three main benefits: This approach has three main benefits: 1) due to the independence, users can modify the creation of each component (at different levels of abstraction) in isolation; 2) the combinatorial explosion in the number of levels that can be generated [20]; and 3) the 2475-1502 © 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information. Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. https://orcid.org/0000-0002-5468-284X https://orcid.org/0000-0002-8463-9236 https://orcid.org/0000-0003-4803-5037 https://orcid.org/0000-0002-1752-8069 https://orcid.org/0000-0002-2458-9599 https://orcid.org/0000-0001-7376-1327 https://orcid.org/0000-0002-0284-4114 https://orcid.org/0000-0003-4366-4125 mailto:mcbeukman@gmail.com mailto:fokammanuel1@students.wits.ac.za mailto:marcel.kruger1@students.wits.ac.za mailto:guy.axelrod1@students.wits.ac.za mailto:umairpenalty -@M nasir1@students.wits.ac.za mailto:umairpenalty -@M nasir1@students.wits.ac.za mailto:branden.ingram@wits.ac.za mailto:benjamin.rosman1@penalty -@M wits.ac.za mailto:benjamin.rosman1@penalty -@M wits.ac.za mailto:steven.james@wits.ac.za https://doi.org/10.1109/TG.2023.3297619 460 IEEE TRANSACTIONS ON GAMES, VOL. 16, NO. 2, JUNE 2024 ability to specify the desired structure by referencing subcom- ponents, allowing easier generation of complex levels compared to normal, non-hierarchical methods. We extend PCGNN [9], a recent method that uses neuroevo- lution and novelty search to evolve diverse level generators, by hierarchically composing these independent generators to create large and complex structures in tile-based games. We demonstrate that using composition makes it significantly easier to generate complex structures compared to using a single, noncompositional generator, an effect that becomes more pro- nounced as we increase the complexity of the low-level struc- tures. Furthermore, we can automatically generate large-scale towns and cities by specifying a few, simple objectives.1 II. BACKGROUND A. Hierarchical and Compositional Reinforcement Learning Reinforcement Learning (RL) [21] is a field focused on solving sequential decision-making problems, where an agent interacts with an environment (e.g., by placing specific tiles in a tilemap level) and receives a scalar reward signal indicating how good an action was (e.g., obtaining a high reward when removing a tile that creates a path in a maze [10]). However, long-horizon tasks require a long sequence of ac- tions to solve (e.g., generating a level by sequentially placing many tiles) and are often challenging for standard RL methods [19], [22]. Hierarchical RL addresses this by decomposing com- plex tasks into 1) smaller subtasks and 2) a top-level policy that selects which subtask to perform [19], [23]. In compositional RL, agents compose low-level skills to perform more complex behaviors, allowing tasks to be specified in a more understand- able way by referencing these skills [20]. B. Evolutionary Algorithms Many PCG methods [1], [8], [11] use aspects of evolutionary computing, a subclass of optimization algorithms that attempt to mimic natural selection [24]. Genetic algorithms (GAs) usu- ally consist of a collection (or population) of individuals, each possessing a genome, which describes the individual (e.g., an integer vector representing the height of a platform [11]). These genomes are mapped to phenotypes, which can be thought of as the result or instantiation of this individual in the actual problem domain (e.g., a level generated using the given height infor- mation). To create the next generation, the current population’s high-performing individuals (determined by the fitness function) are merged through crossover to produce children, which are then subjected to slight mutations. 1) NeuroEvolution of Augmenting Topologies: NeuroEvolu- tion of Augmenting Topologies (NEAT) [25] is a GA that evolves the weights and structure of neural networks. NEAT starts with a population of simple networks with no hidden layers, which gradually increase in complexity through evolution, to better solve the problem under consideration. 1Code is available at https://github.com/Michael-Beukman/MCHAMR. 2) Novelty Search: Novelty search [26] rewards individuals based on their novelty compared to the population, instead of their objective performance (as in traditional GAs). This results in improved exploration and can help to solve hard or deceptive2 problems. C. PCGNN PCGNN [9] is a method that uses NEAT [25] and novelty search [26] to evolve level generators. The main goal of this work is to learn reusable level generators that can quickly generate multiple different levels, as opposed to searching for single levels each time one is desired. Each individual in this population is a neural network, which can be used to generate multiple levels. To obtain a level from a network, an initial, random, tilemap is created. Then, for each tile, the neural network receives as input the surrounding tiles and outputs the current center tile. This process is repeated, sequentially, for each tile. PCGNN generally uses multiple fitness functions, which are as follows: 1) the normal novelty search objective, to incentivize exploration; 2) intragenerator novelty, which incentivizes one neural network to generate multiple diverse levels; and 3) one or more feasibility fitness functions, which describe the feasibility criteria for the specific game (e.g., solvability in a maze). PCGNN generates levels quickly and can generalize to unseen level sizes, allowing the generation of arbitrarily-sized levels without retraining. III. RELATED WORK A. General PCG Although there are numerous approaches to PCG, many fo- cus on generating simple levels and are, therefore, difficult to generalize to more complex settings, such as modern games. Search-based techniques, such as evolutionary algorithms, are commonly used to generate levels that maximize a specific objective function [1], [8], [9], [11], [17]. Similarly, the recent paradigm of PCG via RL generates levels using RL, training an agent policy to sequentially place tiles to maximize some reward [10], [16], [28]. However, it is challenging to design a monolithic objective or reward function that incentivizes the generation of complex and functional structures while being optimizable [13]. Other methods rely on a dataset of existing content (which may not be available for many games), applying machine learning to generate novel content [29], [30], [31]. 1) Generating Complex Levels: While many approaches fo- cus on simple 2-D tile-based games, such as Super Mario Bros and The Legend of Zelda, other work rather aims to generate more complex content. One notable example is the Generative Design in Minecraft (GDMC) competition, where the task is to generate an entire settlement in Minecraft [15], [18]. This competition aims to improve the generation of holistic and complex constructions (e.g., an entire, coherent town instead of just a single building) while taking the external environment into account. Many submissions to this competition, however, 2Deceptive problems are those where directly maximizing fitness can lead to being stuck in local minima [26], [27]. Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. https://github.com/Michael-Beukman/MCHAMR BEUKMAN et al.: HIERARCHICALLY COMPOSING LEVEL GENERATORS FOR THE CREATION OF COMPLEX STRUCTURES 461 focused on more hand-designed, rule-based [17] methods specif- ically designed for settlement generation, which may require significant effort to generalize to other scenarios. This has led to work that focuses on automatically generating lower-level structures one would find in a settlement, such as buildings. For instance, Green et al. [32] use constrained growth algorithms to separately generate the building and floor plan, which can be useful when customization is desired. Barthet et al. [17] use DeLeNoX [33], to evolve diverse building generators for Minecraft using an autoencoder-based novelty score. Here, the focus is on generating creative buildings, rather than generating complex and functional structures or how to combine these structures into an actual settlement. 2) Adversarial and Open-Ended Approaches: Recently, PCG has also been used to generate a large number of diverse lev- els on which machine learning agents can be trained, leading to these agents becoming more robust [34], [35]. Level generators and game-playing agents can often work in tandem, where the generator generates levels that challenge the agent. As the agent improves, the level generator must also improve to generate more complex and harder levels [7], [36]. Most of these methods, however, focus on simple games (such as mazes [37] or 2-D terrains [38]), making it unclear how to generalize them to more complex games. Furthermore, the focus is often on obtaining robust and high-performing artificial agents [37] instead of generating video game levels to be played and enjoyed by humans. Prioritizing the former could lead to overly difficult levels. These levels may also have different characteris- tics compared to human-designed ones [39], complicating their use as a substitute for manual content creation. Finally, treating the generation process as one large problem may limit the ability of the generator to create levels with enough complexity to challenge the machine learning agent. Instead, having multiple generators that solve simpler problems at different levels of abstraction could enable the generation of more complex and larger-scale structures [40]. B. Compositional PCG Much work has also been done on combining different PCG methods to generate more complex pieces of content, or even entire games [41]. For instance, Togelius et al. [42] combine an answer set programming (ASP)-based approach [43] with a GA that searches over variables for the ASP. Liapis et al. [41] advocate for game design orchestration, where different content generators are combined to generate full, coherent, games. One benefit of this compositional approach is allowing algorithms to specialize in (and thus excel at generating) specific pieces of content. However, there are still numerous open problems in this field, such as how to best coordinate automated generators and human designers. Hierarchy can also be used to improve the generation speed of PCG methods. For example, Smith and Bryson [44] find that using ASPs to generate large levels is infeasibly slow but that using hierarchy can lead to much faster generation. They first generate the high-level structure of a level and subsequently fill in the details within this fixed structure. However, this approach uses hand-designed high-level structures, which may not be easily generalizable to new games [13]. Snodgrass and Ontanon [40] also leverage hierarchy to gen- erate structures at different scales. From a set of example levels, they extract a set of high-level and low-level patterns and fit two multidimensional Markov chains to these data. To generate a level, then, the high-level model generates the structure while the low-level generator fills in the details. This method results in improved generation compared to a nonhierarchical approach but requires example levels as training data, which may not always be available [29]. Hierarchy can also be used to separately construct different aspects of a level. For instance, Dormans [45] first generates the “mission”: the high-level task that the player must complete. The physical layout of the level is then generated based on the mission. Similarly, in Unexplored [46], a graph representing the level is created by applying a set of replacement rules to create, remove, and modify nodes to obtain certain properties. This graph is then mapped onto a grid, and each node is trans- formed into a room [47]. Although this approach is hierarchical, each of the 5000 replacement rules is hand-designed, hindering application to other settings. Another use of composition is to increase the resolution of high-level sketches provided by a designer. For instance, Liapis et al. [48] allow a designer to draw a high-level, low- resolution sketch of a level. Then, using techniques such as GAs, the PCG system replaces each high-level tile with a more detailed and fleshed-out component. While this can be used to obtain a high-resolution version of a designer’s sketch, it may be less suitable when a complex structure consisting of several specific components is desired. Instead of hand-designing the high-level sketch, Liapis [49] allows the designer to specify a fitness function that is used to evolve it. The sketch is then parsed into a graph indicating which segments are connected, thereby defining constraints for each segment (such as the number and location of doors). Using these constraints, each segment is evolved and placed in the high-level sketch to form a complete level. While this work is promising, it focuses on dungeon levels, without a clear way to apply the same technique when generating other types of levels. Furthermore, this approach directly evolves the sketch and the low-level segments, meaning that evolution occurs at generation time, which may be prohibitively slow [9]. Dormans and Leijnen [50] take a different perspective: Their two-step process first generates a large amount of diverse con- tent, and the second step reorganizes this content into an actual level. While this simplifies the generation step, the content is reorganized without any hierarchical elements. Other methods create levels by generating and combining different layers, effectively composing together different gen- erators. However, these methods generally focus on iteratively furnishing a level, as opposed to hierarchically generating a complex layout. For instance, Green et al. [51] first generate the structure of a dungeon level—tiles such as walls and the floor. Then, a different method furnishes this structure by placing items such as treasure and enemies. Also following a similar layered approach, Wu et al. [52] generate natural levels. They break the level down into several layers such as ocean, land, and forests, Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. 462 IEEE TRANSACTIONS ON GAMES, VOL. 16, NO. 2, JUNE 2024 Fig. 1. Example of MCHAMR, with the (a) high-level and (b) composed towns and (c) the base components. The tree structure defining how components are combined is shown in (d), with leaf nodes corresponding to low-level tiles. (a) High-level view of a town. (b) Town after composition. (c) Base components. (d) Tree structure for (b). with each layer being generated by a cellular automaton (CA). This approach is a promising way to generate landscapes, but the handcrafted rules could be difficult to generalize to other domains. Furthermore, although CAs can generate landscapes, they may be less well-suited to generating structures that satisfy certain complex constraints—for instance, cities where houses must be reachable by roads. Dwarf Fortress [53] also uses multiple layers; here, the world, history, and several other aspects evolve over time in a rule-based simulation. This process begins by first generating the world and progressively adding more spe- cialized designed systems. The world is created by generating an elevation map using a randomized fractal, followed by multiple layers of maps including temperature, rainfall, and vegetation. Once the world is created, the simulation of civilization begins where settlements are built, trade routes are formed, and wars are fought. The simulation stops at a designated point in time, and the player starts the game in a unique living world. IV. HIERARCHICALLY COMPOSING LEVEL GENERATORS Here, we describe our approach, Multilevel Composition of Hierarchical and Adaptive Models via Recursion (MCHAMR). To illustrate our method, we first consider the example of generating a simple medieval town. At a high level, we can represent the town as a 2-D tilemap, shown in Fig. 1(a), with houses, a large castle, and roads. Each of these components, however, can be decomposed into simpler components; for instance, a house that is a single tile in Fig. 1(a) actually consists of external walls and an empty interior, as shown in Fig. 1(c). Using our composition algorithm (described below), we can use the definitions of these smaller structures together with the high-level map to obtain a fully-fledged and detailed town, shown in Fig. 1(b). Furthermore, the user has control over each component. Should they wish to make a similar town but would prefer to replace or modify a specific structure, this is possible without altering any of the other components. To implement this method in an automatic way, we require the concept of a generator g ∈ G. This object can generate a tilemap W , which is represented as a 2-D or 3-D matrix, where each element is taken from some tile set T . Each generator optionally has a tile mapping Mg : T → G that controls, which subgenerators are used when this generator places a specific tile. For instance, in the above example, the town generator’s mapping specifies that the “house” tile actually maps to the generator shown in the top-left pane of Fig. 1(c). In essence, we construct a tree (Fig. 1(d) shows the tree for the previous example), where each node is a level generator, with parent nodes generating placeholders to be filled by their children and leaf nodes producing the lowest-level, nonabstract, structures. To generate the level, we start at the root and traverse through the tree. Finally, for each generator g, we also haveSg , which indicates the size of the subtiles of this generator, i.e., the size at which the next level of the hierarchy will be generated. For example, if our town generator gtown produces an abstract tilemap of size 10 × 10, and has an associatedSgtown of 3 × 3, then the final level will have size 30 × 30. Each tile in the abstract map corresponds to a 3 × 3 block of low-level tiles. Given a set of generators, our algorithm (detailed in Algo- rithm 1) works as follows: We start with the top-level generator, which generates a tilemap (line 4 in Algorithm 1). In standard PCG, the procedure would terminate here. We instead go further and interpret each tile as an instruction to use another generator and place its output at that location (lines 14–16). Each of these lower-level generators can also be composed of generators. If at any point, though, the generator does not contain a tile mapping Mg , we end the recursion (lines 5–6). The overall generation process is illustrated in Fig. 2. This method tends to produce blocky structures since each lower-level tile is of the same size. To overcome this, we combine connected tiles of the same type into a single, larger, “logical” tile (line 12). Then, at generation time, we generate one large structure of this size, instead of many small ones. To achieve this, we find and merge contiguous rectangles by attempting to expand the dimensions of each tile one at a time until we can no longer do so. We repeat this process at every level of the hier- archy, coalescing connected tiles before recursively calling the subgenerators. Coalescing not only improves the cohesiveness of the generated structure but also gives the top-level generator more control over the scale of the lower-level components. Fig. 3 illustrates this process; Appendix D contains some example levels. Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. BEUKMAN et al.: HIERARCHICALLY COMPOSING LEVEL GENERATORS FOR THE CREATION OF COMPLEX STRUCTURES 463 Fig. 2. High-level illustration of MCHAMR. We begin with a top-level generator, which generates an abstract tilemap. Each tile in this map is an instruction to use a lower-level generator and to place its output at that location. Each of these generators can be further composed of other generators. In the end, we obtain a fully-fledged level. Fig. 3. (a) A level and (b) the result after coalescing connected tiles. Cyan tiles were coalesced into one larger tile. Now, if we are interested in using MCHAMR with automatic level generators, they must satisfy some requirements. Specif- ically, the generators must generate levels quickly (as we need to generate many low-level structures), be able to generate structures of arbitrary sizes (as the sizes of the final level and its components are not fixed beforehand), and generate many diverse levels (to prevent the different structures from looking identical, and thus uninteresting, to a player). Although our approach is agnostic to the exact level genera- tors used, one method that is particularly well-suited to act as the low-level generator is PCGNN, which satisfies all of our requirements. Additional benefits include that the training time is generally low [9] and, while we can include detailed domain knowledge, this is not required. Algorithm 1: MCHAMR. 1: // We call this initially with the top-level generator, as well as the desired size of the final level. 2: procedure GENERATE(g ∈ G, size ∈ Z 2 ∪ Z 3) 3: // Generate a map, possibly abstract, using g 4: map = MAKEMAP(g, size/Sg) 5: if Mg is null then 6: return map // Return map if this is the lowest level 7: end if 8: // Otherwise recurse to the next level in the hierarchy 9: // Create an empty map of sufficient size 10: FilledOutMap = Empty(size) 11: // For each position, tile and coalesced size in the map 12: for all pos, tile, Sc ∈ COALESCE(map) do 13: // Recursively generate using the appropriate size 14: NewMap = GENERATE(Mg(tile), size = Sg × Sc) 15: // Place this generated map at the correct location 16: FilledOutMap[pos× Sg : (pos+ Sc)× Sg] = NewMap 17: end for 18: return FilledOutMap 19: end procedure A. Using PCGNN in MCHAMR Having presented the workings of MCHAMR, we next describe a concrete approach that uses PCGNN to train the low-level Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. 464 IEEE TRANSACTIONS ON GAMES, VOL. 16, NO. 2, JUNE 2024 generators. First we train each component separately, using some objective function that describes a feasible individual. Once each of these generators has been trained, we can compose them together, needing only to specify which tiles map to which generators. This has multiple benefits; for instance, we can train and design multiple generators in parallel, obtaining a repertoire of components that can be composed later on. The approach is also modular, so we could leverage the same generator for different purposes (e.g., a house could be used in many different scenarios). Additionally, we can also train generators faster in this fac- tored way compared to training one monolithic generator. Con- sider building an n× n level that consists of some high-level structure (e.g., an abstract map consisting of single-tile houses and roads) and low-level components (e.g., a generated house). Let us compose the n× n level out of a high-level structure of size √ n×√ n and low-level components of size √ n×√ n. Now, during training, the flat method must generate levels of size n× n. For the composed method, however, we have two separate training procedures, each generating levels of size√ n×√ n. Thus, the overall time complexity3 of training the flat method would be O((n× n)) = O(n2), whereas the composed method would be O(2( √ n×√ n)) = O(n). For large levels, this speedup in training time can be quite significant. Note that during inference, however, each method generates the same amount of tiles. Furthermore, as there is no dependence between different level generators during training, we can redefine the meaning of a specific generator. For instance, a town generates a tilemap containing houses, roads, and gardens. We could also change the interpretation of the individual tiles, resulting in the same generator-generating cities that consist of towns, highways, and parks. This effectively constructs multiple different tree struc- tures, with the same generator as the root and different child generators. In general, this approach would work as long as the same feasibility criteria are valid in both cases. Finally, while PCGNN is particularly suited to be used as the low-level generator in MCHAMR, this is by no means a requirement. We could use other suitable level generators (e.g., [8], [28], [31]), hand-designed components, or a combination of these. This provides a significant amount of control and flexibility, which is useful in designing a game [54]. V. EXPERIMENTS AND RESULTS A. Experimental Setup 1) Domains: We consider two domains to demonstrate the capabilities of MCHAMR. We first quantitatively demonstrate the effects of composition in a simple 2-D town-building game. We next experiment on Minecraft to demonstrate that our approach can also be applied to more complex 3-D games. 2) Experiments: We perform three main experiments in this section. In Section V-B, we first illustrate the benefits of our hierarchical generation approach as the complexity of the 3We omit factors such as the population size and the number of generations as they are kept constant for both approaches. lower-level structures increases. The second experiment, in Section V-C, directly compares our hierarchical method against a noncompositional, flat approach. Finally, in Section V-D, we qualitatively evaluate our method by generating complex towns and cities in Minecraft. More details about our PCGNN im- plementation and our experiments, including hyperparameters and exact fitness functions, are listed in Appendices A and C, respectively. In our quantitative experiments, we assess the extent to which each method fulfills the fitness functions used during optimization. This enables us to measure how leveraging hierarchy can streamline the optimization process, resulting in improved fitness. Achieving a higher fitness value corresponds to the generator more faithfully realizing the designer’s intended outcome. B. Hierarchical Generation A compositional approach allows us to simplify the task of the top-level generator by abstracting away the details of the lower- level components. In particular, for a compositional approach to build a house, it requires a single action—placing the high-level house tile. A noncompositional approach, however, requires a large number of coordinated actions—placing each of the low- level tiles that make up the house. In this experiment, we compare these two paradigms, using a simple town level with houses, gardens, and roads. To this end, we introduce the concept of window size, a proxy for how complex the lower-level structures are. For instance, a window size of 1 × 1 means that placing a single tile is sufficient to generate a high-level structure, corresponding to the compositional setting. A larger window size, such as 2 × 2, means that a house requires four coordinated actions to build, which corresponds to a noncompositional approach. Similarly, 5 × 5 means that a house requires 25 coordinated actions, i.e., the low-level structures are harder to build. We implement this as follows (see Fig. 4 for an example): For a window size of 2 × 2, say, we consider each nonoverlapping 2 × 2 window as a single tile. If all the tiles within a window of a certain size are identical, then a single tile of that type is placed in the aggregated level. Otherwise, the tile is replaced with a “default” tile—gardens in this case. While we could change this rule (e.g., taking the majority tile), our choice simulates that a certain number of coordinated actions must be performed to generate a single component. By contrast, in the compositional case, only one action is required. In essence, the larger the window size, the more coordinated actions are required to generate a single tile. We also consider window sizes of 3 × 3, 4 × 4, 5 × 5, and 10 × 10, to evaluate how the complexity of the low-level structures influences our final performance. Note that we generate levels with an aggregated size of 10 × 10 tiles. This means that, for a window size of 2 × 2, the number of total tiles is 20 × 20, which is then aggregated into a 10 × 10 level (where each 2 × 2 block in the large level is compressed to a single tile). This experimental setup has the added benefit of being com- parable, as each method uses the same fitness functions, and the only difference is in the size of the generated structures. The fitness functions used here are 1) reachability, where houses must Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. BEUKMAN et al.: HIERARCHICALLY COMPOSING LEVEL GENERATORS FOR THE CREATION OF COMPLEX STRUCTURES 465 Fig. 4. Top row illustrates three generated levels, with window sizes of 1 × 1, 2 × 2, and 5 × 5, respectively. The bottom row shows the aggregated level, i.e., the level that each of the above ones reduces to. The red squares indicate logical tiles that were collapsed to the default tile of grass due to not being fully populated with the same tile. Here, blue tiles are houses, green tiles are gardens, and gray corresponds to roads. Fig. 5. Plot showing the maximum fitness value in the population (i.e., how “correct” the generated levels are) over time for different window sizes (i.e., how many coordinated actions are required to build the lower-level structures). The mean over 10 seeds is shown, with standard deviation shaded. be reachable via roads, and 2) a probability fitness, incentivizing a roughly equal number of house, garden, and road tiles. See Appendix C for more details. We compare the fitness of each method over time in Fig. 5, which indicates that using the compositional approach results in a higher final fitness value compared to the other, noncomposi- tional methods. The performance decreases significantly when we have a much larger 10 × 10 window size (corresponding to an overall level size of 100 × 100), where each house requires 102 = 100 coordinated actions to build. Even this is still signif- icantly fewer actions than a real Minecraft house. Overall, the results show that simplifying the task of the top-level generator by abstracting away the details of the lower-level components is beneficial. Fig. 6. Illustrating the fitness over time on 20 random town layouts for MCHAMR (consisting of the composed town and house generators) compared to the flat, noncompositional method, corresponding to vanilla PCGNN. We first compute the average fitness across 10 seeds and plot the mean and standard deviation over the 20 layouts. C. Composition Versus Flat Generation Our next experiment directly compares MCHAMR against a noncompositional baseline that generates the entire level using PCGNN. In particular, we are again interested in building towns, this time attempting to replicate a specific, randomly generated, town layout. For the compositional approach, we learn two separate gener- ators for houses and towns while the noncompositional method generates the entire level at once. In particular, we have a 25 × 25 level, consisting of a collection of 5 × 5 houses. The high-level town structure also has a size of 5 × 5. The fitness functions used did not include novelty, and measured the average overlap between the desired level and the generated one. The desired levels use one set layout for houses, where walls surround empty space, and a randomly generated town layout. We generate 20 of these random town layouts, train a separate generator on each of them, and average the fitness values obtained. The fitness results over time are shown in Fig. 6, where it is clear that PCGNNs fitness cannot touch that of MCHAMR. Our composed method achieves significantly higher fitness, and generates much more accurate levels than the flat method. See Appendix C for examples of the generated levels. D. Minecraft Showcase Finally, we evaluate our method on Minecraft and show a few qualitative examples of interesting and complex structures that were generated by MCHAMR. We use the Evocraft [14] library to place and visualize the generated structures in the game.4 Here, we generate 3-D settlements, where each town consists of houses, gardens, and roads. Additionally, to demonstrate the notion of reusing a single generator, we further generate cities using the town generator, by redefining houses to be towns. 4[Online]. Available: https://github.com/real-itu/Evocraft-py Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. https://github.com/real-itu/Evocraft-py 466 IEEE TRANSACTIONS ON GAMES, VOL. 16, NO. 2, JUNE 2024 Fig. 7. Generated city and a zoomed-in portion of an alleyway. The city and town generators are the same. Concretely, we use the following generators, with Appendix C discussing the fitness functions in more depth. 1) Town: A high-level 2-D tilemap of a town. We used several objectives, but (similarly to Section V-B) primarily rewarded reachability and having roughly an equal number of house, road, and garden tiles. 2) House: A 3-D house, incentivized to have a roof, walls, and an empty interior. The house also had novelty and intragenerator novelty objectives. 3) Garden: A 2-D tilemap with flowers, grass, ponds, and trees. The generator is incentivized to generate levels with at least one of every tile, no more than 5% pond tiles, between 20% and 70% grass tiles, and trees that are not too close to each other. Gardens and houses share the same novelty objectives. In Fig. 7, we use the same generator for the city and the town. We also show a first-person view of a specific section to illustrate the detail in each part of the generated settlement. Fig. 8 shows an annotated example of a generated city. The large, high-level structure of the city is generated by the top-level generator. Then, each tile that it places is transformed into a town by the town generator. We see that coalescing results in longer towns and the towns themselves, while not identical, contain similar repeating structures. In Fig. 9, we illustrate the benefits of incentivizing novelty during training. In this figure, we use the same houses and garden generators as before, alongside a town generator that was trained using four fitness functions: 1) intragenerator novelty; 2) novelty search; 3) reachability; and 4) a probability fitness incentivizing roughly an equal number of houses, gardens, and roads. We use the tile-pattern KL-divergence metric, with a pattern size of 2 × 2, as the novelty distance function [55] and weigh the fitness functions with ratios 1 : 1 : 4 : 4. We generate cities using the same neural network as the towns. These levels show that if we use the same generator to generate multiple levels, we can obtain qualitatively different structures while still adhering to a certain style. Furthermore, running the same training procedure multiple times—with the same hyperparameters but a different initial random seed—can result in very different structures. Details about training, novelty objectives and a comparison of novelty scores can be found in Appendix E. Fig. 8. Annotated example of a city. Finally, we note that the structures we generate are very large in the scale of standard PCG. For instance, Super Mario Bros. levels have size 114 × 14. Much of the work in Minecraft also generates relatively small structures, such as 7 × 7 × 7 mazes [16] or 20 × 20 × 20 lattices [17]. The composed towns we generate can easily be 200 × 5 × 200 or larger, totaling more than 100 000 blocks. Despite this massive scale, we are still able to generate coherent structures and sensible towns. Large settle- ments are also generated for the GDMC competition [15], but unlike our approach, these generations often require significant hand-designing effort [18]. VI. DISCUSSION The approach introduced here, MCHAMR, follows a recent trend that emphasizes the importance of more complex and open-ended creations in PCG [14], [15], [17]. We break the generation problem down into separate components and train a model for each component. This is different from much of the contemporary research on generative models, where methods tend to train one monolithic model. We believe that there are several good reasons for this factorization. First, by factorizing each salient component of a level, each of these can be changed separately without altering anything else. For instance, suppose we have a good town generator that we are satisfied with, but wish to change the house layout. If we had one large model, it would need to be entirely retrained with an alternative objective function, with no guarantee that the other pieces would indeed remain unchanged. On the other hand, when we factorize the components, each component can be changed independently. Second, if we have separate generators, each generator’s fitness function is much simpler to create (for the designer) and also simpler to optimize (for the learning algorithm). By contrast, it can be challenging to design a single monolithic objective function for complex tasks such as building a town. Even if we can create such an objective, it would likely be hard to optimize the agent. Our approach does require a designer to specify the com- ponents and desired hierarchy, as well as particular fitness functions. We believe that this gives the designer immense con- trol over the generation, as they can completely specify which components should be used, and how they should be combined. Additionally, we believe that designing a fitness function for each component—while requiring some effort—is an elegant Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. BEUKMAN et al.: HIERARCHICALLY COMPOSING LEVEL GENERATORS FOR THE CREATION OF COMPLEX STRUCTURES 467 Fig. 9. Showing three levels each from two generators (a) and (b). Each generator comes from the same experiment, just with different initial random seeds. Generator A has large swaths of gardens, with some towns around the center. Generator B generally has gardens in the bottom and left sides, with towns in the middle and along the top and right edges. way to allow designers to specify what is defined as good, without needing to design the components themselves. Our method has numerous applications, such as (partially) generating large open-world games. This would allow designers freedom in specifying certain, reusable low-level components that can be composed in numerous different ways, thereby enticing players toward exploration. Furthermore, in contrast to many other methods, we abstract away details relevant to a particular game by having separate high- and low-level generators. Separating these responsibilities could enable the abstract generators to be used in a variety of games, needing only to swap out the low-level generators for each game. Relatedly, since we independently train the generators, it would be possible to have a community-driven database of useful generators, which can then be seamlessly composed together to generate novel artifacts. This could be similar to Picbreeder [56],5 where users collectively contribute to the generation of many interesting images. VII. LIMITATIONS AND FUTURE WORK Our method is just a first step in this direction, and there are numerous avenues for future work. One promising avenue would be to use a combination of different PCG methods as low-level generators [8], [10], [16], instead of just PCGNN. For instance, we could use data-based approaches to generate the low-level components (using, e.g., existing house datasets), while generating the high-level structure using a fitness-based method. Furthermore, while our method is designed particularly with tile-based games in mind, we believe that it could be extended to other types of games by leveraging more appropriate low-level generators. Our tile-based focus may additionally lead to discretization artifacts, as components can only be placed on a rectangular grid. While this simplifies the hierarchical com- putation, it may lead to blocky-looking structures. Coalescing is one way to partially alleviate this problem: By generating at a higher resolution and coalescing similar tiles, we could obtain smoother shapes. Future work could also explore other techniques to address this limitation. While the coalescing rules we used were intentionally simple, they can be made arbitrarily complex; for instance, a designer 5[Online]. Available: https://nbenko1.github.io/ may wish to only coalesce under certain conditions, and leave most connected tiles as single components. In future work, we would like to explore the use of quality- diversity algorithms [57] to obtain a collection of diverse and high-performing low-level generators and use these interchange- ably to obtain more diverse content. Furthermore, since we use a 2-D generator as the root, the generated levels do not have any verticality. Adding vertical aspects to the levels (e.g., mountains, multistory houses, etc.) would thus be valuable. Finally, we have a clear separation between each component without any explicit communication between components, be it at the same or across different hierarchical levels. Thus, all structures must come from the top-level generator, similar to the top-down approach outlined by Liapis et al. [41], and no emergent structure is generated via the interaction of the low- level generators. This may carry some disadvantages, such as neighboring components being oblivious to one another, leading to incoherent generations. However, in our approach, this problem could be circum- vented by adding more low-level components, and expanding the tileset of the top-level generator—thereby increasing its complexity. The tradeoff here is that this may require more human effort in designing these additional generators (via their fitness functions) and altering the existing hierarchy. Despite these limitations, this independence enables us to learn modular components that can be used in several settings, whereas reuse would be more difficult if there is a tight coupling between components. Furthermore, we allow the designer to specify the structure and the high-level generator in charge of implementing it. This gives the designer more control compared to a case where the only structure is obtained by the unpre- dictable interaction of the low-level generators. Relatedly, independently training the generators does not enable them to learn how to best combine their generated components, or for one generator to make up for the shortfall of another. Instead, the designer specifies the hierarchy and fitness functions for each component. This shifts some of this responsibility onto the designer but avoids the problem where the high- and low-level generators are incompatible. Future work could consider modifications to this, where generators are jointly trained. This idea could also relate to more open-ended avenues, where the generated structures increase in complexity over time, as opposed to reaching an endpoint when the feasibility fitness is maximized [14], [17]. One way to achieve this could be Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. https://nbenko1.github.io/ 468 IEEE TRANSACTIONS ON GAMES, VOL. 16, NO. 2, JUNE 2024 learning how to dynamically compose different generators or using learned objective functions. VIII. CONCLUSION We introduce MCHAMR, a compositional approach to level generation, which leverages multiple simple generators to gen- erate large and complex structures. Our approach has multiple benefits, which are as follows: 1) being configurable, allowing the designer to choose which low-level generators are used; 2) it being straightforward to combine different generators, with- out needing to specify one monolithic fitness function; and 3) simplifying each generator’s task by decomposing the problem, potentially allowing for less training or smaller (and thus faster) models. We demonstrate that our approach improves generation com- pared to a noncompositional approach and that it is able to generate large-scale and complex settlements in Minecraft. Ultimately, we hope that this work is a step toward more complex and large-scale generations, which is necessary for the adoption of PCG in the gaming industry. ACKNOWLEDGMENT Computations were performed using HPC infrastructure pro- vided by the MSS unit at the University of the Witwatersrand. We thank the reviewers for their insightful comments, which helped to strengthen the final version of this article. REFERENCES [1] J. Togelius, G. Yannakakis, K. O. Stanley, and C. Browne, “Search-based procedural content generation: A taxonomy and survey,” IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 172–186, Sep. 2011. [2] M. Hendrikx, S. Meijer, J. Van Der Velden, and A. Iosup, “Procedural content generation for games: A survey,” ACM Trans. Multimedia Comput. Commun. Appl., vol. 9, no. 1, pp. 1–22, 2013. [3] G. Smith, “Procedural content generation: An overview,” in Level Design Processes and Experiences. Boca Raton, FL, USA: CRC Press, 2017. [4] O. Korn, M. Blatz, A. Rees, J. Schaal, V. Schwind, and D. Görlich, “Procedural content generation for game props? A study on the effects on user experience,” Comput. Entertainment, vol. 15, no. 2, pp. 1–15, 2017. [5] N. Brewer, “Computerized dungeons and randomly generated worlds: From Rogue to Minecraft [scanning our past],,” Proc. IEEE, vol. 105, no. 5, pp. 970–977, May 2017. [6] V. Volz, J. Schrum, J. Liu, S. M. Lucas, A. Smith, and S. Risi, “Evolving Mario levels in the latent space of a deep convolutional generative adver- sarial network,” in Proc. Genet. Evol. Comput. Conf., 2018, pp. 221–228. [7] L. Gisslén, A. Eakins, C. Gordillo, J. Bergdahl, and K. Tollmar, “Adver- sarial reinforcement learning for procedural content generation,” in Proc. IEEE Conf. Games, 2021, pp. 1–8. [8] S. Earle, J. Snider, M. C. Fontaine, S. Nikolaidis, and J. Togelius, “Illu- minating diverse neural cellular automata for level generation,” in Proc. Genet. Evol. Comput. Conf., 2022, pp. 68–76. [9] M. Beukman, C. W. Cleghorn, and S. James, “Procedural content gen- eration using neuroevolution and novelty search for diverse video game levels,” in Proc. Genet. Evol. Comput. Conf., 2022, pp. 1028–1037. [10] A. Khalifa, P. Bontrager, S. Earle, and J. Togelius, “PCGRL: Procedural content generation via reinforcement learning,” in Proc. AAAI Conf. Artif. Intell. Interactive Digit. Entertainment, 2020, pp. 95–101. [11] L. Ferreira, L. T. Pereira, and C. F. M. Toledo, “A multi-population genetic algorithm for procedural generation of levels for platform games,” in Proc. Genet. Evol. Comput. Conf., 2014, pp. 45–46. [12] N. Shaker et al., “The 2010 Mario AI championship: Level generation track,” IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 4, pp. 332–347, Dec. 2011. [13] J. Togelius et al., “Procedural content generation: Goals, challenges and actionable steps,” in Proc. Artif. Comput. Intell. Games, Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, 2013, pp. 61–75. [14] D. Grbic, R. B. Palm, E. Najarro, C. Glanois, and S. Risi, “EvoCraft: A new challenge for open-endedness,” in Applications of Evolutionary Computation. Berlin, Germany: Springer, 2021. [15] C. Salge, M. C. Green, R. Canaan, and J. Togelius, “Generative design in Minecraft (GDMC): Settlement generation competition,” in Proc. 13th Int. Conf. Found. Digit. Games, 2018, pp. 1–10. [16] Z. Jiang, S. Earle, M. C. Green, and J. Togelius, “Learning controllable 3D level generators,” in Proc. 17th Int. Conf. Found. Digit. Games, 2022, pp. 1–9. [17] M. Barthet, A. Liapis, and G. N. Yannakakis, “Open-ended evolution for Minecraft building generation,” IEEE Trans. Games, to be published, doi: 10.1109/TG.2022.3189426. [18] C. Salge et al., “The AI settlement generation challenge in Minecraft: First year report,” Künstliche Intelligenz, vol. 34, pp. 19–31, 2020. [19] S. Pateria, B. Subagdja, A. Tan, and C. Quek, “Hierarchical reinforcement learning: A comprehensive survey,” ACM Comput. Surv., vol. 54, pp. 1–35, 2021. [20] G. N. Tasse, S. D. James, and B. Rosman, “A Boolean task algebra for reinforcement learning,” in Proc. Int. Conf. Neural Inf. Process. Syst., 2020, pp. 9497–9507. [21] R. S. Sutton and A. G. Barto, Reinforcement Learning - An Introduction. Cambridge, MA, USA: MIT Press, 1998. [22] O. Nachum, H. Tang, X. Lu, S. Gu, H. Lee, and S. Levine, “Why does hierarchy (sometimes) work so well in reinforcement learning?,” 2019, arXiv:1909.10618. [23] B. Hengst, Hierarchical Approaches. Berlin, Germany: Springer, 2012. [24] D. E. Goldberg, Genetic Algorithms in Search. Reading, MA, USA: Addison-Wesley, 1989. [25] K. O. Stanley and R. Miikkulainen, “Evolving neural networks through augmenting topologies,” Evol. Comput., vol. 10, no. 2, pp. 99–127, 2002. [26] J. Lehman and K. Stanley, “Abandoning objectives: Evolution through the search for novelty alone,” Evol. Comput., vol. 19, no. 2, pp. 189–223, 2011, doi: 10.1162/EVCO_a_00025. [27] L. D. Whitley, “Fundamental principles of deception in genetic search,” in Foundations of Genetic Algorithms, vol. 1. New York, NY, USA: Elsevier, 1991. [28] S. Earle, M. Edwards, A. Khalifa, P. Bontrager, and J. Togelius, “Learn- ing controllable content generators,” in Proc. IEEE Conf. Games, 2021, pp. 1–9. [29] A. Summerville et al., “Procedural content generation via machine learn- ing (PCGML),” IEEE Trans. Games, vol. 10, no. 3, pp. 257–270, Sep. 2018. [30] J. Liu, S. Snodgrass, A. Khalifa, S. Risi, G. Yannakakis, and J. Togelius, “Deep learning for procedural content generation,” Neural Comput. Appl., vol. 33, no. 1, pp. 19–37, 2021. [31] T. Shu, J. Liu, and G. Yannakakis, “Experience-driven PCG via reinforce- ment learning: A Super Mario Bros study,” in Proc. IEEE Conf. Games, 2021, pp. 1–9. [32] M. C. Green, C. Salge, and J. Togelius, “Organic building generation in Minecraft,” in Proc. 14th Int. Conf. Found. Digit. Games, 2019, pp. 1–7. [33] A. Liapis, H. P. Martínez, J. Togelius, and G. Yannakakis, “Transforming exploratory creativity with DeLeNoX,” in Proc. Int. Congr. Chem. Cement, 2013, pp. 56–63. [34] N. Justesen, R. R. Torrado, P. Bontrager, A. Khalifa, J. Togelius, and S. Risi, “Illuminating generalization in deep reinforcement learning through procedural level generation,” in NeurIPS Workshop Deep Reinforcement Learn., 2018. [35] K. Cobbe, O. Klimov, C. Hesse, T. Kim, and J. Schulman, “Quantifying generalization in reinforcement learning,” in Proc. Int. Conf. Mach. Learn., 2019, pp. 1282–1289. [36] P. Bontrager and J. Togelius, “Learning to generate levels from nothing,” in Proc. IEEE Conf. Games, 2021, pp. 1–8. [37] J. Parker-Holder et al., “Evolving curricula with regret-based environment design,” in Proc. Int. Conf. Mach. Learn., 2022, pp. 17473–17498. [38] R. Wang, J. Lehman, J. Clune, and K. O. Stanley, “Paired open-ended trailblazer (POET): Endlessly generating increasingly complex and diverse learning environments and their solutions,” 2019, arXiv:1901.01753. [39] A. Dharna, J. Togelius, and L. B. Soros, “Co-generation of game levels and game-playing agents,” in Proc. AAAI Conf. Artif. Intell. Interactive Digit. Entertainment, 2020, pp. 203–209. [40] S. Snodgrass and S. Ontanon, “A hierarchical MDMC approach to 2D video game map generation,” in Proc. 11th Artif. Intell. Interactive Digit. Entertainment Conf., 2015, pp. 205–211. Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. https://dx.doi.org/10.1109/TG.2022.3189426 https://dx.doi.org/10.1162/EVCO_a_00025 BEUKMAN et al.: HIERARCHICALLY COMPOSING LEVEL GENERATORS FOR THE CREATION OF COMPLEX STRUCTURES 469 [41] A. Liapis, G. Yannakakis, M. J. Nelson, M. Preuss, and R. Bidarra, “Orchestrating game generation,” IEEE Trans. Games, vol. 11, no. 1, pp. 48–68, Mar. 2019. [42] J. Togelius, T. Justinussen, and A. Hartzen, “Compositional procedural content generation,” in Proc. 3rd Workshop Procedural Content Gener. Games, 2012, pp. 1–4. [43] A. M. Smith and M. Mateas, “Answer set programming for procedural content generation: A design space approach,” IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 187–200, Sep. 2011. [44] A. J. Smith and J. J. Bryson, “A logical approach to building dun- geons: Answer set programming for hierarchical procedural content gen- eration in Roguelike games,” in Proc. 50th Anniversary Conv. AISB, 2014. [45] J. Dormans, “Adventures in level design: Generating missions and spaces for action adventure games,” in Proc. Workshop Procedural Content Gener. Games, 2010, pp. 1–8. [46] Ludomotion, “Unexplored,” [PC Game]. Delft, The Netherlands: Ludo- motion, 2017. [47] BorisTheBrave, “Dungeon generation in Unexplored,” 2021. Accessed: Apr. 14, 2023. [Online]. Available: https://www.boristhebrave.com/2021/ 04/10/dungeon-generation-in-unexplored/ [48] A. Liapis, G. N. Yannakakis, and J. Togelius, “Sentient world: Human- based procedural cartography,” in Proc. Int. Conf. Evol. Biologically Inspired Music Art, 2013, pp. 180–191. [49] A. Liapis, “Multi-segment evolution of dungeon game levels,” in Proc. Genet. Evol. Comput. Conf., 2017, pp. 203–210. [50] J. Dormans and S. Leijnen, “Combinatorial and exploratory creativity in procedural content generation,” in Proc. Workshop PCG Games, 2013, pp. 1–4. [51] M. C. Green, A. Khalifa, A. Alsoughayer, D. Surana, A. Liapis, and J. Togelius, “Two-step constructive approaches for dungeon generation,” in Proc. 14th Int. Conf. Found. Digit. Games, 2019, pp. 1–7. [52] Z. Wu, Y. Mao, and Q. Li, “Procedural game map generation using multi-leveled cellular automata by machine learning,” in Proc. Genet. Evol. Comput. Conf., 2021, pp. 68–76. [53] T. Adams and Z. Adams, “Dwarf Fortress,” 2021. [Online]. Available: http://www.bay12games.com/dwarves/ [54] G. Lai, W. H. Latham, and F. F. Leymarie, “Towards friendly mixed initiative procedural content generation: Three pillars of industry,” in Proc. 15th Int. Conf. Found. Digit. Games, 2020, pp. 1–4. [55] S. M. Lucas and V. Volz, “Tile pattern KL-divergence for analysing and evolving game levels,” in Proc. Genet. Evol. Comput. Conf., 2019, pp. 170–178. [56] J. Secretan et al., “Picbreeder: A case study in collaborative evolution- ary exploration of design space,” Evol. Comput., vol. 19, pp. 373–403, 2011. [57] J. Mouret and J. Clune, “Illuminating search spaces by mapping elites,” 2015, arXiv:1504.04909. Authorized licensed use limited to: University of Witwatersrand. Downloaded on October 01,2024 at 09:56:55 UTC from IEEE Xplore. Restrictions apply. https://www.boristhebrave.com/2021/04/10/dungeon-generation-in-unexplored/ https://www.boristhebrave.com/2021/04/10/dungeon-generation-in-unexplored/ http://www.bay12games.com/dwarves/ << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Gray Gamma 2.2) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Warning /CompatibilityLevel 1.4 /CompressObjects /Off /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /sRGB /DoThumbnails true /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams true /MaxSubsetPct 100 /Optimize true /OPM 0 /ParseDSCComments false /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo false /PreserveFlatness true /PreserveHalftoneInfo true /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Remove /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true /Algerian /Arial-Black /Arial-BlackItalic /Arial-BoldItalicMT /Arial-BoldMT /Arial-ItalicMT /ArialMT /ArialNarrow /ArialNarrow-Bold /ArialNarrow-BoldItalic /ArialNarrow-Italic /ArialUnicodeMS /BaskOldFace /Batang /Bauhaus93 /BellMT /BellMTBold /BellMTItalic /BerlinSansFB-Bold /BerlinSansFBDemi-Bold /BerlinSansFB-Reg /BernardMT-Condensed /BodoniMTPosterCompressed /BookAntiqua /BookAntiqua-Bold /BookAntiqua-BoldItalic /BookAntiqua-Italic /BookmanOldStyle /BookmanOldStyle-Bold /BookmanOldStyle-BoldItalic /BookmanOldStyle-Italic /BookshelfSymbolSeven /BritannicBold /Broadway /BrushScriptMT /CalifornianFB-Bold /CalifornianFB-Italic /CalifornianFB-Reg /Centaur /Century /CenturyGothic /CenturyGothic-Bold /CenturyGothic-BoldItalic /CenturyGothic-Italic /CenturySchoolbook /CenturySchoolbook-Bold /CenturySchoolbook-BoldItalic /CenturySchoolbook-Italic /Chiller-Regular /ColonnaMT /ComicSansMS /ComicSansMS-Bold /CooperBlack /CourierNewPS-BoldItalicMT /CourierNewPS-BoldMT /CourierNewPS-ItalicMT /CourierNewPSMT /EstrangeloEdessa /FootlightMTLight /FreestyleScript-Regular /Garamond /Garamond-Bold /Garamond-Italic /Georgia /Georgia-Bold /Georgia-BoldItalic /Georgia-Italic /Haettenschweiler /HarlowSolid /Harrington /HighTowerText-Italic /HighTowerText-Reg /Impact /InformalRoman-Regular /Jokerman-Regular /JuiceITC-Regular /KristenITC-Regular /KuenstlerScript-Black /KuenstlerScript-Medium /KuenstlerScript-TwoBold /KunstlerScript /LatinWide /LetterGothicMT /LetterGothicMT-Bold /LetterGothicMT-BoldOblique /LetterGothicMT-Oblique /LucidaBright /LucidaBright-Demi /LucidaBright-DemiItalic /LucidaBright-Italic /LucidaCalligraphy-Italic /LucidaConsole /LucidaFax /LucidaFax-Demi /LucidaFax-DemiItalic /LucidaFax-Italic /LucidaHandwriting-Italic /LucidaSansUnicode /Magneto-Bold /MaturaMTScriptCapitals /MediciScriptLTStd /MicrosoftSansSerif /Mistral /Modern-Regular /MonotypeCorsiva /MS-Mincho /MSReferenceSansSerif /MSReferenceSpecialty /NiagaraEngraved-Reg /NiagaraSolid-Reg /NuptialScript /OldEnglishTextMT /Onyx /PalatinoLinotype-Bold /PalatinoLinotype-BoldItalic /PalatinoLinotype-Italic /PalatinoLinotype-Roman /Parchment-Regular /Playbill /PMingLiU /PoorRichard-Regular /Ravie /ShowcardGothic-Reg /SimSun /SnapITC-Regular /Stencil /SymbolMT /Tahoma /Tahoma-Bold /TempusSansITC /TimesNewRomanMT-ExtraBold /TimesNewRomanMTStd /TimesNewRomanMTStd-Bold /TimesNewRomanMTStd-BoldCond /TimesNewRomanMTStd-BoldIt /TimesNewRomanMTStd-Cond /TimesNewRomanMTStd-CondIt /TimesNewRomanMTStd-Italic /TimesNewRomanPS-BoldItalicMT /TimesNewRomanPS-BoldMT /TimesNewRomanPS-ItalicMT /TimesNewRomanPSMT /Times-Roman /Trebuchet-BoldItalic /TrebuchetMS /TrebuchetMS-Bold /TrebuchetMS-Italic /Verdana /Verdana-Bold /Verdana-BoldItalic /Verdana-Italic /VinerHandITC /Vivaldii /VladimirScript /Webdings /Wingdings2 /Wingdings3 /Wingdings-Regular /ZapfChanceryStd-Demi /ZWAdobeF ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 150 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages false /ColorImageDownsampleType /Bicubic /ColorImageResolution 900 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.00111 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /ColorImageDict << /QFactor 0.40 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 150 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages false /GrayImageDownsampleType /Bicubic /GrayImageResolution 1200 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.00083 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /GrayImageDict << /QFactor 0.40 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages false /MonoImageDownsampleType /Bicubic /MonoImageResolution 1600 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.00063 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /CHS /CHT /DAN /DEU /ESP /FRA /ITA (Utilizzare queste impostazioni per creare documenti Adobe PDF adatti per visualizzare e stampare documenti aziendali in modo affidabile. I documenti PDF creati possono essere aperti con Acrobat e Adobe Reader 5.0 e versioni successive.) /JPN /KOR /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken waarmee zakelijke documenten betrouwbaar kunnen worden weergegeven en afgedrukt. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR /PTB /SUO /SVE /ENU (Use these settings to create PDFs that match the "Suggested" settings for PDF Specification 4.0) >> >> setdistillerparams << /HWResolution [600 600] /PageSize [612.000 792.000] >> setpagedevice