[CODE] Post-processing to ensure map connectivity

23 views
Skip to first unread message

Ray

unread,
Nov 15, 2009, 3:19:35 PM11/15/09
to

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 generator, you may need a post-processing step to
make sure that your map is fully connected. It's easy to do in a
rooms-and-corridors dungeon; you just find a place to draw another
corridor.

But corridors are kind of wrong for caverns. Ideally, you want to
connect the caverns while not changing their shape or introducing
any identifiably artificial features, just by shifting the open
spaces until they contact each other.

I have a couple bits of code that solve the problem, and I've pasted
them in this post.

This code is fully general; it will work on any kind of map.

First, you need to be able to detect multiple unconnected regions.

If you call floodall, it will tell you how many disconnected
walkable regions there are in your map. It has two side
effects, both intentional.

It will also mark each open tile with a number 2 or greater
indicating what region it belongs to. (wall tiles are
marked 0, 1 is used internally for unmarked open tiles).

Also, it will fill in two arrays, minx[] and miny[], with
the minimum x and y values found in that region.

Second, you need to find a map that is connected given a
map that's not connected.

joinall takes two map parameters; the first is the map you
have, and the second is the map that joinall fills in based
on it. It returns the number of separate regions found so
you can tell when you're finished, but is mainly called
for its side effect, which is filling in the result map.

Joinall uses floodfill. Both work on maps which are
represented as arrays of integers where an impassable tile
is represented as 0 and a walkable square is represented as
a nonzero integer.

Joinall uses the minx and miny arrays to determine which
regions can be shifted toward [0,0]. If any 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 regions found in the input map. Call it with
some sort of idiom like this:

do{
joinall(map1,map2);
count = joinall(map2,map1);
} while (count > 1)

After the loop both map1 and map2 will be fully joined.


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. Whichever of XMAX and YMAX is least, setting
REGION to that number plus 2 ensures both correct results
and termination.

/* I wrote this code; I'm making it public domain.
Anybody can use it, post it publicly, or do anything
else they want with it. I'd appreciate credit, but
like I said, it's public.
- Ray Dillinger, 15 Nov 2009.
*/


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);
}
}


/* find 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 is 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.
*/
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).*/
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
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);
}
}


Krice

unread,
Nov 15, 2009, 5:02:41 PM11/15/09
to
On 15 marras, 22:19, Ray <b...@sonic.net> wrote:
> But corridors are kind of wrong for caverns. Ideally, you want to
> connect the caverns while not changing their shape or introducing
> any identifiably artificial features

What is ideal about that? I imagine that dungeons would
usually be either artificial or a mix of naturally formed
caverns and artificial features like corridors. If there
is only untouched caverns then I think dwarfs never went
to that cave and it's some kind of beast's lair.

Gelatinous Mutant Coconut

unread,
Nov 15, 2009, 7:02:55 PM11/15/09
to
Ray, I'm afraid I can't really visualize how this works; could you
post a before-and-after image?

Ray

unread,
Nov 16, 2009, 1:49:01 AM11/16/09
to
Gelatinous Mutant Coconut wrote:

> Ray, I'm afraid I can't really visualize how this works; could you
> post a before-and-after image?

Okay.... f'r example, here's the output of a cellular automaton that
generates caves. They're nice looking caves, but 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 this kind of separation 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 lot of
work - basically a brute-force solution - but at least it's reasonably
straightforward.

Bear

Ray

unread,
Nov 16, 2009, 1:53:50 AM11/16/09
to
Krice wrote:

> If there
> is only untouched caverns then I think dwarfs never went
> to that cave and it's some kind of beast's lair.

Ding! Exactly right! Natural caverns are prime beast-lair
territory, so I don't want corridors messing them up.

Dwarfs make a whole different kind of place, but if you
want you can use this algorithm on that kind of dungeon too
and it will still make all the walkable spaces join while
preserving their shapes.

Bear

Gerry Quinn

unread,
Nov 16, 2009, 8:56:26 AM11/16/09
to
In article <4b00f6e8$0$1629$742e...@news.sonic.net>, be...@sonic.net
says...

> Gelatinous Mutant Coconut wrote:
>
> > Ray, I'm afraid I can't really visualize how this works; could you
> > post a before-and-after image?

I couldn't either!

> Okay.... f'r example, here's the output of a cellular automaton that
> generates caves. They're nice looking caves, but not all connected.

[snip maps]

> And now this map is fully joined.
>
> The key realization is that this kind of separation 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 lot of
> work - basically a brute-force solution - but at least it's reasonably
> straightforward.

It's a very nice solution, IMO, especially the shift-up-and-left part
of it. My guess is that this alone would work well enough in most
cases that instead of the diagonal flipping, you could as an
alternative simply select the largest region when shift-up-and-left has
achieved all it is capable of.

- Gerry Quinn

Ray

unread,
Nov 16, 2009, 10:46:13 AM11/16/09
to
Gerry Quinn wrote:

> In article <4b00f6e8$0$1629$742e...@news.sonic.net>, be...@sonic.net
> says...
>> Gelatinous Mutant Coconut wrote:
>>

>> > Ray, I'm afraid I can't really visualize how this works...

> I couldn't either!

> It's a very nice solution, IMO, especially the shift-up-and-left part
> of it. My guess is that this alone would work well enough in most
> cases that instead of the diagonal flipping, you could as an
> alternative simply select the largest region when shift-up-and-left has
> achieved all it is capable of.

It probably depends on the map generator whether that's true; certainly
for the cellular-automata cavern generator it's sufficient.

and the code that does exactly that:

      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;

Is probably the ugliest bit in the whole thing.

It uses the result of a comparison as an integer in an
expression inside a triply nested array reference involving
four different arrays. I wrote it in C but I was thinking
in APL.

The line between nice solutions and horrifying hacks is hard to
find, and that array reference jumps rope with it.


Bear

Gerry Quinn

unread,
Nov 16, 2009, 2:43:41 PM11/16/09
to
In article <4b0174d1$0$1633$742e...@news.sonic.net>, be...@sonic.net
says...

Hehe, I didn't even look at the code, it was the algorithm I thought
was nice ;-D

- Gerry Quinn

Jeff Lait

unread,
Nov 16, 2009, 4:20:37 PM11/16/09
to
On Nov 15, 9:19 pm, Ray <b...@sonic.net> wrote:
> Some map generation algorithms generate connected maps automatically,
> because they always work by extending a connected square.
>
> I have a couple bits of code that solve the problem, and I've pasted
> them in this post.
>
> This code is fully general; it will work on any kind of map.
> the minimum x and y values found in that region.  

Perhaps I'm missing something, but:

#######
#.....#
#.###.#
#.#.#.#
#.###.#
#.....#
#######

is centered at 0,0, so is unable to shift, so doesn't terminate?

Or is 0,0 the bottom left corner?

The claim is then:
If all regions each touch all of the n/s/e/w boundaries, then there is
only one region.

From visualizing, I am satisfied of the truth of this, but I can't
place a proof...

Outline?:
Say we have one region satisfying this property. It connects both the
north and south wall, and is connected. But this means it divides the
east wall from the west wall - no other region can touch both east and
west without crossing through this first region. Thus it must be the
only 4 way connected region.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

Jotaf

unread,
Nov 16, 2009, 7:56:33 PM11/16/09
to
Nice work! The problem with the classic solution of simply
floodfilling the "main" area and rejecting the rest is that now there
are lots of spaces completely blank. You could never get a fully
connected cavern that also spans the whole map that way.

Jotaf

Gelatinous Mutant Coconut

unread,
Nov 16, 2009, 8:36:13 PM11/16/09
to
I think that the system could be generalized in such a way that there
isn't any need to rotate the map, like this:

You have N unconnected regions. While N > 1, choose two distinct
regions. Choose one floor tile within each region. Now, repeatedly
move one of the regions such that the two chosen tiles become closer
each step; stop before taking any move that would cause the moving
region to have open squares overlapping the open squares of another
region. Those two regions are now connected, so N = N-1; do whatever
you need to do to mark them as a single region and continue.

Since you are moving two open squares towards each other, you are
guaranteed to connect two regions (though your moving region might
first hit a different region than the one it was moving towards, which
is fine too.)

Jakub Debski

unread,
Nov 17, 2009, 5:53:36 AM11/17/09
to
Ray submitted this idea :

> Some map generation algorithms generate connected maps automatically,
> because they always work by extending a connected square.

In my roguelikelib
http://sourceforge.net/projects/roguelikelib/
I use similar solution. Independent regions are flood filled with
increasing values. Then the disconnected areas are connected by
corridors until the transitive closure is guaranted by Warshall
algorithm.

regards,
Jakub


Kusigrosz

unread,
Nov 17, 2009, 7:33:31 AM11/17/09
to
On 2009-11-16, Jeff Lait <torespon...@hotmail.com> wrote:
> On Nov 15, 9:19�pm, Ray <b...@sonic.net> wrote:
>> Some map generation algorithms generate connected maps automatically,
>> because they always work by extending a connected square.
>>
>> I have a couple bits of code that solve the problem, and I've pasted
>> them in this post.
>>
>> This code is fully general; it will work on any kind of map.
>> the minimum x and y values found in that region. �
>
> Perhaps I'm missing something, but:
>
> #######
> #.....#
> #.###.#
> #.#.#.#
> #.###.#
> #.....#
> #######
>
> is centered at 0,0, so is unable to shift, so doesn't terminate?
>
> Or is 0,0 the bottom left corner?

I think it is the upper left corner, and the diagonal is the / one.
I suppose it could be any corner if only the diagonal with respect to
which the flipping is done was _not_ the one passing through that
corner.

> The claim is then:
> If all regions each touch all of the n/s/e/w boundaries, then there is
> only one region.

If no region can be shifted up or left, all regions must be touching
the upper and left boundaries. Now consider the region that touches
the upper border farthest to the right. It must be the same region
which touches the left border farthest down - as regions cannot
intersect. Thus this region cuts off other regions (if any) from
touching the right and down borders, so if there are any other
regions they can be shifted right and down; after flipping with respect
to the / diagonal they can be shifted up and left.

--
Kusi...@AUtorun.itvk.pl To send mail, remove 'AU' from the address
You see here a scroll labeled "Q-e0fHUoKD8"

Jeff Lait

unread,
Nov 17, 2009, 11:38:58 AM11/17/09
to
On Nov 17, 1:33 pm, Kusigrosz <Kusigr...@AUtorun.itvk.pl> wrote:

> On 2009-11-16, Jeff Lait <torespondisfut...@hotmail.com> wrote:
>
> > On Nov 15, 9:19 pm, Ray <b...@sonic.net> wrote:
> >> Some map generation algorithms generate connected maps automatically,
> >> because they always work by extending a connected square.
>
> >> I have a couple bits of code that solve the problem, and I've pasted
> >> them in this post.
>
> >> This code is fully general; it will work on any kind of map.
> >> the minimum x and y values found in that region.  
>
> > Perhaps I'm missing something, but:
>
> > #######
> > #.....#
> > #.###.#
> > #.#.#.#
> > #.###.#
> > #.....#
> > #######
>
> > is centered at 0,0, so is unable to shift, so doesn't terminate?
>
> > Or is 0,0 the bottom left corner?
>
> I think it is the upper left corner, and the diagonal is the / one.
> I suppose it could be any corner if only the diagonal with respect to
> which the flipping is done was _not_ the one passing through that
> corner.

Ah, depends on your display, I instinctively have 0,0 bottom left.

> > The claim is then:
> > If all regions each touch all of the n/s/e/w boundaries, then there is
> > only one region.
>
> If no region can be shifted up or left, all regions must be touching
> the upper and left boundaries. Now consider the region that touches
> the upper border farthest to the right.

Okay.

> It must be the same region
> which touches the left border farthest down - as regions cannot
> intersect.

Why? This is the part I stumble and revert to some handwaving.

I have the same problem with my proposed proof where I claim the
existence of a top-down connection prohibits a disjoint region from
having a left-right connection. I'm very much missing the right
language to frame the problem as it seems self evident.

David Ploog

unread,
Nov 17, 2009, 12:40:07 PM11/17/09
to
On Tue, 17 Nov 2009, Jeff Lait wrote:
> On Nov 17, 1:33�pm, Kusigrosz <Kusigr...@AUtorun.itvk.pl> wrote:
>> On 2009-11-16, Jeff Lait <torespondisfut...@hotmail.com> wrote:

>>> The claim is then:
>>> If all regions each touch all of the n/s/e/w boundaries, then there is
>>> only one region.
>>
>> If no region can be shifted up or left, all regions must be touching
>> the upper and left boundaries. Now consider the region that touches
>> the upper border farthest to the right.
>>

>> It must be the same region
>> which touches the left border farthest down - as regions cannot
>> intersect.
>
> Why? This is the part I stumble and revert to some handwaving.
>
> I have the same problem with my proposed proof where I claim the
> existence of a top-down connection prohibits a disjoint region from
> having a left-right connection. I'm very much missing the right
> language to frame the problem as it seems self evident.

Isn't this the same fact as the classical "two continuous curves in the
unit square [0,1]x[0,1], one going from (0,0) to (1,1) and the other one
going from (0,1) to (1,0) have to intersect"? This is a consequence of a
continuous function f on a compact interval [a,b] assuming all values in
[f(a),f(b)] (for f(a)<f(b), else switch). But I may be missing something.

David

David Damerell

unread,
Nov 17, 2009, 1:17:47 PM11/17/09
to
Quoting Jeff Lait <torespon...@hotmail.com>:
>I have the same problem with my proposed proof where I claim the
>existence of a top-down connection prohibits a disjoint region from
>having a left-right connection. I'm very much missing the right
>language to frame the problem as it seems self evident.

I think that's because it _is_ self-evident.
--
David Damerell <dame...@chiark.greenend.org.uk> flcl?
Today is First Wednesday, November.
Tomorrow will be First Thursday, November.

Kusigrosz

unread,
Nov 17, 2009, 1:32:44 PM11/17/09
to
On 2009-11-17, Jeff Lait <torespon...@hotmail.com> wrote:
> On Nov 17, 1:33�pm, Kusigrosz <Kusigr...@AUtorun.itvk.pl> wrote:
>> If no region can be shifted up or left, all regions must be touching
>> the upper and left boundaries. Now consider the region that touches
>> the upper border farthest to the right.
>
> Okay.
Lets call the region A.

>> It must be the same region
>> which touches the left border farthest down - as regions cannot
>> intersect.
>
> Why? This is the part I stumble and revert to some handwaving.

If we treat each FLOOR cell as a square on the plane R2, with the
edges and vertices also 'in' (so it's a closed square). two
neighbouring FLOOR cells must have at least a common vertex.
Any region made by floodfill is then path-connected - we can
draw a line (usually not straight) between any two points of it
that is completely contained in the region.

Now for every region we draw a line from any point where it touches
the level's upper border to any point where it touches the left one.
For different regions their lines cannot intersect each other (the
intersection points would have to belong to both). The line of the
region A connects to the upper border farther right than any other.
If it didn't connect to the left border lowest of all, it would have
to intersect the line that ends below it. But if no line ends below it,
no region touches below either.

> I have the same problem with my proposed proof where I claim the
> existence of a top-down connection prohibits a disjoint region from
> having a left-right connection. I'm very much missing the right
> language to frame the problem as it seems self evident.

I didn't understand the algorithm when reading for the first time.
In fact, I got it only when drawing ASCII pictures for a post with
questions ;-)

Jeff Lait

unread,
Nov 17, 2009, 3:44:14 PM11/17/09
to

Ah, that is sounding like the right language! Thank you, I'll have to
think on this, but I think it points in the right direction.

Ray

unread,
Nov 17, 2009, 6:35:47 PM11/17/09
to
Gelatinous Mutant Coconut wrote:


That is true, and would also work.

Bear

Jotaf

unread,
Nov 17, 2009, 7:53:20 PM11/17/09
to
Ray, would it be right to say this method is based on accretion of
connected regions? Could we make up a fancy name based on that, for
future reference? :)

Jotaf

Ray

unread,
Nov 18, 2009, 2:09:18 AM11/18/09
to
Jotaf wrote:


Sure, you could say that. Why, are you making up a name to call it
in the context of a library or webpage?

Bear


Paul Donnelly

unread,
Nov 18, 2009, 12:31:44 PM11/18/09
to
Jotaf <jot...@hotmail.com> writes:

Region concretion?

Ray

unread,
Nov 18, 2009, 1:24:53 PM11/18/09
to
Ray wrote:

As I thought about this, I came up with a case where it fails.

You can reach a point where neither region can move such that the
selected floortiles become closer. Consider this map, where the
x's represent the selected tiles.

.###########
.##.........
.##.#######.
.##x####x##.
.#######.##.
.........##.
###########.

Neither selected tile can move toward the other because the
regions they're in are both up against the edges in the directions
they'd have to move.


Bear

Gelatinous Mutant Coconut

unread,
Nov 18, 2009, 4:30:44 PM11/18/09
to
On Nov 18, 1:24 pm, Ray <b...@sonic.net> wrote:
> You can reach a point where neither region can move such that the
> selected floortiles become closer.  Consider this map, where the
> x's represent the selected tiles.  
>
> .###########
> .##.........
> .##.#######.
> .##x####x##.
> .#######.##.
> .........##.
> ###########.
>
> Neither selected tile can move toward the other because the
> regions they're in are both up against the edges in the directions
> they'd have to move.  

Ah. I had sort of been thinking of the regions as existing as boxes
within an unbounded map space; you're right that the algorithm could
fail if you implemented it directly on a character array with no
ability to be resized.

Jotaf

unread,
Nov 20, 2009, 11:03:15 AM11/20/09
to
On Nov 18, 9:30 pm, Gelatinous Mutant Coconut

Anyway in this extremely contrived case you can just roll the dice
again :P

Jotaf

Pender

unread,
Nov 25, 2009, 4:08:16 PM11/25/09
to
This is an interesting algorithm. I have one suggestion. I think one
or more additional iterations of CA should be applied to the end
result to eliminate situations where two smooth curves are brought
together until they just barely kiss, thus leaving two very sharp
outcroppings of rock on either side in an otherwise-smooth cavern, or
worse, an intermittent trail of single-tile wall obstacles along the
face on which they are joined. You can see some of both in Ray's
examples above.

It's pretty easy to show that an additional iteration of CA won't
create disconnections if you (1) only eliminate walls and never add
them, and (2) do not eliminate any wall tiles unless they have at
least one floor cell neighbor, and this will make for a more
consistent/organic look.

Gelatinous Mutant Coconut

unread,
Nov 25, 2009, 9:47:35 PM11/25/09
to
On Nov 25, 4:08 pm, Pender <penderpr...@gmail.com> wrote:
> It's pretty easy to show that an additional iteration of CA won't
> create disconnections if you (1) only eliminate walls and never add
> them, and (2) do not eliminate any wall tiles unless they have at
> least one floor cell neighbor, and this will make for a more
> consistent/organic look.

That could also make an interesting weathering effect to apply to
regular rooms-and-tunnels levels themed as being old and abandoned. It
might look a bit too regular with just the CA rules, though; maybe you
could roll a % chance of actually removing any wall that the CA flags
for removal, with the % being greater for more worn-down dungeon
levels.

Ray

unread,
Nov 25, 2009, 10:54:12 PM11/25/09
to
Pender wrote:

> This is an interesting algorithm. I have one suggestion. I think one
> or more additional iterations of CA should be applied to the end
> result to eliminate situations where two smooth curves are brought
> together until they just barely kiss, thus leaving two very sharp
> outcroppings of rock on either side in an otherwise-smooth cavern, or
> worse, an intermittent trail of single-tile wall obstacles along the
> face on which they are joined. You can see some of both in Ray's
> examples above.

That would work, I guess. You could make a cavern generator that
had joining as one of the steps in the middle.

The code was about joining regions though, not about CA cavern
generators. I just used one of those as the example. You could,
in fact, use joining as a middle or final step in a lot of different
map generators.

Another possibility would be to toss a bunch of rectangular rooms
randomly into a map, along with corridors and corners to hold most
of them apart so they don't wind up as one big room, and use the
region joiner to join them up. It's much easier than most methods
of making sure your maps are joined.

Come to think of it you might want to go over the result of that
process with a CA to remove dead-ends and things, too. But which
steps come after the region joiner would depend on what kind of
map you were creating.

Bear

Reply all
Reply to author
Forward
0 new messages