Author: Peter Farabaugh (pete@tbe.net) Subject: Tapestry Dungeon Algorithms (long) Newsgroups: rec.games.roguelike.development Date: 2001-10-24 08:56:27 PST As requested, here are the algorithms I use for dungeon generation: * RDungeon RDungeon uses a variation on an algorithm developed for Tyrant. This algorithm is detailed at http://arns.freeservers.com/workshop18.html. The major enhancement that I added, is the ability to make hot points. Points that are very likely to be selected when determining a spot to build. I add hot points at the end of corridors, for example. Therefore, characters are less likely to end in dead-ends. The Algorithm: 1. Fill the Dungeon with rock. 2. Build something near the center 3. Find a starting point a. possibly take a point off the hot points list, if not empty. b. otherwise find a wall tile next to an open tile. 4. Try to place something there. a. Choose something (from weighted list) b. Figure out its dimensions. c. if all square in the area of the thing are walls then goto 4d otherwise goto 3. d. place the thing. e. add any appropriate hotpoints to the list. f. place a floor at the join point (the starting point). g. possibly place a door at the join point. 5. Repeat 3-5 until enough things are there . The types of things to be generated are determined by a weighted list stored as part of the definition of a dungeon type. Elements of this list include: -- rooms of various sizes -- corridors -- vaults -- round rooms -- caverns -- twisty passages -- composite rooms By varying the weights of these types a wide variety of dungeons can be made. Here is a sample weight table: -chances => { 55 => 'hall', 80 => 'long_hall', 90 => 'wandering_hall', 95 => 'room', 97 => 'small_room', 99 => 'large_room', 100 => 'huge_room', 101 => 'vault', 102 => 'cave', 104 => 'large_cave', } This makes good mines because the chances are weight heavily towards corridors and caves. On the other hand this: -chances => { 5 => 'hall', 10 => 'long_hall', 12 => 'wandering_hall', 50 => 'small_room', 90 => 'room', 97 => 'large_room', 100 => 'huge_room', 121 => 'vault', 122 => 'cave', 124 => 'large_cave', 126 => 'round_room', }, makes very tightly packed rooms, with very few corridors (I use it for a tomb). Each room generated (that is not a vault) can be given a type. Room types add flavor to the dungeon. Libraries, kitchens, middens, etc are examples. Each type can have a snippet of code to populate it. For example, the midden will have trash heaps added and maybe some vermin: midden => { -name => 'midden', -parent => '_base', -features => [["trashheap",'1d5']], -residents => [["_rat",'1d5']], }, Otherwise the room may be given one or more special features. Lighting, dividing walls, closets, cells, inner rooms, pools, and chests with traps or guardians are all things that can be added to rooms. A particularly cool thing that can be added to a room is a corpse with it's equipment and an undead spirit to guard it. The spirit has a AI that does not let it get out of LOS of the corpse. The code for this is in the RDungeon class (Dungeons/RDungeon.pm) * CavernDungeon The algorithm for generating caverns is surprisingly simple, but incredibly effective. It was about the 10th algorithm I tired. (The first nine being awful). I saw a post on one of the groups that briefly mentioned using a drunkards walk to generate caves. I tried it and was amazed at how effective it was. The whole cave algorithm took maybe an hour to implement. To generate a big cavern. -- start from the center of the space. Do a drunkards walk for n squares. -- repeat m times that's it! m and n can be configured and depend on the size of the dungeon. I ended up modifying the drunkard's walk to not make 180 degree turns. I added a second step where I build several very small caverns with a floor type of cave wall. This forms closed in areas, giving a more natural look. Here's a more detailed algorithm: 1. Fill the dungeon with rock. 2. determine cave dimensions. 3. Loop through n tendrils: a. start at center of cave. b. loop through m squares (tendril length) b1. place a floor tile at current location b2. move to a random adjacent square that is in bounds. 4. Choose n random points in the dungeon. a. set bounds for a small area with the point at its center a. For each repeat step 3 placing walls instead of floors. Use a small value for number and length of tendrils. 5. Maybe add a river or lake. ** variations *** caves To make a system of caves: 1. choose a spot, add it to a list of starting points, and build a cave (using the above algorithm). 2. repeat m times 3. Make corridors. a. choose and remove 2 random starting points from the list. b. connect them with a corridor (as twisty as you like). c. take another point and connect it to the 2nd point. d. repeat until out of points. *** water caverns 1. build a cavern. 2. build another cavern with a floor type of water (starting from the same center point. 3. build several smaller caverns with cave floors as islands. 3. build several smaller caverns with cave walls as closed areas. * MapDungeon This one is simple. I store an ascii representation of the terrain in a series of 128x128 data files appropriately named. map1_1.dat, map2_1.dat, etc.). I then read them in and build a grid. In addition I read a .inf file for each that lists the features like so: x,y:feature[,args] I then create and place the features. The entry for the dungeon in Data::Dungeon.pm stores general information about the dungeon (name, etc.) and where the player starts. Here's a sample section of a .dat file (obviously this needs a fixed width font to display correctly): WWWWWWWWWwwwAAAAAwwwwwAAMMMMMMMMMMMMMMMMMMMMMMMhhhhh WWWWWWWWWWWwAAAAwwWWWwAAMMMMMpMMMMMMMMMMMMMMMMMMhhhh WWWWWWWWWWWwwwwwwWWWwAAAMMMMppppMMMMMMMMMMMMMMMMMhhh WWWWWWWWWWWWWWWWWWWWwppMMMppppppMMMMMMMMMMMMMMMMMMhh WWWWWWWwwwwwWWWWWWWwppppppppppppMMMMMMMMMMMMMMMMMMMh WWWWWWWwAAAwwwwwwWWwppppppppppppMMMMMMMMMMMMMMMMMMMM WWWWWWWwwwAAwwAAwwWwppppppppppppppMMMMMMMMMMMMMMMMMM WWWWWWWWWwAAAAAAAwwWwwppppppppppppppMMMMMMMMMMMMMMMM WWWWWWWWWwwwAAAAAAwwWWwwpppppppppppppMMMMMMMMMMMMMMM WWWWWWWWWWWwAAAAAAAwWWWWwwwwwpppppppppMMMMMMMMMMMMMM WWWWWWWWWWwwAAAAAAAwWWWWWWWWWwwppppppppMMMMMMMMMMMMh WWWWWWWWWWwAAAAAAAwwWWWWWWWWWWWwppppppMMMMMMMMMMMMMM WWWWWWWWWWwAAAAwwwwwwwWWWWWWWWWWwpppppMMMMMMMMMMMMMM WWWWWWWWWWwAAAAwwwwAAwWWWWWWWWWWWwppppMMMMMMMMMMMMMM WWWWWWWWWWwAAAAAAAAAwwWWWWWWWWWWWWwppppMMMMMMMMMMMMM WWWWWWWWWwwwAAAAAAAwwWWWWWWWWWWWWWWwpppMMMMMMMMMMMMM WWWWWWWWwwAAAAAAAAwwWWWWWWWWWWWWWWwpppppMMMMMMMMMMMM WWWWWWwwwAAAAAAAAwwWWWWWWWWWWWWWWWwpppppppMMMMMMMMMM WWWWWwwAAAAAAAAAAwwWWWWWWWWWWWwwwwAppppppppMMMMMMMMM WWWWWwAAAAAAAAAAAAwWWWWWWWWWWwwAAAAAppppppppMMMMMMMM Here's a sample .inf file: 53,58:cave,-dungeon,krongs_delve 53,62:cave,-dungeon,spider_caves 56,59:town,-dungeon,dirtwater 55,58:cave,-dungeon,cardinals_tomb 55,52:cave,-dungeon,krang_thrak_lair 53,55:tower,-dungeon,gloms_tower 60,55:city,-dungeon,whispervale 50,55:castle,-dungeon,fortress_of_the_moon 55,50:e_tent,-dungeon,gypsy_camp * PatternDungeon This is very similar to the mapDungeon. The ascii pattern is stored directly in the dungeon definition along with a key that tells what the symbols mean. For example: -key => { '.' => 'grass', t => 'grass|tent', f => 'dirt|campfire', }, The syntax for an entry is terrain[|feature]. Here's a sample dungeon entry: gypsy_camp => { -name => 'Gypsy Camp', -parent => '_pattern', -tileset => 'stone', -data => qq( .................... .................... .................... .................... .................... .........t.......... .......t............ ....t........t...... .................... ..t.............t... .........f.......... ..............t..... ....t............... ..............t..... .....t....t......... .................... .................... .................... .................... .................... ), -key => { '.' => 'grass', 't' => 'grass|tent', 'f' => 'dirt|campfire', }, -entry_pt => [2,10], -leaveFromSides => 1, -nostairs => 1, -persistant => 0, -mapped => 1, -simpleMapAll => 1, }, * SettlementDungeon and GriddedSettlement These two types are used to build towns and cities. The former simply chooses elements defined in the dungeon description and places them randomly. The latter, does the same but in a grid. Both type support optional walls, and will support rivers or roads running through them. * TowerDungeon Another no brainer. Generate a big circle. Possibly generate a small circle inside. Possibly generate radial walls. Put a door on level 1. put stairs. * CastleDungeon 1. generate 4 small towers near the corners of the map. It used an ascii pattern to create the towers- its a lot easier than generating small circles. 2. join them with walls. 3. put gates in (if on the first level). 4. do the first three steps again on a smaller scale in the center. (inner keep) 5. use the BuildingDungeon algorithm to fill the inner keep with rooms. 6. optionally put small buildings randomly in the courtyard. * BuildingDungeon I still have to implement this one. It is a pain in the ass. I wrote it several years ago for another incarnation of the game (in tcl) but I've lost the code. Basically, it uses a qix (the old videogame) like algorithm to divide up the area into rooms. The trick is to get the connectivity right, so that there are no doors on corners and all the rooms are accessible. I will try to expand this document as time goes by, in the meantime feel free to post or email comments. I will also try to put together a html version of this and put it on the web site. Pete -- The Tapestry Development Website: http://tapestrygames.org Comments to: pete@tbe.net