Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[zwei]

I have recently experimented with map generation for roguelikes - case being open caverns and different kind of dungeons than traditional rectangular rooms connected by tunnels.

Here are samples of what my algrothim can output: http://db.tt/2BpXEYc7

Any criticism is welcome, as well as ideas for additional raw pixel sources as well as postprocessors - so far i am using cloud fractal slices, random node placement, random line placement and brownian motion as sources of raw data and mirroring/rotation, erode/dilate and and/or for combination of various outputs.

Heart of algorithm is using CCL to detect distinct regions and then joining closest regions (rinse, repeat) - it provides both awesome results and well as being incredible cpu strain - some of maps took nearly minute to generate even after major optimalizations, but some only take milisecconds. It however, allows me to make weirdly shaped maps without having to deal with orphaned sub regions.

I am currently looking for good idea on how to detect peninsula-like regions.

( http://foh.zweistein.cz/ is undead project under whose header it is being done and which wentcover, fyi)

[Soadreqm]

These are pretty sweet.

[Randos]

Nice maps.

I had pretty good luck with some much simpler formulas for creating lake regions.  I would start at a given point and simply say:  Choose a random direction from North, South, East, or West and go one tile in that direction marking your territory as you go as "lake".  It will come back over itself sometimes but that's good because this allows some areas to grow thicker.  It tends to make a sporadic design but obviously can never part from itself so there is no worry of connecting things together.  You could also add to that loop by saying:  every 100th step break in a straight direction for 100 paces, and then you would be building tunnels (or streams, or paths) that lead off and start building more areas.

This might not make the most interesting or realistic design patterns, but it is much more CPU friendly and easier to experiment with! 

[zwei]

Nice maps.

I had pretty good luck with some much simpler formulas for creating lake regions.  I would start at a given point and simply say:  Choose a random direction from North, South, East, or West and go one tile in that direction marking your territory as you go as "lake".  It will come back over itself sometimes but that's good because this allows some areas to grow thicker.  It tends to make a sporadic design but obviously can never part from itself so there is no worry of connecting things together.  You could also add to that loop by saying:  every 100th step break in a straight direction for 100 paces, and then you would be building tunnels (or streams, or paths) that lead off and start building more areas.

This might not make the most interesting or realistic design patterns, but it is much more CPU friendly and easier to experiment with!

Yeah, i called this Brownian Motion algorithm.

It makes really nice maps, and is indeed very cheap computation wise.

[professorlamp]

Sooo... How do you actually go about implementing the algorithms into the code?
I'm still fairly new to programming but eventually this sort of thing is going to spring up and I have noooo idea where I'd even begin

[Beyondrepair]

^ Pseudocode of "Brownian motion" (random walk):

x, y : int = 0, 0; //or whatever
n : int = 100; //or whatever

go_west -> x -= 1;
go_north -> y -= 1;
go_east -> x += 1;
go_south -> y += 1;

while (n > 0)
{
n -= 1;
mark(x, y);

r : int = rand(1, 4);
if (r == 1) go_west();
if (r == 2) go_north();
if (r == 3) go_east();
if (r == 4) go_south();
}

Of course you can get more interesting behavior by modifying the probability function from a flat 25% and/or resetting the position every so often.

A weakness of this method is that you can't easily determine if a given position (x, y) has been marked without running the whole iteration first, thus it's not very suitable for on-the-fly generation.

[Skyrunner]

Interestig shapes o.O
I wonder, did you intend the caves to be symmetrical? Like the one that vaguely looks like a skull. Or the ones that look like a psychology blob test.

[zwei]

Interestig shapes o.O
I wonder, did you intend the caves to be symmetrical? Like the one that vaguely looks like a skull. Or the ones that look like a psychology blob test.

Not at first, but symetry does not hurt and allows to make more coherent maps.

Symetry of "skull" was gotten by flipping map vertically and combining it with itself.

More interesting and less obvious results can be obtained by combining rotated version of itself.