Abstract Dungeons
Introduction
Abstract dungeons are a nice method for non try and error approaches. They help you designing more higher level features and reduce randomness in a way which could make the game much more interesting and beatable.
This page is somewhat related to Grid Based Dungeon Generator.
Terms
Area usually means a rectangle or generally a polygon which is used to define the borders of any part of the map.
Gateway is a cell which serves as a final connection between two areas.
Benefits
- fast dungeon generation
- almost WYMIWYG
- reduced trial and error
- same dungeon can be painted with different styes
- easy rejection of unwanted dungeons
Drawbacks
- based upon the layout-algorithm maybe not good looking distribution
Abstract layout
The first thing to do is do create the basic layout of our map. This can be done in several ways, some of them i'll mention here:
Uniform grid
This is the approach used in Grid Based Dungeon Generator and many games. The map is divided into a grid of areas, resulting in a mostly aligned dungeon layout. Some areas can be joined together to make longer corridors or just different shaped rooms.
This grid can be usefull for more artificial maps, like a building, space stations and starships.
BSP
Binary space partioning is somewhat more elegant as it results in a more uneven distributed layout. It starts by dividing the whole map into 2 smaller areas, and repeats the step for each new area until a specified area condition is met.
With this approach i usually pass parameters like minimum width/height/area as conditions. Furthermore i'm sometimes dividing areas into even distributed grids, so that a area is not always splitted into two minor parts.
BSP is usable for most fantasy dungeons.
Custom evolving strategy
You could also implement a custom strategy for map layout. A nice example would be to start with a long corridor and attaching symetrical areas to the borders of alreaty existing ones.
This could also result in nice spaceship design.
Knowing your neighbours
After the map is created, each area is checked for neighbours. This is rather straightforward for rectangles, a example quick and dirty implementation could be as the following (D Code):
private void getAreaNeighbours() {
for (int source=0;source<_areas.length;source++) {
for (int test=source+1;test<_areas.length;test++) {
Area s = _areas[source];
Area t = _areas[test];
bool found = true;
if (
(s.x2 < t.x1) ||
(s.y2 < t.y1) ||
(s.x1 > t.x2) ||
(s.y1 > t.y2)
) {
found = false;
}
// do additional processing
if (found) {
bool testLines(int p1, int p2, int s1, int s2) {
if (
((s1 >= p1) && (p2-s1>2)) ||
((s1 <= p1) && (s2-p1>2))
) {
return true;
}
return false;
}
found = false;
if (s.x1 == t.x2)
found |= testLines(s.y1, s.y2, t.y1, t.y2);
if (t.x1 == s.x2)
found |= testLines(s.y1, s.y2, t.y1, t.y2);
if (s.y1 == t.y2)
found |= testLines(s.x1, s.x2, t.x1, t.x2);
if (t.y1 == s.y2)
found |= testLines(s.x1, s.x2, t.x1, t.x2);
}
// Error: cannot append type game.mapgenerator.Room to type Room[]()|
if (found == true) {
s.addNeighbour(t);
}
}
}
}
The above code also guarantees that two areas do not count as connected if they just touch by corners. The neighbours should be stored related to the area.
Abstract connections
Since the map layout is finished and every area knows its neighbours, the hard work can begin. Usually the map needs a entrance and a exit, no matter if they are implemented as stairs, lifts, teleports. Two areas are marked for that purpose. (Its up to the implementation to chose areas far away from each other)
Now a simple A* algorithm can traverse the map starting at the area marked as entrance. If it reaches the exit, we have a single, guaranteed route to the exit. The route can be directed by "influence points", which can be spread whole over the map. The points add costs for visiting a room by distance to the point. Of course you could give certain rooms additional costs if you want to place a special item there which should not be on the way to the exit:
In the below example a influence point was placed in the middle of the map to avoid a straight connection from start to exit:
################################################ # # # # # # # # # # # # # # # # # # # # # # # # # # # ######## # # # # # # # # #################### ############### # # # # ######## # # # # # # # # # # # # # # # # # # # # # ######### # # # # # # # # # # # # ############# # # ######## # # # # # # # # ############### # # ############### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ################################################ # # # # # # # # # # # # # S # # # # # # # # # # # # # # # # # # # # # # # # # # # #########...######### # # # # # # # # # # # # # # # # # ############################ # # # # # # # # # ######### ###### # IP# # # # # # # # # # # # E # # # # #......# # ########## # # # # # # # # # # # # # # # # ####### # # # # # # # # # # # #.....####### #########.....####### # # # # # # # # # # # # # # # # # # # # # # # # # # #################....####### # # # # # # # # # # #......####### # # # # # ######## . # # # # # # # # . ########## # # # # # . . . ######## # # # # . . . . # # # # # . . . . #.....###### # # . . . . . # # # # . . . . . # # # # . . . . . # # ################################################
Its up to the levedesign to create a new route, e.g. one with different enemies so that the player could "choose" a path. For that purpose every area established as a route gets additional costs (maybe their neighbours too). This avoids taking the same route twice until A* can't get any further.
################################################ # # # . . # # # # # # # . . # # # # # # # . . # # # # # ######## S . . ############## # ######## # . . # # ##### # # #...# . # # # # # # . # . # # # # # # . #####..############# # # # # . # # # ########### ########....####### # # # # # # # # # # # # # # # # # #......# # # # # # # # # ############# ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # ########..#########......####################### # . # # # . . # # # # . # # # . . # # # # . # # # . . # # # # ######################### # ####### # # # # # # # # # # # # # # IP# # # # # # # # # # # # # # # # #....##########################.....############ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ####### # # # ###### # # # # ######### ####### # # # # # # # # # # # # # # # # # # # #....########### # # # # # # . ###############......############ # . . # # # # # # . . # # # # # ######## . # # # # # # #########......#######.......# # # # # # # # # ############ # # # # # # . . # ######## # # # # . . # # ######### # # . . E # # # # ##################### # # # # . . . . . # # # # . . . . . # # # # . . . . . # ################################################
Even a mostly linear level with a workaround for the big fat monster (BFM) could be possible. Just pick a area which features BFM and reroute using a new A* algorithm; starting some areas before to some areas after the monster.
################################################ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ############# # # # # # # # # # ########## ########################### # # # # # # # # # # # # # # # # # # # # # # # S # # # # # # # # # # # # # # # # # # # # # ###################### #......##### # # # # # # # # # # # # # # # # # ################ # # # # # # # # # ########## ######## #...######## # # # # ###### # # . # # # # # # # # # . # # # # # # # # # . # # # # # # # # # . # # # # # # # # #####..######################################### # START. . # # # # # # #REROUTE . # # # # # # # . . # # # # # # #......# . ####### # # # # # ######.....# # # # # # # # # # # # # # # # # # # ######################## # # # # IP # # # # # # # # # # E # # # # # # # # # # # # # # # #......####### #...########...########## # # # # # # # # ########### # # # # # # # # # # # #BFM# # # # # # # # # ##### # # # #......####### # # #......########## # # # # # # # # # # # # # # # # # ########### # # #...##### # # . . # # # # . #......###### . . #......# # # . . END . . . . . # # # . .REROUTE . . . . # # # . . . . . . . # # ################################################
The next step could be to randomly attach every non connected room to a already conncted one:
################################################ # . # # . . . . # # . # # . . . . # # . # # . . . . # # . # # . . #.....# # # . # # . ##### # # # . #.....##....# . # # # ##########....# . # . # # # # # . . . # . # # # # # . . . #....#############...# # # . #......#....# # . . # # #...# # # # # . . # #....# ###### # # # . . # # # . # # # # ######.....# # # . # # # # # # # # # . # # ########### # # #...##..##....######## . . # # # # # # # . . . # #......# # # # # . . . # . # # # # # . . . # . # # # # # . . . # . # #...##..##....##.....##...######..#########....# # . # # # # # # . . # # . # # # # # # . . # # . # # # # # # . . # # #...# ######## # # # . . # # # # # . # # # . . # # # # # . # # #...#####....# # # # # #...#...##### # . # #....#######...######## . # # . # # # # # . . # # . # # # # # . . # # . # # # # # . . # # . # # #...# # . . # # . # # . ######## #####################....# # . . #...# # # # . # #......# . # # # # # . # # ##### # # # # # . # # # # # # # # #...####### # # # # # # # # . # #......# # # #.....#....#...# . # # #...############ . # . # # . . . . #...####### # . . . . . . # # . . . . . . # # . . . . . . # # . . . . . . # ################################################
There are much more things possible, maybe it will be continued.
Connections have to be stored the same way as neighbours; if you keep this state it could also be usefull for fast pathfinding.
Abstract Theming
Now we've got a fully abstract, but boring dungeon. In fact, at this stage no walls are painted, the whole dungeon only exists as a graph. Lots of objects/structs, some routes and some areas marked for special purposes. The next step is theming, which is done on a per area basis.
############################################### # # # ## ######## # # # # ## ######## # # + # ## # # # # # # ## # + # # # # ## # # # # #+######## + # # # ####### ###########+#### + # # ####### ########## ############ ######### ######## ######### ### ####+### # ######## ########## ### # ## # ######## ##### ### # ## # #### ### # ### ### # ## # #### ## # ### # ## # ## # #### + #### + ## ## # ## # ####+########+######+#####+##################+# ### ######## ###### ##### ##### # # ### #### ###### ##### ##### # # ### #### ###### #### #### # # ### ## ###### #### # #### # # ##### ## ###### + # #### # # #### ## ############# #### # # #### ##################### #### # # #####+################### #### + #### ## ########### #+###########+######### ### ############# # ########### ######### ## ############# # ###### ######### # ###### ###### # ### ############ # # ##### ###### # # ### ##### #### # # ### ###### + ### ## #### #### # + # ###### ###### + + #### ###+######+##############################+##### # ### ######### + ########## + #### # #### ####### ### ######### ## ### # ##### ###### #### ######### ### ### # ##### + ##### ######### ###### ### # ##### ############ ####### ###### ### ########## #############+###### ######## # ########## ############### ##### ##########+## # ###+############### #####+####### # # + # + # ### ###### # # ## # # ## ### #### # # ## # # ### # #### # # ## # # # + #### # # ## # ################# # ######### # ################# # ###############################################
############################################### #### + ###### + ##################### ## ###### ###### ###### ######## + #### ## + ###### ###### + ##### #### ## ####### + + + # ##### #### ## ################################ ##### ### ## ################################+###### ### ##++################### ##### ###### ### # ############### ##### ###### ### # + ############ ##### ######+### # ## ####### ### ##### ###### ### # ## ####### ### # ###### ### # ## + ### # ######### ### # + + ### + + # # ########## ### # ########### # #+################++############+###########++# # ################ ############ # #### # # ####### ### ############ # #### # # ####### ### + ### #### # # #### + #### ##### #### ## #### #### # ### #### ## ##### #### ## #### #### # ### + ##### #### ## #### #### # ########+##+###############+## ####+########### ######## ## ############### ## #### ###########+######## + ####### ## #### ########### ## + # # #### ########### ############ ## # #### # #### ########### ############ ## # #### # ## ### ###### ############ ## # #### # ## #### # ###### ############ ## # #### # ## + ###### ############ ## # #### # ###+####+##########################+##+#+####+# # ## ############### + + # # ## ############### #### ## # # # ## + #### #### ## # # # ######## #### #### #### + # # ######## #### ## ########## # ############## ###### ## ########## # ############## ###### ##################### ### ############## ######+##################### ### # ########+###### #####################+### # + ## #### #### + + ### # ##### ## #### ###### ######## ####### ### # ##### #### ###### #################### # ############# ###### #################### # ############# + #################### ###############################################
The above dungeons are generated using two painters:
- Room painter
- Tunnel painter
The first one has tunnels assigned to the main routes, everything else is a room.
The second one has assigned a painter based upon the number of connections; room painters for endpoints, tunnel painter for areas with more then one connection.
A third one could make the left part as tunnels and the right part as rooms, or assign painters based on treasures, monsters and so on.
In any case, these assignment were made before actually painting.
Easy painting
Now the painting starts per Area. The only thing to worry about is to make the area accessible to each neighbour. This can be done as the following:
Given Area A1 we already know its connections, the theme and the theme of the connected room. First we need to get a list of cells which can be served as openings to the other area, again with some ugly, unoptimized D-Code:
private Cell[] getNeighbourCells(Room s, Room t) {
Cell[] result;
int x1 = s.cellX1;
int y1 = s.cellY1;
int x2 = s.cellX2;
int y2 = s.cellY2;
int x1b = t.cellX1;
int y1b = t.cellY1;
int x2b = t.cellX2;
int y2b = t.cellY2;
void isIn(int x, int y) {
if ( (x >= x1b) && (y >= y1b) && (x <= x2b) && (y <= y2b) ) {
if (
((x == x1b) && (y == y1b)) ||
((x == x1b) && (y == y2b)) ||
((x == x2b) && (y == y1b)) ||
((x == x2b) && (y == y2b))
)
return;
result ~= cellAt(x,y);
}
}
// don't allow corners
for (int x=x1+1;x<=x2-1;x++) {
isIn(x,y1);
isIn(x,y2);
}
for (int y=y1+1;y<=y2-1;y++) {
isIn(x1,y);
isIn(x2,y);
}
return result;
}
The above code just loops through each cell of our current area and checks where its borders overlap with the connected one. After it is finished it returns a array of cells.
Now based upon the painter of our current and the neighbour area, we can choose how many cells should serve as a passage next to each other. Two "cave" painters could use the whole bunch of cells, two rooms usually choose a random single cell which serves as a door. A Room connected to a cave could either result in a door (1 cell) or a huge hole in the wall (2 or more cells). Anyway, these cells are marked as fixed and free and are stored as 'gateways' in that area; they are never allowed to be a wall. This can be done in advance for every area.
After this is done, the painter of a area is responsible for filling its area. A room painter would draw a wall on its borders (remember not overpainting fixed cells), a tunnel painter could fill the whole area with wall and draw a line from each gateway to the center, so they are guaranteed to connect. In fact, this step could be done for every painter, so that these cells are marked as fixed and free too.
Remarks
If the resulting rooms look to evenly distributed, the painting algorithm for rooms can be tweaked to not fill the entire area and skip some columns/rows. Additional the room painter has to draw a corridor to its center to count for the offset.
Roundtrips as seen above are possible if two gateways are choosen between two tunnel areas.
to be continued...