放个小东西。。。Random Dungeon Design

helanmouse · 发表于 2008-4-30 23:02:40

http://www.aarg.net/~minam/dungeon_design.html

Random Dungeon Design
The Secret Workings
of
Jamis Buck's Dungeon Generator

So you've tried my Dungeon Generator once or twice, and it's got you thinking. Perhaps you're a programmer and would like to incorporate similar features in a program of your own. Or maybe you're not a programmer, but would be interested in an overview of how this program works.
Either way, I've been asked how this random dungeon generator works many, many times, and I finally decided that, to save myself time, I'd just put up the description on a web page.
If you find this explanation useful, please let me know. Likewise, if you feel that I was too technical, or not techinical enough, or too ambiguous, let me know that, too, and I can try and improve it.
Please send all comments, questions, suggestions, and flames to:

[email protected]

I. A Dungeon is a MazeFirst of all, it is helpful to think of any dungeon as simply a maze—a collection of corridors that turn every which way. The first part of generating any dungeon, then, is to create a random maze.
Now, there are lots of different ways to generate mazes (for some idea of how many different types of mazes and algorithms there are, check out the Maze Algorithms page at Think Labyrinth). For the dungeon generator, I just picked a straightforward algorithm that I'm pretty familiar with—it's a variation on the "Hunt-and-Kill" algorithm. The algorithm creates a 2D, normal, orthoganol, perfect maze, which simply means that the maze is rectangular, with all passages intersecting at right angles, and that there are no loops or inaccessible areas in the maze.
Here's how the algorithm I picked works. Feel free to substitute this one with any other algorithm.

x

y

unvisited

visited

current cell

invalid

visited

C

Once that process finishes, you'll have your maze! There are a few variations you can do to make the maze more interesting; for example, my dungeon generator has a parameter called "randomness". This is a percentage value (0–100) that determines how often the direction of a corridor changes. If the value of randomness is 0, the corridors go straight until they run into a wall or another corridor—you wind up with a maze with lots of long, straight halls. If the randomness is 100, you get the algorithm given above—corridors that twist and turn unpredictably from cell to cell.
II. Mazes vs. DungeonsIt is important to note that the algorithm given above results in no loops in the maze. It is also important to note that the algorithm results in a dense maze—that is, every cell contains a corridor.
This "pure" maze is probably not what you had in mind when you asked for a dungeon. For example, sometimes a dungeon passage intersects with another passage, or with itself, forming a loop. Also, an underground dungeon may cover a lot of territory, but not fill every square meter of rock—it is probably sparse, as opposed to dense.
There are two steps I used to convert the maze into something more like a dungeon (though still lacking rooms).
The first step involves a parameter I called sparseness. It is an integer value; you may want to experiment with it to arrive at a value (or set of values) that work best for you. It is used as follows:

sparseness

After sparsifying the maze, you should wind up with large "blank" gaps, where no passages go. The maze, however, is still perfect, meaning that it has no loops, and that no corridor is inaccessible from any other corridor.
The next step is to remove dead-ends by adding loops to the maze. The "deadends removed" parameter of my generator is a percentage value that represents the chance a given dead-end in the maze has of being removed. It is used as follows:

[li]Look at every cell in the maze grid. If the given cell is a dead-end cell (meaning that a corridor enters but does not exit the cell), it is a candidate for "dead-end removal." [/li][li]Roll d% (ie, pick a number between 1 and 100, inclusive). If the result is less than or equal to the "deadends removed" parameter, this deadend should be removed. Otherwise, proceed to the next candidate cell. [/li][li]Remove the dead-end by performing step #3 of the maze generation algorithm, above, except that a cell is not considered invalid if it has been visited. Stop when you intersect an existing corridor. [/li]So, now you have something looking more like a dungeon. All it lacks, now, are rooms…
III. Room Generation and PlacementThis was perhaps the trickiest step. Looking at my generator, you'll see three parameters: "room count" (R[sub]n[/sub]), "room width", (R[sub]w[/sub]), and "room height" (R[sub]h[/sub]).
Generating rooms is actually easy: R[sub]w[/sub] is just a random number between the minimum and maximum widths. R[sub]h[/sub] is generated similarly.
Placing the rooms was trickier. The idea is to find a place in the maze where the given room overlaps a minimum of corridors and other rooms, but where the room touches a corridor in at least on place. To this end, I implemented a weighting system.
The program tries to put the room at every possible place in the dungeon. The algorithm works as follows:

infinity

W[sub]min[/sub]

R[sub]w[/sub]

W[sub]max[/sub]

H[sub]min[/sub]

R[sub]h[/sub]

H[sub]max[/sub]

C

IV. Populating the DungeonI won't go into any great detail here, since I took the algorithms for this part straight from the Dungeon Master's Guide. The idea is simply to put something in each room of the dungeon: hidden treasure, a monster, some description, etc. At this stage, you also determine whether any given door is secret or concealed, and also what the door's properties are (wooden, locked, trapped, etc, etc.). Random tables work quite well to determine all of this.
V. FinisAnd that, as they say, is the proverbial that. All that remains is to display the dungeon, and that has nothing to do with dungeon generation algorithms. :)
Feel free to download the source code for my dungeon generator—that's where you'll find the real technical explanation. The sources are a bastardized mix of C and C++, but fairly readable for all of that. The "jbmaze.cpp" file contains the maze generation algorithms, and the "jbdungeon.cpp" file contains the dungeon generation stuff. The "jbdungeondata.cpp" file populates the dungeon.
The sources can be obtained here:

Core Code and Web Interface

Windows Interface

not

must

qDecoder

web

(The Windows version does

need this library.)

GD

Enjoy!