a - Provas de Concursos Públicos (2024)

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SULINSTITUTO DE INFORMÁTICACURSO DE CIÊNCIA DA COMPUTAÇÃOCIRO GONÇALVES PLÁ DA SILVAAnalysis and Development of aGame of the Roguelike GenreFinal Report presented in partial fulfillment of therequirements for the degree of Bachelor ofComputer Science.Advisor: Prof. Dr. Raul Fernando Weber Porto Alegre2015 UNIVERSIDADE FEDERAL DO RIO GRANDE DO SULReitor: Prof. Carlos Alexandre NettoVice-Reitor: Prof. Rui Vicente OppermannPró-Reitor de Graduação: Prof. Sérgio Roberto Kieling FrancoDiretor do Instituto de Informática: Prof. Luís da Cunha LambCoordenador do Curso de Ciência da Computação: Prof. Raul Fernando WeberBibliotecária-Chefe do Instituto de Informática: Beatriz Regina Bastos HaroACKNOWLEDGEMENTSFirst, I would like to thank my advisor Raul Fernando Weber for his support andcrucial pieces of advisem*nt.Also, I'm grateful for the words of encouragement by my friends, usually in the formof jokes about my seemingly endless graduation process.I'm also thankful for my brother Michel and my sister Ana, which, despite not beingphysically present all the time, were sources of inspiration and examples of hard work.Finally, and most importantly, I would like to thank my parents, Isabel and Roberto,for their unending support. Without their constant encouragement and guidance, this workwouldn't have been remotely possible.ABSTRACTGames are primarily a source of entertainment, but also a substrate for developing,testing and proving theories. When video games started to popularize, more ambitiousprojects demanded and pushed forward the development of sophisticated algorithmictechniques to handle real-time graphics, persistent large-scale virtual worlds and intelligentnon-player characters. Our goal in this work is to develop a game of the roguelike genre, and to analyze andcompare the algorithmic techniques used to address the challenges of such process. Morespecifically, we are going to focus on two design features, the first one being the proceduralgeneration of dungeons, and the second being the artificial intelligence for enemies.Some of the results we have shown include, concerning generating proceduraldungeons, that the techniques of basic iteration and BSP trees can be applied to any practicaldungeon size, while cellular automata and maze generation through depth-first search must beoptimized or restricted in some ways to increase scalability. Also, when it comes to theartificial intelligence for enemies, we concluded that both stateless and state-based techniquescan be used with any practical number of concurrent actors without noticeable delay.However, we argued that state-machine actors can be designed to present more complex,flexible intelligent behavior. Regarding path-finding, we have shown that breadth-first searchis satisfactory in terms of effectiveness, while in terms of efficiency it performs poorly if nosubstantial reductions of the search space are employed.Keywords: Procedural Dungeon Generation. Artificial Intelligence. Game Development.Roguelike.Análise e Desenvolvimento de um Jogo do Gênero RoguelikeRESUMOJogos são primeiramente uma fonte de entretenimento, mas também um substrato parao desenvolvimento, teste e prova de teorias. Quando os jogos eletrônicos começaram a sepopularizar, projetos mais ambiciosos exigiram e empulsionaram o desenvolvimento desofisticadas técnicas algorítmicas para lidar com gráficos em tempo real, mundos virtuaispersistentes de larga escala e personagens não-jogadores inteligentes.Nosso objetivo neste trabalho é desenvolver um jogo do gênero roguelike, e analisar ecomparar as técnicas algorítmicas usadas para lidar com os desafios desse processo. Maisespecificamente, focaremos em duas características de design, sendo a primeira a geraçãoprocedural de geração de masmorras, e a segunda a inteligência artificial de inimigos.Alguns dos resultados que mostramos incluem, em relação à geração procedural demasmorras, que as técnicas de iteração básica e árvores de partição de espaço binário podemser aplicadas para qualquer tamanho prático de masmorra, enquanto que autômatos celulares ea geração de labirintos utilizando busca em profundidade precisam ser otimizadas ourestringidas de alguma forma para aumentar a escalabilidade. Além disso, no que concerne ainteligência artificial de inimigos, concluímos que tanto as técnicas de atores que nãoguardam estados quanto as que possuem máquinas de estados podem ser utilizadas paraqualquer número prático de atores concorrentes sem atraso notável. Porém, argumentamosque atores com máquinas de estados podem ser projetados para apresentar comportamentointeligente mais complexo e flexível. Em relação à busca de caminhos, mostramos que abusca por amplitude é satisfatória em termos de efetividade, porém em termos de eficiênciaela tem baixo desempenho se não há reduções substanciais no espaço de buscas.Palavras-Chave: Geração Procedural de Masmorras. Inteligência Artificial.Desenvolvimento de Jogos. Roguelike.LIST OF FIGURESFigure 1.1 – Typical Rogue session..........................................................................................11Figure 1.2 – Moria overworld...................................................................................................12Figure 1.3 – Tiled-graphic versions of NetHack and Angband................................................12Figure 1.4 – ADOM in graphical tiles and ASCII....................................................................13Figure 2.1 – A simple workflow for a video game...................................................................18Figure 2.2 – A procedurally generated story in Dwarf Fortress...............................................20Figure 2.3 – Skills from ADOM and Path of Exile..................................................................22Figure 3.1 – Room connectivity approaches in dungeon generation........................................27Figure 3.2 – Examples of procedurally generated mazes.........................................................30Figure 3.3 – Example of a cave-like dungeon level using cellular automata...........................31Figure 3.4 – Example of a dungeon level generated using the BSP tree..................................33Figure 3.5 – An example of dungeon level generated by using genetic algorithms.................34Figure 4.1 – A diagram representing an update loop for an emotion-based agent...................47Figure 5.1 – Workflow for the game prototype developed for the thesis.................................55Figure 5.2 – A typical session of the game developed for the thesis........................................57Figure 5.3 – Example of a dungeon level generated using the basic iteration technique.........58Figure 5.4 – Example of a dungeon level generated using the BSP Tree technique................59Figure 5.5 – Example of a dungeon level generated using the cellular automata technique....60Figure 5.6 – Example of a maze dungeon level generated using the depth-first searchtechnique...................................................................................................................................60Figure 5.7 – Dungeon size vs. time to generate using the basic iterative approach..................63Figure 5.8 – Dungeon size vs. time to generate using the BSP Tree technique........................64Figure 5.9 – Dungeon size vs. time to generate using cellular automata..................................65Figure 5.10 – Number of concurrent A.I actors vs. total processing time in the euclidean chase..........................................................................................................................................66Figure 5.11 – Number of concurrent A.I actors vs. total processing time breadh-first searchpath-finding...............................................................................................................................67LIST OF TABLESTable 3.1 – Procedural dungeon generation techniques vs. desired characteristics..................38Table 4.1 – Example of a state-based monster with tactical states and transitions...................43Table 4.2 – Degrees of elitism for three randomly chosen candidates.....................................46Table 5.1 – State-machine actor implemented for the game prototype of the thesis................61LISTA DE ABBREVIATIONS AND ACRONYMSNPC Non-Player CharacterCRPG Computer Role-playing Video GameDCSS Dungeon Crawl Stone SoupADOM Ancient Domains of MysteryFOV Field of ViewCONTENTS1 INTRODUCTION...................................................................................................91.1 Definition of Roguelike...............................................................................................................................91.2 Historical Context.....................................................................................................................................10Figure 1.1 – Typical Rogue session...................................................................................................11Figure 1.2 – Moria overworld............................................................................................................12Figure 1.3 – Tiled-graphic versions of NetHack and Angband.........................................................12Figure 1.4 – ADOM in graphical tiles and ASCII.............................................................................131.3 Objectives..................................................................................................................................................141.4 Related Work............................................................................................................................................151.4.1 Work Related to the Roguelike Genre................................................................................................151.4.2 Work Related to the Design Features.................................................................................................162 DESIGN FEATURES..........................................................................................172.1 General Features......................................................................................................................................172.1.1 Game Workflow.................................................................................................................................17Figure 2.1 – A simple workflow for a video game............................................................................182.1.2 Graphics..............................................................................................................................................182.1.3 User Interface......................................................................................................................................192.1.4 Storyline and Quests...........................................................................................................................19Figure 2.2 – A procedurally generated story in Dwarf Fortress........................................................202.1.5 Time Progression................................................................................................................................212.1.6 Character Development......................................................................................................................21Figure 2.3 – Skills from ADOM and Path of Exile............................................................................222.2 Procedural Dungeon Generation............................................................................................................222.3 Artificial Intelligence................................................................................................................................243 PROCEDURAL DUNGEON GENERATION......................................................253.1 Basic Iteration...........................................................................................................................................25Figure 3.1 – Room connectivity approaches in dungeon generation.................................................273.2 Unique Dungeon Features.......................................................................................................................273.3 Mazes.........................................................................................................................................................28Figure 3.2 – Examples of procedurally generated mazes..................................................................303.4 Cellular Automata....................................................................................................................................30Figure 3.3 – Example of a cave-like dungeon level using cellular automata....................................313.5 BSP Tree....................................................................................................................................................313.6 Genetic Algorithms...................................................................................................................................32Figure 3.4 – Example of a dungeon level generated using the BSP tree...........................................33Figure 3.5 – An example of dungeon level generated by using genetic algorithms..........................343.7 Parametrization........................................................................................................................................343.8 Analysis and Comparison........................................................................................................................35Table 3.1 – Procedural dungeon generation techniques vs. desired characteristics......................384 ARTIFICIAL INTELLIGENCE.............................................................................394.1 Path-finding...............................................................................................................................................394.2 Stateless Actors.........................................................................................................................................414.3 State-machine Actors...............................................................................................................................42Table 4.1 – Example of a state-based monster with tactical states and transitions.......................434.4 Swarm Intelligence...................................................................................................................................434.5 Genetic Algorithms...................................................................................................................................44Table 4.2 – Degrees of elitism for three randomly chosen candidates..........................................464.6 Emotion-based Actors..............................................................................................................................46Figure 4.1 – A diagram representing an update loop for an emotion-based agent............................474.7 Instancing of In-game Entities................................................................................................................474.8 Analysis and Comparison........................................................................................................................485 IMPLEMENTATION............................................................................................545.1 Experimental Environment.....................................................................................................................545.2 General Implementation..........................................................................................................................54Figure 5.1 – Workflow for the game prototype developed for the thesis..........................................55Figure 5.2 – A typical session of the game developed for the thesis.................................................575.3 Procedural Dungeon Generation............................................................................................................57Figure 5.3 – Example of a dungeon level generated using the basic iteration technique..................58Figure 5.4 – Example of a dungeon level generated using the BSP Tree technique.........................595.4 Artificial Intelligence................................................................................................................................59Figure 5.5 – Example of a dungeon level generated using the cellular automata technique.............60Figure 5.6 – Example of a maze dungeon level generated using the depth-first search technique.. .60Table 5.1 – State-machine actor implemented for the game prototype of the thesis....................615.5 Benchmarking Results.............................................................................................................................62Figure 5.7 – Dungeon size vs. time to generate using the basic iterative approach...........................63Figure 5.8 – Dungeon size vs. time to generate using the BSP Tree technique.................................64Figure 5.9 – Dungeon size vs. time to generate using cellular automata...........................................65Figure 5.10 – Number of concurrent A.I actors vs. total processing time in the euclidean chase.....66Figure 5.11 – Number of concurrent A.I actors vs. total processing time breadh-first search path-finding.......................................................................................................................................................676 CONCLUDING REMARKS AND FUTURE WORK............................................68REFERENCES.......................................................................................................701 INTRODUCTIONGames have been used throughout the history of mathematics and computer science todevelop, test and prove theories. Many are the emblematic examples of how mathematiciansand computer scientists developed algorithms to beat humans in games, one of them being theDeep Blue computer program, which won a chess match against grandmaster Garry Kasparov(IBM, 2015). When video games started to popularize, more ambitious projects demandedand pushed forward the development of more sophisticated algorithmic techniques to handlereal-time graphics, persistent large-scale game worlds and intelligent non-player characters(NPCs).Our study revolves around this substrate, but before going more into details, it isimportant to characterize the Roguelike genre, as well as to acknowledge the historicalevolution of it, so that we can have a clear vision on where our goals stand.1.1 Definition of RoguelikeOne simple definition of the term Roguelike is to say that it is characterized by gamesthat were inspired directly or indirectly by the game Rogue (PETER, 2010). Morespecifically, it is a sub-genre of role-playing games (RPGs) that share certain features with thegenre's archetype, such as the permanent death of the player character (or perma-death),random (or procedurally generated) dungeons and turn-based movement (ROGUEBASIN,2013).While that is a generally accepted loose definition (BISKUP, 2000) (LAIT, 2009)(ROGUETEMPLE, 2015), various attempts were made to define the genre more rigidly. Oneof the most well known is called the “Berlin Interpretation”, which was created at theRoguelike Development Conference 2008 (ROGUEBASIN, 2008). Several game featureswere discussed by the attendants, and were weighed as “high value” or “low value” factors.Among the high value factors, we mention:• Random environment generation: the world is procedurally generated, and most likelythe player will never see the same dungeon level twice;• Perma-death: when the player character dies, it can no longer be played with;• Turn-based: The game does not run in real-time, so it only changes whenever the useracts in some way;• Grid-based: The world is represented by a uniform grid of tiles;• Complexity: The game is complex enough so that there are several solutions to acommon goal. This is achieved by having several interactions between items and monsters;• Resource management: The player has limited resources, and must come up withstrategies to manage them in the best way possible to advance in the game;• Hack'n'Slash: Fighting a large number of monsters is an important part of the game;• Exploration: The player has to explore new dungeon levels for every new game, andmust make it so in a careful, planned way.Although we can intuitively look at a game and see if it meets some or most of theabove criteria, we believe it is difficult to establish a concrete definition for the genre.Ultimately, instead of saying which games belong to the genre, we define how “rogue-like” agame is. This means that the more features of the genre it has, the more it is considered aRoguelike. One way to better exemplify such features is to show which games have beenrelated to the genre historically, and that is what we show below.1.2 Historical ContextBeing a sub-genre of role-playing video games, our first step towards understandingRoguelikes is to start with the beginnings of the former. Computer role-playing video games(CRPGs) are games in which the player controls one character (or a party), immersed in awell-defined world, through a computer (ROLLINGS; ADAMS, 2003). They in turn wereinspired by the so-called tabletop (or “pen and paper”) role-playing games. In those, playerscreate characters and assume their roles, guided by a set of rules and the narration of aspecially designated player called the game master (COVER, 2010). Originally played face-to-face, they inspired the first CRPGs to be developed for the mainframes in the mid 1970's,being dnd one of the first examples of games inspired by the tabletop RPGs like Gary Gygax'sD&D. Other examples of games that helped define the CRPG genre include Dungeon andpedit5 and later the Ultima series (BARTON, 2007).From that substrate came the canon for the genre, which is Rogue. Inspired by theaforementioned dungeon crawlers, it presented a distinctive set of features that led otherdevelopers to create a number of variants for it, which made it the archetype for the “rogue-likes”. In every game, the player started from scratch in an unknown dungeon, and had to11fight hordes of monsters of increasing difficulty. For that, he had to pick up equipments to aidhim in his quest, as well as level up his character to become more powerful. If it was killed,the only thing that was preserved was a high-score entry showing his progress up until thatmoment (WICHMAN, 1997). Figure 1.1 shows a typical Rogue session. The “@” representsthe player, and the “H” represents an attacking hobgoblin.Figure 1.1 – Typical Rogue session. Source: Screen capture of the game by the author.Rogue was considered a very addictive game in some universities in the 1980's,especially because the combination of permanent death and randomly generated levelsresulted in a high level of replayability. Two important descendants of Rogue – Hack andMoria – were an attempt of their creatorsto extend Rogue in some way. Hack 1.0, the firstwidespread version of the game featured the same number of dungeon levels as Rogue andhad the same objective, though the number of monsters was doubled, as well as addition of apet companion, persistent levels and the need for food management (BROUWER, 2003).Moria on the other hand kept Rogue's non-persistence of dungeon levels, but added anoverworld, that is, a town where the player could trade and store items (GRABINER, 2015).Figure 1.2 shows a screenshot of a Moria session where the player is in the town. Thepresence of a town was one of the main differences from Rogue.Figure 1.2 – Moria overworld.Source: Screen capture of the game by the author.Moria and Hack in turn inspired their own, more ambitious, descendants. Angband(ANGBAND, 2015), the most important variant of Moria, had 100 dungeon levels, some ofthem with unique features called vaults, where the player would face harder enemies butwould be rewarded with treasures. It also added a number of unique items, called artifacts,which would be invaluable to defeat the large number of unique monsters also added to thegame.NetHack (NETHACK, 2015), Hack's successor, unified various independentdevelopment branches of his predecessor as a means to aggregate the additions they made.The game was ported to other operating systems (as opposed to only BSD) and featured moreplayer classes, monsters and dungeon levels, as well as more unique items and monsters. Recently, both NetHack and Angband started to support the use of tile-based graphics,as well as the traditional ASCII style characters. Figure 1.3 shows screenshots of the tiledversions of both games (NetHack to the left, Angband to the right).Figure 1.3 – Tiled-graphic versions of NetHack and Angband.Source: Screen captures of the games by the author.13In the mid 90s, Many roguelikes were developed inspired by NetHack and Angband.Of those, we cite Crawl, first released in 1995 by Linley Henzell, it followed the sameprinciple of finite resources NetHack had, which meant that the player could not stay at asame level while gaining experience. Its plot was also simple: to dive down a single dungeonand retrieve an artifact at the bottom, and subsequently rise up to the surface again. Currently,Crawl's most active variant is Dungeon Crawl Stone Soup (DCSS), and it is developed openlyby the community (DCSS, 2015).Ancient Domains of Mystery (ADOM), first released in 1994, on the other hand had amix between persistent and non-persistent dungeon levels, which left some room for the so-called “grinding”, that is, staying in the same place while defeating monsters and gainingexperience. Also, it featured a much more detailed storyline, a number of side quests and anoverworld to connect them. In 2012, ADOM underwent a crowdfunded campaign called“ADOM Resurrection”. As a result, there were several additions to the game, one of which isthe integration with NotEye, which made it possible to provide tile support to the game(BISKUP, 2012). Figure 1.4 shows a screenshot of ADOM both in ASCII (right) and tile-based graphics.Figure 1.4 – ADOM in graphical tiles and ASCII.Source: Screen captures of the game by the author.We would also like to mention Tales of Middle-Earth (ToME), arguably the mostsuccessful Angband variant (DOULL, 2013). It was developed with the intent of mergingseveral ideas from other Angband variants. Many were the additions, including an expansiveoverworld (comprising most of Middle-Earth), several branching quests and reworked racesand classes. Also, the creators wanted to further approximate the game to J.R.R Tolkien'smythos. In 2012, the ToME 4 was released, and it was renamed to Tales of Maj'Eyal, todistance itself from Tolkien's mythology and instead creating it's own original fantasy setting.Finally, we would like to mention one of the most remarkable examples of deeplycomplex roguelike experience, which is that of Dwarf Fortress. In it, you can choose to playan adventurer and explore the massive, randomly-generated world, or you can simulate thebuilding and management of a dwarven civilization. To summarize the complexity of thisgame, entire worlds are randomly generated, including civilizations, wars, towns, down tosingle individuals. Regarding battle mechanics, it simulates individual body parts (includinginternal organs) and the several types of damage they can suffer from, like cut, burn, rot andfreeze, among others (ADAMS, 2015).We observe, from the context described above, that the genre's developmentintertwines with that of modern computers in general, starting from mainframes runningsimple terminal-based dungeon crawlers, passing through games still simple in graphics,though with great depth of content, and recently even fully-fledged commercial games, withsophisticated graphics and well-developed storylines.1.3 ObjectivesIt is based on what was stated before, while keeping in mind the context of the area,that this work has been elaborated. Our goal is to develop the prototype of a game of theroguelike genre, and to analyze and compare the algorithmic techniques used to address thechallenges of such process. Of those challenges, we are going to focus on two, the first onebeing procedural generation of dungeons, and the second being the artificial intelligence forthe enemies.More specifically, we will:• Present the main challenges of developing a game of the Roguelike genre, both from acomputational and a design points of view;• For two of them, explore and compare different approaches to solve them;• Implement a prototype of a Roguelike as a means to test and validate the approachesexplored;• Analyze the results of the implementation, from a performance point of view, as wellas in terms of playability;• Conclude with the best configuration of features, and point out the direction ofpossible future work in the game.151.4 Related WorkWhile searching for related work, we focused in two aspects. First we searched forpublications related to the Roguelike genre in general. Then, we moved on to work related tothe two design features explored, that is procedural dungeon generation and monster'sartificial intelligence.1.4.1 Work Related to the Roguelike GenreBased on our research, few works aim specifically for the genre. Most of the relatedwork focus on “dungeon crawlers” in general, so we ought to name the few we have found.(ALMGREN et al, 2012) is the one that most closely relates to ours. It features thedevelopment of a space-themed roguelike, and, much like our work, analyzes design features,focusing on procedural content generation. It also talks about the artificial intelligence, albeitwith less emphasis that we do.(IBÁÑEZ, 2014), similarly to the previously pointed work, deals with thedevelopment of a roguelike, and the various design choices that come with it. It also focuseson procedural generation, by generating both random dungeon maps and random items. Itseemed to us that both theses focus on the game as the main end-product of their work,whereas we use it as a means to analyze, in theory and practice, the chosen design features indepth.Another work in the genre, but from a different perspective, was found in (AMARI,2009). In it, the authors simulate the world of a roguelike game by using artificial chemistrysimulations. Then, it removes a part of the simulation to transform it into a playable game.They show that a simple roguelike can come out of a set of chemical rules embodied into anabstract chemical model.Finally, we mention (GARDA, 2013), not as a work aimed at algorithmic techniquesor actual implementation of games, but instead as a source of informationfor the definition ofthe genre itself. It also aims to characterize the term the author calls “neo-rogue”. The termwould mean, in simple terms, the recent wave of games inspired by Rogue and roguelikes,which branched from the more strict design features of the genre and adopted other ones fromdifferent genres. These are also dubbed by the community “roguelike-like”, “roguelite” (thisone, coming from 'rogue' and 'light', was popularized specially because of the more lenientapproaches to perma-death), “roguelike-renaissance”, among others.1.4.2 Work Related to the Design FeaturesSeveral works, including two of the ones already mentioned in the previous section,focus on procedural content generation for CRPGs, especially for dungeon level (or map)generation. We chose some of the more closely related to our chosen genre, especially in thescope of dungeon crawlers.The first we mention is (VALTCHANOV, 2012), which explores the generation ofdungeon levels by using genetic programming. The author generates random maps throughmutations, crossovers and the combination of both, and then evaluates them through a fitnessfunction, which, in the author's words, “guides the search toward finding maps that arecomposed of small, tightly packed clusters of rooms that are connected to efficient paths ofhallway.” This work is our main source for dungeon generation using genetic algorithms,which we will talk about in chapter 3.The next one, (DORMANS, 2012) aims at a broader spectrum of games, which isaction adventure games. In his work, he makes a separation between missions and spaces: theformer being a logical flow of the game and the latter serving as a medium for the events tohappen. That way, by using a generative graph grammar, he creates missions in the form ofgraphs. He then uses that specification to generate spaces, as well as using shape grammarsfor generating spaces. We chose not to explore generative grammars in this work for spacereasons, so his work can be considered a complementary read to ours.Finally, in the context of procedural generation, we talk about (CRUZ, 2014). In this monograph, the author tries to evaluate the quality of procedurally-generated maps by using a number of metrics. Such metrics include the number of steps walked, items collected, money collected, among others. We studied his methodology so that we could devise our own experiments.Concerning Artificial Intelligence, aside from the two papers we mentioned in section 1.3 that dealt with the subject, we only found more general works of Artificial Intelligence foragents. Because of that, we will mention them when exploring their theory in Chapter 5.172 DESIGN FEATURESWhen designing a game, and in our case a roguelike, there are several design featureswhich must be addressed. For some of them, simple (or complex but fail-proof) solutionsexist, while others present challenges both in terms of computational complexity as well asperceived playability. In the next section we will list some of the aspects involved indeveloping the game prototype. After that, we will talk more in depth about the two chosendesign features for the thesis.2.1 General Features The following are some of the main features which must be addressed in possibly anygenre of games, but with different levels of emphasis. For example, while CRPGs are heavilybased on character development, platform adventures are less focused on it, but focusconsiderably on user interface. Thus, we will try to define them in terms of our chosen genre.2.1.1 Game WorkflowOne of the first decisions a designer must make about a game is the workflow, that is,how the different game events (or screens) will be built and how they will relate to each other.For instance, a game usually starts on a main menu, and from there different choices can bemade, such as playing a new game, loading a saved game, changing options and exiting thegame. Usually, the game workflow is represented by a finite-state machine (FSM), where theevents are states and transitions happen based on user input. Diagrams of different levels ofabstraction can be made to represent the chain of events that happen in a game. Figure 2.1shows a simple one of these.One important aspect that must be thought about is the game pace, that is, how thegame will progress. Most games fall in either the turn-based or real-time categories, althoughsome games may present a mix of the two. In turn-based progress, the game will wait for theuser-input and change the game state accordingly, while in real-time, the game will progresseven when no action is performed by the player. In the case of roguelikes, the majority is turn-based, but there are a few with real-time progression, such as Angband's variant Mangband(MANGBAND, 2015), Diablo (DIABLO, 2015), which shares most traits of a roguelike, andis thus recognized by some as one, and Pyromancer (ROGUECENTRAL, 2015).As the complexity of the game increases, so will the game workflow become morecomplicated. That means careful planning of the game features, modes and interactions mustbe made before the game starts to be developed. The game developed for this work aimed fora simple workflow, so that the chosen features could be tested at length without unnecessarycomplications. This was facilitated by the fact that both features were modular, that is, theirlogic mostly did not depend on the rest of the game, so in theory they could be applied (witheventual necessary modifications) to any game that followed roughly the same set of rules.Figure 2.1 shows a visual representation of a simple workflow for a video game.Figure 2.1 – A simple workflow for a video game.Source: Created by the author.2.1.2 GraphicsWhen it comes to displaying the game information to the user, different levels ofgraphics can be used, from pure text, to ASCII graphics to full 3D games. Roguelikes thoughhave historically represented, and are generally recognized by their ASCII characters. Thereason for that is that most of the roguelike developers choose to focus on game content ratherthan graphics, as developing a game with sophisticated graphics is resource demanding. Also,19it is important to mention that graphics alone do not make the game user-friendly. For that,the way the user inputs commands must also be taken into account when designing the game. The game developed for this work followed the tradition of ASCII, although we usecolors to make it more aesthetically pleasing. Aside from that, different colors can be used torepresent distinct creatures with the same letter. Thus, a brown “o” might represent a regularorc, while a dark blue “o” might be an orc chieftain.2.1.3 User InterfaceAs stated above, well-drawn graphics do not guarantee a good player experienceregarding the game interface. The game designer must also plan how the information will bedisplayed to the player, and also how the input devices will be applied to the game actions.For instance, most roguelikes focus the majority of commands in keyboard input, with someminor functionalities attributed to the mouse (like displaying information on mouse-hover/click). Because roguelikes tend to prioritize complexity over graphical design, thelarge number of commands in the games of the genre tend to make the learning of keybindings (which keys do what) an important part of becoming skilled at a particular game.Games such as ToME try to make better use of the mouse so as to provide more intuitive userinput.In our game, we kept to the traditional key bindings most classic roguelikes possess.Despite that, as our game has relatively simple interactions, the user will have no troublememorizing them. Aside from that, we will explore limited use of the mouse, to performsimple actionssuch as looking at dungeon entities to find out information about them.2.1.4 Storyline and QuestsWhile the storyline and quests are not usually a priority for the genre (especially forthe older games), in general there is a main goal for the game. In games such as Rogue, Moriaand Nethack, and their descendants Angband, Crawl, ADOM and others, the goal is to go tothe deepest level in the dungeon to either defeat the final boss or retrieve an important artifact.Aside from that, most of them also present side-quests. These include defeating intermediatebosses, retrieving other artifacts that facilitate or are even mandatory for the progression ofthe player, and some even include puzzles to the game (we cite NetHack's Sokoban puzzleand ADOM's labyrinth).Most of those quests and storylines are devised beforehand by the game designer,although there is research on procedurally generating them (see related work). We alsomention games with procedural quests or storylines, like Dwarf Fortress's world generation,which creates an entire world and simulates its history, down to the stories and relationshipsof individual beings (people and notable monsters). Figure 2.2 shows an example ofprocedurally generated story for an individual in Dwarf Fortress.Another recent example of such system is Middle-earth: Shadow of Mordor's NemesisSystem (MIDDLEEARTH, 2015), in which the players must gather information regarding orcwarchiefs, by finding pieces of intelligence or by killing their subalterns, so that they can findand defeat them, so as to increase the power of their weapons. Much of this system israndomly generated, including the bosses' names, strengths and weaknesses, their hierarchyand the information that leads the player to them. The bosses also do their own quests, andmay become stronger and advance in ranks on the hierarchy.In our work, we decided to keep the game objectives simple, so as to focus on otherdesign features. However, in Chapter 6 we will point out how our game could be expanded inthis direction.Figure 2.2 – A procedurally generated story in Dwarf Fortress.Source: Screen capture of the game by the author.212.1.5 Time ProgressionThe time progression of a game relates to how the player perceives the changes in thegame as time passes, based on how it shows the information on the screen and how user inputis handled. Games are usually either turn-based or real-time, as stated before. In a turn-basedgame, information will be shown to the player and the game will not progress as long as theplayer does not enter input. In real-time, on the other hand, events will continue to happeneven though the player does no action.This means, from a design viewpoint, that turn-based game progression will imply amore sequential workflow, whereas with real-time progression, the user input will be non-blocking, thus the game design will have to be adapted, or else playability problems couldarise. For instance, if there are no turns, will the monsters keep attacking the player everyclock tick even if he is not active? Also, what happens if a player and a monster try to move atthe same time to the same location?Those problems can be solved by adding a speed attribute to every individual, andmaking an action cost a certain amount of clock ticks. Also, there is a need to manage theorder of actions based on their time duration, thus a dynamic queue is a common solution.Our game uses turn-based time progression, so that no further complications arise withrelation to the artificial intelligence.2.1.6 Character DevelopmentCharacter development is one of the most (if not the most) important aspect of theCRPG genre (and its sub-genres such as roguelike), as, the name implies, the player is playinga role of a character, so it must evolve in some way. The most common way of addingcharacter development is the experience/level model. In it, the player must kill monsters orcomplete tasks in order to gain experience, which in turn makes the character advance levels.When he advances a level, he becomes stronger in general, with improvements being forinstance the increase of hit points (HP), attributes or abilities.Additionally, other systems can be added to the game to make it richer in depth. Oneof them is the skill system, in which the character learn skills as they progress the game.Those skills will aid the player in some way, in areas such as combat, crafting items andinteraction with NPCS. In roguelikes, two ways of implementing skill acquirement (andimprovement) can be recognized: by spending points gained at level up and by using the skillsa certain number of times. The skills themselves may be just a simple list, or they can beorganized into prerequisites, which becomes the so-called “skill tree”. Figure 2.3 shows botha simple skill list from ADOM, on the left, and a complex skill tree from Path of Exile (POE,2015), on the right.Figure 2.3 – Skills from ADOM and Path of Exile.Source: (left) Screen capture of ADOM by the author, (right) (IGN, 2015).Another way of enhancing character development, which usually intertwines withskills, is that of player classes and races. Both classes and races are a way to guide thegameplay to some kind of style (like being a melee fighter or a spell caster), though racesusually deal with starting characteristics and restrictions (sometimes including which classescan be played), while classes guide the way the character progresses throughout the game.In our game, we chose to keep the player simple, without races, skills or classes.However, we added experience levels which give the player attribute improvements, as wellas the possibility to collect items to aid him in the adventure.2.2 Procedural Dungeon GenerationProcedural (or random) dungeon generation, the first of our chosen design features tofocus, is part of a larger concept called Procedurally Generated Content (PCG). PCG dealswith generating content in general for games in a procedural fashion. This includes dungeonlevels, quests and plots, monsters, and even music and graphics, among others. We chose toconcentrate on this because:• It is a recognizable feature of roguelikes;• A good number of techniques were designed over time for this;• Some of those techniques may provide good results, albeit not scaling well.23Because of that, we believe testing those techniques, of varying levels of complexity,may lead us to derive useful conclusions. To start with, PCG can be categorized in a numberof ways. According to (DOULL, 2008), there are seven loose types of procedural generation,namely:• Runtime random level generation: Deals with creating dungeon levels by usingrandomized algorithms while the game is being played, generally when the playerchanges levels (in the case of roguelikes, typically when he goes down a stair).• Design of level content: It is used when the above method does not reliably producesatisfactory results. In this case, the maps are generated randomly in a level designtool, as opposed to runtime, and then supervised for correctness by a level designer.• Dynamic world generation: This technique uses a random seed to iteratively grow theplaying field by permuting it with pseudo-random number generator techniques. Itusually subdivides from a top-down perspective, thus working well with fractalgeneration and level of detail techniques.• Instancing of in-game entities: Consists of randomizing the parameters of in-gameentities (like monsters) so that large populations of unique entities can be created withinsignificant chance of repetition.• User mediated content: This technique employs PCG to generate a range ofpossibilities, which can then be chosen, and subsequentlyfine-tuned by the user ifdesired.• Dynamic systems: Refers to the modeling of systems such as weather and crowdbehavior by using PCG techniques, as a means to create (statistically) unrepeatablesituations in a game, thus increasing replayability.• Procedural puzzles and plot generation: In this category, procedural techniques areused to make the stories and challenges of a game more unpredictable. For example,randomness may be added to parts of the game's quest dependency graph, so thatconsulting walkthrough manuals would be less game-breaking.Of those, we will focus on run-time random level generation, which deals withcreating dungeons while the game is progressing. Also, we will experiment with instancing ofin-game entities in Chapter 4. This kind of PCG is related to randomizing the parameters forthe generation of content so that unique instances of content (in our case monsters) appears.2.3 Artificial IntelligenceArtificial intelligence in games refers to handling actors not controlled by the player.When it comes to monsters, this most of the time means planning ways to attack (and defeat)the player. In most roguelikes, the classic way to achieve that is to calculate the shortest pathfrom the monster to the player character, move in its direction, and attack if close enough.This type of behavior can be modeled by stateless actors, which would, at any given time,check for a set of conditions and act based on them, without considering any internalinformation they may have acquired throughout the gameplay session. Also, the problem offinding the shortest (or most interesting) path is known as path-finding.However, if the game designer intends to deliver a more interesting experience to theplayer, several techniques may be employed to enrich the NPCS. We mention some of thecategories of techniques which can be used, which we will analyze in Chapter 4:• Stateless Actors: The simplest form of actors, they consist of a series of if-conditions(generally forming a tree of conditionals) which are tested every turn. Depending onthe result of the tests, the actor will react accordingly.• State-machine Actors: By adding internal states to actors, more sophisticated behaviorcan be modeled, since they can become less “reflexive” and more “cognitive” entities.• Swarm Intelligence: Deals with using decentralized, collective behavior to add groupintelligence to actors at low computational cost.• Randomization of Parameters: Previously mentioned as “instancing of in-gameentities”, it can be used in the context of AI, in combination with other, parameter-based techniques, to generate a large number of unique actors.• Genetic Algorithms: They can be used to evolve the decision-making of a certain kindof monster by random mutations and crossovers.• Emotion-based Actors: It consists of modeling human (or animal) emotions into a setof traits and adding them to actors, thus defining their “personality”, so that theirpersonalities determine (or at least influence) their courses of action.The above categories can be used not only by themselves, but also in combinationwith each other to create unique NPC behavior for a game, as well as to generate the levels ofchallenge, fun and replayability desired by the designer. In chapter 5 we will present the set ofAI techniques implemented for our game and their practical results.253 PROCEDURAL DUNGEON GENERATIONIn this chapter, we will focus on the problem of generating dungeon levelsprocedurally. As stated in the previous chapter, we will specifically focus on run-timedungeon generation, that is, the techniques will be applied while the game is running. If theresults take a perceptible time to calculate, a loading screen (which will serve to notify theuser processing needs to be done before the game proceeds) might be needed. Otherwise, thegame will simply calculate and present the new level to the player once he reaches a changinglevel point (like stairs or portals).There are several techniques that can be used for this purpose, and all of them makeuse of randomness in some way. For that matter, a technique called random number generator(RNG) must be employed. While it is generally implicit, games actually use pseudo-randomgenerating methods (PRNGs), which have several advantages over true random methods forthis application. Two of them are:• Non-blocking generation: While true (or natural) random number sources have a limiton the throughput (because of their limited entropy over time), PRNGs havetheoretically unlimited possibilities (they must be built so as to provide enoughrepetition-free sequences for the specific application).• Predictability: For developing, testing and debugging purposes, the fact that a certainseed (initial value from which the random numbers are extracted) will always result inthe same sequence of numbers is desirable, because true random sources will generateunpredictable outputs, which makes analysis harder.In the following sections, we will present several random dungeon generationtechniques. They vary in computational complexity and perceived quality, the latter being asubjective evaluation (although we mentioned a related work which attempted to measurethem in a more principled fashion). Because of that, in section 3.8 we will analyze andcompare them in those regards. 3.1 Basic IterationThe most basic technique, present in some form in most of the classic roguelikes,consists of creating a number of randomly placed rectangles, which will represent the rooms,26and try to connect them by corridors. To make sure the player can reach every room from anystarting point, one must check the connectivity of the rooms. A simple way to guarantee thatis to always connect a newly created room to the previous one (after the first), thus makingsure every room added will keep the rooms fully reachable between each other. Onecharacteristic of this approach is: the connection of corridors will not take into accountpreviously created rooms, so some corridors may cross other rooms and corridors. Also,because new rooms are always connected to the last one created, the level may appear to be asingle path of successive rooms. Both may not be a desired effect by the designer.One way to avoid those problems is to model the dungeon into a graph, where verticeswould represent the rooms, and the corridors would be edges. Following that, the followingcan be done:• Start from any room, connect it to another room (based on some criteria, like theclosest, or even a randomly chosen room) and then do a search by using algorithmssuch as depth-first search, breadth-first search or Dijkstra's, successively until everyroom is connected to the others.• Connect every room to the others by using corridors, and then find the minimumspanning tree for this graph. After that, just prune the unwanted corridors. Oneinteresting approach to this problem is to make the center coordinate of the rooms tobe the vertices of the graph, and then apply the Delaunay Triangulation(DELAUNAY, 1934) to it. This way, the resulting edges will represent non-intersecting corridors, which may be desirable.After we guarantee the dungeon is fully connected in some way, we can add furthercorridors for an added effect. For instance, a number of corridors, based on the number ofrooms, may be added to increase the number of paths of the dungeon level. In addition to that,corridors that lead nowhere may be added, characterizing dead ends. Figure 3.1 shows thedifference between dungeon levels generated using corridor connections to previouslyinserted rooms (left) and using minimum spanning trees (right).27Figure 3.1 – Room connectivity approaches in dungeon generation.Source: Created by the author.3.2 Unique Dungeon FeaturesUnique dungeon features are predefined structures, usually modular, which can beadded to levels. While not necessarily random by themselves, those features are generallyused in combination with other procedural generation techniques so that, in the end, theirplacement and varying parameters will make them a useful tool for map variability. Dungeonfeatures can also span an entire level, although in this case the random factor of it will begenerally restricted to the monsters and items inside it. Some of the most common uniquedungeon features include:• Vaults: Rooms with pre-designed structures that can contain monsters, items and traps.The general idea behind them is to offer the player a chance for high reward, at thecost of higher danger.• Temples: Features that are geared towards the player's interaction with divinities. Theycontain an altar for the interaction to happen, and sometimes NPCs called priestswander inside it, with various divinity-related events.• Shops: Shops are dungeon features that allow players to trade items. Usually, the tradeis mediated by a special NPC called the shopkeeper. Items can be completely random,or the shop can have a theme, for instance a “magic shop” or an “armor shop”.28• Towns: Normally occupying an entire level, towns are generally the place for anumber of shops and quest-giver NPCs. While most towns in classic roguelikes havefixed building placement, there are examples where the town itself is randomlygenerated.• Fountains: Fountains are mentioned here because they greatly contribute to therandomness of a gameplay session. When drunk from, various outcomes may happen,such as simply satisfying thirst, attribute changing, mutation acquirement and others. • Vegetation: In some roguelikes, vegetation is implemented first as a way to increasevariability, but also as producing a number of interactions. Some of them includechopping trees down for wood, strategic positioning, transformation into monsters(“Ents”) and agriculture. Sparse vegetation may be randomly placed in the dungeon,or more intricate arrangements may be used for added effect, such as growth based oncellular automata (as seen in ADOM's herbs).• Waterways: As vegetation, waterways (rivers, lakes and ponds) can be used toincrease level variability, as well as being strategic geographic components. They canbe generated using techniques such as the Drunkard's Walk or cellular automata. TheDrunkard's Walk is a form of random walk, which consists of a series of random stepsin succession through a medium (in the case of waterways, randomly traversingthrough the dungeon rectangle). It differs from the regular walk in that its terminationconditions lead to a biased ending state (VOLCHENKOV; BLANCHARD, 2011).3.3 MazesAs opposed to the classic “rooms connected by corridors” approach, mazes consistmostly (if not only) of long, winding corridors, which the player must venture in order toadvance in the game. Some of the approaches to generating mazes include:• Depth-first Search: By modeling the search space to be a two-dimensional grid, withthe squares as the vertices and the transition to neighbors as the edges, as well asrandomizing the choice for neighbor visitation, a maze can be built. For differenteffects, some choices of neighbor visiting can be favored through weightedrandomness. Thus, for example, if horizontal visitation is favored over vertical, thealgorithm will produce more long horizontal corridors.29• Kruskal's algorithm (KRUSKAL, 1956): First, we create a list of all walls, and createa set for each grid square, containing initially only itself. After that, for each wall(randomly picked), if the squares divided by this wall belong to different sets, thenremove the wall and join the original sets together. Because of Kruskal's originalpurpose, which is to find a minimum spanning tree on equally weighted edges, theresulting patterns will be usually easy to solve. • Prim's algorithm (PRIM, 1957): Also being a minimum spanning tree algorithm,regular Prim will yield similar results to those of Kruskal's. However, instead ofkeeping a list of edges for it, we keep a list of adjacent grid squares. By doing that, andby randomly selecting adjacent square grids for visiting for cells with multipleneighbors, the algorithm will tend to branch out more in comparison to the regularapproach.• Cellular Automata: They can also be used for maze generation. Particularly, two rulesets for Conway's Game of Life (GARDNER, 1970) have been widely used for thispurpose, namely Maze and Mazectric (WOJTOWICZ, 2001). The rule strings forthem, which are B3/S12345 and B3/S1234, mean that a dead cell will become alive ifit has three alive neighbors, and a live cell will continue to live if it has from 1 to 4(and also 5, in the case of Mazectric) live neighbors, dying otherwise. These, based ona random starting pattern (which can be considered a seed), will result in complexmaze-like structures. While the generated patterns are more complex than the previousapproaches, it has some drawbacks, the most important one being not guaranteedconnectivity between two points. Some kind of workaround must be used to solvethat, like randomly placing the up stair and the down stair of the level, and thenrunning a search algorithm to make sure it is connected. Another possibility is togenerate a path independent of the automaton's maze, and then overwriting theresulting corridors to it, thus guaranteeing at least one path between the stairs. Anotherpossibility would be to allow the player to dig through walls, thus not needing toworry about connectivity.Figure 3.2 shows examples of mazes generated by the above techniques. Upper-leftshows a maze generated by randomized Kruskal's, upper-right by modified Prim, lower-leftby “Maze” cellular automaton rule and lower-right by “Mazectric” cellular automaton rule.30Figure 3.2 – Examples of procedurally generated mazes.Source: (upper) (WIKIPEDIA, 2015), (lower) created by the author using the Gollysimulator.3.4 Cellular AutomataAside from the previously mentioned application on mazes (for the rules Maze andMazectric), cellular automata can be used to generate natural-looking, cave-like dungeonlevels. To do this, first the designer must find an applicable rule set, by either choosing frompreviously tested ones, or by creating its own. A common rule set used in this application isknown as the “4-5” rule, which states that, in terms of dungeons, a floor will “be born” ifthere are more than five floors around it, and it will not “die” if there are four or more floorsaround it. The result of this is that floors will tend to stay in organic structures, and fine-grained cells will tend to disappear after a certain number of simulation steps.After an appropriate rule set is chosen, the designer must populate the space withfloors randomly through the dungeon space. An adequate ratio of walls/floors must be foundby experimenting, but we have found out that 40-50% of floors in the space yields the bestresults. Next, a certain number of iterations must be made in the simulation, so that therandomness is transformed into the desired cave-like appearance. Again, experimenting must31be done on the number of the steps simulated for the best results, but we have found that after3-5 steps most “artifacts” disappear from the simulation.Finally, the last step in this process is verifying connectivity, since in this process it isnot rare that isolated areas occur.One way to handle this is by using the Flood fill algorithm,which consists in, starting from a chosen point (where the stairs will be), to recursively“color” the 2D square grid until it is constrained by walls. In the end, if all the walkablespaces in the dungeon were colored, it means that it is fully connected. If there weredisconnected areas, the designer must generate another level, connect the areas in some way,refrain from adding anything on unreachable areas or make wall-digging possible. Figure 3.3shows an example of the above process. In it, “# represents walls and “.” represents walkablespaces.Figure 3.3 – Example of a cave-like dungeon level using cellular automata.Source: Created by the author.3.5 BSP TreeThe binary space partitioning method (BSP) can also be applied to level generation. Itis used to make recursive subdivisions of a given space by using hyperplanes. In the case of atwo-dimensional, grid-based game, a rectangle with the dimensions of the dungeon level is32recursively subdivided, horizontally or vertically, into two smaller rectangles of arbitrary size,resulting in the end in a structure called the BSP tree. Dungeons can be generated with thismethod by using the following procedure:1. Start with a rectangular dungeon filled with walls.2. Randomly choose a splitting direction, horizontal or vertical, and the correspondingcoordinate for the split.3. Split the dungeon rectangle into two sub-dungeons.4. Repeat steps 2 and 3 for every resulting sub-dungeon a set number of times, or untilno further subdivisions can be made, the criteria being a given minimal rectangle size.5. For each sub-dungeon, create a room inside it, with size ranging from the minimumroom size to the size of the sub-dungeon rectangle.6. After all rooms are created, connect all leaves (last sub-dungeon divisions) from thetree to their sister.7. Go up one level in the BSP Tree and connect all sub-regions to their sisters, the sameway done in step 6, thus connecting a room in a sub-region to a room in their sister, oreven to corridors.8. Repeat step 7 until every level of sub-dungeon is connected to their sister.One direct advantage of this process is that, because of the properties of a BSP Tree,the rooms will all be reachable between themselves. Figure 3.4 shows an example of thisprocess. In it, the green lines represent the binary partitions, made in 4 iterations on a 50×50map, with equal ratio for horizontal/vertical splits.3.6 Genetic AlgorithmsGenetic algorithms is a paradigm inspired by biological evolution in which candidatesfor the solution of a problem are successively mutated, crossed-over and selected through afitness function, so that better candidates evolve, eventually possibly to the best possiblesolution. When applied to dungeon generation, the candidates are the dungeon levelsthemselves (coded in some way), the mutation and crossover operations are, respectively,random changes in a dungeon level and the combination between two different candidates.33Figure 3.4 – Example of a dungeon level generated using the BSP tree.Source: Created by the author using the Eskerda dungeon simulator (ESKERDA, 2015).The first step is to find a way to represent candidates, commonly called chromosomes,in an appropriate format. One simple (yet impractical) alternative is to represent each cell ofthe dungeon level as a bit, which will be turned on if the cell is a wall, and turned offotherwise. Another way, encountered in (VALTCHANOV, 2012), is to represent the rooms ina tree structure, with the vertices representing rooms, and edges representing the corridors (orconnections) to other rooms.Then, the operations of mutation and crossover must be defined. An example ofmutation operator for tree-structured chromosomes is to randomly select a number of nodeswith at least one available door (leading to a corridor) and then add another number of childnodes to them. For crossover, we mention exchanging a random sub-tree between twocandidates.Finally, when it comes to selection, a fitness function must be defined. This means thata way to evaluate the quality of a given dungeon level must be embodied in a function, so thatthe process of selection gradually improves the candidates throughout the generations.Valtchanov's fitness model is characterized by favoring clusters of rooms with little spacebetween them, connected by efficient hallways. It also favors maps with up to three uniquefeature rooms which are close to the edges of the map. The way those characteristics are34analyzed is by first translating the tree structures to actual dungeon levels, and then evaluatingthem.After the fitness function is defined, the candidates of a generation are randomlyorganized into groups called tournaments. Then, each tournament has their candidates sortedby the fitness function, and the bottom half of them is replaced by the children of the top half.This process is repeated by a set number of generations, or until a certain threshold of fitnessis reached. Figure 3.5 shows an example of map generated by the above process. The coloredareas indicate special rooms.Figure 3.5 – An example of dungeon level generated by using genetic algorithms.Source: (VALTCHANOV, 2012).3.7 ParametrizationParametrization is the concept of adding parameters, that is, directives on how agenerator should work, and then varying their values, as a means to increase the variability ofresults. They can also be set by the player in a new game setup, as a way to generate the samelevels, in the scope of the whole dungeon, not just a single level. Common parameters are:• Seed: A constant (numeric value or string) used to build a level (or a dungeon) in aspecific manner. It is generally passed to the pseudo-random number generator, which35affects the whole dungeon (or world) creation. Multiple seeds can also be used togenerate different aspects of the game.• Motif: A parameter which represents the type of environment which will be generated.For instance, a dungeon can be set to be generated with a volcanic, aquatic orcavernous motif, among others. • Dead ends: Corridors which lead the player nowhere can be generated at a given rate,from no dead ends to many.• Unique features: This parameter can mean the rate in which unique features such asvaults, shops and temples appear throughout the dungeon (none to many).• Dungeon size: The size of the dungeon can be decided by a parameter. It is importantto note that if the dungeon size is bigger than the game window size, a decision mustbe made on what approach will be used to handle that. For instance, the game may bealways centered on the player, so the game draws only the parts visible to the player'scurrent position. Another way is to use a sliding window, in which the game slides theviewing screen a certain amount whenever the player reaches the edges of it.• Type of corridors: Corridors can be set to form straighter or more convoluted patterns.• Difficulty: Sets the difficulty the player will encounter throughout the game. It canaffect the game in different ways, such as the monsters' spawn rate, monster strengthand intelligence, the number of traps, among others.3.8 Analysis and ComparisonIn this section we will briefly analyze every technique described above, and comparethem both in complexity and apparent quality of the results, starting from the standarddungeon algorithm. When creating a dungeon with classic “rooms and corridors” layout, thetechnique of iteratively creating a room and connecting it to the last created room with acorridor will yield results in linear time. If we call the operation of setting a tile to walkablesetToWalkable, let nbe the maximum number of rooms to be created, and for every roomcreation we will have to set to walkable a rectangle of cells with maximum height h and widthw, we will have, in the worst case, n×w×h operations of setToWalkable. However, since inpractice w and h are bounded to a small maximum number (for example 10) due to the usualsize constraint of rooms in roguelikes, we can say that the algorithm will run the so-calledmakeRoom n times, making it linear in the number of rooms. In fact, experiments showed that36after a number of rooms have been created, most room creation attempts will fail because oflack of space, thus this technique will run fast enough even for big dungeon sizes.Concerning unique dungeon features, most of them, like shops, temples and castleshave fixed size, thus their construction can be considered constant in time complexity.However, features such as waterways or vegetation may use techniques which do not run inconstant time. For techniques which use Cellular Automata, we will mention them below. Forthe creation of a waterway using the Drunkard Walk, which we call drunkardWalk, we defineits size by the number of cells we want it to occupy. In theory, this number, which we can callwaterwaySize, is bounded by the dungeon size, which is w×h. So, in the worst case,waterwaySize = w×h, and drunkardWalk(waterwaySize) ∈ O(w×h). In practice, waterwaysrarely occupy the whole dungeon, instead they are a small fraction of the dungeon, like 5%.This means that it has a negligible computational cost even for large dungeons.Mazes, on the other hand, will need slightly more processing time to be created. Usingdepth-first search will result in every possible walkable cell being visited exactly once, whichmeans, if we call the number of cells (or vertices) V = w×h, and E = V×4 (because each cellwill have four visitable neighbors in the case of non-diagonal maze-creation, not countingmap edges), they will run in O(V) time complexity. It is important to note that, since thistechnique may involve deep recursion, especially at large dungeon sizes, it may cause stackoverflow problems, thus it is advised to program it in an iterative way, by storingbacktracking information in the maze itself.Kruskal and Prim, being minimum spanning tree algorithms, will involve furthercalculations such as sorting the weights of the edges, they will run slower than the depth-firstsearch. Kruskal was shown to run in O(E log V), while Prim runs in O(|E| + |V| log |V|) if ituses a Fibonacci heap and an adjacency list as data structures. In practical terms, any of thesealternatives will run efficiently enough for any practical dungeon size.In the case of Cellular Automata, the most intuitive way of running the simulation fora fixed-size dungeon level is, at every generation, to calculate the number of neighbors foreach cell and decide if they become alive, stay alive or die. This means, for g generations,dungeon size w×h, and the maximum number of neighbors for a cell being nine (including thecell itself), the algorithm will perform 9×w×h×g cell updates. However, every application ofcellular automata mentioned in this work uses a fixed, small number of generations, forexample five. This means that, in our case, the worst case will be O(w×h). In practice,because of this fixed number of generations, we can assume that all of the applications ofcellular automata in this paper will run efficiently enough for any practical map sizes.37Concerning the binary space partitioning technique described in this thesis, the numberof subdivisions made in the map space will be constrained by a set number of iterations, oruntil it reaches a minimum rectangle size. For the version with set number of subdivisions k,the algorithm will have to run the makeRoom function 2k times. Thus, it is important to keepk small, or else, for large maps, the amount of function calls may exceed the stack size.Fortunately, the number of iterations is generally a small number, like five. According to (VALTCHANOV, 2012), experiments with on-demand dungeongeneration by using genetic algorithms, setting the number of generations to 500 and amaximum of 100 rooms, dungeons were generated in approximately 30 seconds, using asingle core of a 2.4 GHz processor, with room for optimization. This means that, if thistechnique were to be used in runtime dungeon generation, some kind of measure should beemployed so that this processing time would not affect gameplay. Solutions include adding aloading screen after the user changes a level and generating the next level while the user isexploring the current level.Finally, as parametrization is simply a way to increase variability throughconfiguration, and not a technique to generate maps by itself, the running time in this casedepends on the techniques employed by a given configuration.Next, we will compare the above regarding overall quality. While this is a highlysubjective measure, we can get some guidelines by talking about desirable characteristics theycan have. Some of them include:• Scalability: This relates to how it scales on larger dungeon sizes. It is tightly related tocomputational complexity.• Connectivity: Whether it is fully connected by default, or further methods must beemployed to guarantee it.• Combinability: Ease of combination with other techniques or unique design features.• Reliability: Relates to how much the technique is expected to give useful results in apractical time.• Variability: How different each random generation of this technique will be from theothers. • Uniqueness: This means whether the technique creates results that are not made byothers. 38Based on the above characteristics, and keeping in mind the subjectivity of quality, wechose to compare the techniques visually by using a table. In table 3.1, we list the techniques and cross them with the desired characteristics. When no comparison is applicable, “--” is used.Table 3.1 – Procedural dungeon generation techniques vs. desired characteristics.Technique Scalability Connectivity Combinability Reliability Variability UniquenessStandard Scalable Fully connected Yes Reliable Medium Not uniqueUnique Features Scalable -- Yes Reliable -- UniqueMazes Scalable1 Fully connected No Reliable Low Not UniqueCellular Automata Scalable2 Verification needed No Non-reliableHigh UniqueBSP Tree Non-scalable Fully connected Yes Reliable Medium Not uniqueGenetic Algorithms Non-scalable Fully connected Yes Non-reliableMedium Not UniqueParametrization Scalable -- -- Reliable High UniqueSource: Created by the author.1 After implementing the technique, we discovered that it can only be considered scalable if it is implemented inan iterative way.2 After implementing the technique, we discovered that the number of generations must be small, or an efficientevaluation technique must be applied for it to be scalable.394 ARTIFICIAL INTELLIGENCEIn this chapter, we will describe, analyze and compare a number of artificialintelligence techniques which can be applied to agents in games. More specifically, we willexpress them in terms of their application in roguelikes. One distinction which comes up when defining artificial intelligence for games is thatof “pseudo-intelligence”. This means that, even though the actor works as intended, which isto provide challenge and fun for the player's gameplay, the actual programming maysometimes be considered “mindless”. For instance, agents following a set of if-then rules maynot be considered rational, whereas an agent which possesses complex tactical planning,learning capabilities and emotions that regulate its interactions with the environment,