Spatial analysis of irregular areas

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

For the last few days I've been attempting to tackle the problem of
algorithmically dividing the space within an irregular area (such as the map of
a cavern, for example) into seperate, defined areas, such as chambers and
corridors. However, this seems to be far more complicated than I originally
anticipated.

What I hoped is that the initial layout of the map could be generated using
cellural automata, or a similar approach that produces good cave-like maps,
then analyse the map to determine large open areas and the graph of their
connectivity to aid in the placement of features. For example, sticking a
treasure cache in an sheltered alcove inside a larger chamber, preferentially
placing items and larger groups of creatures inside rooms as opposed to
tunnels, or finding the relative center of a larger area to place a man-made
feature, such as an alter and its surrounding edifice, perhaps worshiped by the
tribe of orcs who inhabit this particular cavern, ect.

Sadly, it seems that the more time I spend on this problem, the more difficult
it actually becomes. For any set of rules or procedures I devise to define a
room or trace its approximate outline, it is easily defeated by the next map I
throw at it. Virtually anything that I've yet thought of works only for a small
subset of potential layouts. I suppose this is probably inevitable given a
computer's difficulty with fuzzy pattern matching, but I'd still like to think
the problem is not so insurmountable, and that I'm simply missing something.

I've been without any access to the internet on a consistant basis for the last
couple months, so I've not had much opportunity to perform much research thus
far. Of course, I doubt that one could find a paper on such a specific topic as
this, but something of even passing relevance that might provide some insight or
inspiration would be helpful.

I was wondering if anyone here might be able to point me in the direction of
some potentially relevant material that you might be aware of, or share any
ideas on the subject.

 

[oskar]

Archived from groups: rec.games.roguelike.development (More info?)

It sounds like you may want to use a blob detector from the computer
vision field.
It would give you a center and size of blob-like regions of the image.

 

[Thomas]

Archived from groups: rec.games.roguelike.development (More info?)

Maybe a modified version of the recursive floodfill algorithm might
work....

-Thomas
RL: CHAZM

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

James Bulgin <jgbulgin@hotmail.com> schrieb:
> For the last few days I've been attempting to tackle the problem of
> algorithmically dividing the space within an irregular area (such as
> the map of a cavern, for example) into seperate, defined areas, such
> as chambers and corridors. However, this seems to be far more
> complicated than I originally anticipated.

In order to distinguish separate chambers, you should be able to grow
the walls until you have small, distinguishable chambers. Just
recursively pretend every tile adjacent to a wall is a wall until you
have an area small enough for you to consider a separate chamber. You
can also find the center of a chamber by growing the walls until there
is only one tile left. (I don't mean actually making more walls, but
pretending to in order to distinguish the separation of the chambers.)

--
Jim Strathmeyer

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

There are some useful algorithms in the field of morphological
filtering. You might find what you're looking for by doing some
research in that area. Assuming, for brevity's sake, that each element
of your cave is a pixel, take a 5X5 pixel neighborhood/filter - every
time the neighborhood around a pixel is open (not a wall), make the
pixel open, if the neighborhood is closed (wall), make the pixel closed
- in this manner, you can quickly discern the location of a room-sized
cavern in a cave. Corridors would be a little trickier, since they're
ill-defined for cavern topologies, but should probably just be any open
pixels linking two rooms. For alcoves, you might try to add a second
piece to the algorithm - looking for the largest open region around any
pixels that were still open after the first pass, you would also have
to have a check to ensure that your potential alcove was not actually a
corridor to another room as well.

Another alcove alternative might be having a 3 x 3 or 4 x 4
neighborhood check, followed by a 5 x 5 neighborhood rejection check so
that the center of large rooms was not selected, but smaller rooms WERE
selected. There is a LOT of interesting algorithms that morphological
filtering can provide, I definitely recommend it for something like
cavern room defining.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

>> For the last few days I've been attempting to tackle the problem of
>> algorithmically dividing the space within an irregular area (such as
>> the map of a cavern, for example) into seperate, defined areas, such
>> as chambers and corridors. However, this seems to be far more
>> complicated than I originally anticipated.

>In order to distinguish separate chambers, you should be able to grow
>the walls until you have small, distinguishable chambers. Just
>recursively pretend every tile adjacent to a wall is a wall until you
>have an area small enough for you to consider a separate chamber. You
>can also find the center of a chamber by growing the walls until there
>is only one tile left. (I don't mean actually making more walls, but
>pretending to in order to distinguish the separation of the chambers.)

I think this would probably be the simplest way to do it.

You could do it something like this:
Mark all wall squares
Until there are no unmarked squares
--Detect small, unmarked, rectangular areas (1xn or 2xn, these will
become filled next iteration)
----Assign each such area a unique number
--For each square, if it touches a marked square, mark it
Until there are no unnumbered squares
--If an empty square touches a numbered square, give it the same number

After this, you should have all of your caverns numbered. Corridors
would be split between caverns. (If you wanted to mark corridors,
you'd have to specify a maximum size. After that many iterations of
the first loop you can say all marked squares are potential corridors.
You'd have to let the second loop run over the potential corridors for
about as many iterations to get the real corridors.)

Anyway, I'd have to try it to see how it works. (If you try, let us
know.)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

"James Bulgin" <jgbulgin@hotmail.com> wrote in message
news:dd00ne$13gf$1@news.vol.cz...
> For the last few days I've been attempting to tackle the problem of
> algorithmically dividing the space within an irregular area (such as
> the map of
> a cavern, for example) into seperate, defined areas, such as chambers
> and
> corridors. However, this seems to be far more complicated than I
> originally
> anticipated.
>
> What I hoped is that the initial layout of the map could be generated
> using
> cellural automata, or a similar approach that produces good cave-like
> maps,
> then analyse the map to determine large open areas and the graph of
> their
> connectivity to aid in the placement of features. For example,
> sticking a
> treasure cache in an sheltered alcove inside a larger chamber,
> preferentially
> placing items and larger groups of creatures inside rooms as opposed
> to
> tunnels, or finding the relative center of a larger area to place a
> man-made
> feature, such as an alter and its surrounding edifice, perhaps
> worshiped by the
> tribe of orcs who inhabit this particular cavern, ect.
>
> Sadly, it seems that the more time I spend on this problem, the more
> difficult
> it actually becomes. For any set of rules or procedures I devise to
> define a
> room or trace its approximate outline, it is easily defeated by the
> next map I
> throw at it. Virtually anything that I've yet thought of works only
> for a small
> subset of potential layouts. I suppose this is probably inevitable
> given a
> computer's difficulty with fuzzy pattern matching, but I'd still like
> to think
> the problem is not so insurmountable, and that I'm simply missing
> something.
>
> I've been without any access to the internet on a consistant basis for
> the last
> couple months, so I've not had much opportunity to perform much
> research thus
> far. Of course, I doubt that one could find a paper on such a specific
> topic as
> this, but something of even passing relevance that might provide some
> insight or
> inspiration would be helpful.
>
> I was wondering if anyone here might be able to point me in the
> direction of
> some potentially relevant material that you might be aware of, or
> share any
> ideas on the subject.

I have two ideas:

- Incorporate that information into the generation of your cave
structure.
- Choose a bunch of grid positions. Overlay circles of increasing
radii, find the set of grid positions with circles whose center is not
contained in eachother (i.e. the intersection of their area is empty).
Those will be roughly equivalent to your larger cavern areas.

Something like floodfill isn't picky enough. What have you tried in
terms of algorithms so far?

--
Glen
Lyt E+++ T-- R+ P+++ D+ G+ F:*band !RL RLA-
W:AF Q+++ AI++ GFX++ SFX-- RN++++ PO--- !Hp Re-- S+

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

On 2005-08-05 18:41:01, "Glen Wheeler" <gew75@uow.edu.au> wrote:

> I have two ideas:
>
> - Incorporate that information into the generation of your cave
> structure.

I considered this, and it is certainly simpler, however there are a number of
serious limitations. Firstly, fractal and most cellular automata methods for
generating caverns are unsuited to this due to the unpredictable nature of the
spaces they output. You can't really say 'put a chamber here' and have it turn
out exactly to specifications. More planned methods to cave generation, such as
seeding tunnels and chambers and then semi-randomly growing them by adding floor
tiles adjacent to existing ones have promise, but they have the potential (and
in fact are likely to) generate additional interesting features that cannot be
accounted for with the basic structural information they are assigned upon
their generation. For example, a chamber-like bulge nestled in the side of what
was defined as a corridor (due to an unusually high concentration of deposition
in that area) would never be eligable for placing 'chamber' features in. With
some time and effort, I'm sure that you could still generate perfectly
satisfying dungeons in this way, but I felt like continuing to tackle the
original problem for a bit longer, just to see if I could get it workable
first.

> - Choose a bunch of grid positions. Overlay circles of increasing
> radii, find the set of grid positions with circles whose center is not
> contained in eachother (i.e. the intersection of their area is empty).
> Those will be roughly equivalent to your larger cavern areas.

> Something like floodfill isn't picky enough. What have you tried in
> terms of algorithms so far?

A number of different things, none of which have been nearly sucessful enough to
use, however.

I tried a statistical analysis, examining the number of open tiles directly
adjacent to each open tile, then propagating these values by repeatedly adding
a value to each tile equivalent to the sum of all its neighbours in the
previous generation. Then, chambers were defined as having a certain threshold
value, and all adjacent tiles that were also above this threshold were blobbed
together into a single chamber.

This was moderately successful, but demonstrated some problems. Finding a good
threshold value was tricky, and seem to depend far too heavily on the
individual map to pick a suitable value without human intervention on a per-map
basis. Even worse, areas that were absolutely distinct from adjoining areas, and
connected to larger chambers only by narrow corridors would get missed entirely
if they were too small in relation to other chambers on the map. What defines a
distinct chamber seems to depend both upon its absolute size, but even moreso
upon its size in relation to features around it. Demarkation by a narrow
corridor is enough, in most human eyes, to label the area beyond it a room.

Then a tried a number of scanline approaches, determining the width and height
of accessable terrain at all points, then splitting scanlines by notable
changes in length of the scanlines running perpendicular to it. The scanlines
would then be merged together into a number of regions when adjacent to
scanlines of the same general length. Then these smaller regions would be
merged together into larger regions based upon a set of rules and the relative
properties of the two regions in question and their neighbours. These rules
would determine which irregularities were merely bumps along the surface of the
room, which represented corridors, alcoves, partially adjacent chambers, ect.

This tended to be highly successful for highly regular rooms, but the algorithms
tended to be easily mislead by certain configurations of terrain. Local merging
of small regions based only upon their immediately adjacent regions is often
too shortsighted to see the bigger picture that a human could, and figure out
the role of it within the larger map. Sadly, the map was usually carved into
too many small regions to do anything but the most local of analysis, and
merging regions in the 'wrong' order tended to prevent a proper labelling.

I also tried various types of 'tracers' that travelled along the walls,
recursively subdividing the space as it encountered gaps in the ideal
rectangular wall that could represent either (depending on its size and
configuration) a slightl bumb in the terrain, and alcove, or a corridor. As
regions were finished being traced, they were conditionally merged with their
parent regions depending on the classification of each region.

This suffers from the problem of not having a good idea where to start the
tracer without already knowing the map's layout. Without a suitable starting
position, its easy for its results to get messed up. Also, it tends to suffer
similar problems to the scanline approach above.

Most of the different things I've tried all seem to show promise, but I've been
having a hard time advancing them for the 'it seem like it could work' stage to
actually having a precise idea of how to approach refining them to the point
that they're actually usable.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

"James Bulgin" <jgbulgin@hotmail.com> wrote in message
news:dd0aqn$1c16$1@news.vol.cz...
> On 2005-08-05 18:41:01, "Glen Wheeler" <gew75@uow.edu.au> wrote:
>
>> I have two ideas:
>>
>> - Incorporate that information into the generation of your cave
>> structure.
>
> I considered this, and it is certainly simpler,
>[..]
>> - Choose a bunch of grid positions. Overlay circles of increasing
>> radii, find the set of grid positions with circles whose center is
>> not
>> contained in eachother (i.e. the intersection of their area is
>> empty).
>> Those will be roughly equivalent to your larger cavern areas.
>
>> Something like floodfill isn't picky enough. What have you tried in
>> terms of algorithms so far?
>
> A number of different things, none of which have been nearly sucessful
> enough to
> use, however.
>
> [..]
>
> Most of the different things I've tried all seem to show promise, but
> I've been
> having a hard time advancing them for the 'it seem like it could work'
> stage to
> actually having a precise idea of how to approach refining them to the
> point
> that they're actually usable.
>

That's...a bit hard for me to understand. Are you having trouble
writing down what the definition of a cavern? Could you be more
specific about what problems the aforementioned techniques had? If you
can write down these problems explicitly, then it would be easier to
write an algorithm which picks caverns, corridors, etc that do not have
those characteristics.

Also keep in mind that whatever method you think of, and whatever
constraints you choose, the generator (even if it is cellular automata)
is going to be a very important consideration.

--
Glen
Lyt E+++ T-- R+ P+++ D+ G+ F:*band !RL RLA-
W:AF Q+++ AI++ GFX++ SFX-- RN++++ PO--- !Hp Re-- S+

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <dd00ne$13gf$1@news.vol.cz>, James Bulgin <jgbulgin@hotmail.com> wrote:
>For the last few days I've been attempting to tackle the problem of
>algorithmically dividing the space within an irregular area (such as the map of
>a cavern, for example) into seperate, defined areas, such as chambers and
>corridors. However, this seems to be far more complicated than I originally
>anticipated.

Can you divide up areas using Voronoi Diagram / Delaunay
Triangulation?

http://www.cs.cornell.edu/Info/People/chew/Delaunay.html

The starting points could be driven by a "party planner" type
algorithm, like in the old Scientific American article by (I think) A.
K. Dewdney.

Alan

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At Fri, 5 Aug 2005 15:30:54 +0000 (UTC),
James Bulgin wrote:

> I was wondering if anyone here might be able to point me in the direction of
> some potentially relevant material that you might be aware of, or share any
> ideas on the subject.

You could try to divide your map into rooms by use of a floodfill
algorithm. Instead of filling cell by cell, scale it up a little
and fill boxes, say, 4x4, like this:

############################################################
###....####################################.....############
##......######################..#########.........##########
##......#####################....#######...........####.####
##..xxxx###################.........................##...###
##..xxxx##################..xxxxxxxxxxxxxxxxxxxxxxxx###...##
#...xxxx.##############.....xxxxxxxxxxxxxxxxxxxxxxxx###...##
#...xxxx.#############......xxxxxxxxxxxxxxxxxxxxxxxx.#....##
##..xxxx.##############.....xxxxxxxxxxxxxxxxxxxxxxxx.....###
##..xxxx.###..############..........xxxxxxxxxxxx....xxxx####
##..xxxx.##....############.........xxxxxxxxxxxx....xxxx####
#...xxxx.......############...###...xxxxxxxxxxxx....xxxx.###
#...............###########..#####..xxxxxxxxxxxx.##.xxxx..##
#................#################......xxxx.....##.xxxx..##
##.....#####..........###########....#..xxxx....###.xxxx..##
##....#######...........########....###.xxxx....####xxxx..##
##....#######............######....####.xxxx...#####xxxx..##
##....#######...xxxxxxxx..####....#####.xxxx..#####.xxxx.###
#......######...xxxxxxxx...###....####..xxxx..####..xxxx####
#.......######..xxxxxxxx...###...####...xxxx..###...xxxx####
#........#####..xxxxxxxx...###..####....xxxx........xxxx.###
##........####..xxxxxxxxxxxx#...####....xxxxxxxxxxxxxxxx.###
#####......##...xxxxxxxxxxxx....####....xxxxxxxxxxxxxxxx.###
######..........xxxxxxxxxxxx.....##.....xxxxxxxxxxxxxxxx####
######..........xxxxxxxxxxxx............xxxxxxxxxxxxxxxx####
######.........###.....................####.............####
######......#########.................######............####
#######....#############.......##############.....###..#####
##############################################..############
############################################################

You can get much better results with tuned aligning of the grid,
but even with this approach you get several large areas where
you can put some predefined features (you can move these feature
a little around later, so they seem more random).

Or maybe you could come up with a floodfill algorithm that can't
pass thru small (say, 3-cell wide) openings?

--
Radomir `The Sheep' Dopieralski @**@_
($s) 3 Ching!
. . . ..v.vVvVVvVvv.v.. .