2e:null 2f:["$","title",null,{"children":"Heightmap generation using diamond-square algorithm | Philippe Deschaseaux | Observable"}] 34:T43d,// Apply 1 diamond + 1 square steps of the algorithm, using given randomness function diamondSquare = function(H, rnd) { const nb = 2 * H.length - 1; // Initialize new array and copy values from given heightmap const H2 = []; for (let i = 0; i < nb; i++) { H2[i] = []; for (let j = 0; j < nb; j++) { H2[i][j] = i & 1 || j & 1 ? 0 : H[i >> 1][j >> 1]; } } // Diamond step + cross spread for (let i = 1; i < nb; i += 2) { for (let j = 1; j < nb; j += 2) { let t = (H2[i][j] = (H2[i - 1][j - 1] + H2[i + 1][j - 1] + H2[i - 1][j + 1] + H2[i + 1][j + 1]) / 4 + rnd()); H2[i][j - 1] += t; H2[i + 1][j] += t; H2[i][j + 1] += t; H2[i - 1][j] += t; } } // Residual square step for (let i = 1; i < nb; i += 2) { for (let j = 0; j < nb; j += 2) { let d = j > 0 && j < nb - 1 ? 4 : 3; H2[i][j] = (H2[i][j] + H2[i - 1][j] + H2[i + 1][j]) / d + rnd(); H2[j][i] = (H2[j][i] + H2[j][i - 1] + H2[j][i + 1]) / d + rnd(); } } return H2; }35:[] 32:{"id":"89b5932c77eae070","slug":"heightmap-generation-using-diamond-square-algorithm","title":"Heightmap generation using diamond-square algorithm","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2018-03-27T01:50:30.356Z","update_time":"$D2020-07-10T18:33:17.430Z","view_time":null,"first_public_time":"$D2018-03-27T12:32:38.034Z","has_unpublished_edits":null,"fork":{"id":"079d0a0948a984b3","slug":"heightmap-generation-using-inverse-distance-weighting-in","title":"Heightmap generation using inverse distance weighting interpolation","owner":{"id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux"}},"stars":3,"starred":false,"owner":{"type":"team","id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":"starter_2024"},"version":1462,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"7c1eebd3c1c51af1","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":null}],"members":[{"type":"individual","id":"7c1eebd3c1c51af1","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"003a31fb854ae2bf","slug":"procedural-terrain-generation","title":"Procedural terrain generation","owner":{"id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux"}},"type":"notebook","body":{"title":"Heightmap generation using diamond-square algorithm","cells":[{"id":2,"value":"md`# Heightmap generation using diamond-square algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`This is a [yet](https://beta.observablehq.com/@ehouais/heightmap-generation-using-inverse-distance-weighting-in) [another](https://beta.observablehq.com/@ehouais/heightmap-generation-by-bell-shaped-functions-accumulati) method to generate terrain [heightmaps](https://en.wikipedia.org/wiki/Heightmap). It uses the well-known [diamond-square algorithm](https://en.wikipedia.org/wiki/Diamond-square_algorithm).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":584,"value":"md`We will be using the minstd_rand0 [seedable PRNG](https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use) for randomness.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1042,"value":"md`The **diamondSquare** function implements an iteration of the algorithm, taking an array of dimension ${tex`N^2`}, where ${tex`N = 2k+1`}, and a randomness function, and returning an array of dimension ${tex`N'^2`}, where ${tex`N' = 2(2k)+1`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1447,"value":"array = (size, cb) => Array.from(Array(size), cb)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1449,"value":"array2D = ([n1, n2], cb) => array(n1, i => array(n2, j => cb(i, j)))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":701,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1083,"value":"md`Randomness is controlled by two shaping parameters.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1053,"value":"viewof shaping = formgen(\"Shaping parameters\", {\n p1: {type: \"range\", label: \"p1\", min: 0.1, max: 2, step: 0.01, default: 0.5},\n p2: {type: \"range\", label: \"p2\", min: 0.5, max: 2, step: 0.01, default: 1.1}\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1067,"value":"md`We iterate the algorithm step 9 times, starting from a random 2x2 array to finally generate a 513*513 heightmap.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":152,"value":"viewof heightmap = {\n const { context, dispatch } = viewofCanvas(256, 256);\n const prng = minstRand0(seed);\n let H =\n iterations > 0 ? [[prng(), prng()], [prng(), prng()]] : [[0, 0], [0, 0]];\n\n // Generate heightmap array\n let f = shaping.p1;\n let f2;\n for (let n = 0; n < 9; n++) {\n f2 = 2 * f;\n H = diamondSquare(H, () => n + 1 < iterations && prng() * f2 - f);\n f /= 2 ** shaping.p2;\n }\n\n const N = H.length;\n\n // Compute heightmap stats\n let min = +Infinity;\n let max = -Infinity;\n for (let i = 0; i < N; i++) {\n for (let j = 0; j < N; j++) {\n let h = H[i][j];\n min = Math.min(min, h);\n max = Math.max(max, h);\n }\n }\n\n for (let i = 0; i < N; i++) {\n for (let j = 0; j < N; j++) {\n H[i][j] -= min;\n }\n }\n\n dispatch({ data: H, hunit: 1, vunit: N / 4 });\n const [rxy, rz] = [N / 256, 256 / (max - min)];\n return canvas(context, (i, j) =>\n Array(3).fill(H[(i * rxy) | 0][(j * rxy) | 0] * rz)\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1456,"value":"heightmap","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1441,"value":"heightmap","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1357,"value":"viewof shademap = {\n const Nc = 256;\n const { context, dispatch } = viewofCanvas(Nc, Nc);\n const { data, hunit, vunit } = heightmap;\n const sun = 15 * (τ / 360); // sun elevation (in radians)\n const S = computeShading(\n data,\n [hunit, vunit],\n [0, -Math.cos(sun), Math.sin(sun)],\n 0.7,\n 256\n );\n\n dispatch({\n heightmap: { data, hunit, ratio: vunit / hunit },\n colormap: { data: S }\n });\n return canvas(context, (i, j) => Array(3).fill(S[i * 2][j * 2]));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1368,"value":"{\n const palette = colorShades([253, 205, 159], 256);\n const colormap = { ...shademap.colormap, palette };\n const dims = [width, (width * 0.6) | 0];\n return orbitalCanvas({ ...shademap, colormap }, dims);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1077,"value":"md`The result is different for each value of the PRNG seed.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1073,"value":"viewof seed = slider({title: \"Seed\", min: 1, max: 2147483646, step: 1, value: 307710644})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1139,"value":"md`While the results are pretty satisfactory, this algorithm is inherently biased, as explained in [this **stackoverflow** answer](https://stackoverflow.com/a/12934615), and there are artefacts visible as spikes located at the early displacement points. Decrease the following value to stop randomization earlier and witness those artefacts.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1261,"value":"viewof iterations = slider({title: \"Iterations\", min: 1, max: 9, step: 1, value: 9})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":597,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1361,"value":"τ = 2 * Math.PI","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":845,"value":"import {\n minstRand0,\n sliders,\n canvas,\n viewofCanvas,\n colorShades\n} from \"@ehouais/utils\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":713,"value":"import {isoFloorCasting} from '@ehouais/heightmap-rendering-techniques'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1366,"value":"import { orbitalCanvas } from \"@ehouais/heightmap-rendering-using-a-floorcasting-algorithm\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1359,"value":"import {computeShading} from \"@ehouais/normals-generation-on-a-heightmap-grid\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1374,"value":"import {formgen} from \"@ehouais/form-generator\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 33:"$32:body"