The Diamond-Square Algorithm

https://diamond-square.netlify.app/

by _fourzerofour • 6 years ago

59 9 6 years ago

diamond-square.netlify.app

saagarjha• 6 years ago

(If it isn't clear from the demonstration, Diamond-Square is quite good at terrain generation.)

pubby• 6 years ago

It's kinda flawed in that it produces terrain with prominent creases along the x/y axis. Most terrain generators use something with less artifacts, like several passes of perlin noise.

thunderrabbit• 6 years ago

Does "Noise Scaling" mean randomness?

_fourzerofour2• 6 years ago

Effectively, yes. It's a multiplier for the random displacement that's calculated for a point in the grid as part of the algorithm, which is added to the mean of the adjacent (diamond- or square-wise) points.

cafxx• 6 years ago

Would be ideal to implement the algorithm more efficiently. I remember my Pentium 100MHz rendering and displaying bigger "plasma fractal" images almost instantaneously in ~1995. In this implementation it takes >1 minute (at least until I aborted, and it was nowhere near done) to render a 250x250 version on my 8-core 3.5GHz laptop.

_fourzerofour2• 6 years ago

Great point, and I think this is a next step for me. For what it's worth, this was to teach myself React and Redux and took a couple of nights of work. I was curious about ways to keep the canvas element fundamentally decoupled from the algorithm itself, which allows a couple of benefits out of the box. For example, varying the randomness or changing the color map mid-calculation, I kind of got 'for free', thanks to React re-rendering the canvas every time the algorithm is stepped through or the controls are changed.

It's also worth noting that the algorithm's speed here is tied to (I believe?) your monitor's refresh rate, since it's using requestAnimationFrame to loop without blocking the main thread entirely. I'd briefly considered a "complete" button which would run the whole thing in one go and render once, and that would enable reviewing for performance optimisation without hanging the page. But... I got too excited and wanted to share it first.

DavidVoid• 6 years ago

For the smaller sizes it's fast enough, but for larger sizes I'd recommend showing completed chunks of steps at a time, instead of each individual diamond/square step at a time.

And the algorithm is "embarrassingly parallel" so you can run it really efficiently on the GPU if you want to make some huge maps.

ukoki• 6 years ago

Nice -- I used this technique last year to generate "transport-tycoon-like" terrain: https://peterellisjones.com/posts/generating-transport-tycoo...

Konohamaru• 6 years ago

The functioning of this algorithm to be one of those tasks that computer scientists would call an "embarrassingly parallel problem" <shorturl.at/jrCKP>. One could easily split this into four subtasks each executing in parallel to give O(log n) complexity where n is the desired resolution.

In addition--I do not know if you have used this because I did not peer into your code--you may want to use a quadtree data structure, NOT an array.

The Diamond-Square Algorithm

Related Stories