The Diamond-Square Algorithm(diamond-square.netlify.app)
diamond-square.netlify.app
The Diamond-Square Algorithm
https://diamond-square.netlify.app/
9 comments
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.
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.
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.
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.
And the algorithm is "embarrassingly parallel" so you can run it really efficiently on the GPU if you want to make some huge maps.
Nice -- I used this technique last year to generate "transport-tycoon-like" terrain: https://peterellisjones.com/posts/generating-transport-tycoo...
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.
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.
Does "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.