Random Dungeon Generation
Hello- I'm very interested in generating random dungeons for my tile-based game. So far I've looked through many rogue-like random map articles, the accidental intricacy site, random D&D dungeon generators, random maze generators, and the DungeonMaker manual. Unfortunately, these generators all create, well, boring dungeons.
I believe that the Diablo games generate their levels by taking hand-made dungeon 'pieces' and placing them together like a puzzle, but I'm not sure. I can't find any information on random dungeon generation using this method! I was wondering how this is done, if there is any information about this on the web somewhere, and general thoughts about random dungeon generation techniques.
Thanks!
P.S. here are some links that I mentioned:
(DungeonMaker) http://dungeonmaker.sourceforge.net/
(Accidental Intricacy) http://members.gamedev.net/vertexnormal/articles.html
(D&D Dungeon Generator) http://www.aarg.net/~minam/dungeon.cgi
(Rougelike Development) http://roguelikedevelopment.org/development/
In game programming gems 5 there is an article about procedurally done dungeons, it was meant for (or the pictures showed) 3d maps, but you can do them with 2d. You would have a bunch of peices, corridors, rooms, ect.. and it will put them together. I have not worked on it, but I really like the idea.
[Edited by - Valor Knight on March 30, 2006 12:30:27 PM]
[Edited by - Valor Knight on March 30, 2006 12:30:27 PM]
one good example of how random 'dungeon' generation can work out quite well is the 3d fps game 'nosferatu, wrath of malachi' (or something like that). in this game the 3d levels are randomly put together (maybe per installation). i think it's one of the rare 3d games that use random level generation. maybe you can find some articles or programmer diaries about it. i think there was something up on gamasutra, too.
might be a start.
cheers,
simon
might be a start.
cheers,
simon
I think what you can do is using the same algorithem to create rouge like random maps.
I dont think everything in diablo are premaed pieces, some are just corridors and halls the are generated randomly.
So basically, what I think you can do, is start like a normal dungeon generating.
You "dig" the corridors, except that from time to time, instead of digging the next square, you put a premade room. And then you continue digging from that room's exists' until you reach a dead end.
I dont think everything in diablo are premaed pieces, some are just corridors and halls the are generated randomly.
So basically, what I think you can do, is start like a normal dungeon generating.
You "dig" the corridors, except that from time to time, instead of digging the next square, you put a premade room. And then you continue digging from that room's exists' until you reach a dead end.
Hi,
For dungeon generation you must create your basic pieces or Pads like I called them.
These pieces are not a single tiles but a construction of tiles. Like a 3x3 or 9x9 pad of tiles.
There may be some items included in the pad like a wall, a column a statue. That is impassable objects. Each map should have an appropiate obstruction map for path finding.
You must provide some kind of code so you can tell which side of the block is 'open' and can be connected with other tile... its like the stubs in a puzzle. So a figure of type A can only be accesed from the north, a B type can only for the west, a C type from the south and so on... maybe the one with exits to all sides is an O type. Its your codification. You will find that you will have 15 combinations. But you may refine it for narrow exits.
Then you can build your map. A piece of type A (exit to the north) can be matched with a piece which has an exit to the south... like an C type or an O type. Following those simple rules you can build a grid like:
ZKMZ
LOFD
NRQZ
ZAZZ
Z meaning there is nothing there. So once you get this grid you are free to pick any pad of type K and place it in your map... the pad will cover a 9x9 area. So in this simple example you will get a 4x4 gris with 9x9 pads for a 28x28 map.
There are variations for this idea. I think you can handle them.
Luck!
Guimo
For dungeon generation you must create your basic pieces or Pads like I called them.
These pieces are not a single tiles but a construction of tiles. Like a 3x3 or 9x9 pad of tiles.
There may be some items included in the pad like a wall, a column a statue. That is impassable objects. Each map should have an appropiate obstruction map for path finding.
You must provide some kind of code so you can tell which side of the block is 'open' and can be connected with other tile... its like the stubs in a puzzle. So a figure of type A can only be accesed from the north, a B type can only for the west, a C type from the south and so on... maybe the one with exits to all sides is an O type. Its your codification. You will find that you will have 15 combinations. But you may refine it for narrow exits.
Then you can build your map. A piece of type A (exit to the north) can be matched with a piece which has an exit to the south... like an C type or an O type. Following those simple rules you can build a grid like:
ZKMZ
LOFD
NRQZ
ZAZZ
Z meaning there is nothing there. So once you get this grid you are free to pick any pad of type K and place it in your map... the pad will cover a 9x9 area. So in this simple example you will get a 4x4 gris with 9x9 pads for a 28x28 map.
There are variations for this idea. I think you can handle them.
Luck!
Guimo
This is something I've been considering too for my 3D rpg. I don't know that I will end up implementing random dungeons though, but I was working on how I might implement a 3D mine which was largely vertical with horizontal planar offshoots at various depths. I was leaning towards a sort of fractal accretion, but hadn't really worked it out yet.
There's some great maze generation methodology that can be adapted for dungeon generation. One of the 'problems' that I've seen with a lot of 2D procedural level generation is that even with multiple floors/levels the maze quality only extends over a single level - i.e. at each level your task is to "find the exit of the level". Using a sort of modified Eller's Algorithm, it shouldn't be too hard to create a 2.5D maze that keeps track of where certain paths end.
Essentially, how Diablo works is that it combines fixed terrain objects and paths between them. I think the game also exploits some distance metrics to keep the exit from being too far from the entrance, or being in a particular direction, etc. but that may or may not be the case. It works like any other carving algorithm otherwise - place objects, then carve paths between them.
There's some great maze generation methodology that can be adapted for dungeon generation. One of the 'problems' that I've seen with a lot of 2D procedural level generation is that even with multiple floors/levels the maze quality only extends over a single level - i.e. at each level your task is to "find the exit of the level". Using a sort of modified Eller's Algorithm, it shouldn't be too hard to create a 2.5D maze that keeps track of where certain paths end.
Essentially, how Diablo works is that it combines fixed terrain objects and paths between them. I think the game also exploits some distance metrics to keep the exit from being too far from the entrance, or being in a particular direction, etc. but that may or may not be the case. It works like any other carving algorithm otherwise - place objects, then carve paths between them.
here is an image of what the article I was referring to shows:
I read it more, and it takes predefined pieces of the level, corridor, rooms, doors, ect.. and places them proceduarally. The article is called Procedural Level Generation.
I read it more, and it takes predefined pieces of the level, corridor, rooms, doors, ect.. and places them proceduarally. The article is called Procedural Level Generation.
There's another article here that describes procedural dungeon generation. It's modular and it's probably going to be open source in the end.[font="Georgia, Palatino,"][size=2]
[/font]
[/font]
The problem with just grabbing some generator off the web is that so many articles and discussions talk about broad concepts or are targeted for narrow applications. It sounds like you have an idea: piece a level together out of puzzle pieces. Instead of trying to google for a generator that does this in a way that will work for your game, why not just sit down and figure out what you have to do to make it work for your game? Procedural generation is still kind of a black art. There are a thousand methods to use, and most likely none of them will be exactly what you need right out of the box. You have to try to modify, tweak and hammer them to make them fit.
A lot of the articles you'll read (mine as well) are undirected. There is not much of a specific goal in mind. So many of the rogue-like-style generators generate a dungeon as just a set of rooms filled with random crap. The space is generated from the gameplay perspective, meaning that the generator doesn't take into account how real people build real spaces. Thus you get a lot of rooms and a lot of corridors, and all are laid out willy-nilly. Diablo is as guilty of this as any; the sole difference between Diablo and others merely lies in the quality of the artwork. Break a Diablo or Diablo 2 level down, and you see the same kind of techniques, the same kind of pointlessness in the architecture.
Now, if you go digging around in the Diablo 2 modding community (it used to be pretty active; not sure how it is these days) you will eventually stumble on information of how the levels are pieced together. Diablo 2 does use a lot of pieces that just slot together in different configurations. It might be helpful to look at how they did it, but the concept really isn't hard. You create a specific tile with a given connectivity pattern in mind, and ensure that you match up connectivity patterns with tiles that have the same patterns. There is very little algorithmic complexity in this; it's just pattern matching.
Also, old thread is old. Don't necro threads. If you have something to say about an old topic that you think people want to hear, make a relevant new topic for it.
A lot of the articles you'll read (mine as well) are undirected. There is not much of a specific goal in mind. So many of the rogue-like-style generators generate a dungeon as just a set of rooms filled with random crap. The space is generated from the gameplay perspective, meaning that the generator doesn't take into account how real people build real spaces. Thus you get a lot of rooms and a lot of corridors, and all are laid out willy-nilly. Diablo is as guilty of this as any; the sole difference between Diablo and others merely lies in the quality of the artwork. Break a Diablo or Diablo 2 level down, and you see the same kind of techniques, the same kind of pointlessness in the architecture.
Now, if you go digging around in the Diablo 2 modding community (it used to be pretty active; not sure how it is these days) you will eventually stumble on information of how the levels are pieced together. Diablo 2 does use a lot of pieces that just slot together in different configurations. It might be helpful to look at how they did it, but the concept really isn't hard. You create a specific tile with a given connectivity pattern in mind, and ensure that you match up connectivity patterns with tiles that have the same patterns. There is very little algorithmic complexity in this; it's just pattern matching.
Also, old thread is old. Don't necro threads. If you have something to say about an old topic that you think people want to hear, make a relevant new topic for it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement