Subject: (Article) Simple dungeon generation method Date: Tue, 19 Mar 2002 00:00:51 GMT From: Jimmy_B Organization: EarthLink Inc. -- http://www.EarthLink.net Newsgroups: rec.games.roguelike.development For the Roguelike I'm writing for the TI-89 calculator I needed a dungeon generation method that produced reasonably good results and was extremely lightweight. This is what I came up with; hope it's useful. It's a variation on the interconnected-rooms method, with a twist. Regardless of the format the map will eventually take, it is generated using an array of integers, initialized as zero. First, pick a number of rooms, depending on the size of the map. For each room (number N, starting at 1) give it a random spot and size; retry until you get a room that does not overlap with any existing rooms. Then, write N in a rectangle covering the room's area. After all the rooms are placed, pick a rnumber of separate points, and mark them as if they were 1x1 rooms (but don't do check for overlap with rooms). Find any regions X and Y which are connected (the random point-placement causes this) and replace all instances of one X with Y. Take the number of rooms placed initially plus the number of points placed initially minus the number of overlaps you detected; this is the number of corridors that must be made. To make a corridor, randomly pick a row or column; if there are two different unconnected regions X and Y in that row/column, draw a straight corridor between them, and replace X with Y. Repeat until the necessary number of corridors have been made. Then, iterate through all squares and replace zero with whatever constant you use to represent a wall and non-zero with whatever constant you use to represent open floor. Finally, place doors according to the following rules: A door will be made on any tile which... Has no door adjacent to it, directly or diagonally Has exactly two floor tile neighbors (not counting diagonals) which are opposite eachother Has at least one floor tile neighbor on a diagonal Has at least one wall tile neighbor on a diagonal This only took about 200 LOC to implement (counting comment, blank, and mostly blank lines), and is reasonably fast. For any part which involves retrying, it is necessary to keep count of the number of retries made, and start from scratch whenever that number gets to big. Sample results: ################################################################ ################################ ######################### ################################ ######################### #### + + ########## ######################### #### ##########+############# ######################### #### ########## #############+###################### # #### ########## ############# ###################### # #### ########## #### ########## ########## # #### ########## ####+########### ####### # ######+########### + ########### #######+######## ###### + ####+########### #### ##### ################## #### ########### #### ##### ##################+####+### + + ########### #### ##### ############### + ######+# + + #### ##### ##### # ###### ###### + + ##### #####+## # ###### ##################+#+##### ### # ###### ################## # ### ####### # ###### + + # ### ####### + ###### ################## # ################################################################ ################################################################ ######################## ### ######################## ######################## + + ######################## ###### + ### ################# ###### ######+##############+## ### ################# ###### # ############## ## #####+####################### ###### # ##############+## ##### #######################+###### # + + # #####+##################### # # ######+#####+# + + + + # # + ## ##### #+######## #######+######### # ############# ##### # ####### ####### #### # #############+##### # ######## ####### #### # ############ ### # ######## ####### #### # ############ ###+# + + + + #### # ############ ## #################### ############# ############ ## #### ######## ############# ########## + + #### + + + ######## ################## + + ############### ######## ############################# + ######### ######## ################################################################ ################################################################ ################## ################ #################### ################## + ###### ############# ###### ################## # ###### ####### + ###### ########## + # ###### ####### # ###### ########## # # ###### ####### # ###### ## + # # ######+####### # # ########## + ## ####### # # ########## #+######### ######+## ####### # # ##############+#+# + + + + + + + # ############## + #################### ##########+##+###+## ##############+###+#################### + ###### ## ### ## ############# ################### ########## + + + ## ####### ## + + + #######+######### ####### ## ####+#####################+### ###### ####### ## #### + ### ###### ####### + #### ################## + #### ####### ## #### ################## ###### ############# + + ################## ###### ################################################################