The Diamond-Square Algorithm
diamond-square.netlify.app
The Diamond-Square Algorithm
1–10 of 10 posts
Re: The Diamond-Square Algorithm
#2(If it isn't clear from the demonstration, Diamond-Square is quite good at terrain generation.)
Re: The Diamond-Square Algorithm
#3Does "Noise Scaling" mean randomness?
Re: The Diamond-Square Algorithm
#4Does "Noise Scaling" mean randomness?
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.
Re: The Diamond-Square Algorithm
#5Would 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.
Re: The Diamond-Square Algorithm
#6(If it isn't clear from the demonstration, Diamond-Square is quite good at terrain generation.)
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.
Re: The Diamond-Square Algorithm
#7Would 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.
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.
Re: The Diamond-Square Algorithm
#8Nice -- I used this technique last year to generate "transport-tycoon-like" terrain: https://peterellisjones.com/posts/generating-transport-tycoo...
Re: The Diamond-Square Algorithm
#9Would 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.
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…
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.
Re: The Diamond-Square Algorithm
#10The functioning of this algorithm to be one of those tasks that computer scientists would call an "embarrassingly parallel problem" . 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.