last day (15 days later) » 

7:26 PM
1
A: Midpoint Displacement 2D algorithm producing unusual patterns

M OehmYour problem is that you don't necessarily hit the already populated pixels with your calculations if your map dimensions are not a power of two. For example if your map is 30 units wide, your grid width is 15 in the first pass and 7 in the second pass, where it bases its calculations on the yet ...

 
Applied the suggestions you made, it looks much better now, thanks! Result Although is there a way to remove the graph paper effect? Like maybe a second interpolation?
 
Thanks for sharing the result. The graph paper effect is a typical artefact of the midpoint displacement algorithm. It occurs because you only add noise to the midpoint of each square, not to the edge midpoints. The algorithm is also sensitive to the range modifier; maybe calibrating that gives better results. That's a common problem, have a look at the related questions in the right sidebar.
You could also add noise in two stages: First, add noise to the midpoint of each square. Then add noise to the edges of the squares by treating them as midpoints of a square that is rotated by 45° whose corners are the end points of the edges and the midpoints of the two squares connected by the edges. So you average and add noise in two grids, a rectilinear one and a diagonal one, alternately. After each stage, you should multiply the range by the square root of the range modifier. This will relieve the effect, but it will probably not get entirely rid of it.
Having played a bit with midpoint displacement, I find your graph-paper effect especially pronounced. It is present in most cases, like in the examples on the Wikipedia page, but much weaker. I guess that your creases come from normalising the data where max is much greater than 1. You only add to the terrain and your corners start with a value between 0 and 1. A better strategy might be to start with values around 0.5 (e.g. 0.25 + random()) and allow the midpoint to go both ways: m += range * (random() - 0.5).
I've created a little toy webpage, where you can fiddle with some settings. The default settings allow the terrain to raise or lower at modpoints; they give a reasonable terrain with occasional weak creases. If you set the range decay to 0.3 and tick "normalise", you get a smooth terrain with strong, starburst-like creases. Tick "two-stage algo" and the creases vanish. (There are still peaks, however.) So the solutions are to chose sensible value ranges first and to use a two-pass algorithm for fine-tuning.
 
Okay, I did your first suggestion of adding noise to the edge midpoints which got this. I wasn't entirely sure of your two stage method, I thought you'd refer to changing which points to average the end points from but that ended up giving me some really dark and blocky patterns. Finally I tried your strategy for dealing with normalization by starting the four corners at (0.25 + random()) and allowing the midpoint to go both ways, which gave this which looks like it has greatly reduced the graph paper effect, but still blocky.
 
Looks like MPD is a very sensitive algorithm. Your blockiness comes from the difference in height and width. Because you increase the step uniformly and you have to cater for the largest dimension, the noise will apply to the same line repeatedly in the other dimension. Most example implementations use square grids and usually also uses dimensions that are 2^k + 1, which will save you all the floating-point arithmetic. The example you've linked to does that as does my code. This yields reasonably realistic results.
So what you could do is: Expand you map to a square and work with that. Obviously you are going to throw away a portion of the map after generation. Alternatively, you could subdivide your map into squares, e.g. 3x4 tiles of 160x160 pixels each and displace these. You must create seamless transitions between the tiles, though, so you could consider the tiles map as an advanced state in the algorithm with equal step width in each direction, but with different dimension.
 
I see, I remember the steps mentioning that its limited to fixed sizes, saying that extra steps need to be made to handle rectangles. Annoyingly it didn't say what the extra steps would be. I guess I could calculate the greatest common divider of both values and use that to determine the grid size?
 
7:26 PM
Yes, GCD seems like a good option, but that will only work if your dimensions are not relatively prime or when the GCD is small. I think it is sufficient to have the grid size roughly identical in both directions. You probably know your map sizes, so you could also estimate a good starting grid size and make that a function parameter.
 
I see. My intention was to use this for a general function, but that'll probably make my situation more difficult.
 
7:38 PM
Okay, I'm here. Mind you, I'm not very good at online chats.
 
No worries, I figured since the comments were getting so long.
 
Yes, that's waht SO suggests when there is a long dialogue in the comments. Aren't you happy with the result from your last image? That was a big improvement to your earlier results. What are the terrains you generate for, by the way? Maybe the blockiness isn't that much of an issue.
 
I guess not, although it would be nice to have a more clean result, in case I might use the algorithm for terrain or textures.
 
7:53 PM
I think your best bet is to create a square array of width and height n^2 + 1 that your rectangular array will fit into and clip it after terrain generation. That seems to get the cleanest results. That also makes the arithmetic straightforward.
 
OK. Thanks for all your help. :)
 
Nothing to thank for. If it hadn't interested me, I wouldn't have bothered.
 

last day (15 days later) »