next »

[Hayden Scott-Baron]

I've been playing around with this online dungeon generator:
http://direpress.bin.sh/tools/dungeon.cgi

Is there some existing rulesets in order to generate this sort of thing?

The maps that are generated often seem quite well laid out, and I was interested in whether these sorts of layour are widely known, or whether people tend to develop their own techniques for building maps procedually.

Also, is it something where you start off simple, and work your way up to a more complex generation system?

[Decipher]

That seems like a quite cute maze generator to me. And maze generators are widely known. In fact it's not even hard to code one. I have coded one for Krysp (my submission for the CodeBlocks Challenge). Although the one Krysp implements is not as mature as the one you posted, the two share a lot in common.

As for the existing rulesets, it all depends on you, and how you want your content to be generated. This is what is good about procedural generation you're simply unbounded.

Finally, it simply is up to you how will you code it. If the generator I'm coding is something really complex I'd start off simple and build on, otherwise I'd code straightforward.

[Hajo]

Is there some existing rulesets in order to generate this sort of thing?

I've once been collecting dungeon generation algorithm description for my library. You can find a few of them here:

http://www.simugraph.com/h-world/pmwiki/pmwiki.php?n=Library.Maps

[Hayden Scott-Baron]

I wonder whether the map making algorithm in the example I linked to is available. I love the wiggly labyrinth corridors between the rooms.

I've once been collecting dungeon generation algorithm description for my library. You can find a few of them here:

http://www.simugraph.com/h-world/pmwiki/pmwiki.php?n=Library.Maps

This helps a lot, it's good to get an idea as to how these maps are figured out. I guess the best way to learn is to make a 2D array and start poking through it.

Does anyone know of any guides or tutorials for random map programming?

[george]

Maybe start here at the PCG wiki, more specifically here with the dungeon generation link.

[nihilocrat]

The generator you link to looks like a pimped-out version of a roguelike dungeon generator. If you set some of the options to more conservative values (rectangle rooms, straight/bent corridors, no deadends) you'll notice that you've got what looks like a roguelike dungeon.

The algorithm for those dungeons is pretty simple. Basically you choose a number of rooms, a min room size and max room size, and maybe some other variables, and generate a bunch of non-overlapping rooms. Then, you randomly create doorways to each room based on some other variables. Proceed to generate corridors between these doorways, making sure that all the rooms are connected (there are no disconnected rooms, or sets of rooms disconnected from all the others). If you can't connect rooms with a straight corridor, just make one or more bends in it. From here, you can make more complicated algorithms to generate rooms and corridors to get labyrinth corridors or non-rectangular rooms.

If you need more help with the algorithm, there are plenty of open source roguelikes out there. Hopefully the dungeon generation code is well-written and well-commented.

edit: whoa, thanks for the PCG wiki link! I never knew such a thing existed!

[Ivan]

I made a little roguelike awhile back and I just bruteforced my dungeon generation. Just generated a few random rectangle rooms in the overall space and then connected them with corridors. Unless you're doing mazes and stuff, it's not a bad way of doing things imho.

[Hayden Scott-Baron]

http://dirkkok.wordpress.com/2007/11/21/generating-random-dungeons-part-1/

I found a tutorial that, from first impressions, seems to know what it is talking about.

I'm starting to think that the best approach will be to try to do it myself. Solving the problems is probably the most important part of understanding the process in the first place. Also, I'd like to do something with diagonals and other shapes, which complicates things much more than the average roguelike map. 

Toastie, by brute force are you referring to your method of checking whether or not there was a route from one room to the next? This is one part that confuses me, how you choose paths between each room without overlapping or tangling... but I suppose it's a matter of rules, and waiting for those rules to cease to be invalid.

[Loren Schmidt]

Wow, that's a great generator, Dock.

I've always been fascinated by dungeon generation. I was working on a hex grid roguelike a while ago, but I never got my dungeon generation to work very well. I started with one room, specified door points, and then crawled outward randomly from there, creating rooms (or dead ends) at the end of each corridor. The wall cells bordering the passages and rooms weren't even marked, so the corridor diggers would inadvertently connect to non-door spaces all the time.

The main points I was missing were room packing and nice path finding for the corridors.

Despite how poor my results were, it was a lot of fun to code. I wish you better luck than I in your endeavors, and I look forward to seeing your results.

[Natso]

The dungeon generator linked in the first post seems to draw all of its room content from D&D (I confirm this).  Also, in dungeon generation, you're going to feel like you're cutting some corners to get things to work right.  It always ends up feeling like that.

Cheers
 - Natso

[Hayden Scott-Baron]

The dungeon generator linked in the first post seems to draw all of its room content from D&D (I confirm this).

Is there a documented set of rules for constructing dungeons in this manner in D&D?

[Natso]

Naw, the map layout is whatever the DM wants it to be (D&D in itself can be played without a physical grid/map at all, but it helps a lot to use them)  As for the monsters & room contents themselves, they look to be from D&D 3.0 or 3.5 edition.  If you're interested in the D&D-related generation, you should check out http://www.d20srd.org/ for more info.  As for the map-generator, that is entirely unrelated to D&D, other then that the map can be used for it.  The DM's Guide has a few pointers for dungeon decor & layout, etc, but their layout is really at the DM's own discretion. (Sorry if my original reply was misleading)

Cheers
 - Natso

[Titch]

I have been wondering about psuedo-random generation, but for a performer rather than a dungeon crawling game. I always get hammered by having to ensure that the metrics of the content function properly without having to pre-fabricate blocks of content and stick them together.

[increpare]

I have been wondering about psuedo-random generation, but for a performer rather than a dungeon crawling game. I always get hammered by having to ensure that the metrics of the content function properly without having to pre-fabricate blocks of content and stick them together.

Well one way is usually to generate a sure-fire path first (this isn't necessarily the same as having pre-fabricated content), then to elaborate it as much as possible.

[Natso]

I have been wondering about psuedo-random generation, but for a performer rather than a dungeon crawling game. I always get hammered by having to ensure that the metrics of the content function properly without having to pre-fabricate blocks of content and stick them together.

I hate to make a suggestion with little explanation, but you should look into dynamic programming, if you structure your generation similarly it may become quite a bit easier.  Also, consider the generation function recursively, if you haven't done that yet... (just throwing out some ideas)

Cheers
 - Natso

[Hayden Scott-Baron]

If you map out the pattern of satisfying platform movement you can, theoretically, reverse generate a map to fill out those patterns. 

On the other hand, I believe Derek Yu's Spelunky game is procedurally generated using pre-made chunks of level (right?), which for a cave environment is very well suited.

[Natso]

nethack (an awesome roguelike) takes an approach as follows:

1. Generate some rectangles amongst the entire floor, make sure the rectangles don't collide.
2. Make sure there are at least 2 rooms of suitable sizes for the up/downstairs (and check for other neccessary rooms for particular floors), otherwise return to step 1.
3. Connect the rooms with passages (and generate doors at this point)
4. Go through every room and generate content for it, from several templates (including a standard dungeon room with monsters/treasures, shops, beehives, swamps, throne rooms, etc)

Each of the templates is generic, but has its own requirements.  The the shop, for instance, adjusts inventory based on the size of the room.

(/nethack)

There was a maze-generation algorithm where the entrance and exit are placed on the outer edge.  The rectangle is then split into a 2x2 grid, where the cells are random-sized.  Each of the cells is then split again, and again, until the cell reaches the minimum possible size.  When there is a split, sized leave spaces open (so as to respect the paths entering and leaving them).  A similar approach could be used, splitting a platform-game's room into various areas, then filling them with content based on how much cell space is provided.

Cheers
 - Natso

[Ivan]

http://code.google.com/p/gridhack/source/browse/trunk/grid_level.c

This was my crappy dungeon code that's kind of similar to what nethack does I guess, but is a lot more brutish.

[BorisTheBrave]

Natsuo: I have always wanted to know how did the gnomish mines levels work? For those who haven't played nethack, these levels were more organic cavelike structures. Repeat bisection again?

[Natso]

I want to say (don't take my word for this though) that it places an absurd number of small rooms around (like usual, but more & smaller, so as to leave less gaps.  also, the check requiring at least 1 cell between each room isn't used).  Then, when it would usually construct paths between rooms, it uses a modified form of the maze algorithm (the same maze generator used in Gehennom, and in some other levels).

Alternatively, it creates a maze-level, covers it in small rooms, then trims off the remaining dead-ends.

(The above are semi-guesses, the nethack source code isn't too well documented)

I attempted to do this actually, the demo: http://darknovagames.com/nathack/nathack.html
classic roguelike controls: hjklyubn, you know the drill I'm sure
If you type a capitol O and then move in some direction, it will make the entire map visible (so you can see the wood & cave elements as I describe below)

Algorithm:
1. Construct a maze that covers the entire room.
2. Place the three big rooms (one on left, one enclosed room in the middle, and one room on the right)
3. Snapshot this room, will use it later
4. Now, "erode" the entire room 4-6 times.  Erosion consists of changing a wall-type into floor-type based on surrounding elements (when entirely surrounded, no erosion, but if there are only 2-5 surrounding wall elements, there is a good chance of erosion)
5. The current map becomes the cave area. (grey)  The snapshot's bordered areas become the wooden tunnels & flooring (as seen in the demo).

This created a suitable atmosphere for me.  Since wood was going to be destructable, a suitable environment was needed behind it.

Hope this helps...
 - Natso