Game Development Community

Random Dungeon Generator

by Corey Martin · in Torque Game Builder · 05/04/2005 (6:23 am) · 13 replies

I've been a long time fan of roguelikes and have always dreamt of putting my own together. I've built various parts and pieces of them in different languages and api's over a few years, and one of the components i've had a lot of fun with is the random dungeon/level generation.

I've put together a pretty decent generator in TorqueScript. It's not very fast, so I imagine i'll have to buckle down and figure out the C++ equivellant and implement it via source if it's to be of real use. That aside, it's coming along well, and i'm happy with the results so far. Dungeons are currently created according to several toggles and settings passed along during generation. Things like maximum and minimum room size, maximum hall segment lengths, whether rooms can be built on top of each other, whether halls can be built adjacent (for a double-sized hall effect), and more to come. Rooms and halls are flagged differently than rooms so individual effects or triggers can be fired accordingly.

Here are a few screenshots of some random levels:
tasha.usedbarcode.net/~stoney/RandomDungeon/RandomDungeon-1.jpg
tasha.usedbarcode.net/~stoney/RandomDungeon/RandomDungeon-2.jpg

#1
05/04/2005 (6:47 am)
Hey, cool stuff. :) This could certainly come in useful for people, though its implementation would be the key to its usefulness. Looking forward to seeing this progress. :)

On another note, I don't see that it has to be fast, per se, since the likelihood of needing random level generation on the fly is pretty much nil. More than likely the map would be generated before level load, and then saved out for that session/game. Of course, faster's nice, too, but if we're talking about the difference being in terms of seconds, it shouldn't be all too bad as is.
#2
05/04/2005 (8:54 am)
I've added some additional toggles for newly implemented settings. For one, you can specify maximum rooms now (because before, the generator could and would generate sprawling dungeons with 50+ rooms if it did so within the allowed number of recursions), you can specify whether intentional dead-ends are allowed, and i've implemented a toggle for controling whether rooms are allowed to be built directly adjacent (which forms a larger, single room if allowed to happen). These new checks result in a more controlled, cleaner looking level. Of course, the chaotically designed maps like the ones above would still be desirable for certain types of levels, which is why all of the new features are implemented as toggles. Another thing I implemented right before I posted the above pics, but neglected to mention, is that the dungeon starts out at a parameter passed size at creation, and after all the features have been 'carved out', the unused portions of the map are trimmed down to perfectly fit the map, eliminating any wasted space.
#3
05/04/2005 (9:27 am)
Nice. I agree that you shouldn't worry too much about speed, you only need 1 per level right? :)

This motivates me to get back to *my* dungeon generator and finish it up. My basic approach was to tunnel a perfect maze, then add details (like rooms and such) then do a clean-up pass. I'm not done yet but I like the results. The resulting dungeons are VERY different from yours though. Mine have a much more engineered feeling so it would be horrible for a sprawling cave or anything of the sort. Yours seems like it would be a better fit for something like that. It would be a different gaming experience.
#4
05/04/2005 (9:42 am)
I've added some additional toggles for newly implemented settings. For one, you can specify maximum rooms now (because before, the generator could and would generate sprawling dungeons with 50+ rooms if it did so within the allowed number of recursions), you can specify whether intentional dead-ends are allowed, and i've implemented a toggle for controling whether rooms are allowed to be built directly adjacent (which forms a larger, single room if allowed to happen). These new checks result in a more controlled, cleaner looking level. Of course, the chaotically designed maps like the ones above would still be desirable for certain types of levels, which is why all of the new features are implemented as toggles. Another thing I implemented right before I posted the above pics, but neglected to mention, is that the dungeon starts out at a parameter passed size at creation, and after all the features have been 'carved out', the unused portions of the map are trimmed down to perfectly fit the map, eliminating any wasted space.
#5
05/04/2005 (9:45 am)
@Ken
Sounds cool! I'd love to hear more about it. The idea of randomly generating a game experience fascinates me. I (pipe?) dream of having randomly assembled quests and plots in this particular project somewhere down the road.

Per my above post, I have some toggles implemented now which achieve a similar sort of engineered look, but from the sounds of it, not to the same degree as yours. I'll post up some new screenies tonight after work.
#6
05/04/2005 (11:01 am)
Wow, impressive work! I was doing some random map generation in Unreal and was hoping to do some in T2D later down the road - so it's good to see this kind of stuff running. And with only TScript no less.
#7
05/04/2005 (12:38 pm)
And to think you can actually achieve this with TorqueScript! Wow, neat stuff!:)
#8
05/05/2005 (5:39 am)
tasha.usedbarcode.net/~stoney/RandomDungeon/RandomDungeon-3.jpg
Here's the aforementioned new shot. I've put a lot of revisions in place, and have been able to speed up the creation, but only as a secondary effect. What i've put together isn't really an algorithm, it's more of a heuristic. That is, it's never guaranteed to succeed. It merely keeps trying (or tries a specified number of times) until it meets the given criteria. I've put a lot of time into tweaking the actual creation code to produce acceptable dungeons most of the time. It will generally only take 1 attempt to produce a dungeon acceptable by the given parameters. Currently, it takes between 2 - 2.75 seconds to create a dungeon. If it takes more than one attempt to get a dungeon that is acceptable, the times obviously add up. The ratio of successes to failures and times to create will fluctuate depending on the parameters used. For example, a dungeon with very short hall segments will probably take longer to generate and/or fail more often due to the fact that it will attempt to create rooms very close together, and many checks and retries will be made throughout the creation of the level. I'm going to experiment a bit more with the settings to try and establish an 'effective range' to see just how the time scales.
#9
06/01/2005 (11:28 am)
I think this has great uses. might try to hack my own together.

have you managed to get it working in a game yet?
#10
06/01/2005 (7:06 pm)
Not as of yet (priorities of time have recently shifted), though it was made with the intention of putting together a roguelike. It was put together using ideas from several of the dungeon building articles over at www.roguelikedevelopment.org.
#11
06/04/2005 (8:47 am)
Cool thanks for the link.
#12
05/29/2006 (6:52 am)
I had written a very simple dungeon generator a couple of years ago when I was first learning Torque. It took simple building blocks and created a completely random 2d dungeon. This is completely random generator, it basically just does a quick check to make sure that the blocks line up correctly and generates. Looking back at it now it's doing things in a pretty inefficient manner considering that it's using a lot more difs than it needs to, where it could be rotating them instead. It's also very simplistic, it only generates one level and with portals simply for up, right, down, left (north, south, east, west). But I dug it up nonetheless...

// This file demonstrates a very simple dungeon generation system written entirely
// in Torquescript. By fiddling with the setting variables below you can use this
// script to create dungeons and automatically insert them into your world. 
// For the time being this script is very simple, and only loads geometry. Over time
// I plan to add details features to it.
//-----------------------------------------------------------------------------


function GenerateDungeon()
{
	echo ("Initializing Dungeon Generator");
	%initialx = 0; // Initial X, Y and Z positions, the entire map will be based on these start locations
	%intialy = -0;  // Meaning this is where the dungeon is placed in the world.
	%initialz = 50.45;
		%xsize = 24.5; //This determines how much to step for each tile. Having thisecho configurable allows you to use different
	%ysize = 24.5; //sized blocks for different maps.
	%zsize = 8.166;
	%numx = 5;	// Number of tiles to use for the x for each level
	%numy = 3;	// Number of tiles to use for the y for each level
	%numlevels = 0;	//Maximum number of levels (height).
	%initiallevel = 0;	// Level to start on. This allows you to have dungeons that go up and down
	%playerx = 0;	// Initial x/y/z position of player.
	%playery = 0;
	%playerz = 0;
      %maxblocks = 15; // Maximum types of blocks for this generation
      %maxtiles = 0; // Maximum number of tile looks
	%directoryname = "~/data/interiors/dungeons/";	// name of directory where dungeons are located
	%maxmatches = 6; // This determines the maximum number of matches we will keep track of for the generator

	// The %blockname array works like this... the first value = $name of the .dif file... the next values are booleans
    // which determine if you can connect in a specific direction. In this case it goes: norht south east west 

	echo ("Initializing Blocks");
	%blockname[0,0] = "O.dif";  // Wide Open
      %blockname[0,1] = 1; // north
      %blockname[0,2] = 1; // west
      %blockname[0,3] = 1; // east
      %blockname[0,4] = 1; // south

	%blockname[1,0] = "F.dif";  // Four Way Intersection
      %blockname[1,1] = 1; // north
      %blockname[1,2] = 1; // west
      %blockname[1,3] = 1; // east
      %blockname[1,4] = 1; // south

	%blockname[2,0] = "U.dif";  // North Only
      %blockname[2,1] = 1; // north
      %blockname[2,2] = 0; // west
      %blockname[2,3] = 0; // east
      %blockname[2,4] = 0; // south
	
	%blockname[3,0] = "L.dif";  // West Only
      %blockname[3,1] = 0; // north
      %blockname[3,2] = 1; // west
      %blockname[3,3] = 0; // east
      %blockname[3,4] = 0; // south

	%blockname[4,0] = "R.dif";  // East Only
      %blockname[4,1] = 0; // north
      %blockname[4,2] = 0; // west
      %blockname[4,3] = 1; // east
      %blockname[4,4] = 0; // south

	%blockname[5,0] = "D.dif";  // South Only
      %blockname[5,1] = 0; // north
      %blockname[5,2] = 0; // west
      %blockname[5,3] = 0; // east
      %blockname[5,4] = 1; // south

	%blockname[6,0] = "UD.dif";  // North/South
      %blockname[6,1] = 1; // north
      %blockname[6,2] = 0; // west
      %blockname[6,3] = 0; // east
      %blockname[6,4] = 1; // south

	%blockname[6,0] = "LR.dif";  // East/West
      %blockname[6,1] = 0; // north
      %blockname[6,2] = 1; // west
      %blockname[6,3] = 1; // east
      %blockname[6,4] = 0; // south

	%blockname[7,0] = "UDL.dif";  
      %blockname[7,1] = 1; // north
      %blockname[7,2] = 1; // west
      %blockname[7,3] = 0; // east
      %blockname[7,4] = 1; // south

	%blockname[8,0] = "ULR.dif";  
      %blockname[8,1] = 1; // north
      %blockname[8,2] = 1; // west
      %blockname[8,3] = 1; // east
      %blockname[8,4] = 0; // south

	%blockname[9,0] = "URD.dif";  
      %blockname[9,1] = 1; // north
      %blockname[9,2] = 0; // west
      %blockname[9,3] = 1; // east
      %blockname[9,4] = 1; // south

	%blockname[10,0] = "DLR.dif";  
      %blockname[10,1] = 0; // north
      %blockname[10,2] = 1; // west
      %blockname[10,3] = 1; // east
      %blockname[10,4] = 1; // south

	%blockname[11,0] = "UL.dif";  
      %blockname[11,1] = 1; // north
      %blockname[11,2] = 1; // west
      %blockname[11,3] = 0; // east
      %blockname[11,4] = 0; // south

	%blockname[12,0] = "UR.dif";  
      %blockname[12,1] = 1; // north
      %blockname[12,2] = 0; // west
      %blockname[12,3] = 1; // east
      %blockname[12,4] = 0; // south

	%blockname[13,0] = "DL.dif";  
      %blockname[13,1] = 0; // north
      %blockname[13,2] = 1; // west
      %blockname[13,3] = 0; // east
      %blockname[13,4] = 1; // south

	%blockname[14,0] = "DR.dif";  
      %blockname[14,1] = 0; // north
      %blockname[14,2] = 0; // west
      %blockname[14,3] = 1; // east
      %blockname[14,4] = 1; // south
#13
05/29/2006 (6:53 am)
Continued...

//	echo ("Clearing Old Dungeon Data");
//	for (%i = 0; i< %numy; %i++)
//	{
//		for (%j = 0; %j < %numx; %j++)
//		{
//			for (%t = 0; %t < 4; %t++)
//			{
//				$dungeondata[%j,%i,%t] = 0;
//			}
//		}
//	}
//	echo ("Old Dungeon Clear");

	for (%i = 0; %i< %numy; %i++)	// do generation for each amount in y size
	{
		for (%j = 0; %j < %numx; %j++) // calculate this row
		{
			echo ("Generating Block: " @ %j @ ", " @ %i);
			// We are now going to create a temporary array which will hold the following four values
			// 0 - north 1 - west 2 - east 3 - south... We will store a 0 in any direction that we 
			// can not link up with. If we store a value of 2 in any direction that means that we MUST link
			// to that direction in order for the map to line up properly.

			$tempblock[0] = 1; 	// Initiliaze tempblock to be able to move in each direction
			$tempblock[1] = 1;
			$tempblock[2] = 1;
			$tempblock[3] = 1;

			// First we will test to make sure we aren't on any of the four map edges. If we are we will
			// disable to leave an opening off the map
			// After this must check the values of the block locations to the top and the left of us
			// To make sure that the openings all line up correctly. We do not check the bottom or right
			// Because those blocks have yet to be generated.


			if (%i == 0) // Are we on the far top
				{
					echo ("We're on the far top");
					$tempblock[0] = 0;
				}
			else // We aren't on the top so let's check the value above us to see what we can fit with
				{
					echo ("Not on far top, so check to see if the block above is connecting");
						if ($dungeondata[%j, %i-1, 3] == 1) // does the block to the north have an opening here?
							$tempblock[0] = 2; // if so we must generate an opening, as well
				}
			
			if (%j == 0) // Are we on the far left?
				{
					echo ("We're on the far left");
					$tempblock[1] = 0;
				}
			else	// We aren't on the far left so let's check the value next to us to see what we can fit with.
				{
					if ($dungeondata[%j-1, %i, 2] == 1) // does the block to the west have an opening here?
						$tempblock[1] = 2; // if so we must generate an opening, as well
				}
			if (%j == (%numx -1)) // Are we on the far right?
				{
					echo ("We're on the far right");
					$tempblock[2] = 0;
				}
			if (%i == (%numy -1)) // Are we on the far bottom
				{
					echo ("We're on the far bottom");
					$tempblock[3] = 0;
				}
			// Generate the Connections

			for (%t = 0; %t < 4; %t++) // Do once for each of the four directions
			{
				if ($tempblock[%t] == 2)	// Do we have to go this direction?
					{ 
						echo ("Must go direction: " @%t);	
						$dungeondata[%j, %i, %t] = 1;	// If so set it to 1
					}
				else if ($tempblock[%t] == 0) // Does it have to be empty?
					{
						echo ("Border, we must be closed: " @ %t);
						$dungeondata[%j, %i, %t] = 0; // If so make it empty
					}
				else
					{
						%temp = getRandom (15);
						if (%temp > 1)	// We want mostly matches
							%newtemp = 1;
						else
							%newtemp = 0;
						echo ("We did a random the the result was: " @ %newtemp);
					  $dungeondata[%j,%i,%t] = %newtemp; // Store the value
					}
				echo ("Set as " @ $dungeondata[%j, %i, %t]);
			}


			// Okay we now have generated the areas where we need portals to. Now we have to find a
			// a suitable block which can support them. We will do this by creating a temporary value called
			// Fits found. This is definately very un-optimized code, but it makes it easier to understand
			// and works fine for what we are trying to do.

			// As we cycle through each block, every time we find a block that matches our requirements we will
			// Store it's block number in %match[%matchesfound], and we will increase matches found by 1. We will
			//repeat this process until we either hit our maximum number of matches (for this example hard coded
			// at 6) or until we have cycled through all of the blocks.

			%matchesfound = 0;  // How many matches we have found so far
			%match[0] = -1; // Storage area for each match, if we find a match we will store it 
			%match[1] = -1;
			%match[2] = -1;
			%match[3] = -1;
			%match[4] = -1;
			%match[5] = -1;

			for (%t = 0; %t < %maxblocks; %t++)	// Start cycling through our blocks to find a suitable fit	
			{
				if (%blockname[%t,1] == $dungeondata[%j, %i, 0]) // do we match for north?
				{ 
					echo("North Fit");
					if (%blockname[%t,2] == $dungeondata[%j, %i, 1]) // do we match for west?
					{
						echo ("West Fit");
						if (%blockname[%t,3] == $dungeondata[%j, %i, 2]) // do we match for east?
						{
							echo ("East Fit");
							if (%blockname[%t,4] == $dungeondata[%j, %i, 3]) // do we match for south?
							{
								echo ("We have a match!");
								if (%matchesfound < %maxmatches)
								{
									%match[%matchesfound] = %t;
									%matchesfound++;
								}
									
								
							}
						}
					}
				}
			}

			// At this point we have our matches stored, now let's randomly pick one and place it into the world
			%temp = getRandom(%matchesfound-1);	// Pick a random match
			echo ("Random = " @%temp);
			echo ("Match 0 = " @ %match[0]);
			echo ("Match 1 = " @ %match[1]);
			%blocktouse = %match[%temp];
			echo ("Block to use = " @ %blocktouse);

			echo (%directoryname @ %blockname[%blocktouse,0]);
			%posx = %initialx + (%xsize * %j);
			%posy = %initialy - (%ysize * %i);
			%position = %posx SPC %posy SPC %initialz;
			echo ("Position: " @ %position);

			%obj = new InteriorInstance()
			{
				position = %initialx + (%xsize * %j) SPC %initialy - (%ysize * %i) SPC %initialz;
				rotation = "0 0 0";
				scale = "1 1 1";
				
				interiorFile = %directoryname @ %blockname[%blocktouse,0];
				 showTerrainInside = "0";
			};
			MissionCleanup.add(%obj);

			// We're all done, let's move on to the next map section!
			
		}
	}			
}

The dif names are named things like DR (down and right have doors), ULR (up, right and left have doors) etc. A better way of course would have been to rotate the difs instead, but I wrote this a couple of years ago when I was just getting my feet wet.