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