  | MAIN | NEWS | FAQS | LINKS | ARTICLES | WORKSHOP | Send Mail To:Steve Register

 Creating A Dungeon - Brian Bucklew.
 This article was originally written for Darren Hebden's RLNews ```Section 1 : Creating A Map When creating a rogue-like game (RL from this point on), there are several points you have to address. One of the first problems you are likely to encounter is the problem of generating a suitable dungeon level. Actually, not only do you need a level, you need a pretty much infinite supply of random levels all filled to the brim with monsters, treasure, traps and other various unsundries. Our first goal will be to actually create the maze, empty. Later we can integrate code that stocks our dungeon, but for now our main goal will be to just get a pretty fair complex of passages and rooms. As with an programming problem there are many solutions, each that generates a perfectly acceptable dungeon. The first method we will discuss is a recursive one. Creating A Map : A Recursive Method This algorithm will be based around taking a solid chunk of rock, let's say 256x256 and carving a dungeon out of it using rooms and passages. We'll try to stay as simplistic as possible at the beginning, though this algorithm can be expanded to generate many different dungeon types from caves to castles, with fairly minor changes to the basic code. So we begin with a 256x256 array of blocks, each filled with stone. For our basic dungeon generation we will also need two functions: MakeRoom(), which generates a random room and then calls: MakeHall(), which generates a hall of random length. We will call MakeRoom() which will generate a randomly sized room, which will then call MakeHall() a randomly determined number of times out into the dungeon from the walls of the room. MakeHall() will generate a hall of a random length. At the hall's end, the hall will either 1:End 2:Call MakeHall() a random number of times in random directions or 3:Call MakeRoom(). Later we can improve the algorithm my making a hall stop if it hits another hall or room, or coding rooms so that they won't overlap, but for now this will suffice. lets say, using pseudocode we have: ... StartX and StartY will be integers defining the seed location ... of each room and hall ... Direction will be an integer defining the direction the ... room or hall is facing ... RecurseDepth will be used to terminate the recursion at a specific ... depth First we will define MakeRoom. void MakeRoom( StartX, StartY, Direction, RecurseDepth ) { integer X1,Y1,X2,Y2; // These variables will be used to define // the extents of the room // limit the recursion to some depth if( RecurseDepth > MAXRECURSEDEPTH ) return; DetermineExtents(); /* We need to take direction into account when determining the extents ... For Example: ( '#' = Rock '.' = open space, in standard RL convention ) ########## ########## ########## #####X.... <--- Hall calls MakeRoom at X going west. ########## ########## ########## This is the situation we want to create when determining the extents: a = x1,y1 b = x2,y2 ########## ########## #a****#### #****X.... #****b#### ########## ########## This is good... If we did not take direction into account, we would most likely end up with this: a = x1,y1 b = x2,y2 ########## ########## ###a****## ###**X.... ###****b## ########## ########## This is bad... */ CreateTheRoom(); for( x = x1 to x2 ) for( y = y1 to y2 ) Dungeon[x,y] = OpenSpace; integer R = Random(0,4); // Actually this is probably some non-linear // random choice, but this will suffice. for( x = 0 to R ) { int hx,hy,hd; DetermineLocationOfHall(); // Choose a spot along one of the walls, // Then determine the appropriate direction // (North,South,East or West) depending // on the chosen wall. MakeHall( hx,hy,hd, RecurseDepth+1 ); } } Now, MakeHall which is comparatively simple: void MakeHall( StartX, StartY, Direction, RecurseDepth ) { // Limit the recursion... if( RecurseDepth > MAXRECURSEDEPTH ) return; integer x1,y1; x1 = StartX; y1 = StartY; for( x = 1 to RandomLength ) { if( x1 or y1 is out of bounds ) return; Dungeon[x1,y1] = OpenSpace; // Note: // For ease of stepping in a direction we will define // two arrays containing the X & Y deltas of each direction x1 += DirectionXDelta[Direction]; y1 += DirectionYDelta[Direction]; } RandomChoice = Random(1,3); if( RandomChoice == 1 ) return; if( RandomChoice == 2 ) for( x = 1 to Random(0,3) ) MakeHall( x1,y1, RandomDirection, RecurseDepth+1 ); if( RandomChoice == 3 ) MakeRoom( x1,y1, Direction, RecurseDepth+1 ); } That's it... A simple recursive algorithm for carving out a dungeon. This is by no means an ideal algorthm and requires quite a bit of tweaking and a few algorithmic improvements to generate a really good dungeon, but this example serves to illustrate the method. The Author: Brian Bucklew, 18 bbucklew@inteletek.com Current RL Project : Dungeon or "This game needs a new name"... :) Projected Beta Release : Early 98 ```