31:T49c,md`Reshaping is useful for lots of my procedural generation projects. It's also useful for loot distributions, damage distributions, spell triggers, and any other time you have code to generate a set of numbers, but the game design calls for a different distribution of those numbers than what the code generated. In practice you don't have to sort the values; you only need to approximately count them (e.g. make a histogram). Sorting was the easy implementation for this page. With an actual distribution and a desired distribution histogram you can transform both to the cumulative distribution function, then make them match up, then transform back. The desired distribution can be defined in many ways. In my [damage calculation tutorial](https://www.redblobgames.com/articles/probability/damage-rolls.html#nonparametric) I have a section where you can draw an arbitrary distribution. The Photoshop “curve adjust” tool uses curve handles to define the desired distribution function. In my [polygon map generator](https://www.redblobgames.com/maps/mapgen2/) I used a linear distribution for reshaping the moisture, and a quadratic function for reshaping the elevation.`32:T4ae,animationBefore = { function mySvg(contents) { // Note that this svg is 1x1. It is not a giant overlay. // See http://simblob.blogspot.com/2016/10/outside-box.html return svg``; } // There's a cycle here: in order to build the SVG I need to know its // position. But I can't know its position until I return it. And I can't // return it until I build it. Checkmate. But no! @mbostock gave me this // clever trick: yield the partial svg, grab its position, then yield the // full svg. Haha! let element = mySvg(""); yield element; // Here's where I grab the positions of the other SVGs as well as myself, // and then I can calculate the positions of the other SVGs relative to // myself, and that lets me position elements so that they will sit on top // of or in between the other SVGs on the page. let fromRect = terrainBefore.getBoundingClientRect(); let toRect = distributionBefore.getBoundingClientRect(); let myRect = element.parentNode.getBoundingClientRect(); yield mySvg(svgAnimatedMarkers(sortedTerrain, fromRect, toRect, myRect)); } 33:T407,// Not using this anymore, once I got svgAnimatedMarkers working function drawAnimatedPoints(t) { return "DISABLED"; const r = 0.1; const w = terrain[1].x - terrain[0].x; let points = t.map((p, index) => { let x1 = p.x, x2 = index / (t.length-1) * 100; let x = x1 * (1-phase) + x2 * phase; return {x: x, y: 10*(1-p.y), type: p.y < waterYThreshold? 'water' : p.y >= snowYThreshold? 'snow' : 'land'}; }); let fills = points.map(p => { let base = svg``; if (p.type == 'water') { return svg`${base}`; } else if (p.type == 'snow') { return svg`${base}`; } else { return base; } }); let markers = points.map(p => svg``); return html`` }34:[] 2f:{"title":"Reshaping distributions","cells":[{"id":0,"value":"md`# Reshaping distributions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"md`There are times I've generated a set of numbers that don't have the distribution I want. For example let's use noise to make a mountainous landscape:`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"(waterYThreshold >= snowYThreshold)? html`Error: snowYThreshold must be greater than waterYThreshold` : md`Let's color the low lying areas as water and the highest peaks with snow:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":132,"value":"viewof waterYThreshold = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"viewof snowYThreshold = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":85,"value":"terrainBefore = svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":564,"value":"{\n function percent(x) {\n\treturn d3.format(\".0%\")(x / counts.total);\n }\n\n return md`For my game map I want to decide how much is water, land, and snow. One way to get this is to generate lots of maps until I find one that matches my goals. But instead I'm going to *modify* this map to match the constraints.\n\nLet's **sort the values by elevation**, putting all the low elevations on the left and the high elevations on the right.\n\nThe current distribution is: water=${percent(counts.water)} land=${percent(counts.land)} snow=${percent(counts.snow)}.\n`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":125,"value":"distributionBefore = svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":201,"value":"{\n function percent(x) {\n\treturn d3.format(\".0%\")(x / desired.total);\n }\n return md`The horizontal lines show the water and snow thresholds. Note the black line intersects the thresholds just as they change from water to land to snow. We're going to solve our problem by preserving this property.\n\n Let's choose a distribution instead of taking what the procedural generator gave us: water=${percent(desired.water)} land=${percent(desired.land)} snow=${percent(desired.snow)}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"viewof waterDesired = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":265,"value":"viewof landDesired = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":262,"value":"viewof snowDesired = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":205,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":333,"value":"md`The black line no longer intersects the thresholds at the right place. Let's move the data *vertically* to make it intersect again. We need to *separately* shift the water, land, and snow sections based on the desired intersection points. **Try moving the sliders** above marked \\`waterDesired\\`, \\`landDesired\\`, \\`snowDesired\\` to see the line shifting vertically.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":208,"value":"distributionAfter = svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":393,"value":"md`Now that we have the right amounts of water, land, and snow, we can **sort the data** back to its original positions. This produces terrain with the desired distribution:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"terrainAfter = svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":395,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":469,"value":"md`*I don't know the proper math terminology for this operation*. I'm assigning a *rank* to each data point, and then I am adjusting the y value based on x, y, and the rank. The sorting is for the visual explanation but underneath I only need the rank, or approximate rank. Is this called reshaping or redistribution or rescaling or remapping or what? If you can give me some hints, let me know [@redblobgames](https://twitter.com/redblobgames) on twitter or [redblobgames@gmail.com](mailto:redblobgames@gmail.com) by email. Thanks!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":750,"value":"md`# Appendix: the animation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":770,"value":"md`Each animation a 1x1 SVG that's set to [overflow:visible](http://simblob.blogspot.com/2016/10/outside-box.html) so that it can reach into the rest of the page. I then use \\`getClientBoundingBox()\\` to get the position and size of the other SVGs on the page, and then I can draw over them and in between them. I don't see this technique used much.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":593,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":669,"value":"// This is just like animationBefore, but I was too lazy to factor it out\nanimationAfter = { \n function mySvg(contents) {\n return svg``;\n }\n let element = mySvg(\"\");\n yield element;\n let fromRect = terrainAfter.getBoundingClientRect();\n let toRect = distributionAfter.getBoundingClientRect();\n let myRect = element.parentNode.getBoundingClientRect();\n yield mySvg(svgAnimatedMarkers(scaledTerrain, fromRect, toRect, myRect));\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":666,"value":"function svgAnimatedMarkers(t, fromRect, toRect, myRect) {\n let markers = t.map((p, index) => {\n\t let x1 = fromRect.left-myRect.left + fromRect.width * (p.x-0.5) / 100,\n \t y1 = fromRect.top-myRect.top + fromRect.height * (1-p.y),\n x2 = toRect.left-myRect.left + toRect.width * (index / t.length),\n y2 = toRect.top-myRect.top + toRect.height * (1-p.y);\n let x = mix(x1, x2, phase),\n y = mix(y1, y2, phase);\n let type = (p.y < waterYThreshold)? 'water' : (p.y >= snowYThreshold)? 'snow' : 'land';\n return ``;\n });\n return markers.join(\"\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"md`# Appendix: map parameters`","pinned":false,"hidden":false,"mode":"ojs"},{"id":141,"value":"md`Land below the water threshold becomes water. Land above the snow threshold becomes snow. You can play with these parameters if you'd like, but it's not the main focus of the article. I put these in so that I could easily tune it to find a good map to illustrate the concept.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":162,"value":"viewof smoothness = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":59,"value":"viewof frequency = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":413,"value":"viewof frequency1 = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":415,"value":"viewof phase1 = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":421,"value":"viewof frequency2 = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":424,"value":"viewof phase2 = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":431,"value":"viewof frequency3 = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":435,"value":"viewof phase3 = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"md`# Appendix: implementation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"viewof debugSvg = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"html`\nCSS`","pinned":false,"hidden":false,"mode":"ojs"},{"id":39,"value":"/* x value is from 0 to 100, inclusive; y value is from 0 to 1 */\nterrain = {\n let xStep = Math.pow(10, smoothness);\n let steps = Math.ceil(100 / xStep);\n // I use an integer loop that includes 'steps' instead of looping\n // for (x = 0; x <= 100; x += xStep) because I want the loop to *end*\n // at exactly 100\n let results = [];\n for (let i = 0; i <= steps; i++) {\n let x = i / steps * 100;\n\t let a = Math.sin(frequency * x * frequency1 + phase1),\n \t b = Math.sin(frequency * x * frequency2 + phase2),\n\t c = Math.sin(frequency * x * frequency3 + phase3);\n let mixture = 0.5*a + 0.3*b + 0.2*c;\n let y = 0.5 * (1 + mixture);\n results.push({x, y});\n }\n return results;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":212,"value":"sortedTerrain = {\n let array = terrain.concat();\n array.sort((a, b) => a.y - b.y);\n return array;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":348,"value":"scaledTerrain = {\n function rescale(from1, from2, to1, to2, from) {\n return (from - from1) / (from2 - from1) * (to2 - to1) + to1;\n }\n let waterIndex = Math.round((sortedTerrain.length-1) * desired.water / desired.total);\n let snowIndex = Math.round((sortedTerrain.length-1) * (desired.water + desired.land) / desired.total);\n return sortedTerrain.map(({x, y}, index) => {\n if (index < waterIndex) {\n // alternate way that ignores y but has fewer corner cases:\n // y = rescale(0, waterIndex, 0, waterYThreshold, index)\n y = rescale(0, sortedTerrain[waterIndex].y, 0, waterYThreshold, y);\n } else if (index < snowIndex) {\n y = rescale(sortedTerrain[waterIndex].y, sortedTerrain[snowIndex].y, waterYThreshold, snowYThreshold, y);\n } else {\n y = rescale(sortedTerrain[snowIndex].y, 1, snowYThreshold, 1, y);\n }\n return {x, y};\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":318,"value":"resortedTerrain = {\n let array = scaledTerrain.concat();\n array.sort((a, b) => a.x - b.x);\n return array;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"counts = {\n let total = 0, water = 0, land = 0, snow = 0;\n for (let {x,y} of terrain) {\n total++;\n if (y < waterYThreshold) { water++; }\n else if (y < snowYThreshold) { land++; }\n else { snow++; }\n }\n return {total, water, land, snow};\n} ","pinned":false,"hidden":false,"mode":"ojs"},{"id":273,"value":"desired = ({\n total: waterDesired + landDesired + snowDesired,\n water: waterDesired,\n land: landDesired,\n snow: snowDesired,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":221,"value":"function drawPath(t) {\n let format = d3.format(\".2f\");\n let line = d3.line()\n .x((p, i)=>format(100*i/(t.length-1)))\n .y(p=>format(10*(1-p.y)));\n return `${line(t)} l 2 0 L 102 12 L -2 12 L -2 ${10*(1-t[0].y)} Z`;\n} ","pinned":false,"hidden":false,"mode":"ojs"},{"id":216,"value":"function drawTerrain(t) {\n let id = Math.floor(100000*Math.random());\n let path = drawPath(t);\n return svg`\n \n \n \n \n \n \n \n \n `;\n}\n ","pinned":false,"hidden":false,"mode":"ojs"},{"id":358,"value":"function drawSortedTerrain(d, t) {\n return svg`\n\n \n \n \n\n\n\n\n\n\n\n`;\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":490,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":723,"value":"phase = {\n const frameTime = 30;\n while (true) {\n let t = 0;\n while (t < 1.0) {\n yield Promises.tick(frameTime, t);\n t += frameTime/1000;\n }\n yield Promises.tick(frameTime, 1);\n yield Promises.tick(3000, 1);\n while (t >= 0) {\n yield Promises.tick(frameTime, t);\n t -= frameTime/1000;\n }\n yield Promises.tick(frameTime, 0);\n yield Promises.tick(3000, 0);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":640,"value":"/* like opengl */\nfunction mix(a, b, t) {\n return a * (1-t) + b * t;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"d3 = require('d3')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}