Subject: Recursive dungeon generation
Date: Wed, 6 Mar 2002 10:15:54 +0000 (UTC)
From: Sheep@venus.wmid.amu.edu.pl (The Sheep)
Organization: POZMAN - http://www.man.poznan.pl/
Newsgroups: rec.games.roguelike.development

I was thinking a lot about the algorithm I proposed in the 'level build by
humans' thread and this is what i came to:

Recursive level generation.
===========================

Introduction.
-------------
This article contains some of my thoughts about level generation in
roguelike
games. It's inspired with an algorithm used in Alphaman to generate
buildings,
some articles red on Roguelike News and, that's a little odd, Bison and Yacc
input files format. The ideas may seem a little complicated and hard to
implement, but I hope the article proves useful in some way.

Overview.
---------
The idea is to describe the level in form similar to BNF (Backus-Naur Form),
used usually for describing context-free grammars.

It's natural for humans to describe large and complicated objects in terms
of
more simple ones. So we can describe a level.
For example:
        a level is either: a maze, a dungeon, a cave, a castle, etc...

        a maze is a set of connected corridors and crossroads.
        a corridor is a vertical or horizontal line of floor tiles,
surrounded
by walls on each side, opened at at least one end.
        a crossroad is a single floor tile with walls around, opened in at
least two directions.

        a dungeon is a set of rooms, crossroads and corridors.
        a room is either: a vault, a minor vault, an ordinary room.
        etc...

There are some rules not covered here. For example, we'd like to ensure each
place of the level is reachable. It's not very easy to do, so we won't try
to
describe any level type, like in the example above. We'll try to only
describe
(and then generate) some special level type, constructed by dividing rooms.

Alphaman's buildings.
---------------------
We will use an algorithm similar to this used in Alphaman. I'll first
describe
the original algorithm. It is quite simple:

1. Start with a large, empty room.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

2. Pick an acxis (horizontal or vertical) and a point within the room (far
from walls).
Let's suppose we have picked horizontal axis and point marked with '1'.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X......1........X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

3. Make a wall in selected axis, crossing the chosen point, ending at the
room's walls and with door in point '1'.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X######+########X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

4. You get two new rooms. Repeat the procedure with those of them, that arte
large enough.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X###########+###X
X...............X
X...............X
X...............X
X...............X
X######+########X
X.........#.....X
X.........+.....X
X.........#.....X
X.........#.....X
X.........#.....X
XXXXXXXXXXXXXXXXX

5. You end up with set of interconnected rooms, with exactly one way between
every two rooms. Something like a tree.

The procedure is simple, but the result is not very nice. It's always a
labirynth of rooms and you usually have to walk a lot to explore it. We'll
try
to make the result better.

Adding corridors.
-----------------
We can try to add some corridors, so our level will look more naturally and
there will be more connections between rooms.
So, instead of adding a wall, we'll add two parallel walls, making a
corridor.
We also add doorways at the ends of the corridors, so there will be more
connections. The algorithm goes like this:

1. Start with a large, empty room.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

2. Pick an acxis (horizontal or vertical) and a point within the room (far
from walls).
Let's suppose we have picked horizontal axis and point marked with '1'.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X......1........X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

3. Make a corridor in selected axis, crossing the chosen point, ending at
the
room's walls. If the walls at it's ends are not permanent, make some
doorways
there.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X###############X
X......1........X
X###############X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

4. Make some doors along the corridor's walls. There should be at leas one
door
in each wall, so you make sure all the rooms are connected.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X####+######+###X
X......1........X
X###+###########X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

5. You get two new rooms. Repeat the procedure with those of them, that are
large enough.
XXXXXXXXXXXXXXXXX
X...............X
X###+###########X
X...........2...X
X#####+#####+###X
X...............X
X...............X
X####+######+###X
X......1........X
X###+#####.#####X
X........#3#....X
X........#.+....X
X........+.#....X
X........#.#....X
XXXXXXXXXXXXXXXXX

The result doesn't look so bad, especially if the rooms left at the end are
big
enough (in the example there isn't much place).
But there is another problem -- how to fill the rooms with appropriate
contents
(that is items and monsters)? How to make sure the rooms are connected with
some logic?

Level definitions.
------------------
Here's what we can do. We don't just split in two similar rooms. We will
have
to name these rooms and provide some rules how to split them. For example,
for
a scientific level in sf roguelike:

a level may: (put some probabilities here)
        be a scientific level;

a scientific level must:
        be at least SIZE large, but not larger than SIZE;

a scientific level may:
        consist of two scientific sections, divided (horizontally or
vertically) with a scientific hall;

a scientific hall may:
        be a very wide corridor, with large doors at each end and at least
one
door at each side;
        there may be some plants or statues;
        there may be some scientific guards;
        there may be some scientific monsters;
        tehre may even be some scientific scientifists;

a scientific section may:
        consist of two scientific sections divided (horizontally or
vertically)
with a scientific corridor;

a scientific corridor may:
        be a wide corridor with open doorways at each end and at least one
door
at each side;

a scientific section must:
        be at least SIZE large, but not larger than SIZE;

a scientific section may:
        consist of two scientific labs divided (horizontally or vertically)
with a scientific corridor;

a scientific lab must:
        be at least SIZE large, but not larger than SIZE;

a scientific lab may:
        consist of two scientific labs divided with a scientific wall;

a scientific wall may:
        be a wall with door in the middle;

a scientific lab may:
        be a room with tiled floor;
        there may be some scientific artifacts;
        there may be some scientific monsters;
        there may even be some scientific scientifists;

Building a level.
-----------------
Now, let's see how to produce a random level from such an information.
First, we want to build a level. So we look at the definitions and see that
our
level may be a scientific level with such-and-such probability. But there
may
be also other level definitions, so we have to choose (randomly) which level
definition to choose. Let's suppose we have chosen the scientific level.  We
see that it has to be such-and-such big, so we provide an empty starting
room
of given size.
Now we look into the definion and see that we have to split our level in two
with a scientific hall and put a scientific section on each side. So we pick
a
point, pick an axis, put aour corridor in the middle and a scientific
section
at each side. It would be good to pay attention on the minimal size of each
of
the sections while picking a point to split the level.  Then, we have to
make
our scientific sections. As we look into definitions, we see that we have
two
choices. So we pick randomly one of them.
We can either split these sections into smaller ones, or into scientific
labs.
At some points, we'll have to do the second thing, because there will be no
place to put a scientific section (which is supposedly larger than a lab).
We
continue down the tree of level fetures, until we arrive at the 'atom' ones,
that is the features that doesn't consist of other features, and taht we can
generate using other algorithms.
Sometimes there may be need for the algorithm to 'back up' wrong decissions,
because there is no way it can get to the atoms. This is because of the size
limitations.  It's a drawback and I don't know how to make sure it ever
completes the level.
But I believe it can be solved somehow.

Level representation.
---------------------
With this algorithm you can use different level representations. The most
common, simple two-dimensional array will do. But you can also have a linked
list of features, or even a binary tree.  If there were no doors at the ends
of
the corridors, you could even generete only these parts of the level you
need
at the moment, making all the fetures from the root of the tree to the node
you
want to know.

--
The Sheep