2a:null 2b:["$","title",null,{"children":"Génération procédurale de cartes | linard-y | Observable"}] 31:[] 2e:{"id":"71c29e71509a31c0","slug":"gpc-etape-1","title":"Génération procédurale de cartes","thumbnail":"cf42b241d8fbf4eb4e77a0b7dd2ed4392191e99b4f71c12398808e96cfeb392d","access_level":"public","create_time":"$D2019-12-19T21:58:35.097Z","update_time":"$D2022-01-07T17:57:38.034Z","view_time":null,"first_public_time":"$D2019-12-19T21:58:59.816Z","fork":true,"stars":0,"starred":false,"owner":{"type":"team","id":"9784867a3e59436b","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":"starter_2024"},"version":724,"publish_version":724,"role":null,"authored":false,"authors":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null}],"members":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"1054c72829cb0575","slug":"generation-procedurale-de-cartes","title":"Génération procédurale de cartes","owner":{"id":"9784867a3e59436b","login":"linard-y","name":""}},"type":"notebook","body":{"title":"Génération procédurale de cartes","cells":[{"id":557,"value":"md`# Génération procédurale de cartes`","pinned":false,"hidden":false,"mode":"ojs"},{"id":563,"value":"md`Inspiré par les travaux remarquables de [Amit Patel](https://www.redblobgames.com/maps/mapgen4/), [Azgaar](https://azgaar.wordpress.com/) et [Martin O'Leary](https://mewo2.com/notes/terrain/).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":661,"value":"Navigation(1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":709,"value":"Separation(1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":0,"value":"md`## ETAPE 1 : Diagramme de Voronoï & Quantification (algorithme de Loyd-Max)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":142,"value":"md`Tout d'abord, définissons la taille de ce qui sera notre element d'affichage (un svg) et générons des points [x,y] distribués aléatoirement sur une zone rectangulaire de dimension width x height.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"width = 960;","pinned":false,"hidden":false,"mode":"ojs"},{"id":42,"value":"height = 300;","pinned":false,"hidden":false,"mode":"ojs"},{"id":159,"value":"viewof NbreDePoints = slider({\n min: 0, \n max: 10000, \n step: 250, \n description: \"Nombre de points\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":139,"value":"points = d3.range(NbreDePoints).map(function(d) { return [Math.random() * width, Math.random() * height];});","pinned":false,"hidden":false,"mode":"ojs"},{"id":148,"value":"md`Ensuite, utilisons **d3.js** pour construire le diagramme de Voronoï sur l'ensemble des points.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":112,"value":"voronoi = d3.voronoi().extent([[0, 0], [width, height]]);","pinned":false,"hidden":false,"mode":"ojs"},{"id":186,"value":"{ \n const svg = d3.select(DOM.element('svg'))\n .attr(\"width\", width)\n .attr(\"height\", height);\n \n const couleur = d3.scaleSequential(d3.interpolateSpectral);\n \n voronoi.polygons(points).map(\n function(i, d) {\n svg.append(\"path\").attr(\"d\", \"M\" + i.join(\"L\") + \"Z\").attr(\"fill\", couleur(d/NbreDePoints));\n }\n );\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":529,"value":"Separation(1);","pinned":false,"hidden":false,"mode":"ojs"},{"id":204,"value":"md`Comme on peut le constater, le pavage est un peu irrégulier. Nous allons l'améliorer en utilisant l'algorythme de Lloyd-Max. L’algorithme de Lloyd-Max (encore appelé relaxation) est un algorithme (Max 1960, Lloyd 1982, Peric and Nikolic 2007) qui permet de trouver le quantifieur optimal. C’est à dire, celui pour lequel l’erreur générée entre l’image de départ et celle quantifiée est la plus petite. Dans notre cas l'algorithme va déplacer à chaque itération chaque noeud de la cellule de Voronoï vers le centroïde qui lui est associé.\n\n* Max J., 1960 - Quantizing for minimum distortion information, _Theory IRE Trans._, vol. 6 (pg. 7-12)\n* Lloyd S., 1982 - Least squares quantization in PCM, _IEEE Trans. Inform. Theory_, vol. 28 (pg. 129-137)\n* Peric Z., Nikolic J., 2007 - An effective method for initialization of Lloyd–Max’s algorithm of optimal scalar quantization for Laplacian, Source Inform., vol. 18 (pg. 279-288)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":308,"value":"viewof relax = number({placeholder: \"0\", title: \"Relaxation iteration\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":480,"value":" { \n const svg = d3.select(DOM.element('svg'))\n .attr(\"width\", width)\n .attr(\"height\", height);\n \n const couleur = d3.scaleSequential(d3.interpolateSpectral);\n \n let pts = points;\n for (var i=0; iwidth_ et _height_ du diagramme, le nombre de points, _N_, définissant le diagramme et le nombre d'itérations, _relaxit_, de l'algorithme de relaxation. Ce dermier argument est facultatif, en cas d'absence aucune itération de relaxation ne sera réalisée.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":715,"value":"function creeVoronoi(width, height, N, relaxit) {\n let voronoi;\n let points = d3.range(N).map(function(d) {return [Math.random() * width, Math.random() * height];});\n let relax = relaxit || 0 ;\n for (var i=0; i<=relax; i++){\n voronoi = d3.voronoi().extent([[0, 0],[width, height]])(points);\n points = voronoi.polygons().map(d3.polygonCentroid);\n }\n\n return voronoi; \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":718,"value":"Separation(1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"md`#### Importation des libraries utiles`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"import {button, slider, number} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":676,"value":"import {Navigation, Separation} from \"@linard-y/gpc-fonctions-annexes\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2f:"$2e:body"