25:["$","title",null,{"children":"Wave function collapse | Woo-Mi Jeong | Observable"}] 49:T6cd,s = { const tool = new WFCTool2D(); tool.addTile(`\ @@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@`,{weight:10}) tool.addTile(`\ ........ ........ ........ ........ ........ ........ ........ ........`) tool.addTile(`\ ........ ..####.. .#----## .#----#= .#----#= .#----## ..####.. ........`) tool.addTile(`\ @#...... @###.... @#-##### @#-#-#== @#-#-#== @#-##### @###.... @#......`) tool.addTile(`\ @#...... ##...... ........ ........ ........ ........ ........ ........`) tool.addTile(`\ ........ ........ ######## ======== ======== ######## ........ ........`) tool.addTile(`\ ..#--#.. ..#--#.. ###--### ==#--#== ==#--#== ###--### ..#--#.. ..#--#..`) tool.addTile(`\ ........ ..####.. ##---### =#------ =#------ ##---### ..####.. ........`) tool.addTile(`\ ..#==#.. ..#==#.. ..#==### ..#===== ..#===== ..#==### ..#==#.. ..#==#..`) tool.addTile(`\ ..#==#.. ...#==#. #...#==# =#...#== ==#...#= #==#...# .#==#... ..#==#..`) tool.addTile(`\ ..#==#.. ...#==#. ....#==# .....#== ......#= .......# ........ ........`) tool.addColor("@", [255,255,255]) tool.addColor(".", [255,255,255]) tool.addColor("-", [255,255,255]) tool.addColor("=", [255,255,255]) tool.addColor("#", [10,10,30]) //console.log(tool); //console.log(tool.getTileFormulae()); var wfcInput = tool.generateWFCInput(); var wfc = new WFC(wfcInput); const S = 400; const context = DOM.context2d(S, S); var viewport = {x:0,y:0,w:10,h:10}; wfc.expand([viewport.y,viewport.x],[viewport.y+viewport.h,viewport.x+viewport.w]); for(let i = 0; i<100; i++){ wfc.step(); } console.log(wfc.readout(false)) tool.plotWFCOutput(context.canvas, viewport, wfc.readout(false)); return context.canvas; }4a:T8ce,aaa={ var nd = 10; // number of dimensions (2, 3, etc.) var weights = [0.5, 0.5, 0.5] // weight for each type of tile // this also implies the total number of tiles // here all weights are equal, so the tiles will // generate at equal probability // the rules is an array of 3-tuples. // for each rule, the first element specifies the axis, and the 2nd and 3rd // specifies what tiles can go next to each other on that axis var rules = [ ['x',0,1], // 0th tile can be placed to the left of 1st tile ['x',1,0], // 1st tile can also be placed to the left of 0th tile ['y',1,2], // if you have more than 3 dimensions, the axis can be specified // using integers instead of 'x', 'y' and 'z'. // in fact 'y' is an alias of 0th axis, 'x' the 1st, and 'z' the 2nd ] var wfc = new WFC({nd, weights, rules}); // initialize the wfc! // define a region of interest inside which you want tiles to be generated // by passing two corners of the bounding box/cube/hypercube var size = 5; wfc.expand([-size,-size],[size,size]); for(let i=0; i<1500; i++){ const done = wfc.step(); console.log(done); } console.log(wfc.readout(false)); // the main loop // subsitute with setTimeout/requestAnimationFrame/WebWorker depending on usage /* while (true){ var done = wfc.step(); // advance 1 step, filling at least 1 new coordinate. // step() returns true if the region of interest has // been entirely filled if (done){ size += 5 // all space filled, time to expand more wfc.expand([-size,-size],[size,size]); // newly marked area will begin to // be generated in the next step() } console.log(wfc.readout()); // ^ get the current result, an object mapping coordinate to tile index // something like {'1,2':0, '2,2':2, '3,1':1, ...} // use wfc.readout(false) to read the result as probability distribution, // something like {'1,2',[1,0,0], '2,2':[0.3,0.2,0.5], ...} } return wfc.readout();*/ return wfc.readout(); }4b:T140c,WFC = function({nd,weights,rules,wave}){ wave = wave || {}; var wavefront = {} var n_patterns = weights.length var wavefront = {} function coord(k){ return k.split(",").map(x=>parseInt(x)) } function entropy(x){ var one = 0 for (var i = 0; i < x.length; i++){ one += x[i]*weights[i] } var S = 0 for (var i = 0; i < x.length; i++){ var pi = x[i]*weights[i]/one if (pi != 0){ S -= pi*Math.log(pi) } } return S } function collapse(x){ var one = 0 for (var i = 0; i < x.length; i++){ one += x[i]*weights[i] } var r = Math.random()*one for (var i = 0; i < x.length; i++){ r -= x[i]*weights[i] if (r < 0){ var y = new Array(x.length).fill(0) y[i] = 1 return y } } } function neighborable(d,a,b){ var didx = d.indexOf(1) if (didx < 0){ didx = d.indexOf(-1) ;[a,b] = [b,a] } for (var i = 0; i < rules.length; i++){ if (didx == rules[i][0] || "yxz"[didx] == rules[i][0]){ if (a == rules[i][1] && b == rules[i][2]){ return true } } } return false } function propagate(p){ var stack = [p] while (stack.length){ p = stack.pop() var dirs = [] for (var i = 0; i < nd; i++){ var d0 = new Array(nd).fill(0) d0[i] = -1 dirs.push(d0) var d1 = new Array(nd).fill(0) d1[i] = 1 dirs.push(d1) } for (var i = 0; i < dirs.length; i++){ var q = [] for (var j = 0; j < p.length; j++){ q.push(p[j]+dirs[i][j]) } var x = wavefront[p]; if (x == undefined) {x = wave[p]} var y = wavefront[q]; if (x == undefined) {x = wave[q]} if (typeof y == 'number' || typeof y == 'undefined'){ continue }else if (typeof x == 'number' && typeof y == 'object'){ var mod = false for (var j = 0; j < y.length; j++){ if (y[j] == 0){ continue } if (y[j] > 0 && !neighborable(dirs[i],x,j)){ y[j] = 0 mod = true } } if (mod){ stack.push(q); } }else if (typeof x == 'object' && typeof y == 'object'){ var mod = false for (var j = 0; j < y.length; j++){ if (y[j] == 0){ continue } var ok = false for (var k = 0; k < x.length; k++){ if (x[k] > 0 && y[j] > 0 && neighborable(dirs[i],k,j)){ ok = true break } } if (!ok){ y[j] = 0 mod = true } } if (mod){ stack.push(q) } }else{ throw Error("Invalid propagation parameter",x,y); } } } } function argmax(vals){ var mi = -1; var mv = -Infinity; for (var i = 0; i < vals.length; i++){ if (vals[i] > mv){ mv = vals[i] mi = i } } return mi } this.readout = function(collapse=true){ if (!collapse){ var result = {} for (var k in wave){ var oh = Array(n_patterns).fill(0); oh[wave[k]] = 1; result[k] = oh; } for (var k in wavefront){ var s = wavefront[k].reduce((a,b) => a + b, 0) var oh = wavefront[k].map(x=>(s==0?0:x/s)); result[k] = oh; } return result; } var result = {} for (var k in wavefront){ if (wavefront[k].reduce((a,b) => a + b, 0) == 1){ result[k] = argmax(wavefront[k]) } } return Object.assign({},wave,result) } this.expand = function(xmin, xmax){ var coords = [[0]] for (var i = 0; i < xmin.length; i++){ var cc = [] for (var x = xmin[i]; x < xmax[i]; x++){ var c = [] for (var j = 0; j < coords.length; j++){ c.push(coords[j].concat(x)) } cc = cc.concat(c) } coords = cc; } coords = coords.map(x=>x.slice(1)).filter(x=>!(x in wave || x in wavefront)) coords.map(x=>wavefront[x]=new Array(n_patterns).fill(1)) for (var k in wave){ propagate(coord(k)) } } this.step = function(){ var min_ent = Infinity var min_arg = undefined for (var k in wavefront){ var ent = entropy(wavefront[k]) if (isNaN(ent)){ for (var k in wavefront){ wavefront[k]=new Array(n_patterns).fill(1) } for (var k in wave){ propagate(coord(k)) } console.log(":(") return false } if (ent == 0){ continue; } ent += (Math.random()-0.5) if (ent < min_ent){ min_ent = ent min_arg = coord(k) } } if (min_ent == Infinity){ wave = this.readout(); wavefront = {}; return true; } wavefront[min_arg] = collapse(wavefront[min_arg]); propagate(min_arg); return false; } } 4c:T11c9,WFCTool2D = function(){ var tiles = [] var colors = {} var weights = [] var n_prototypes = 0 var formulae = [] var transformBank = { cw:function(m){ var r = []; for (var i = 0; i < m.length; i++){ r.push([]) for (var j = m.length-1; j >= 0; j--){ r[r.length-1].push(m[j][i]); } } return r; }, fx:function(m){ var r = []; for (var i = 0; i < m.length; i++){ r.push([]) for (var j = m[0].length-1; j >= 0; j--){ r[r.length-1].push(m[i][j]); } } return r; }, fy:function(m){ var r = []; for (var i = m.length-1; i >= 0; i--){ r.push([]) for (var j = 0; j < m[i].length; j++){ r[r.length-1].push(m[i][j]); } } return r; } } function equal(m,r){ for (var i = 0; i < m.length; i++){ for (var j = 0; j < m[0].length; j++){ if (m[i][j] != r[i][j]){ return false; } } } return true; } function fit(d,a,b){ if (d == "x"){ for (var i = 0; i < a.length; i++){ if (a[i][a[i].length-1] != b[i][0]){ return false; } } }else if (d == "y"){ for (var i = 0; i < a[0].length; i++){ if (a[a.length-1][i] != b[0][i]){ return false; } } } return true; } this.addTile = function(s,{transforms="auto",weight=1}={}){ var t = s.split("\n").map(x=>x.split("")) tiles.push(t); formulae.push([ n_prototypes, '', t ]) weights.push(weight) var tests = [] if (transforms == "auto"){ transforms = ['cw','cw+cw','cw+cw+cw'] } for (var i = 0; i < transforms.length; i++){ var tl = transforms[i].split("+") var tt = t for (var j = 0; j < tl.length; j++){ tt = transformBank[tl[j]](tt); } tests.push(tt); } for (var i = 0; i < tests.length; i++){ var ok = true; for (var j = 0; j < tiles.length; j++){ if (equal(tests[i],tiles[j])){ ok = false; break; } } if (ok){ tiles.push(tests[i]) weights.push(weight) formulae.push([ n_prototypes, transforms[i], tests[i] ]) } } n_prototypes++; } this.addColor = function(symbol, color){ colors[symbol] = color } this.getTileFormulae = function(){ return formulae; } this.generateWFCInput = function(){ var rules = [] for (var i = 0; i < tiles.length; i++){ for (var j = 0; j < tiles.length; j++){ if (fit("x",tiles[i],tiles[j])){ rules.push(['x',i,j]) } if (fit("y",tiles[i],tiles[j])){ rules.push(['y',i,j]) } } } return {weights,rules,nd:2} } var viewportCached = {x:0,y:0,w:-1,h:-1}; var waveCached = {}; this.clearPlotCache = function(){ waveCached = {}; } this.plotWFCOutput = function(canvas,viewport,wave){ var ctx = canvas.getContext('2d'); var w = tiles[0][0].length var h = tiles[0].length; var cw = canvas.width/viewport.w var ch = canvas.height/viewport.h if (viewportCached.x != viewport.x || viewportCached.y != viewport.y || viewportCached.w != viewport.w || viewportCached.h != viewport.h){ waveCached = {}; ctx.fillStyle = "black" ctx.fillRect(0,0,canvas.width,canvas.height) } viewportCached = {x:viewport.x,y:viewport.y,w:viewport.w,h:viewport.h}; console.log('-->', wave); for (var k in wave){ console.log('in wave'); if (k in waveCached){ continue } waveCached[k] = wave[k] var [y,x] = k.split(",").map(x=>parseInt(x)); x = (x-viewport.x)/viewport.w*canvas.width y = (y-viewport.y)/viewport.h*canvas.height var v = wave[k]; for (var i = 0; i < h; i++){ for (var j = 0; j < w; j++){ var rgb = [0,0,0]; if (typeof v === 'number'){ rgb = colors[tiles[v][i][j]]; }else{ for (var ii = 0; ii < tiles.length; ii++){ rgb[0] += colors[tiles[ii][i][j]][0]*v[ii]; rgb[1] += colors[tiles[ii][i][j]][1]*v[ii]; rgb[2] += colors[tiles[ii][i][j]][2]*v[ii]; } rgb = rgb.map(Math.round) } ctx.fillStyle = `rgb(${rgb[0]},${rgb[1]},${rgb[2]})`; ctx.fillRect(x+cw*j/w,y+ch*i/h,cw/w+1,ch/h+1); } } } } }4d:[] 29:{"id":"416587be06c76175","slug":null,"title":"Wave function collapse","thumbnail":"f67b4c36d0b3052752cb8fbd54243086ec2ff1aff7306685a1f8a7fba0f28fa8","access_level":"public","create_time":"$D2023-10-30T20:55:59.709Z","update_time":"$D2023-10-31T01:38:59.519Z","view_time":null,"first_public_time":"$D2023-10-30T20:55:59.709Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"536e89b71dfea055","login":"woomi","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/31e0a5a063c4f7c40056ea87b83e7737edd99de7ce9467b98c4b12394d8c0561","tier":"starter_2024","bio":"","following":false},"version":60,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"106dcc0cf6497c8a","login":"woomijeong","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/1b631bfd87ceb9a9978eecf2c926160b7765e71f2b89cb9e83edd9366f41b23f","tier":null,"bio":"","following":false}],"members":[{"type":"team","id":"536e89b71dfea055","login":"woomi","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/31e0a5a063c4f7c40056ea87b83e7737edd99de7ce9467b98c4b12394d8c0561","tier":"starter_2024","role":"editor"},{"type":"individual","id":"106dcc0cf6497c8a","login":"woomijeong","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/1b631bfd87ceb9a9978eecf2c926160b7765e71f2b89cb9e83edd9366f41b23f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Wave function collapse","cells":[{"id":0,"value":"# Wave function collapse","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":23,"value":"$49","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"$4a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"$4b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"$4c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4d","stdlib":"1"}} 24:null