Some map generation algorithms generate connected maps automatically, because they always work by extending a connected square.
But other algorithms, including cellular automata which produce some of the most natural-looking caves, don’t.
Depending on your map generator, you may need a post-processing step to make sure that your map is fully connected. I wanted one that would not change the outline and contour of any of the generated interiors, so I wrote this.
Here are a couple bits of code that solve the problem, completely. This code is fully general; it will work on any kind of map.
It works by producing successive maps in which the unconnected spaces are brought closer to the top, left corner for as long as it is possible for them to move upward or left. Then, if there are still any unconnected areas, it flips the map around the diagonal that runs from the lower-left to upper-right, and repeats the process. When it terminates, it is guaranteed that all open spaces in the map are joined into a single walkable space.
As an example, here’s the output of a cellular automaton that generates caves. They’re nice looking caves, but in this case they’re not all connected.
################################################################################ #######################..##############...##########.......###############..#### ######################....###..#######.....######............###..#######....### ##########..####...##...........######......####....................#####.....## #########....##.................#######.....####...##................####.....## #########........................######......####.####.....####......####.....## ##########..................##..#######......###.######...######.....####.....## ##############......###....#############....###...##############......##......## ################...#####...###################.....#############.............### ########################...###################.....############....###......#### #####....##############....########...########....######..#####...#####....##### ####......############.....######......######.....######...#####..#####...###### ####.......############....#####.......#####.....#######....#####.#####..####### #####.......############...####.........###....########....######..###...####### ######......#############...##................#########....######........####### ######......##############..##................#########.....######........###### #######.....####..#######...###...............#########.....###########.......## #######......##....###......####..............########......############.......# #######......##...###.......####..............#######........##....#####.......# #######.....###...###.......####..............#######...............#####......# ######......###...###.......####...............######...........##...####......# #####.......###...###.......####...............#######....##...####...##..###..# ####..............####.......##..##...##......########...##########......####..# ####....##........####...........##..####....########....#########.......####..# ###....####........##................#####..#########....######.....##...####..# ##.....####.................##......#################....#####.....##########..# #......####.....###...##...####...###################....####.....##########...# #.....######...#####..###..####..####################....###.....##########....# #.....#######..#####..##..####..####...#############.....###.....#########.....# ##....########..###.......###..####......###########....###.......#######.....## ##....########.................###........###..######..###.........#####....#### ##....#########......##.......####...............########...........####...##### ##.....#########....####......#####...............#######...#####....##....##### ###..........####...####......######............#..######..#######..........#### #######.......####...##......############......##...#####..#######..........#### ########......#####.......##################....#...####...######...........#### #########.....######.....####################.......###.....#####...##....###### ##########....########..######################......###.....######.####..####### ###########..###################################...#####...##################### ################################################################################
Now here they are after running
do joinall(map1,map2); while (joinall(map2,map1) > 1);
What happened was that every unconnected region that could be shifted up or left or both shifted up or left or both until it ran into another region – and the region it ran into, which wasn’t moving in the same direction it was, was one that couldn’t be shifted any further up or left or both because it was already in contact with the upper or left edge.
######################..########...################.......###############..##### #####################....###..#.....############............###..#######....#### #########..####...##.................##########....................#####.....### ########....##.................#.....##########...##................####.....### ########..............................##########.####.....####......####.....### #########..................##..#......#########.######...######.....####.....### #############......###....#######....#########...##############......##......### ###############...#####...###################.....#############.............#### #######################...###################.....############....###......##### ####....##############....########...########....######..#####...#####....###### ###......############.....######......######.....######...#####..#####...####### ###.......############....#####.......#####.....#######....#####.#####..######## ####.......############...####.........###....########....######..###...######## #####......#############...##................#########....######........######## #####......##############..##................#########.....######........####### ######.....####..#######...###...............#########.....###########.......### ######......##....###......####..............########......############.......## ######......##...###.......####..............#######........##....#####.......## ######.....###...###.......####..............#######...............#####......## #####......###...###.......####...............######...........##...####......## ####.......###...###.......####...............#######....##...####...##..###..## ###..............####.......##..##...##......########...##########......####..## ###....##........####...........##..####....########....#########.......####..## ##....####........##................#####..#########....######.....##...####..## #.....####.................##......#################....#####.....##########..## ......####.....###...##...####......################....####.....##########...## .....######...#####..###..####........##############....###.....##########....## .....#######..#####..##..####..........###..#######.....###.....#########.....## #....########..###.......###..#...............#####....###.......#######.....### #....########.................##...............#####..###.........#####....##### #....#########......##.......####............#..########...........####...###### #.....#########....####......#########......##...#######...#####....##....###### ##..........####...####......############....#...#######..#######..........##### ######.......####...##......##############.......#######..#######..........##### #######......#####.......##################......######...######...........##### ########.....######.....#####################...######.....#####...##....####### #########....########..###############################.....######.####..######## ##########..###########################################...###################### ################################################################################ ################################################################################
Ta-dah! Just shifting up-and-left until collision occurs works to join most maps this size.
But that technique just used by itself, can fail. Here’s an example of why. Given the initial cave level:
################################################################################ ##..#################################....##########....##########..############# #....#############.####...##########......########......########....############ #....############...##.....#########.......#######.....####.####....############ ##..#############...##.....########...........#####...####..#####..#########..## #################...........######.............############################....# ##################..........######.....##....#..##########################.....# ##########....####..........######.....###..##....#######################......# #########......###.........########...#####........#####....######...####.....## ########.......###.......##################........####......####.....####...### ###...........####......####################.......#####.....####.....########## ##............#####.....###########..#######.......#######...#####...########### ##.............######..###########....#####.........#######...##############..## ###.............##################....####...........######...############.....# ###.............##################...####...............##....##########.......# ##.............###################...####.........##..........#########...#....# #..............###################...#####......#####..........########..###...# #......#......####################....####.....#######..........########..#....# ##...........####################.....#####..#########..........########......## ###..........######...#########.......################.........########......### ####.........#####....########...##...###############......###########.......### #####....##..####.....#######...####..##############......##########.........### ######........##....########....#####..##.....######....###########..........### #######............#########....#####..........####....###########...........### #######............##########...#####.........####.....###########..........#### #######....##...........######..#####......#######......#########....#.....##### #######...####...........#####...###......########...........##.....###....##### #######...####............###............#########.................###......#### #######...####......##..............##############...........##...####........## #######....##......####.......##...########...####..........##########.........# ########...##.....#####......####..######......##..........############........# ########...##....######......####..#####...............######..########........# #######.........########......##...####..........##...######....#######.......## ######.........#############........##..........####..#####......#######.....### #####.........###############............##.....####..#####......########..##### #####........################...#.......####....####...###.......############### #####........#####################......#####....##....###.......############### ######.......######################....#######.........####.....################ #######.....####################################......########################## ################################################################################
We start in. While there are still separate regions, and we can shift any of them up and left, we do that. We get a lot of collisions joining regions. But we wind up not having everything joined, because the little region in the upper left corner never contacted anything and the other region can’t move that direction because it’s touching both the left wall below the unjoined region, and the top to the right of the unjoined region.
#..###########.####...##############....######....##.######..######..########### ....#########...##.....############......####........#####....####....########## ....#########...##.....############.......###.....########....###.....########## #..##########...........##########...........#...##########..###......########## ##############..........#########.............##############...#.....########### ##############..........#########.....##....#..############.....#...############ #########....#.........##########.....###..##....##########.....################ ########.............#############...#####........#####....#...################# #######.............######################........####......#################### ##...........##.....#######################.......#####.....#################### #............####..###############..#######.......#######...#################### #.............###################....#####.........#######...##############..### ##.............##################....####...........######...############.....## ##.............##################...####...............##....##########.......## #.............###################...####.........##..........#########...#....## ..............###################...#####......#####..........########..###...## ......#......####################....####.....#######..........########..#....## #...........####################.....#####..#########..........########......### ##..........######...#########.......################.........########......#### ###.........#####....########...##...###############......###########.......#### ####....##..####.....#######...####..##############......##########.........#### #####........##....########....#####..##.....######....###########..........#### ######............#########....#####..........####....###########...........#### ######............##########...#####.........####.....###########..........##### ######....##...........######..#####......#######......#########....#.....###### ######...####...........#####...###......########...........##.....###....###### ######...####............###............#########.................###......##### ######...####......##..............##############...........##...####........### ######....##......####.......##...########...####..........##########.........## #######...##.....#####......####..######......##..........#..#########........## #######...##....######......####..#####...............####....########........## ######.........########......##...####..........##...####......#######.......### #####.........#############........##..........####..####......########.....#### ####.........###############............##.....####..###.......#########..###### ####........################...#.......####....####...##.......################# ####........#####################......#####....##....###.....################## #####.......######################....#######.........########################## ######.....####################################......########################### ################################################################################ ################################################################################
So the next iteration of joinall detects that there are still multiple floodfill regions but none of them can move up and/or left, so it flips the whole map around the diagonal, like this. Now the little region at the upper left has become the little region at the lower right.
################################################################################ ################################################################################ ###########################......####################################.....###### ##########################.........#######....######################.......##### ##################.....###....##....#####......#####################........#### #################.......##...####....####.......#...################........#### ######..#########.......###..####.....##............###############.........#### ####.....########......####..####..........##........#############.........##### ###.......#######......####...##..........####...##......########.........###### ##........########....####...............#####..####......######....##...####### ##........#########..#..........##......######..####......#####.....##...####### ##.........##########..........####...########...##.......####......##....###### ###........####...##...........##############..............##......####...###### #####......###.................#########............###............####...###### ######....###.....##...........########......###...#####...........####...###### ######.....#....#########......#######......#####..######...........##....###### #####..........###########.....####.........#####...##########............###### ####...........###########....####..........#####....#########............###### ####..........###########....######.....##..#####....########....##........##### ####.........##########......##############..####...#######.....####..##....#### ####.......###########......###############...##...########....#####.........### ####......########.........################.......#########...######..........## ###......########..........#########..#####.....####################...........# ##....#..########..........#######.....####....####################......#...... ##...###..########..........#####......#####...###################.............. ##....#...#########..........##.........####...###################.............# ##.......##########....##...............####...##################.............## ##.....############...######...........####....##################.............## ###..##############...#######.........#####....###################.............# ####################...#######.......#######..###############..####............# ####################.....#####.......#######################.....##...........## ####################......####........######################.............####### #################...#....#####........#####...#############.............######## ################.....##########....##..###.....##########.........#....######### ############...#.....############..#....##.....#########..........############## ###########.....#...##############.............#########..........############## ##########......###..##########...#...........##########...........##########..# ##########.....###....########.....###.......############.....##...#########.... ##########....####....#####........####......############.....##...#########.... ###########..######..######.##....######....##############...####.###########..#
Two more iterations brings the big joined region up against the top and left edge, as before but now upside down. Four more after that brings the little freefloating region from the lower right corner into contact with it.
#########################......####################################.....######## ########################.........#######....######################.......####### ################.....###....##....#####......#####################........###### ###############.......##...####....####.......#...################........###### ####..#########.......###..####.....##............###############.........###### ##.....########......####..####..........##........#############.........####### #.......#######......####...##..........####...##......########.........######## ........########....####...............#####..####......######....##...######### ........#########..#..........##......######..####......#####.....##...######### .........##########..........####...########...##.......####......##....######## #........####...##...........##############..............##......####...######## ###......###.................#########............###............####...######## ####....###.....##...........########......###...#####...........####...######## ####.....#....#########......#######......#####..######...........##....######## ###..........###########.....####.........#####...##########............######## ##...........###########....####..........#####....#########............######## ##..........###########....######.....##..#####....########....##........####### ##.........##########......##############..####...#######.....####..##....###### ##.......###########......###############...##...########....#####.........##### ##......########.........################.......#########...######..........#### #......########..........#########..#####.....####################...........### ....#..########..........#######.....####....####################......#......## ...###..########..........#####......#####...###################..............## ....#...#########..........##.........####...###################.............### .......##########....##...............####...##################.............#### .....############...######...........####....##################.............#### #..##############...#######.........#####....###################.............### ##################...#######.......#######..###############..####............### ##################.....#####.......#######################.....##...........#### ##################......####........######################.............######### ###############...#....#####........#####...#############.............#..####### ##############.....##########....##..###.....##########.........#....#....###### ##########...#.....############..#....##.....#########..........######....###### #########.....#...##############.............#########..........#######..####### ########......###..##########...#...........##########...........############### ########.....###....########.....###.......############.....##...############### ########....####....#####........####......############.....##...############### #########..######..######.##....######....##############...####.################ ################################################################################ ################################################################################
And now this map is fully joined.
The key realization is that separation which endures the first iteration set can only happen when the region closer to the corner *can* move in the opposite direction until it contacts another region. So flipping around the diagonal solves the problem, and we get an algorithm that works on any map. Computationally it’s a brute-force solution because it floodfills the open areas of the map on every iteration. But it’s reasonably straightforward and both correct results and finite-time termination are guaranteed.
here is the code:
/* constants: XMAX and YMAX are the size of your map, and
REGION is some number of regions you want to be able to
operate on simultaneously. If REGION is smaller than the
actual number of disconnected spaces on your map, this
is still guaranteed to join all spaces and terminate,
but will take significantly more iterations and is likely
to produce different results.
*/
/* floodfills one walkable area of a map, starting at point x,y
and writing mark into every walkable tile of that set.
simultaneously updates minx and miny to that mark wherever
needed. */
void floodfill(int map[XMAX][YMAX], int x, int y, int mark,
int minx[REGION], int miny[REGION]){
int i;
int j;
for (i=-1;i<=1;i++)
for (j=-1;j<=1;j++)
if (i+x < XMAX && i+x >= 0 &&
j+y < YMAX && j+y >= 0 &&
map[i+x][j+y] != 0 && map[i+x][j+y] != mark){
map[i+x][j+y] = mark;
/* side effect of floodfilling is recording minimum x and y
for each region*/
if (mark < REGION){
if (i+x < minx[mark]) minx[mark] = i+x;
if (j+y < miny[mark]) miny[mark] = j+y;
}
floodfill(map, i+x, j+y, mark, minx, miny);
}
}
/* finds all regions, mark each open cell (by floodfill) with an integer
2 or greater indicating what region it's in. */
int floodall(int map[XMAX][YMAX], int minx[REGION], int miny[REGION]){
int x;
int y;
int count = 2;
int retval = 0;
/* start by setting all floor tiles to 1. */
/* wall spaces are marked 0. */
for (x=0;x< XMAX;x++){
for (y=0;y< YMAX;y++){
if (map[x][y] != 0){
map[x][y] = 1;
}
}
}
/* reset region extent marks to -1 invalid */
for (x=0;x<REGION;x++){
minx[x] = -1;
miny[x] = -1;
}
/* now mark regions starting with the number 2. */
for (x=0;x< XMAX;x++){
for (y=0;y< YMAX;y++){
if (map[x][y] == 1){
if (count < REGION){
maxx[count] = x;
minx[count] = x;
maxy[count] = y;
miny[count] = y;
}
floodfill(map, x, y, count, maxx, minx, maxy, miny);
count++;
retval++;
}
}
}
/* return the number of floodfill regions found */
return(retval);
}
/* joinall makes an iterative step toward joining all map regions.
The output map is guaranteed to have the same number of
open spaces, or fewer, than the input. With enough
iterations, an output map having exactly one open space
will be produced. Further iterations will just copy that
map. Call using an idiom like
do {
joinall(map1, map2);
regioncount = joinall(map2, map1);
} while (regioncount > 1)
to get a fully connected map.
Algorithm/Data:
Joinall uses the minx and miny arrays to record the
minimum x and y coordinates of squares found in each
region. This is how it determines which regions can
be shifted toward [0,0]. If any regions can be
shifted, it produces an output map by shifting those
regions. If none can be shifted, it produces an output
map by flipping the input map around the diagonal. If
there was only one region in the first place, it just
copies the input map to the output map. It returns the
number of unjoined regions found in the input map.
The maps are arrays of integers; each open tile is marked
with a number 2 or greater indicating what region it
belongs to. Wall tiles are marked 0, and 1 is used
internally for unmarked open tiles.
*/
int joinall(int mapin[XMAX][YMAX], int mapout[XMAX][YMAX]){
int minx[REGION];
int miny[REGION];
int x;
int y;
int count;
int retval;
retval = floodall(mapin, minx, miny);
/* if we have multiple unconnected regions */
if (retval > 1){
/* check to see if there are still regions that can be moved toward
0,0. */
count = 0;
for (x = 2; x < REGION; x++)
if (minx[x] > 0 || miny[x] > 0) count = 1;
/* if no regions can still be moved toward (0,0) */
if (count == 0){
/* the new map is the old map flipped about the diagonal. */
for (x = 0; x < XMAX; x++)
for (y = 0; y < YMAX; y++)
mapout[XMAX-x-1][YMAX-y-1] = mapin[x][y];
return(retval);
}
else{ /* there exist regions that can be moved toward 0,0 */
/* write rock to every square of new map that is either
rock or a region we can move; copy the map to all other squares. */
for (x = 0; x < XMAX; x++)
for (y = 0; y < YMAX; y++){
if (mapin[x][y] >= REGION) mapout[x][y] = mapin[x][y];
else mapout[x][y] = 0;
}
/* now copy regions we can move to new map, each with a shift
toward (0,0). Ugh. This is ugly code. Remember that in C
comparison results are integer, not boolean. So this is a
triply nested array reference using them as integers, which
won't work in most sane languages. If you're translating
this into a sane language, TRUE is 1 and FALSE is 0. */
for (x = 0; x < XMAX; x++)
for (y = 0; y < YMAX; y++)
if (mapin[x][y] != 0 && mapin[x][y] < REGION){
mapout[x-(minx[mapin[x][y]] > 0)]
[y-( miny[mapin[x][y]] > 0)] = 1;
}
return(retval);
}
}
else{ /* there was only one connected region - the output map is the
same as the input map. */
for (x = 0; x < XMAX; x++)
for (y = 0; y < YMAX; y++)
if (mapin[x][y] == 0) mapout[x][y] = 0;
else mapout[x][y] = 1;
return(1);
}
}