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:
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:
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.
Smaller maps should look more like on your pictures.
Also you can just force border walls after the generation.
Generate a noise map using for example simplex or perlin noise
Scale the noise map by a function of the distance to the wall so there is smaller probability of having high parts near walls.
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.
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.
