6
\$\begingroup\$

I want to create 2D Terrain randomly. It should look like a connected Cave (Shown below). What is the best method or Algorithm to get similar results?

The important part is the open area(green) and that it is fully surrounded by walls(brown).

4 Examples:

enter image description here enter image description here enter image description here enter image description here

\$\endgroup\$
  • \$\begingroup\$ Have you read the other cave-generation related posts on here? There are quite a few of them. \$\endgroup\$ – Tim Holt Jan 30 '18 at 4:17
  • 1
    \$\begingroup\$ Are you specifically looking for a "donut" shape like that, or just general connected terrain? \$\endgroup\$ – Tim Holt Jan 30 '18 at 4:19
  • \$\begingroup\$ Do you have any other criteria (min/max size, etc) that need to be considered? \$\endgroup\$ – Pikalek Jan 30 '18 at 22:56
2
\$\begingroup\$
  1. Generate a cave map using an algorithm based on cellular automata. For example http://www.roguebasin.com/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels

1.1. To make the cave fully connected you can for example do an iterative method based on (1).

First generate the cave map from randomly filled area.

Identify connected regions by flood-fill.

Remove the ones with are under some arbitrary threshold.

Then discretize the cave into squares (or rectangles). I did this to reduce number of nodes (and it was needed for some other features so might as well do it there).

Then form a graph between these squares (square is a vertex, edge is between square that are connected).

Find the MST (minimal spanning tree), but treat all vertices (squares) in one connected cave region as one vertex of MST (use the region_id for determining equality of nodes). I made a quick sketch of how it could look like: enter image description here

Regenerate the cave but put some more empty cells on the path of the MST, this will make it more probable for it to be a passage there after some iterations of CA.

Do until there is only one region.

I found it quite fast for maps of the size 256x256.

That's how it should look like after a few iterations. I had more visualizations but unfortunately I can't recompile it right now and make screens. enter image description here Smaller maps should look more like on your pictures.

Also you can just force border walls after the generation.

  1. Generate a noise map using for example simplex or perlin noise

  2. Scale the noise map by a function of the distance to the wall so there is smaller probability of having high parts near walls.

\$\endgroup\$
  • \$\begingroup\$ What algorithm did you use to discretize the cave into rectangles? \$\endgroup\$ – Pikalek Feb 2 '18 at 21:25
  • \$\begingroup\$ Brute force, but i restricted the rectangles to be at most with width height ratio of 2. For bigger regions square are more feasible. You dont even need to to do it accurately though, putting some big squares in the biggest places will do the job \$\endgroup\$ – Sopel Feb 2 '18 at 21:33
4
\$\begingroup\$

You could generate, analyse and discard random noise fields.

Just generate thousands of them, and keep the ones that have a fully enclosing wall on the outside.

For generation, I would use Simplex Noise. Here is my implementation in C for it.

After generating a 2D field with values in range [-1,1], you pick a threshold value (let's assume 0.0) and define WALL as > 0 and VOID as <= 0.

Then you test the entire rim (x==0 || x==max || y==0 || y==max) for being WALL. If one value on the rim is not WALL, discard this cave, and generate a new one with different noise coordinates.

You can put more restrictions on it too, as: no disconnect of the cavity. To test this, floodfill from a void sample. If the set does not contain all void values, then the void is disconnected, and could be discarded.

For a little more efficiency, you could also dynamically pick the threshold value by setting it to the lowest value found on the rim. This way, a closed rim is guaranteed. (Note that you can also guarantee this using Sean's suggestion of scaling the values based on distance to the centre.)

And then examine the cave. If it is too small, or disconnected, continue to the next random field.

But the key point I am trying to make here: you don't have to specifically force your generator to satisfy constraints, it is enough if you can analyse and identify these constraints after which your filter your solution.

\$\endgroup\$
  • 5
    \$\begingroup\$ There's no reason to throw away any results. Just apply a radial function that drives the edges of the map towards the wall value, with the strength of that radial being +MAX when very near the edges. That's the cool thing about noise masks - you can combine many masks, presets, and other functions to produce the final result. The radial function will ensure a round-ish cave. A further mask can be used to ensure openings near points of interest, and additional noise layers + masks can ensure passages. \$\endgroup\$ – Sean Middleditch Jan 30 '18 at 1:19
3
\$\begingroup\$

I think you will get similar results if you do it like this.

Start with some points in a circle around your cave area.

Jitter the points by moving each one randomly from it's starting position.

Trace the lines in between each point using an algorithm to generate thickness.

You could do this last part by checking point-to-line-segment distance on each square, or by creating a line of arbitrary thickness.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.