Random Dungeon Generation Theory
by Jacob Williams · in Torque Game Engine · 12/16/2008 (9:50 pm) · 35 replies
So, in a world of overused acronyms, I am working on a SMOSFRPTPDCG, and for those of you who can't read my mind, that comes out to "Singleplayer/Multiplayer Online Science Fiction Role Playing Third Person Dungeon Crawler Game." I am at the milestone in my development process that requires me to learn a little theory on random dungeon generation. I have seen a few posts around here proposing different theories, but has anyone really made anything like this work... effectively? The thought that is floating around in my mind is this: At mission run-time, pull from a library of difs that are categorized by entrances and exits. So if I have a north/east dif (north and east entrances/exits) I could line that dif up with a piece that has a south entrance and another piece that has a west entrance. After all the pieces have been snapped into place, I could generate a .mis file with a random name, and continue the loading process. When the mission is complete, I could allow the player to either save the mission or delete it. I also would like to throw in a mini map that is created based on the generated level, but have no idea how to even attempt it.
So here is what I am asking the community; What is a better way of accomplishing this, or even better, if you have made this type of thing work, mind throwing a little code my way to get me started? I plan to document all of this as I go along and release a resource if something like this is wanted.
This is the part where i pick your brain... go!
So here is what I am asking the community; What is a better way of accomplishing this, or even better, if you have made this type of thing work, mind throwing a little code my way to get me started? I plan to document all of this as I go along and release a resource if something like this is wanted.
This is the part where i pick your brain... go!
About the author
#2
Do you want help more on the 'how do I do it on Torque' side of things, or the actual process of generating a random dungeon?
If you're using DTS, actually, you could use mounting to make far more complex levels and caves (and reuse more pieces), because you could arbitrarily rotate everything. Of course, you can do that with DIF as well, but with DTS it's far simpler. You could start, for example, with your 'main room' then mount corridors branching off it, and mount more corridors and rooms to those.
If you were doing it this way, you could simply let the algorithm ramble and create whatever it liked at each mount point. You'd have to have some way of checking whether the piece you're about to place is going to intersect another piece already placed, though. Simple bounding box checks should be enough.
The disadvantage, of course, is that things wouldn't really line up perfectly, unless you design your mount points very specifically. You'd just tend to get something like the lungs - lots of tunnels that branch and branch. Instead of a more structured dungeon.
That actually sounds like it would be nice for caves - rambling and branching - but maybe not for man-made dungeons. You'd probably want to resort to a different algorithm for that, and even abandon the arbitrary piece-mounting system.
12/17/2008 (5:05 am)
If you're doing level construction after lighting, you could force a relight somehow...Do you want help more on the 'how do I do it on Torque' side of things, or the actual process of generating a random dungeon?
If you're using DTS, actually, you could use mounting to make far more complex levels and caves (and reuse more pieces), because you could arbitrarily rotate everything. Of course, you can do that with DIF as well, but with DTS it's far simpler. You could start, for example, with your 'main room' then mount corridors branching off it, and mount more corridors and rooms to those.
If you were doing it this way, you could simply let the algorithm ramble and create whatever it liked at each mount point. You'd have to have some way of checking whether the piece you're about to place is going to intersect another piece already placed, though. Simple bounding box checks should be enough.
The disadvantage, of course, is that things wouldn't really line up perfectly, unless you design your mount points very specifically. You'd just tend to get something like the lungs - lots of tunnels that branch and branch. Instead of a more structured dungeon.
That actually sounds like it would be nice for caves - rambling and branching - but maybe not for man-made dungeons. You'd probably want to resort to a different algorithm for that, and even abandon the arbitrary piece-mounting system.
#3
12/17/2008 (5:46 am)
@Jacob: You'll want to google the interwebs for dungeon generation algorithms, and you'll find some stuff. It's hard to do, though I was able to make a simple one that generated a set of rooms ala Anarchy Online's subway system-themed missions. There's a few different ways to do it, but you probably want to generate your .mis file before launching the mission, so that it can light properly (you don't want the player standing in the dark in the game waiting for a relight, it's bad customer relations).
#4
12/17/2008 (8:39 am)
Quote:generate your .mis file before launching the missionThat's a good idea... I might just have to steal it ;)
#5
At that moment you're free to create as much stuff on the server as you want, and it'll get sent and lit on the clients. But since you'll essentially have a dynamic mission, relighting will always occur, so you need to take that in consideration when setting up your lights in order to avoid massive loadtimes. You'll also want to deal with the piling up of .ml files in the mission folder, each new random dungeon will generate a new .ml file with a different filename.
You really should go with DIFs for this, it'll look a lot better, lighting wise, than statics. Use Constructor-generated lightmaps heavily to avoid placing DIF-affecting lights on the mission, and if your dungeons are actually dungeons, get rid of the sun to save on relight time.
12/17/2008 (8:53 am)
You can create objects before mission lighting without problems. A mission is just a missionGroup with a bunch of stuff inside it that gets created when the .mis is exec'ed. This is done before the loading screen is displayed. Afterwards the server sends commands so the client starts the loading process (and show the loading screen).At that moment you're free to create as much stuff on the server as you want, and it'll get sent and lit on the clients. But since you'll essentially have a dynamic mission, relighting will always occur, so you need to take that in consideration when setting up your lights in order to avoid massive loadtimes. You'll also want to deal with the piling up of .ml files in the mission folder, each new random dungeon will generate a new .ml file with a different filename.
You really should go with DIFs for this, it'll look a lot better, lighting wise, than statics. Use Constructor-generated lightmaps heavily to avoid placing DIF-affecting lights on the mission, and if your dungeons are actually dungeons, get rid of the sun to save on relight time.
#6
After seeing these results, here is what I want to do. I want to take a amount of area (for instance, the 600 x 600 platform), and create a grid. I want each square in the grid to have a set of properties, but for testing purposes, just an isFilled variable. Then I will have the script pull a square randomly where isFilled = false. This way, I won't have all these blocks overlapping each other.
And for the bigger picture...
Dungeon Generation would be easier using a grid system. If each dungeon piece is the size of a square, it would be a simple matter to set a square's properties to match up square entrances and exits.
For Example:
Not exactly sure how I will calculate the nearby squares, but it should be a pretty trivial matter. The getCompatiblePiece function will take the exit value and simple return the opposite direction, so getCompatiblePiece(%grid[0]) would return "east," and another random generator would choose the exit. So the returned value from the function would be something like "east-south."
So what do you more experienced programmers think?
12/17/2008 (10:34 am)
So here is an image of my preliminary testing. What you see is a .mis that was generated randomly when chosen from the mission select screen, and 20 cubes randomly placed on a 600 x 600 platform. After seeing these results, here is what I want to do. I want to take a amount of area (for instance, the 600 x 600 platform), and create a grid. I want each square in the grid to have a set of properties, but for testing purposes, just an isFilled variable. Then I will have the script pull a square randomly where isFilled = false. This way, I won't have all these blocks overlapping each other.
And for the bigger picture...
Dungeon Generation would be easier using a grid system. If each dungeon piece is the size of a square, it would be a simple matter to set a square's properties to match up square entrances and exits.
For Example:
%gird[0].isFilled = true;
%grid[0].interiorFile ="~/data/interiors/dungeonPieces/north-west.dif";
%grid[0].entrance = "north";
%grid[0].exit = "west";
if (%nearbySquare.isFilled = false) {
%pieceSelected = getCompatiblePiece(%grid[0]);
%nearbySquare.interiorFile = ~/data/interiors/dungeonPieces/"@%pieceSelected@".dif";
}Not exactly sure how I will calculate the nearby squares, but it should be a pretty trivial matter. The getCompatiblePiece function will take the exit value and simple return the opposite direction, so getCompatiblePiece(%grid[0]) would return "east," and another random generator would choose the exit. So the returned value from the function would be something like "east-south."
So what do you more experienced programmers think?
#7
The way I did it was a lot like the way you're talking about. Basically, I had some flags for each square that told which directions contained a doorway, and then sampled the NSEW directions for their flags. I assembled those into the flags for my square, which gave me the doorways that needed to be present. The only difference was that I was generating 2D maps and using a image > mis converter for testing, but premade DIF's a good, and give you the ability to add functions to randomly select from a range of squares that match the criteria you have. It's a good plan.
12/17/2008 (12:01 pm)
Quote:Not exactly sure how I will calculate the nearby squares, but it should be a pretty trivial matter.
The way I did it was a lot like the way you're talking about. Basically, I had some flags for each square that told which directions contained a doorway, and then sampled the NSEW directions for their flags. I assembled those into the flags for my square, which gave me the doorways that needed to be present. The only difference was that I was generating 2D maps and using a image > mis converter for testing, but premade DIF's a good, and give you the ability to add functions to randomly select from a range of squares that match the criteria you have. It's a good plan.
#8
Using the above code, the command:
12/17/2008 (2:27 pm)
Below is the function I have written to create a virtual grid and set the position of the grid for .dif placement. The below function works fine, but it just seems to me that this is not the most efficient way to do this, so again I ask you more experienced programmers, "How can I do this better?"function createGrid (%squareSize){
%posX = 1;
%posY = 1;
%posZ = 10;
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[0,%i] = new ScriptObject();
$Grid[0,%i].position = (%squareSize * %i) SPC %posY SPC %posZ;
$Grid[0,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[1,%i] = new ScriptObject();
$Grid[1,%i].position = (%squareSize * %i) SPC %squareSize * 2 SPC %posZ;
$Grid[1,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[2,%i] = new ScriptObject();
$Grid[2,%i].position = (%squareSize * %i) SPC %squareSize * 3 SPC %posZ;
$Grid[2,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[3,%i] = new ScriptObject();
$Grid[3,%i].position = (%squareSize * %i) SPC %squareSize * 4 SPC %posZ;
$Grid[3,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[4,%i] = new ScriptObject();
$Grid[4,%i].position = (%squareSize * %i) SPC %squareSize * 5 SPC %posZ;
$Grid[4,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[5,%i] = new ScriptObject();
$Grid[5,%i].position = (%squareSize * %i) SPC %squareSize * 6 SPC %posZ;
$Grid[5,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[6,%i] = new ScriptObject();
$Grid[6,%i].position = (%squareSize * %i) SPC %squareSize * 7 SPC %posZ;
$Grid[6,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[7,%i] = new ScriptObject();
$Grid[7,%i].position = (%squareSize * %i) SPC %squareSize * 8 SPC %posZ;
$Grid[7,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[8,%i] = new ScriptObject();
$Grid[8,%i].position = (%squareSize * %i) SPC %squareSize * 9 SPC %posZ;
$Grid[8,%i].isFilled = false;
}
for( %i = 0 ; %i < 10 ; %i++ ) {
$Grid[9,%i] = new ScriptObject();
$Grid[9,%i].position = (%squareSize * %i) SPC %squareSize * 10 SPC %posZ;
$Grid[9,%i].isFilled = false;
}
}Using the above code, the command:
createGrid(100); echo ($Grid[2,4].position);would return "400 300 10"
#9
sourceforge.net/projects/nethack
12/17/2008 (2:50 pm)
It seems like converting the NetHack generator would actually be fairly simple. You are just replacing the ascii characters with blocks...sourceforge.net/projects/nethack
#10
A couple of thoughts come to mind as far as ideas...
* Have main just a few paths that people can stick to, and secondary paths branching off
* Change material types (eg, "cave", "gray stone", "wooden support beams")
* Have recognizable landmarks at branching paths so people can remember places
* Give the player a compass and/or some kind of mini-map to avoid confusion
Having material types and landmarks will really help people not get lost. They will know, "Oh I'm in the natural cave part", or "Ah here is the side passage with the statue by it". You could also do things like throw in fog, different types of lanterns or torches, etc. as another way of differentiation. Also, think about the fact that if a player walks for more than about 20-30 seconds along a passageway that has no break or feature change, they are going to begin to think maybe it's time to turn around and go back.
12/17/2008 (3:55 pm)
Keep in mind that it's far easier to navigate to some point and not get lost in NetHack because you can view it from above. Put the player in first or third person mode and it's a lot more likely they will get lost in a complex dungeon. My bet is that dungeon creation for an immersive (first/third person) space is going to have some different needs.A couple of thoughts come to mind as far as ideas...
* Have main just a few paths that people can stick to, and secondary paths branching off
* Change material types (eg, "cave", "gray stone", "wooden support beams")
* Have recognizable landmarks at branching paths so people can remember places
* Give the player a compass and/or some kind of mini-map to avoid confusion
Having material types and landmarks will really help people not get lost. They will know, "Oh I'm in the natural cave part", or "Ah here is the side passage with the statue by it". You could also do things like throw in fog, different types of lanterns or torches, etc. as another way of differentiation. Also, think about the fact that if a player walks for more than about 20-30 seconds along a passageway that has no break or feature change, they are going to begin to think maybe it's time to turn around and go back.
#11
That should accomplish the same thing as the code you posted. Using nested for()'s can do 2d arrays very easily, especially in cases like this. The function I wrote may need a tweak or two since I wrote it out fast (I left the %squaresize thing, because it looked more like a data tag than anything else, so you can change that if you need to), but it's 99% of what you need to streamline that at any rate. Hope it helps.
12/17/2008 (5:11 pm)
@Jacob: What you want to do is make that function into a nested for(), like so:function createGrid (%squareSize){
%posX = 1;
%posY = 1;
%posZ = 10;
for( %i = 0 ; %i < 10 ; %i++ )
{
for( %j = 0; %j < 10; %j++)
{
$Grid[%i,%j] = new ScriptObject();
$Grid[%i,%j].position = (%squareSize * %i) SPC %posY SPC %posZ;
$Grid[%i,%j].isFilled = false;
}
}That should accomplish the same thing as the code you posted. Using nested for()'s can do 2d arrays very easily, especially in cases like this. The function I wrote may need a tweak or two since I wrote it out fast (I left the %squaresize thing, because it looked more like a data tag than anything else, so you can change that if you need to), but it's 99% of what you need to streamline that at any rate. Hope it helps.
#12
For those of you who are watching my progress, here is the next screenshot:
I know this looks quite boring, but it represents a function I just finished up. What you see, is 100 blocks that have been randomly placed. I now have a function that checks to see if a block is full before filling it, so no block is ever placed on top of another. Here is a screenshot of another random mission with only 30 blocks added.
So I think that is a good start, I get to start on the fun generation algorithms tomorrow. I will keep you guys posted!
12/17/2008 (11:20 pm)
First, I want to say thanks to all you guys that are taking the time to help me out. I think I am on to something here and quite frankly... I need all the help I can get.For those of you who are watching my progress, here is the next screenshot:
I know this looks quite boring, but it represents a function I just finished up. What you see, is 100 blocks that have been randomly placed. I now have a function that checks to see if a block is full before filling it, so no block is ever placed on top of another. Here is a screenshot of another random mission with only 30 blocks added.
So I think that is a good start, I get to start on the fun generation algorithms tomorrow. I will keep you guys posted!
#13
This is looking great. An idea for you would be to make some randome textures with arrows representing where doors would be. This way you can make sure your algorythm is working properly. In the last screenshot, there would be no way to leave the original tunnel.
Just some thoughts. :-)
12/18/2008 (2:59 am)
I backed out of this conversation due to the fact you got beyond my abilities quickly.This is looking great. An idea for you would be to make some randome textures with arrows representing where doors would be. This way you can make sure your algorythm is working properly. In the last screenshot, there would be no way to leave the original tunnel.
Just some thoughts. :-)
#14
Just in case you hadn't seen it, but I assume you've read it. :)
12/18/2008 (3:22 am)
Creating Objects Without Creating ThemJust in case you hadn't seen it, but I assume you've read it. :)
#15
@BrokeAss Games - Actually, I didn't see that. I just use the FileObject to write out each individual line to a .mis file. I think serializing the mission just to write it out would adversely affect performance... but I could be wrong.
12/18/2008 (7:21 am)
@Mike - Currently, there are no algorithms in place, so that is why that last shot appears so random. Also, thanks for the idea about the arrows, that sounds like a very effective way to test this stuff out.@BrokeAss Games - Actually, I didn't see that. I just use the FileObject to write out each individual line to a .mis file. I think serializing the mission just to write it out would adversely affect performance... but I could be wrong.
#16
12/18/2008 (7:40 am)
Thats awesome, a randomized city/dungeon generator would be a awesome thing. I have seen a few that had a good start like this one. But none of them made the extra step to package and clean up the code for user friendlyness. ie Docs and working example.
#17
I wrote a couple of new functions to create what you see here. First, the generator picks a random empty grid square and marks it as filled. From there, I call the function getNearbySquare() to randomly choose a square that is adjacent and not filled. If an unfilled grid square cannot be found, it randomly chooses a filled square and starts the process over. The map you see above was generated in less than a second, but took about 30 seconds to light :(. Next, I am going to work on a catalog of dif shapes that can be called upon to fill out the mission a bit.
12/18/2008 (10:41 am)
Time for another update! Below is a platform randomly generated from 20X20 Squares. I wrote a couple of new functions to create what you see here. First, the generator picks a random empty grid square and marks it as filled. From there, I call the function getNearbySquare() to randomly choose a square that is adjacent and not filled. If an unfilled grid square cannot be found, it randomly chooses a filled square and starts the process over. The map you see above was generated in less than a second, but took about 30 seconds to light :(. Next, I am going to work on a catalog of dif shapes that can be called upon to fill out the mission a bit.
#18
12/18/2008 (10:50 am)
It would be faster if you used dts shapes with polysoup collisions applied. Dif takes too long to light, unless you are only generating this during the first load, in which case....disreguard my comment. It is looking really good tho.
#19
Now I have the ability to use mount points, which should make lining things up a bit easier. As a side note, the collisions in this scene were done in Max, as polysoup seemed like a great idea but ended up a disappointment. If 2 dts shapes are side by side, the the player falls through where the shapes meet.
12/18/2008 (2:54 pm)
@Mike - Because the dif files are in different places on every generation, you have to re-light the scene every time. So I took your advice and switched to DTS. Below is an image of 75 of the same size (20x20) .dts squares. This mission took about 10 seconds to load, as opposed to the 5 minutes + to load that many difs.Now I have the ability to use mount points, which should make lining things up a bit easier. As a side note, the collisions in this scene were done in Max, as polysoup seemed like a great idea but ended up a disappointment. If 2 dts shapes are side by side, the the player falls through where the shapes meet.
#20
12/18/2008 (3:14 pm)
Quote:If 2 dts shapes are side by side, the the player falls through where the shapes meet.OOPS. Sorry. I forgot about that, Plus, if 2 polysoup shapes bounding boxes touch, it will lag your game horribly. (haven't tried it in tgea yet) Collision shapes will work just fine for this tho. What you have there is great. :)
Torque Owner Mike Rowley
Mike Rowley
As for placing them at random, you could save all the peices in a text/script file and call getRandom(); to randomise them. (you may have to write the function as I don't know if it exists in the engine.) I've never attempted anything like this, so can't help you much there. Ed Maurinas books show you how to write/read from a text file to get objects into a world.