A technique that I've had some luck with in the past is working with perfect mazes (meaning there is always a valid path from start to finish) and modifying them. I got the idea from a web site I stumbled upon some time ago while researching this stuff. Sadly I no longer have the link or the author's name.
For instance, if we start a basic DFS style maze:
Initialize an array of empty cells
Keep a stack of visited cells for backtracking
Track how many cells we've visited in total
Pick a random cell to start and mark as visited
do
{
find all neighbors of the current cell that have not yet been visited (no exits)
if we have neighbors
{
pick a random one to move into
knock down the wall between the cells
mark the current cell as a corridor, non-wall, etc
add the current cell to our stack
set current cell to the next cell
iterate visited count
}
else
{
get the last cell on our stack
set as current cell
}
} while(cells visited < total cells)
Then we proceed to shrink the maze a bit by finding all of the dead ends (that is, cells with only one exit) and removing them N number of times.
for n = 0 to iterations
{
loop through all cells and add the ones with a single exit to a list
for each cell in the list
{
remove the exits from this cell and the cell it leads to
remove the cell by setting it to 'empty'
}
}
Next we extend the remaining dead ends until they collide with an existing corridor/cell. This will create loops and remove all dead ends. This part is pretty much the same as the maze generation, but with a different termination clause.
loop through all cells and add the ones with a single exit to a list
keep a stack of cells we have visited
for each cell in the list
{
do
{
find all neighbors of the current cell that are not in our visited stack
if we have neighbors
{
pick a random one to move into
knock down the wall between the cells
mark the current cell as a corridor, non-wall, etc
add the current cell to our stack
set current cell to the next cell
}
else
{
get the last cell on our stack
set as current cell
}
} while(the current cell has only one exit (ie, is still a dead end))
}
From here you have the basic layout of a dungeon done. You have a fully navigable set of corridors and only need to add the 'rooms'. Probably the easiest way is to simply take the leftover empty space and designate those as rooms. Add a door along a random wall that touches a corridor, and you're done!
Another method that works well for room placement, especially if you'd like to have pre-designed room chunks, is to do the following:
for r = 0 to roomsToPlace
{
choose a random room from a preset list
give the room a default large score (max int, for instance)
for y = 0 to mapHeight, y += roomHeight
{
for x = 0 to mapWidth, x += roomWidth
{
'place' the room's top-left corner at x, y
keep a temp score for this location
for each cell along the room's walls
{
for each outer neighbor of the wall cell
{
if mapCell == corridor
tempScore += 1;
if mapCell == room
tempScore += 100;
if mapCell overlaps the room cell
tempScore *= 3;
}
}
if tempScore < score and tempScore > 0
{
score = tempScore
set the room's real position to x and y
}
}
}
}
This will let you generate dungeons with your pre-frab rooms while maintaining some randomness in terms of placement while also ensuring that the rooms will always be attached to corridors. Changing the weights around will give drastically different results so there's room for customization, as well as adding weights above and beyond the basic ones listed there.
EDIT: Fixed bad room chunk placement code.
Show Posts
Where do you get them made?
