Jump to content
  • Advertisement
Sign in to follow this  
EdvardDumansky

Methods for procedurally generating 2d tunnels

This topic is 2535 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey everyone, sorry if this is the wrong section for this post but I don't think any of the others fit. I'm working on world generation for the 2d "platformer" style worlds in my game. The base of the terrain is generated using Perlin Noise, and I'm at the point where I want to add cave/tunnel systems. Caves are easy enough; a 2d Perlin Noise function can create a huge variety of caves. My issue is with finding a method that can generate the type of tunnel system I'm looking for. Ideally there would be large caves scattered throughout the world with tunnels connecting some of them, branching out, etc. If anyone has recommendations I'd appreciate them!

Share this post


Link to post
Share on other sites
Advertisement
A single-octave of Ridged Multifractal (basically, Perlin noise with an abs modifier applied per layer) perturbed by a turbulence function makes rather convincing cave systems:
minecraft_cave_perturb.jpg


The Ridged Multifractal output is passed through a step function to delineate areas of solid and open. The threshold value of the step function can be used to determine the approximate size of the tunnels. After the step function, a turbulence function that translates the input coordinates to the cave function based on the output of another set of regular Perlin noise fractals then noises up the smooth network of caves created by the ridge function, to make it more cave-like. I talk a bit more about generating 2D and 3D worlds with caves here.

Share this post


Link to post
Share on other sites
That image is pretty close to what I'm looking for. I've got the ridged multifractal working (I think haha). Right now I get the output from the multifractal and have the program decide if it's greater than a specific value (the closer the value is to max the thinner the tunnels). Using that I get tunnels that are very smooth, which seems to match the result you got for your tunnels.

Where you're losing me is at the turbulence section. If I understand correctly, I need to have a second set of Perlin Noise which will decide how much each tile is displaced by. You mention to only displace by the Y value when creating the base outline of the terrain, but wouldn't you need to displace by both X and Y for caves? Along the same line, how much exactly do I displace by? You use the value of 0.25, which is then explained to be 1/4 of the screen. Would that mean I move each tile either + or - 1/4 of the world width?


EDIT: I reread my post and the information you linked to, which made me realize there were a few things I didn't quite understand. Below is what I believe is the correct step-by-step break down for how all this works; it might help in figuring out if my understanding of the process is incorrect.

1. Use a Ridged Multifractal to create a base for the tunnels. This is a temporary array with values of 1 or 0. To increase the general width of the tunnels the threshold should be increased, meaning that if you have it set so that a value of 95 out of a possible 100 is empty (a tunnel), the tunnels will be thinner overall than if you had it set to 90 of 100.

2. Go through every single point in the map and decide how much the vertical (Y) value should be offset by turbulence. This is done by having a Perlin Noise function that goes through the entire map and returns with values between -0.25 and 0.25. In reality that range is either negative/positive one fourth of the height of the map. If the map is 1000 tiles high then the most an individual tile can be raised or lowered by is 250 tiles. Any tile can be raised or lowered; it doesn't matter if it's solid or open.

3. Multiply the main terrain array by the temporary terrain array, carving out the caves.

Share this post


Link to post
Share on other sites

That image is pretty close to what I'm looking for. I've got the ridged multifractal working (I think haha). Right now I get the output from the multifractal and have the program decide if it's greater than a specific value (the closer the value is to max the thinner the tunnels). Using that I get tunnels that are very smooth, which seems to match the result you got for your tunnels.

Where you're losing me is at the turbulence section. If I understand correctly, I need to have a second set of Perlin Noise which will decide how much each tile is displaced by. You mention to only displace by the Y value when creating the base outline of the terrain, but wouldn't you need to displace by both X and Y for caves? Along the same line, how much exactly do I displace by? You use the value of 0.25, which is then explained to be 1/4 of the screen. Would that mean I move each tile either + or - 1/4 of the world width?


Exact numbers are very subjective in something like this. The best I can say is to experiment and see what works. In the above linked image, I only applied turbulence in the X axis. This does sometimes result in the occurrence of straight-line artifacts in the generated output, but sometimes it is best to sacrifice a little bit of quality in the interest of reducing the function complexity. Again, this is a subjective factor that needs to be decided on an individual basis.




EDIT: I reread my post and the information you linked to, which made me realize there were a few things I didn't quite understand. Below is what I believe is the correct step-by-step break down for how all this works; it might help in figuring out if my understanding of the process is incorrect.

1. Use a Ridged Multifractal to create a base for the tunnels. This is a temporary array with values of 1 or 0. To increase the general width of the tunnels the threshold should be increased, meaning that if you have it set so that a value of 95 out of a possible 100 is empty (a tunnel), the tunnels will be thinner overall than if you had it set to 90 of 100.
[/quote]

My personal style is to try to reduce dependence on temporary variables and arrays, and rely as much as I can on implicit functions. But other than that, you have the basic idea.



2. Go through every single point in the map and decide how much the vertical (Y) value should be offset by turbulence. This is done by having a Perlin Noise function that goes through the entire map and returns with values between -0.25 and 0.25. In reality that range is either negative/positive one fourth of the height of the map. If the map is 1000 tiles high then the most an individual tile can be raised or lowered by is 250 tiles. Any tile can be raised or lowered; it doesn't matter if it's solid or open.
[/quote]

Basically. But once again, exact values and proportions are subjective.



3. Multiply the main terrain array by the temporary terrain array, carving out the caves.
[/quote]

Yep.

Share this post


Link to post
Share on other sites
Thanks for the reply. I went ahead and tried implementing it based on what I understand at this point and... I don't think it's working correctly ;) Here's a link to an image of what's happening. Since you said the exact values for noise were subjective, I made the range -10 to 10 tiles rather than -0.25% to 0.25% of the world width. Am I misunderstanding how it's implemented?

Share this post


Link to post
Share on other sites
Hard to say what you might be doing wrong without looking at code, but in that linked shot I'm seeing an awful lot of repetition. Plus the visible area is far too small/blocky for me to really see what's going on.

When I set out to develop a noise function, I usually don't start doing it in my game or whatever. I usually start by setting up functions, mapping them to buffers to save as TGA images, and examining the output visually. Only when I have worked out the particulars in a test-bed fashion do I try to shoehorn it into a game. It can be just too much of a pain trying to implement the system in-place.

Share this post


Link to post
Share on other sites
I looked over my code another time for stupid mistakes and found that I had been using the Ridged Multifractal code instead of regular Perlin Noise, which seemed to cause the repetition. rolleyes.gif By fixing this I was able to see exactly what kind of change the turbulence causes, but sadly it's nothing like the example in your article. Even though seeing a small piece of the screen doesn't give the full picture of what's happening, it does still allow you to see the general pattern on a micro scale. Here's an image of the my result; the red lines provide a general outline of where the tunnels are. I've played around with the maximum amount a tile is allowed to be displaced (in your example -0.25% to 0.25%), as well as the values for the Perlin Noise function (which includes the number of octaves, the persistence [which I use to find the frequency and amplitude], and point separation [the scale used to determine how far apart the source points are]). The result does vary depending on what settings I choose, but it's always some derivative of the image I linked to. It's possible to tell where the tunnels are generally, but it just looks like they got moved around randomly rather than what you'd expect from a Perlin Noise function.

Do you happen to have some "control" values for the Perlin Noise function which worked for you that I could plug in to my own implementation?

Share this post


Link to post
Share on other sites
All the values I used can be found by reading the tables in the code boxes at the article link. They might not be optimal for your case.Without seeing your code, I simply can not say what you might be doing wrong. Possibly your turbulence frequency is way too high and way too powerful. Who knows?

Have you broken it down so that you see the results from just the ridged fractal, then the results from just the turbulence source? Doing so will help you study the parts in isolation and give you a better understanding of how they work together. Ensure that each piece works, then try to combine them together.

Share this post


Link to post
Share on other sites
I've tested both the Ridged Multifractal and Perlin Noise functions separately and they're producing results which are similar to the images on your site for each step (Ridged Multifractal, Perlin Noise). This got me thinking that it's what I do after I have that data has been calculated that's causing the issue. There's nothing obvious jumping out at me in the code, so maybe a fresh pair of eyes will see what I'm missing. For all I know I could have implemented it completely incorrectly. Because I know the Ridged Multifractal is producing the results I want I didn't bother to paste it here (I can if you feel it's needed). What I do essentially is calculate it for every point and save the result (either a 1 or 0) in an array (arr_WorldGen_DataTemporary). The code below then goes through all those points and decides how much each of those points should be moved on the X axis (also note that Z has been substituted for Y). If there's anything confusing going on in my code please let me know and I'll try to clarify.


var_WorldGen_PointSeparationX = var_WorldGen_WorldWidth# * 0.001
var_WorldGen_PointSeparationZ = var_WorldGen_WorldHeight# * 0.001
glob_PerlinNoise_Persistance# = 0.5
var_Octave = 4
var_Frequency# = 2 ^ var_Octave
var_Amplitude# = glob_PerlinNoise_Persistance# ^ var_Octave
NOISE FAST PARAMS var_Octave, var_Frequency#, var_Amplitude#, glob_WorldGen_Seed
var_Turbulence_Max# = var_WorldGen_WorldWidth# / 0.25
var_Sync_Counter = 0

`Apply turbulence to tunnels.
FOR var_Array_PositionX = 0 TO var_WorldGen_WorldWidth# - 1
var_X# = var_Array_PositionX / var_WorldGen_WorldWidth#
var_X# = var_X# * var_WorldGen_PointSeparationX
FOR var_Array_PositionZ = 0 TO var_WorldGen_WorldHeight# - 1
var_Z# = var_Array_PositionZ / var_WorldGen_WorldHeight#
var_Z# = var_Z# * var_WorldGen_PointSeparationZ

var_TileValue = arr_WorldGen_DataTemporary(var_Array_PositionX, var_Array_PositionZ)
var_Value = ((NOISE FAST GET2D(var_X#, var_Z#) + 1.0) * var_Turbulence_Max#) - var_Turbulence_Max#
var_Array_PositionX_New = var_Array_PositionX + var_Value

`Apply new tunnel data to main array.
IF var_Array_PositionX_New > -1 AND var_Array_PositionX_New < var_WorldGen_WorldWidth#
arr_WorldGen_AllData(var_Array_PositionX_New + con_Chunk_Size, var_Array_PositionZ + con_Chunk_Size, con_WorldBlocks_Ground) = var_TileValue * arr_WorldGen_AllData(var_Array_PositionX_New + con_Chunk_Size, var_Array_PositionZ + con_Chunk_Size, con_WorldBlocks_Ground)
ENDIF

INC var_Sync_Counter
IF var_Sync_Counter = 5000
SYNC
var_Sync_Counter = 0
ENDIF
NEXT var_Array_PositionZ
NEXT var_Array_PositionX

Share this post


Link to post
Share on other sites
I've done some more reading on Perlin Noise based turbulence (specifically at this link) and feel that I finally understand exactly how it works. Sadly this just makes the problem I'm having that much more perplexing. I'm now pretty much convinced that the code below--which decides how much each block should be transposed--is not the issue, though I could be overlooking something. At the same time both the Ridged Multifractal and Perlin Noise functions *appear* to be working as expected, though changing values for the Perlin Noise function does affect the output. Is it just a matter of trying an infinite number of combinations for the Perlin Noise function to find one that works?




var_TileValue = arr_WorldGen_DataTemporary(var_Array_PositionX, var_Array_PositionZ)
var_Value = NOISE FAST GET2D(var_X#, var_Z#) * var_Turbulence_Max#
var_Array_PositionX_New = var_Array_PositionX + var_Value

`Apply new tunnel data to main array.
IF var_Array_PositionX_New > -1 AND var_Array_PositionX_New < var_WorldGen_WorldWidth#
arr_WorldGen_AllData(var_Array_PositionX_New + con_Chunk_Size, var_Array_PositionZ + con_Chunk_Size, con_WorldBlocks_Ground) = var_TileValue * arr_WorldGen_AllData(var_Array_PositionX_New + con_Chunk_Size, var_Array_PositionZ + con_Chunk_Size, con_WorldBlocks_Ground)
ENDIF

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!