Hey unrelated. But I require your expertise if that is ok.

I would like to generate some procedural dungeons and towns and have no idea where to start. There is not much source on this. I am more interested in theory, algorithims and techniques than implementation since I will be using a non standard language on the .NET platform to implement this. I would also prefer to start simple.

Cheers.

I've written a few journal articles as well as some other stuff about dungeon generation. In this journal entry I whipped up a quick maze/labyrinth generator class that encodes connection information between maze nodes, and in this journal post I show how the maze nodes can be encoded into a very simple tile-based dungeon map. Of course, the algorithm is very crude, but with some work put into the node pieces, and perhaps even recursive subdivision of some of the nodes to add refinement of detail if necessary, it can be workable. The technique produces space-filling mazes that fill all the nodes of the maze; by pruning side branches or otherwise eliminating nodes, more sparse mazes can be made which result in less square dungeon layouts.

My original Golem 2D isometric created dungeons as a tree. A random room was placed, selected from a pattern. Rooms had 'hot spots' or places along the perimeter where a connection such as a doorway or adjoining room could potentially be placed. When a room was placed in the map, these hotspots were enumerated and placed in a list, along with their connection and type info, designating what types of pieces could connect to it, and how much area was available in the map at that hotspot for a piece to be placed. Then a hotspot was randomly chosen from the list, and a new feature with new hotspots (or no hotspots, in the case of some features) was selected randomly and placed.

This technique worked fairly well, but it isn't really suitable for some types of levels, since it does create a branching tree structure without any loops, unless special case logic during feature selection and placement is written to allow some pieces to overlap. All paths from one branch to another pass through the root node, and this tree-like layout becomes very obvious after the player spends some time exploring.

I achieved some pretty good success with progressive refinement techniques. I would begin with selecting a choice from some finite set of large-scale layouts holding to a particular pattern for a dungeon, and progressively refine each element of the layout, adding more and more detail as I went. The layouts, and the possible paths of refinement for each piece, were determined by the type of level it was. The layouts themselves could be randomly generated, using a maze algorithm with pruning, or they could be hard-coded.

For example, consider the evil Temple of Al'kadum. The torture chambers underneath that temple are said to be quite extensive, and the 'penitent cells' are numerous, dank and cruel. There is an inner nave, where the altar to the hideous god is erected. There are kitchens where the mundane preparation of meals are carried out. There are storerooms where the monks store tithes and tributes 'donated' by the local peasantry. And there are, of course, armories; Al'kadum wishes that the congregation be devout and vigilant, and commands his priests to ensure such vigilance with the sword if need be. All of these things need to be taken into consideration when determining the layout of the Temple.

I usually start with a list of things that have to be in the Temple, and a list of things that can be in the Temple. A list of must-haves might look like: {Nave, Penitent Cells, Kitchen, Armory, Storage Cells, High-Priest's Quarters, Monk's Quarters, Torture Chambers }. A list of optionals might look like {Treasure Room, Library, Choir Chamber, Statuary Hall, Empty Rooms} and so forth. When a layout is constructed, each node or location in the layout designates the type of location it can refine down to. A block in the layout may be designated 'Penitent Cells' + 'Storage Chamber' + 'Armory', meaning that during refinement it can refine down into any one of these possibilities. Nodes are randomly selected and progressively defined; when selecting what to refine a node down into, the list of must-haves is checked first, and if one of the possibilities is on this list, then it is refined down into that, and the must-have is crossed off the list. This way, I ensure that all of the necessities are taken care of, after which I can start adding in anything from the optionals list. Note that something can be on both lists. For instance, more than one block of Penitent Cells could be generated.

The optionals list gives the unique flavor. Usually, these selections are weighted so that, for instance, Empty Rooms occurs far more frequently than Treasure Room.

Each node type then refines down even further. How many torture chambers are constructed? How are they laid out? They can either be templated with a randomly chosen layout as before, or purely randomly generated using appropriate constraints, depending upon the algorithms you have worked out. Every element of the dungeon can be refined this way, down to the smallest bit of trash in the corner of the High Priest's toilet chamber; it's all a matter of the levels of refinement you work out.

I've found that the most important thing when designing a dungeon generator is this: make it make sense. Don't just slap up a brain-dead drunkard's walk algorithm and churn out yet another endless series of generic mazes. Every level, every dungeon, should have a purpose, and should be constructed to demonstrate that purpose. Was it built to hold prisoners? Was it built to provide shelter? A place of worship? Simple dry-goods storage? The more sense your areas and dungeons make, the more able the player will be to immerse themselves in the world you have created.

Corollary to making sense is detail: appropriate detail, and sufficient detail. After all, a dungeon is just a bunch of rooms. It's what is in the rooms that counts. This is, of course, largely a matter of artwork and asset creation, but it's also a matter of populating the dungeon in a manner that makes sense.

I also wrote an article about the basics of constructing a natural cave system using a particle-accretion system where the particles are circular open spaces. That article is here. There are a few others up there; I have many others written or partly written, but I haven't updated that site in years. I'm lazy.

Thanks. Im going to digest this and then try and whip something up.

I had a few minutes to check out your PDF documentation in the zip download, and I am fairly impressed with the design of your noise library. The concept of creating a graph of filters and generators is a great way to build this type of a library.

So thanks for posting the library, and taking the time to document it and some sample usage in the PDF. I look forward to digging into the source code - I'll be sure to post more comments once I get a chance!

Quote: Original post by Jason Z
I had a few minutes to check out your PDF documentation in the zip download, and I am fairly impressed with the design of your noise library. The concept of creating a graph of filters and generators is a great way to build this type of a library.

So thanks for posting the library, and taking the time to document it and some sample usage in the PDF. I look forward to digging into the source code - I'll be sure to post more comments once I get a chance!

Credit where it's due, the design is based on libnoise which I used for awhile. I liked the design, I just didn't like the lack of flexibility in noise sources so I built my own.

And thanks for taking a look at it. It's still rough, so if you see anything that could be improved, let me know.

Firstly thank you. What you have there is a veritable gold mine. It seems like a network is the only way to allow a dungeon with circuitous routes. I have some questions.

When you say pattern what do you mean? How does one select from a pattern? I am used to the notion of recognizing and matching patterns.

So a layout can be randomly generated. But there is a hurdle that I am having trouble with. How do you control a maze generating alorithim to be able to recognize and appropriately structure then label the rooms. It seems you will need a pretty clever architect there before you even think about pruning.

Interior Design:

You note that what is inside the rooms is more important than the layout itself. Are these done by hand or is there a way to do these randomly?

Roads and planning:

Do you know any thing about how they would be? It seems a tree might be simplest here with one main branch and then a series of random bifurcations. One could then use a similar pruning technique as you mention above to place appropriate buildings.

I worked a lot with patterns, or pre-generated layouts. When starting on a level-generation routine, the first instinct is to go with 100% procedural. Even now, after all this time, I always want to go 100% procedural. However, sometimes it can simplify things to go with a few pre-generation steps. It's a tradeoff. Maximum randomness means maximum effort. In many cases, you can trade a few procedural, implicit methods for roughly equivalent non-procedural explicit methods, and still obtain sufficient randomness.

For example, going back to the Temple above. There are an infinite number of ways the Temple could be built; however, only a relatively small subset of those ways make sense. The trick lies in applying the constraints to obtain the desired result. A place to start applying the constraints is in the overall layout. As you mentioned, it can be difficult architecting the grand layout procedurally. What if the procedure makes it so monks have to travel through the torture chambers to get to their sleeping cells, or makes it so the monks have to bring prisoners through the sacred nave to get to the prisons? These are things that can add complexity to the procedural layout generator, and thus are candidates for pre-generation.

To begin constructing the level, you might start with a template that contains meta-data about section locations, types, restrictions on neighboring types, etc... Something like this, for example:


This, of course, is just a hastily thrown together example, but it shows what I mean. The physical layout of sections (not rooms; the actual layout of rooms within sections is the responsibility of the next level of refinement) is pre-generated, but each section can possibly be different things based on random selection. This removes the tricky task of procedurally generating the layout, while still providing opportunities for randomization. If a large set (I sometimes created 10 or 15 different layout templates, depending on the complexity of a given level type) of templates is provided, then that still gives you 100s of possible permutations in any given level, and saving some tricky and bug-prone coding as well. And that's not even counting the possible randomization at further levels of refinement.

The principle can extend down into the sections themselves, although I've found that it's typically easier to write fully procedural generators for these kinds of subsections than it is to write a generator for the over-all layout. The section generator is given connection data that records how and where the section connects to neighboring sections (part of the template) and uses that, plus the rectangle of space it is allocated within the level map, to construct the physical layout of rooms within that section. Maze generators can work well here, especially if constraints are applied to the generator. For instance, storage and sleeping quarters type sections might have lots of long hallways with small cubical cells tightly packed along their lengths. Dungeon sections can be made twisty to confuse escapees and funnel them down dead ends for easy re-capture.

The refinement continues as you go deeper. Say you generate a complex of torture chambers. You place some rooms, some twisty passages, maybe a secret door or two to a chamber where the 'special' victims are given the royal treatment. This chamber has an iron maiden and a rack; that chamber has a stocks and a rack full of whips and knives. (Sounds like an S&M nightmare; ugh) This other chamber has a barrel full of acid for slow dipping. All of these possibilities are selected at random for each room, and placed according to some set of rules (or templates).

All sorts of things are subject to randomization: garbage and litter, wall-hangings, floor coverings, tile patterns, the statues placed around the perimeter of the nave depicting horrid beasts from beyonder planes, and so forth. The idol of the vicous god sits on an altar. What does that altar look like? Is it a slab of purest black basalt? Is it ornately carved of grey granite, and stained with the blood of innocents? What about the statue itself? Does it sit upon an elaborate pedestal, or does it hang from the ceiling? Is there a hidden compartment inside the pedestal? Does that compartment contain gold, a magical item, or a deadly poison trap?

One advantage of using templated layouts is that architectural peculiarities can be reused across several different establishments. If two separate buildings were built by the same builders, then it is likely that certain floor plans or architectural characteristics will be similar, even if the buildings serve different purposes. So certain templates or sub-section templates and rules can be reused for different locations. The nearby fortress, for example, might have been built by monks long ago, and probably features dungeons beneath it chillingly similar to these grim, death-reeking holes.

With a dynamically-typed language such as Lua at the heart of the generation scheme, I can easily prototype a dungeon using a library of templates, and if I come up with some clever generational scheme to do something procedurally, I can swap out the template for the procedure. If they are given the same type of interface, the swapping-out can be seamless and painless.

I haven't played a whole lot with roads and such, outside of the particulars of blending roads well with height-mapped terrains and such; and my towns have all been heavily templated in much this same manner.

Thanks! I will print this page (together with the two journal pages); I think I have enough basis to start trying to rustle something up. Thank you for pointing me in a direction when I had none. That is the most important way to teach i feel.

It is a shame all this good information is buried inside the comments of this post which will soon - for all intents - disappear.

One last minor thing, is that template you have pictured above the actual description? that is, do you template using image type data or do you do the templates in a special domain language (the approach I plan to take).

I template in a special domain language; the image was purely for illustration purposes. My templates will encode information such as how doorways between sections should align, as well as high-level pathing information to make it easier for entities to navigate across the level.

Glad all this could be of help to you. I have been working on trying to collect it all together onto my gd.net page, but that has been a project I've been neglecting for years. Hopefully some day I'll finish it, or at least start making concrete progress again.

So it clocks in at 20 pages. Although I am still waiting on your next post.