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
#22
If you're worried about collision, maybe use invisible DIFs to collide with? But have the visible elements be DTS. That way you don't need to relight, and you can add all the DTS detail you want, and have accurate (and simplified) DIF collision.
12/19/2008 (12:43 am)
That's brilliant! It's great to see someone who knows what they want to do, and then just go out there and do it. A nice break from my own project experience ;)If you're worried about collision, maybe use invisible DIFs to collide with? But have the visible elements be DTS. That way you don't need to relight, and you can add all the DTS detail you want, and have accurate (and simplified) DIF collision.
#23
12/19/2008 (4:42 am)
This is turning out to be really great. You are doing much better than I could.
#24
Some games to look at are Phantasy Star Online (Dreamcast and regular Xbox) then there is the PC game Nosferatu.
Both applied a random generator of sorts, Nosferatu did more so then Phantasy Star Online.
Where Phantasy star online dropped in preconstructed levels for the most part, Nosferatu actually compiled and built the entire game before a player started, this also affected items and enemies.
The way they set this up is similar to mount nodes, depending on what node was in the area a specific room was attached to said node.
IE in Nosferatu when rooms are generated, preset nodes were dumped in them, plus all rooms were precreated, hallways, living rooms, castle dungeons, etc etc. Once a base rooms is dropped, lets say a Hall Way, a node is marked at the end of each corridor, from here Nosferatu would generate a new room that would attach to the nodes, as well as dropping items randomly in object nodes spread about the room.
Nosferatu was a game that hit under the radar, though not spectacular, its random level genrator was amazing.
Something I like best was its generation of multiple floors.
A room with stairs had nodes on it, IE node 1 was bottom floor and node two was top floor, thus the engine new exactly where to put connecting rooms.
I hope this helps further your ideas in development.
1 warning, something the creators Nosferatu wrath of Malachi spoke about is that randomly generated rooms are great, but in some areas you should send players to a basic level that you created, this breaks up the monotony of the game and breathes life into the game.
Say at the final dungeon node once they hit the node marked "exit to enemy boss" they are sent to a mission that was built in constructor or where ever, one that wasn't randomly generated.
it gives a nice human touch to it!
So awesome job with the creation of the game and I hope I was able to give some other games to look at for reference!
12/19/2008 (7:27 am)
Here is an interesting thought to apply to the system, I'm a bit late with jumping onto this wagon but the interest and the growing code has greatly piqued my curiosity.Some games to look at are Phantasy Star Online (Dreamcast and regular Xbox) then there is the PC game Nosferatu.
Both applied a random generator of sorts, Nosferatu did more so then Phantasy Star Online.
Where Phantasy star online dropped in preconstructed levels for the most part, Nosferatu actually compiled and built the entire game before a player started, this also affected items and enemies.
The way they set this up is similar to mount nodes, depending on what node was in the area a specific room was attached to said node.
IE in Nosferatu when rooms are generated, preset nodes were dumped in them, plus all rooms were precreated, hallways, living rooms, castle dungeons, etc etc. Once a base rooms is dropped, lets say a Hall Way, a node is marked at the end of each corridor, from here Nosferatu would generate a new room that would attach to the nodes, as well as dropping items randomly in object nodes spread about the room.
Nosferatu was a game that hit under the radar, though not spectacular, its random level genrator was amazing.
Something I like best was its generation of multiple floors.
A room with stairs had nodes on it, IE node 1 was bottom floor and node two was top floor, thus the engine new exactly where to put connecting rooms.
I hope this helps further your ideas in development.
1 warning, something the creators Nosferatu wrath of Malachi spoke about is that randomly generated rooms are great, but in some areas you should send players to a basic level that you created, this breaks up the monotony of the game and breathes life into the game.
Say at the final dungeon node once they hit the node marked "exit to enemy boss" they are sent to a mission that was built in constructor or where ever, one that wasn't randomly generated.
it gives a nice human touch to it!
So awesome job with the creation of the game and I hope I was able to give some other games to look at for reference!
#25
Here is a picture of my current algorithm with a 10x10 grid of 20meter square dungeon blocks. Though only 72 pieces total. The only reason I used DIF's is because I have no idea how to model a .dts. So, yes, polysoup would work.
Like I said, this really interested me :D I'll post some code once I get it working better tomorrow.
12/20/2008 (10:33 pm)
I saw this thread and it instantly interested me. I just spent today writing this random dungeon generator. It goes over a square grid of places where a dungeon piece can be placed. It scatters a few pieces randomly at the start (this is pretty much what randomizes the rest of the dungeon) and then goes over each x by y spot, and adds a piece with exits matching adjacent rooms, plus random doors going to uncreated areas, or no random doors. I want to spend tomorrow changing the algorithm to instead start by placing a dungeon piece, and then following it along a path creating a dungeon, and clearing up any ends left open, creating a dungeon that can be lengthy and made to fit together, and not just a grid with several pieces matching.Here is a picture of my current algorithm with a 10x10 grid of 20meter square dungeon blocks. Though only 72 pieces total. The only reason I used DIF's is because I have no idea how to model a .dts. So, yes, polysoup would work.
Like I said, this really interested me :D I'll post some code once I get it working better tomorrow.
#26
12/21/2008 (2:38 am)
@Morrock - That looks really good. I would love to take a look at your algorithm once you get it working the way you want to to. I am stumped currently on finding the most efficient way to make the entrances and exits match up, but I think you just about got that nailed. Looking forward to seeing your code tomorrow! 
#27
What I did for this was make a function that "scrubbed" through each cell in the grid and just added pieces that reflected the surrounding exits. Worked 99.9999% reliably, though for some reason every once in a while there would be one piece that was blank. I dropped work on the project before I fixed the issue, but I'm sure it was just something simple.
Great to see other people doing this.
12/21/2008 (6:14 am)
Quote:I am stumped currently on finding the most efficient way to make the entrances and exits match up, but I think you just about got that nailed.
What I did for this was make a function that "scrubbed" through each cell in the grid and just added pieces that reflected the surrounding exits. Worked 99.9999% reliably, though for some reason every once in a while there would be one piece that was blank. I dropped work on the project before I fixed the issue, but I'm sure it was just something simple.
Great to see other people doing this.
#28
and the interiors...
The result:
50 of the 5x5 cells.
My generator starts off with a single cell imaginary cell at 0 0. Nothing is created, and even the shape of the cell is not yet known. From there, a cell is created in a random cardinal direction. This process is repeated with the new cell, and will continue to go on until you've reached the desired number of cells. (defined in the newMaze function.
Then the next phase begins and does what Ted described. It runs through every cell and checks its neighbors. The shape of each cell is now defined. Step 3 is when every cell is created using the correct shape. I have not seen any errors with it so far.
--
That maze/dungeon above was generated in a very little amount of time (excluding the relight). It's got problems as far as distributing the rooms evenly. You'll notice that the cells will clump together often, especially with smaller numbers of rooms. This can be solved by putting a little "weight" in one or two directions in the randomDirection function.
It's not done, I only put about an hour into it, but it's a good start. Pick through the code as you please. I'll post updates later.
12/21/2008 (8:53 am)
Last night I wanted to make a random dungeon generator of my own, so I did.function randomDirection(%current)
{
%random = getRandom();
if(%random < 0.25){return VectorAdd(%current,"0 1");}
if(%random < 0.5){return VectorAdd(%current,"0 -1");}
if(%random < 0.75){return VectorAdd(%current,"1 0");}
if(%random < 1){return VectorAdd(%current,"-1 0");}
}
function newMaze(%length)
{
$mazeRoom[0] = "0 0 0";
$mazeLength = %length;
for(%i=0;%i<%length;%i++)
{
%newRoom = randomDirection($mazeRoom[%i]);
while($isRoom[%newRoom] != "")
{
%newRoom = randomDirection($mazeRoom[%i]);
}
$mazeRoom[%i+1] = %newRoom;
$isRoom[%newRoom] = true;
}
mazeStage2();
}
function mazeStage2()
{
for(%i=0;%i<=$mazeLength;%i++)
{
%roomType = "";
if($isRoom[VectorAdd($mazeRoom[%i],"0 1")])
{
%roomType = "n";
}
if($isRoom[VectorAdd($mazeRoom[%i],"0 -1")])
{
%roomType = %roomType@"s";
}
if($isRoom[VectorAdd($mazeRoom[%i],"1 0")])
{
%roomType = %roomType@"e";
}
if($isRoom[VectorAdd($mazeRoom[%i],"-1 0")])
{
%roomType = %roomType@"w";
}
$roomType[%i] = %roomType@".dif";
}
mazeStage3();
}
function mazeStage3()
{
for(%i=0;%i<=$mazeLength;%i++)
{
new InteriorInstance("")
{
position = VectorScale($mazeRoom[%i],5);
rotation = "1 0 0 0";
scale = "1 1 1";
interiorFile = "~/data/interiors/maze/"@$roomType[%i];
useGLLighting = "0";
showTerrainInside = "0";
};
}
}
function clearMaze()
{
for(%i=0;%i<200;%i++)
{
$isRoom[$mazeRoom[%i]] = "";
$mazeRoom[%i] = "";
}
$mazeLength = "";
}and the interiors...
The result:
50 of the 5x5 cells.My generator starts off with a single cell imaginary cell at 0 0. Nothing is created, and even the shape of the cell is not yet known. From there, a cell is created in a random cardinal direction. This process is repeated with the new cell, and will continue to go on until you've reached the desired number of cells. (defined in the newMaze function.
Then the next phase begins and does what Ted described. It runs through every cell and checks its neighbors. The shape of each cell is now defined. Step 3 is when every cell is created using the correct shape. I have not seen any errors with it so far.
--
That maze/dungeon above was generated in a very little amount of time (excluding the relight). It's got problems as far as distributing the rooms evenly. You'll notice that the cells will clump together often, especially with smaller numbers of rooms. This can be solved by putting a little "weight" in one or two directions in the randomDirection function.
It's not done, I only put about an hour into it, but it's a good start. Pick through the code as you please. I'll post updates later.
#29
I also had another idea that I thought might work well. If the dungeon uses dts shapes. you can create a number of mount points in each room. From there, you can have another random generator populate the room with other dts shapes and mount them. So, for instance, if you want random treasure chests, they can be randomly placed. What do you think? Also, to everyone who is helping this come together. When we get something solid, you guys mind if I add this as a resource?
12/21/2008 (9:53 am)
@Maxwell - absolutely amazing! In about 50 lines of code you managed to guide me all the way through my programmer's block ;) I also had another idea that I thought might work well. If the dungeon uses dts shapes. you can create a number of mount points in each room. From there, you can have another random generator populate the room with other dts shapes and mount them. So, for instance, if you want random treasure chests, they can be randomly placed. What do you think? Also, to everyone who is helping this come together. When we get something solid, you guys mind if I add this as a resource?
#30
The first bug was tiny. In my shape-checking stage, it saw "0 0 0" as a false value, so it would give the wrong shape to cells surrounding the first one.
The second bug required some thought... Cells would snake around, and sometimes there would be nowhere to expand. This was an excellent opportunity to add a 3rd dimension to the cells. If you can't go north, south, east, or west... go down!
100 of the 15x15 cells. Gorgeous, huh? Took only milliseconds to generate.
As you can see, I re-did the cell shapes. (that took some time)
And don't forget your new cell parts.
12/21/2008 (12:02 pm)
Minutes after my post, I found two bugs.The first bug was tiny. In my shape-checking stage, it saw "0 0 0" as a false value, so it would give the wrong shape to cells surrounding the first one.
The second bug required some thought... Cells would snake around, and sometimes there would be nowhere to expand. This was an excellent opportunity to add a 3rd dimension to the cells. If you can't go north, south, east, or west... go down!
100 of the 15x15 cells. Gorgeous, huh? Took only milliseconds to generate.As you can see, I re-did the cell shapes. (that took some time)
function randomDirection(%current)
{
%random = getRandom();
if(%random < 0.25){return VectorAdd(%current,"0 1");}//n
if(%random < 0.50){return VectorAdd(%current,"0 -1");}//s
if(%random < 0.75){return VectorAdd(%current,"1 0");}//e
if(%random < 1){return VectorAdd(%current,"-1 0");}//w
}
function newMaze(%length)
{
$mazeRoom[0] = "0 0 0";
$isRoom["0 0 0"] = true;
$mazeLength = %length;
echo("Making maze of "@%length@" cells.");
for(%i=0;%i<%length;%i++)
{
for(%t=0;%t<20;%t++)
{
%newRoom = randomDirection($mazeRoom[%i]);
if($isRoom[%newRoom] == "")
{
break;
}
if(%t == 19)
{
%newRoom = VectorAdd($mazeRoom[%i],"0 0 -1");
$downPiece[%i] = true;
echo("Going down...");
break;
}
}
echo("Room #"@%i@" located at "@%newRoom);
$mazeRoom[%i+1] = %newRoom;
$isRoom[%newRoom] = true;
}
mazeStage2();
}
function clearMaze()
{
for(%i=0;%i<200;%i++)
{
$isRoom[$mazeRoom[%i]] = "";
$mazeRoom[%i] = "";
}
$mazeLength = "";
}
function mazeStage2()
{
for(%i=0;%i<=$mazeLength;%i++)
{
%roomType = "";
if($isRoom[VectorAdd($mazeRoom[%i],"0 1")]!$= "")
{
%roomType = "n";
}
if($isRoom[VectorAdd($mazeRoom[%i],"0 -1")] !$= "")
{
%roomType = %roomType@"s";
}
if($isRoom[VectorAdd($mazeRoom[%i],"1 0")]!$= "")
{
%roomType = %roomType@"e";
}
if($isRoom[VectorAdd($mazeRoom[%i],"-1 0")]!$= "")
{
%roomType = %roomType@"w";
}
$roomType[%i] = %roomType@".dif";
if($downPiece[%i] == true)
{
$roomType[%i] = "down.dif";
}
if($roomType[%i] $= ".dif"){$roomType[%i] = "single.dif";}
}
mazeStage3();
}
function mazeStage3()
{
for(%i=0;%i<=$mazeLength;%i++)
{
new InteriorInstance("Room"@%i)
{
position = VectorScale($mazeRoom[%i],15);
rotation = "1 0 0 0";
scale = "1 1 1";
interiorFile = "~/data/interiors/maze/"@$roomType[%i];
useGLLighting = "0";
showTerrainInside = "0";
};
}
}And don't forget your new cell parts.
#31
12/21/2008 (8:15 pm)
@Maxwell - Again, you amaze me. You managed to do in a few hours what it was taking me days to accomplish. I would love to try this out, but the link to the interiors is broken.
#34
I don't know about TGEA.
I included the constructor files though, so if you want to make some changes and export them with your exporter of choice, you can do that.
01/01/2009 (10:54 am)
Sorry, I forgot to mention I exported with the Torque 1.5.* exporter. So it will not work in 1.4.*I don't know about TGEA.
I included the constructor files though, so if you want to make some changes and export them with your exporter of choice, you can do that.
#35
01/01/2009 (12:27 pm)
Ah, yes, never thought about that. I'm using this as mod for a game, and I forgot I had to use their exporter. 
Torque Owner Jacob Williams