All articles
28 min read

Wave Function Collapse: How to Generate Infinite Tile-Based Worlds With Code

wave function collapseprocedural generationtile-basedcreative codingJavaScriptcanvasgame developmentalgorithms

Wave Function Collapse is one of the most elegant procedural generation algorithms ever invented. Named after the quantum mechanics concept, it generates complex, globally consistent patterns from simple local rules. Define which tiles can sit next to each other, and the algorithm fills an entire grid with a coherent result — roads that connect, rivers that flow, terrain that transitions smoothly.

This article builds 8 Wave Function Collapse visualizations from scratch using JavaScript and Canvas. Every example runs live in your browser. We start with the basic constraint concept, build a full WFC solver, then apply it to terrain, cities, platformer levels, pipe networks, pixel art, and an interactive editor where you paint your own tile rules.

1. Tile Adjacency: The Constraint Foundation

Before we build WFC, we need to understand adjacency constraints. Each tile has four edges (top, right, bottom, left), and two tiles can sit next to each other only if their touching edges match. This first example lets you see how constraints work — tiles are colored by edge type, and compatible neighbors light up when you hover.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const EDGE={G:0,W:1,R:2,S:3};
const COLORS=['#4a7c59','#3b82c4','#c4443b','#c49a3b'];
const EDGE_NAMES=['Grass','Water','Road','Sand'];
const tiles=[
  {name:'Grass',edges:[0,0,0,0],color:'#2d5a1e'},
  {name:'Water',edges:[1,1,1,1],color:'#1a5276'},
  {name:'Road H',edges:[0,2,0,2],color:'#555'},
  {name:'Road V',edges:[2,0,2,0],color:'#555'},
  {name:'Road +',edges:[2,2,2,2],color:'#555'},
  {name:'Coast N',edges:[1,3,0,3],color:'#c2b280'},
  {name:'Coast S',edges:[0,3,1,3],color:'#c2b280'},
  {name:'Coast E',edges:[3,1,3,0],color:'#c2b280'},
  {name:'Coast W',edges:[3,0,3,1],color:'#c2b280'},
  {name:'Sand',edges:[3,3,3,3],color:'#dcc282'},
  {name:'Road End N',edges:[2,0,0,0],color:'#555'},
  {name:'Road End S',edges:[0,0,2,0],color:'#555'},
];
const S=60,PAD=10,mx=-1,my=-1;let hover=-1;
function compatible(a,b,dir){
  const eidx=[[2,0],[3,1],[0,2],[1,3]];
  return tiles[a].edges[eidx[dir][0]]===tiles[b].edges[eidx[dir][1]];
}
c.addEventListener('mousemove',e=>{
  const r=c.getBoundingClientRect();const px=e.clientX-r.left,py=e.clientY-r.top;
  hover=-1;
  for(let i=0;i<tiles.length;i++){
    const col=i%6,row=i/6|0;
    const tx=40+col*(S+PAD),ty=40+row*(S+PAD);
    if(px>=tx&&px<tx+S&&py>=ty&&py<ty+S)hover=i;
  }
});
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='18px monospace';
  x.fillText('Tile Adjacency Constraints — Hover to see compatible neighbors',40,25);
  const compat=new Set();
  if(hover>=0){for(let i=0;i<tiles.length;i++){for(let d=0;d<4;d++){if(compatible(hover,i,d)){compat.add(i);break}}}}
  for(let i=0;i<tiles.length;i++){
    const col=i%6,row=i/6|0;
    const tx=40+col*(S+PAD),ty=40+row*(S+PAD);
    x.globalAlpha=hover>=0&&i!==hover&&!compat.has(i)?0.2:1;
    x.fillStyle=tiles[i].color;x.fillRect(tx,ty,S,S);
    const e=tiles[i].edges;
    const ec=4;
    x.fillStyle=COLORS[e[0]];x.fillRect(tx+S/4,ty,S/2,ec);
    x.fillStyle=COLORS[e[1]];x.fillRect(tx+S-ec,ty+S/4,ec,S/2);
    x.fillStyle=COLORS[e[2]];x.fillRect(tx+S/4,ty+S-ec,S/2,ec);
    x.fillStyle=COLORS[e[3]];x.fillRect(tx,ty+S/4,ec,S/2);
    if(i===hover){x.strokeStyle='#fff';x.lineWidth=2;x.strokeRect(tx-1,ty-1,S+2,S+2)}
    x.globalAlpha=1;
    x.fillStyle='#eee';x.font='9px monospace';x.textAlign='center';
    x.fillText(tiles[i].name,tx+S/2,ty+S+12);x.textAlign='left';
  }
  if(hover>=0){
    const t=tiles[hover];let y2=180;
    x.fillStyle='#eee';x.font='14px monospace';
    x.fillText('Edges: T='+EDGE_NAMES[t.edges[0]]+' R='+EDGE_NAMES[t.edges[1]]+' B='+EDGE_NAMES[t.edges[2]]+' L='+EDGE_NAMES[t.edges[3]],40,y2);
    x.fillText('Compatible with: '+[...compat].map(i=>tiles[i].name).join(', '),40,y2+20);
  }
  requestAnimationFrame(draw);
}
draw();
</script></body></html>

2. Basic WFC Solver

Now the real algorithm. We create a grid where each cell starts as a superposition of all possible tiles. Each step: (1) find the cell with lowest entropy (fewest remaining options), (2) collapse it to one tile (weighted random), (3) propagate constraints to neighbors, removing any tiles that would violate adjacency. Watch the grid resolve from chaos to order, cell by cell.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const TILES=[
  {edges:[0,0,0,0],color:'#2d6b1e',w:4},
  {edges:[1,1,1,1],color:'#1a5276',w:2},
  {edges:[0,2,0,2],color:'#666',w:1},
  {edges:[2,0,2,0],color:'#666',w:1},
  {edges:[2,2,2,2],color:'#777',w:0.5},
  {edges:[2,2,0,0],color:'#666',w:1},
  {edges:[0,2,2,0],color:'#666',w:1},
  {edges:[0,0,2,2],color:'#666',w:1},
  {edges:[2,0,0,2],color:'#666',w:1},
  {edges:[3,3,3,3],color:'#dcc282',w:2},
  {edges:[0,0,3,3],color:'#8bae6a',w:1},
  {edges:[3,0,0,3],color:'#8bae6a',w:1},
  {edges:[3,3,0,0],color:'#8bae6a',w:1},
  {edges:[0,3,3,0],color:'#8bae6a',w:1},
];
const DIRS=[[0,-1],[1,0],[0,1],[-1,0]];
const EDGE_PAIR=[[2,0],[3,1],[0,2],[1,3]];
const GS=20;let cols,rows,grid,collapsed=0,done=false,speed=3;
function canAdj(a,b,d){return TILES[a].edges[EDGE_PAIR[d][0]]===TILES[b].edges[EDGE_PAIR[d][1]]}
function init(){
  cols=Math.floor((W-40)/GS);rows=Math.floor((H-60)/GS);
  grid=Array.from({length:cols*rows},()=>({opts:[...Array(TILES.length).keys()],tile:-1}));
  collapsed=0;done=false;
}
init();
function entropy(cell){if(cell.tile>=0)return 999;return cell.opts.length+Math.random()*0.1}
function propagate(idx){
  const stack=[idx];const visited=new Set();
  while(stack.length){
    const cur=stack.pop();if(visited.has(cur))continue;visited.add(cur);
    const cx=cur%cols,cy=cur/cols|0;
    for(let d=0;d<4;d++){
      const nx=cx+DIRS[d][0],ny=cy+DIRS[d][1];
      if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
      const ni=ny*cols+nx;const ncell=grid[ni];
      if(ncell.tile>=0)continue;
      const before=ncell.opts.length;
      ncell.opts=ncell.opts.filter(t=>grid[cur].opts.some(ct=>canAdj(ct,t,d)));
      if(ncell.opts.length===0){done=true;return false}
      if(ncell.opts.length===1){ncell.tile=ncell.opts[0];collapsed++}
      if(ncell.opts.length<before)stack.push(ni);
    }
  }
  return true;
}
function step(){
  if(done)return;
  let minE=999,minIdx=-1;
  for(let i=0;i<grid.length;i++){const e=entropy(grid[i]);if(e<minE){minE=e;minIdx=i}}
  if(minIdx<0||grid[minIdx].tile>=0){done=true;return}
  const cell=grid[minIdx];
  const weights=cell.opts.map(t=>TILES[t].w);
  const total=weights.reduce((a,b)=>a+b,0);
  let r=Math.random()*total;
  for(let i=0;i<cell.opts.length;i++){r-=weights[i];if(r<=0){cell.tile=cell.opts[i];cell.opts=[cell.opts[i]];collapsed++;break}}
  if(!propagate(minIdx)){done=true}
}
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='14px monospace';
  x.fillText('Wave Function Collapse — '+collapsed+'/'+(cols*rows)+' cells collapsed'+(done?' — Click to restart':''),20,20);
  const ox=(W-cols*GS)/2,oy=35;
  for(let i=0;i<grid.length;i++){
    const gx=i%cols,gy=i/cols|0;
    const px=ox+gx*GS,py=oy+gy*GS;
    if(grid[i].tile>=0){
      x.fillStyle=TILES[grid[i].tile].color;x.fillRect(px,py,GS-1,GS-1);
    } else {
      const n=grid[i].opts.length;
      const bright=Math.floor(20+n/TILES.length*40);
      x.fillStyle=`rgb(${bright},${bright},${bright+20})`;
      x.fillRect(px,py,GS-1,GS-1);
    }
  }
  if(!done)for(let i=0;i<speed;i++)step();
  requestAnimationFrame(draw);
}
c.addEventListener('click',()=>{init()});
draw();
</script></body></html>

3. Terrain Generation

WFC shines at terrain. Define tiles for deep water, shallow water, sand, grass, forest, and mountains, with transition rules (deep water can only touch shallow water, not grass directly). The algorithm produces natural-looking landscapes with smooth transitions — no hard edges between biomes. Click to generate a new world.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const B=[
  {name:'Deep Water',edges:[0,0,0,0],color:'#0a3d6b',w:3},
  {name:'Shallow',edges:[1,1,1,1],color:'#1a6fa0',w:2},
  {name:'Sand',edges:[2,2,2,2],color:'#d4b96a',w:1.5},
  {name:'Grass',edges:[3,3,3,3],color:'#3a8c3f',w:4},
  {name:'Forest',edges:[4,4,4,4],color:'#1e5e24',w:3},
  {name:'Mountain',edges:[5,5,5,5],color:'#6b6b6b',w:1},
  {name:'Snow',edges:[6,6,6,6],color:'#e8e8e8',w:0.5},
  {name:'DW-Sh N',edges:[1,0,0,0],color:'#0f4e82',w:1},{name:'DW-Sh E',edges:[0,1,0,0],color:'#0f4e82',w:1},
  {name:'DW-Sh S',edges:[0,0,1,0],color:'#0f4e82',w:1},{name:'DW-Sh W',edges:[0,0,0,1],color:'#0f4e82',w:1},
  {name:'Sh-Sa N',edges:[2,1,1,1],color:'#5a9ab5',w:1},{name:'Sh-Sa E',edges:[1,2,1,1],color:'#5a9ab5',w:1},
  {name:'Sh-Sa S',edges:[1,1,2,1],color:'#5a9ab5',w:1},{name:'Sh-Sa W',edges:[1,1,1,2],color:'#5a9ab5',w:1},
  {name:'Sa-Gr N',edges:[3,2,2,2],color:'#8aac55',w:1},{name:'Sa-Gr E',edges:[2,3,2,2],color:'#8aac55',w:1},
  {name:'Sa-Gr S',edges:[2,2,3,2],color:'#8aac55',w:1},{name:'Sa-Gr W',edges:[2,2,2,3],color:'#8aac55',w:1},
  {name:'Gr-Fo N',edges:[4,3,3,3],color:'#2d7a33',w:1},{name:'Gr-Fo E',edges:[3,4,3,3],color:'#2d7a33',w:1},
  {name:'Gr-Fo S',edges:[3,3,4,3],color:'#2d7a33',w:1},{name:'Gr-Fo W',edges:[3,3,3,4],color:'#2d7a33',w:1},
  {name:'Fo-Mt N',edges:[5,4,4,4],color:'#4a6a4a',w:0.8},{name:'Fo-Mt E',edges:[4,5,4,4],color:'#4a6a4a',w:0.8},
  {name:'Fo-Mt S',edges:[4,4,5,4],color:'#4a6a4a',w:0.8},{name:'Fo-Mt W',edges:[4,4,4,5],color:'#4a6a4a',w:0.8},
  {name:'Mt-Sn N',edges:[6,5,5,5],color:'#9a9a9a',w:0.6},{name:'Mt-Sn E',edges:[5,6,5,5],color:'#9a9a9a',w:0.6},
  {name:'Mt-Sn S',edges:[5,5,6,5],color:'#9a9a9a',w:0.6},{name:'Mt-Sn W',edges:[5,5,5,6],color:'#9a9a9a',w:0.6},
];
const DIRS=[[0,-1],[1,0],[0,1],[-1,0]];
const EP=[[2,0],[3,1],[0,2],[1,3]];
const GS=12;let cols,rows,grid,done,collapsed;
function canAdj(a,b,d){return B[a].edges[EP[d][0]]===B[b].edges[EP[d][1]]}
function init(){
  cols=Math.floor((W-20)/GS);rows=Math.floor((H-50)/GS);
  grid=Array.from({length:cols*rows},()=>({opts:[...Array(B.length).keys()],tile:-1}));
  done=false;collapsed=0;
}
init();
function propagate(idx){
  const stack=[idx];const vis=new Set();
  while(stack.length){
    const cur=stack.pop();if(vis.has(cur))continue;vis.add(cur);
    const cx=cur%cols,cy=cur/cols|0;
    for(let d=0;d<4;d++){
      const nx=cx+DIRS[d][0],ny=cy+DIRS[d][1];
      if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
      const ni=ny*cols+nx;const nc=grid[ni];
      if(nc.tile>=0)continue;
      const before=nc.opts.length;
      nc.opts=nc.opts.filter(t=>grid[cur].opts.some(ct=>canAdj(ct,t,d)));
      if(nc.opts.length===0){return false}
      if(nc.opts.length===1){nc.tile=nc.opts[0];collapsed++}
      if(nc.opts.length<before)stack.push(ni);
    }
  }
  return true;
}
function step(){
  if(done)return;
  let minE=999,minI=-1;
  for(let i=0;i<grid.length;i++){if(grid[i].tile>=0)continue;const e=grid[i].opts.length+Math.random()*0.1;if(e<minE){minE=e;minI=i}}
  if(minI<0){done=true;return}
  const cell=grid[minI];
  const ws=cell.opts.map(t=>B[t].w);const tot=ws.reduce((a,b)=>a+b,0);
  let r=Math.random()*tot;for(let i=0;i<cell.opts.length;i++){r-=ws[i];if(r<=0){cell.tile=cell.opts[i];cell.opts=[cell.opts[i]];collapsed++;break}}
  if(!propagate(minI)){done=true}
}
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='14px monospace';
  x.fillText('WFC Terrain — '+collapsed+'/'+cols*rows+(done?' — Click to regenerate':''),10,18);
  const ox=(W-cols*GS)/2,oy=30;
  for(let i=0;i<grid.length;i++){
    const gx=i%cols,gy=i/cols|0;
    if(grid[i].tile>=0){x.fillStyle=B[grid[i].tile].color}
    else{x.fillStyle='#1a1a2e'}
    x.fillRect(ox+gx*GS,oy+gy*GS,GS-1,GS-1);
  }
  if(!done)for(let i=0;i<10;i++)step();
  requestAnimationFrame(draw);
}
c.addEventListener('click',init);
draw();
</script></body></html>

4. City Block Generator

Urban layouts are a perfect fit for WFC. Define tiles for roads, intersections, buildings, parks, and empty lots, with rules like "roads must connect" and "buildings only appear next to roads." The algorithm generates coherent city grids with connected road networks and properly placed buildings. Each click builds a new city.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const R=1,E=0,B=2,P=3;
const T=[
  {name:'Empty',e:[E,E,E,E],w:2,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s)}},
  {name:'Road H',e:[E,R,E,R],w:2,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px,py+s*.3,s,s*.4);x.strokeStyle='#aa3';x.setLineDash([4,4]);x.beginPath();x.moveTo(px,py+s/2);x.lineTo(px+s,py+s/2);x.stroke();x.setLineDash([])}},
  {name:'Road V',e:[R,E,R,E],w:2,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px+s*.3,py,s*.4,s);x.strokeStyle='#aa3';x.setLineDash([4,4]);x.beginPath();x.moveTo(px+s/2,py);x.lineTo(px+s/2,py+s);x.stroke();x.setLineDash([])}},
  {name:'Cross',e:[R,R,R,R],w:0.5,draw:(px,py,s)=>{x.fillStyle='#555';x.fillRect(px,py,s,s);x.fillStyle='#666';x.fillRect(px+s*.3,py+s*.3,s*.4,s*.4)}},
  {name:'T N',e:[E,R,R,R],w:0.8,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px,py+s*.3,s,s*.7);x.fillRect(px+s*.3,py+s*.3,s*.4,s*.7)}},
  {name:'T S',e:[R,R,E,R],w:0.8,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px,py,s,s*.7);x.fillRect(px+s*.3,py,s*.4,s*.7)}},
  {name:'T E',e:[R,E,R,R],w:0.8,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px,py,s*.7,s);x.fillRect(px,py+s*.3,s*.7,s*.4)}},
  {name:'T W',e:[R,R,R,E],w:0.8,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px+s*.3,py,s*.7,s);x.fillRect(px+s*.3,py+s*.3,s*.7,s*.4)}},
  {name:'Bldg',e:[B,B,B,B],w:3,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);const h=s*.7+Math.random()*s*.2;x.fillStyle=['#4a6a8a','#7a5a4a','#5a7a5a','#8a7a4a'][Math.random()*4|0];x.fillRect(px+s*.1,py+s-h,s*.8,h);for(let wy=py+s-h+3;wy<py+s-3;wy+=6)for(let wx=px+s*.15;wx<px+s*.85;wx+=7){x.fillStyle='#ffd';x.fillRect(wx,wy,3,3)}}},
  {name:'Park',e:[P,P,P,P],w:1.5,draw:(px,py,s)=>{x.fillStyle='#1e4a1e';x.fillRect(px,py,s,s);x.fillStyle='#2d6b2d';for(let i=0;i<3;i++){const tx=px+s*.2+Math.random()*s*.6,ty=py+s*.3+Math.random()*s*.5;x.beginPath();x.arc(tx,ty,s*.12,0,Math.PI*2);x.fill()}}},
  {name:'Bldg-Rd N',e:[R,B,B,B],w:1,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px+s*.3,py,s*.4,s*.3);x.fillStyle='#5a6a7a';x.fillRect(px+s*.1,py+s*.35,s*.8,s*.6)}},
  {name:'Bldg-Rd S',e:[B,B,R,B],w:1,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px+s*.3,py+s*.7,s*.4,s*.3);x.fillStyle='#5a6a7a';x.fillRect(px+s*.1,py+s*.05,s*.8,s*.6)}},
  {name:'Bldg-Rd E',e:[B,R,B,B],w:1,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px+s*.7,py+s*.3,s*.3,s*.4);x.fillStyle='#5a6a7a';x.fillRect(px+s*.05,py+s*.1,s*.6,s*.8)}},
  {name:'Bldg-Rd W',e:[B,B,B,R],w:1,draw:(px,py,s)=>{x.fillStyle='#2a2a2a';x.fillRect(px,py,s,s);x.fillStyle='#555';x.fillRect(px,py+s*.3,s*.3,s*.4);x.fillStyle='#5a6a7a';x.fillRect(px+s*.35,py+s*.1,s*.6,s*.8)}},
];
const DIRS=[[0,-1],[1,0],[0,1],[-1,0]],EP=[[2,0],[3,1],[0,2],[1,3]];
const GS=36;let cols,rows,grid,done,collapsed;
function canA(a,b,d){return T[a].e[EP[d][0]]===T[b].e[EP[d][1]]}
function init(){
  cols=Math.floor((W-20)/GS);rows=Math.floor((H-50)/GS);
  grid=Array.from({length:cols*rows},()=>({opts:[...Array(T.length).keys()],tile:-1}));
  done=false;collapsed=0;
}
init();
function propagate(idx){
  const stack=[idx];const vis=new Set();
  while(stack.length){const cur=stack.pop();if(vis.has(cur))continue;vis.add(cur);const cx=cur%cols,cy=cur/cols|0;
  for(let d=0;d<4;d++){const nx=cx+DIRS[d][0],ny=cy+DIRS[d][1];if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
  const ni=ny*cols+nx,nc=grid[ni];if(nc.tile>=0)continue;const bf=nc.opts.length;
  nc.opts=nc.opts.filter(t=>grid[cur].opts.some(ct=>canA(ct,t,d)));
  if(!nc.opts.length)return false;if(nc.opts.length===1){nc.tile=nc.opts[0];collapsed++}
  if(nc.opts.length<bf)stack.push(ni)}}return true;
}
function step(){
  if(done)return;let mE=999,mI=-1;
  for(let i=0;i<grid.length;i++){if(grid[i].tile>=0)continue;const e=grid[i].opts.length+Math.random()*0.1;if(e<mE){mE=e;mI=i}}
  if(mI<0){done=true;return}const cell=grid[mI];
  const ws=cell.opts.map(t=>T[t].w),tot=ws.reduce((a,b)=>a+b);
  let r=Math.random()*tot;for(let i=0;i<cell.opts.length;i++){r-=ws[i];if(r<=0){cell.tile=cell.opts[i];cell.opts=[cell.opts[i]];collapsed++;break}}
  if(!propagate(mI))done=true;
}
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='14px monospace';
  x.fillText('WFC City Blocks — Click to rebuild',10,18);
  const ox=(W-cols*GS)/2,oy=30;
  for(let i=0;i<grid.length;i++){
    const gx=i%cols,gy=i/cols|0,px=ox+gx*GS,py=oy+gy*GS;
    if(grid[i].tile>=0){T[grid[i].tile].draw(px,py,GS-1)}
    else{x.fillStyle='#1a1a1a';x.fillRect(px,py,GS-1,GS-1)}
  }
  if(!done)for(let i=0;i<5;i++)step();
  requestAnimationFrame(draw);
}
c.addEventListener('click',init);draw();
</script></body></html>

5. Platformer Level Generator

WFC can generate side-scrolling platformer levels. Define tiles for sky, ground, platforms, ladders, and decorations. The constraint rules ensure ground is continuous, platforms float logically, and ladders connect different heights. Each generation produces a playable-looking level layout.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const S=0,G=1,P=2,L=3;
const TL=[
  {name:'Sky',e:[S,S,S,S],w:5,draw:(px,py,s)=>{const g=x.createLinearGradient(px,py,px,py+s);g.addColorStop(0,'#1a1a3e');g.addColorStop(1,'#2a2a5e');x.fillStyle=g;x.fillRect(px,py,s,s)}},
  {name:'Ground',e:[G,G,G,G],w:3,draw:(px,py,s)=>{x.fillStyle='#5a3a1a';x.fillRect(px,py,s,s);x.fillStyle='#6a4a2a';x.fillRect(px,py,s,4)}},
  {name:'Surface',e:[S,G,G,G],w:2,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='#4a8a2a';x.fillRect(px,py+s*.6,s,s*.4);x.fillStyle='#5a9a3a';x.fillRect(px,py+s*.55,s,5)}},
  {name:'Surf L',e:[S,G,S,S],w:1,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='#4a8a2a';x.fillRect(px+s*.3,py+s*.6,s*.7,s*.4);x.fillStyle='#5a9a3a';x.fillRect(px+s*.3,py+s*.55,s*.7,5)}},
  {name:'Surf R',e:[S,S,S,G],w:1,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='#4a8a2a';x.fillRect(px,py+s*.6,s*.7,s*.4);x.fillStyle='#5a9a3a';x.fillRect(px,py+s*.55,s*.7,5)}},
  {name:'Platform',e:[S,P,S,P],w:1.5,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='#8a7a5a';x.fillRect(px,py+s*.4,s,s*.15);x.fillStyle='#9a8a6a';x.fillRect(px,py+s*.38,s,3)}},
  {name:'Plat L',e:[S,P,S,S],w:0.8,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='#8a7a5a';x.fillRect(px+s*.2,py+s*.4,s*.8,s*.15);x.fillStyle='#6a5a3a';x.fillRect(px+s*.2,py+s*.4,4,s*.15)}},
  {name:'Plat R',e:[S,S,S,P],w:0.8,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='#8a7a5a';x.fillRect(px,py+s*.4,s*.8,s*.15);x.fillStyle='#6a5a3a';x.fillRect(px+s*.76,py+s*.4,4,s*.15)}},
  {name:'Ladder',e:[L,S,L,S],w:0.6,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='#8a6a3a';x.fillRect(px+s*.3,py,4,s);x.fillRect(px+s*.6,py,4,s);for(let ry=0;ry<s;ry+=8)x.fillRect(px+s*.3,py+ry,s*.34,2)}},
  {name:'Sky+Cloud',e:[S,S,S,S],w:1,draw:(px,py,s)=>{x.fillStyle='#1a1a3e';x.fillRect(px,py,s,s);x.fillStyle='rgba(255,255,255,0.15)';x.beginPath();x.arc(px+s*.5,py+s*.4,s*.2,0,Math.PI*2);x.arc(px+s*.3,py+s*.45,s*.15,0,Math.PI*2);x.arc(px+s*.7,py+s*.45,s*.15,0,Math.PI*2);x.fill()}},
  {name:'Deep',e:[G,G,G,G],w:2,draw:(px,py,s)=>{x.fillStyle='#3a2a0a';x.fillRect(px,py,s,s);for(let i=0;i<3;i++){x.fillStyle='#4a3a1a';x.fillRect(px+Math.random()*s*.7,py+Math.random()*s*.7,s*.2,s*.2)}}},
];
const DIRS=[[0,-1],[1,0],[0,1],[-1,0]],EP=[[2,0],[3,1],[0,2],[1,3]];
const GS=28;let cols,rows,grid,done,collapsed;
function canA(a,b,d){return TL[a].e[EP[d][0]]===TL[b].e[EP[d][1]]}
function init(){
  cols=Math.floor((W-20)/GS);rows=Math.floor((H-50)/GS);
  grid=Array.from({length:cols*rows},()=>({opts:[...Array(TL.length).keys()],tile:-1}));
  done=false;collapsed=0;
}
init();
function propagate(idx){
  const stack=[idx];const vis=new Set();
  while(stack.length){const cur=stack.pop();if(vis.has(cur))continue;vis.add(cur);const cx=cur%cols,cy=cur/cols|0;
  for(let d=0;d<4;d++){const nx=cx+DIRS[d][0],ny=cy+DIRS[d][1];if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
  const ni=ny*cols+nx,nc=grid[ni];if(nc.tile>=0)continue;const bf=nc.opts.length;
  nc.opts=nc.opts.filter(t=>grid[cur].opts.some(ct=>canA(ct,t,d)));
  if(!nc.opts.length)return false;if(nc.opts.length===1){nc.tile=nc.opts[0];collapsed++}
  if(nc.opts.length<bf)stack.push(ni)}}return true;
}
function step(){
  if(done)return;let mE=999,mI=-1;
  for(let i=0;i<grid.length;i++){if(grid[i].tile>=0)continue;const e=grid[i].opts.length+Math.random()*0.1;if(e<mE){mE=e;mI=i}}
  if(mI<0){done=true;return}const cell=grid[mI];
  const ws=cell.opts.map(t=>TL[t].w),tot=ws.reduce((a,b)=>a+b);
  let r=Math.random()*tot;for(let i=0;i<cell.opts.length;i++){r-=ws[i];if(r<=0){cell.tile=cell.opts[i];cell.opts=[cell.opts[i]];collapsed++;break}}
  if(!propagate(mI))done=true;
}
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='14px monospace';
  x.fillText('WFC Platformer Level — Click to regenerate',10,18);
  const ox=(W-cols*GS)/2,oy=30;
  for(let i=0;i<grid.length;i++){
    const gx=i%cols,gy=i/cols|0,px=ox+gx*GS,py=oy+gy*GS;
    if(grid[i].tile>=0){TL[grid[i].tile].draw(px,py,GS-1)}
    else{x.fillStyle='#0a0a1e';x.fillRect(px,py,GS-1,GS-1)}
  }
  if(!done)for(let i=0;i<8;i++)step();
  requestAnimationFrame(draw);
}
c.addEventListener('click',init);draw();
</script></body></html>

6. Pipe Network

A classic WFC application: generating connected pipe networks. Each tile is a pipe segment (straight, corner, T-junction, cross, or cap), and the constraint is simple — pipe openings must match. Open edges connect to open edges, closed to closed. The result is a satisfying network of interconnected plumbing that always makes sense.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const O=1,C=0;
const T=[
  {name:'Empty',e:[C,C,C,C],w:0.5,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s)}},
  {name:'H Pipe',e:[C,O,C,O],w:2,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px,py+s*.35,s,s*.3);x.fillStyle='#5aaacc';x.fillRect(px,py+s*.38,s,s*.04)}},
  {name:'V Pipe',e:[O,C,O,C],w:2,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py,s*.3,s);x.fillStyle='#5aaacc';x.fillRect(px+s*.38,py,s*.04,s)}},
  {name:'Cross',e:[O,O,O,O],w:0.8,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px,py+s*.35,s,s*.3);x.fillRect(px+s*.35,py,s*.3,s);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'NE',e:[O,O,C,C],w:1.5,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py,s*.3,s*.65);x.fillRect(px+s*.35,py+s*.35,s*.65,s*.3);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'SE',e:[C,O,O,C],w:1.5,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.65);x.fillRect(px+s*.35,py+s*.35,s*.65,s*.3);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'SW',e:[C,C,O,O],w:1.5,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.65);x.fillRect(px,py+s*.35,s*.65,s*.3);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'NW',e:[O,C,C,O],w:1.5,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py,s*.3,s*.65);x.fillRect(px,py+s*.35,s*.65,s*.3);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'T N',e:[O,O,C,O],w:0.8,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px,py+s*.35,s,s*.3);x.fillRect(px+s*.35,py,s*.3,s*.35);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'T S',e:[C,O,O,O],w:0.8,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px,py+s*.35,s,s*.3);x.fillRect(px+s*.35,py+s*.65,s*.3,s*.35);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'T E',e:[O,O,O,C],w:0.8,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py,s*.3,s);x.fillRect(px+s*.65,py+s*.35,s*.35,s*.3);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'T W',e:[O,C,O,O],w:0.8,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py,s*.3,s);x.fillRect(px,py+s*.35,s*.35,s*.3);x.fillStyle='#6abace';x.fillRect(px+s*.35,py+s*.35,s*.3,s*.3)}},
  {name:'Cap N',e:[O,C,C,C],w:0.5,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py,s*.3,s*.5);x.fillStyle='#cc5a3a';x.beginPath();x.arc(px+s*.5,py+s*.5,s*.15,0,Math.PI*2);x.fill()}},
  {name:'Cap S',e:[C,C,O,C],w:0.5,draw:(px,py,s)=>{x.fillStyle='#1a1a2e';x.fillRect(px,py,s,s);x.fillStyle='#4a8aaa';x.fillRect(px+s*.35,py+s*.5,s*.3,s*.5);x.fillStyle='#cc5a3a';x.beginPath();x.arc(px+s*.5,py+s*.5,s*.15,0,Math.PI*2);x.fill()}},
];
const DIRS=[[0,-1],[1,0],[0,1],[-1,0]],EP=[[2,0],[3,1],[0,2],[1,3]];
const GS=32;let cols,rows,grid,done,collapsed;
function canA(a,b,d){return T[a].e[EP[d][0]]===T[b].e[EP[d][1]]}
function init(){
  cols=Math.floor((W-20)/GS);rows=Math.floor((H-50)/GS);
  grid=Array.from({length:cols*rows},()=>({opts:[...Array(T.length).keys()],tile:-1}));done=false;collapsed=0;
}
init();
function propagate(idx){
  const stack=[idx];const vis=new Set();
  while(stack.length){const cur=stack.pop();if(vis.has(cur))continue;vis.add(cur);const cx=cur%cols,cy=cur/cols|0;
  for(let d=0;d<4;d++){const nx=cx+DIRS[d][0],ny=cy+DIRS[d][1];if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
  const ni=ny*cols+nx,nc=grid[ni];if(nc.tile>=0)continue;const bf=nc.opts.length;
  nc.opts=nc.opts.filter(t=>grid[cur].opts.some(ct=>canA(ct,t,d)));
  if(!nc.opts.length)return false;if(nc.opts.length===1){nc.tile=nc.opts[0];collapsed++}
  if(nc.opts.length<bf)stack.push(ni)}}return true;
}
function step(){
  if(done)return;let mE=999,mI=-1;
  for(let i=0;i<grid.length;i++){if(grid[i].tile>=0)continue;const e=grid[i].opts.length+Math.random()*0.1;if(e<mE){mE=e;mI=i}}
  if(mI<0){done=true;return}const cell=grid[mI];
  const ws=cell.opts.map(t=>T[t].w),tot=ws.reduce((a,b)=>a+b);
  let r=Math.random()*tot;for(let i=0;i<cell.opts.length;i++){r-=ws[i];if(r<=0){cell.tile=cell.opts[i];cell.opts=[cell.opts[i]];collapsed++;break}}
  if(!propagate(mI))done=true;
}
let flow=0;
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='14px monospace';
  x.fillText('WFC Pipe Network — Click to regenerate',10,18);
  const ox=(W-cols*GS)/2,oy=30;
  for(let i=0;i<grid.length;i++){
    const gx=i%cols,gy=i/cols|0,px=ox+gx*GS,py=oy+gy*GS;
    if(grid[i].tile>=0){T[grid[i].tile].draw(px,py,GS-1)}
    else{x.fillStyle='#0a0a1e';x.fillRect(px,py,GS-1,GS-1);
      x.fillStyle='#2a2a4e';x.font='9px monospace';x.textAlign='center';
      x.fillText(grid[i].opts.length,px+GS/2-0.5,py+GS/2+3);x.textAlign='left'}
  }
  if(!done)for(let i=0;i<6;i++)step();
  flow+=0.02;requestAnimationFrame(draw);
}
c.addEventListener('click',init);draw();
</script></body></html>

7. Pixel Art Pattern Generator

WFC can generate repeating pixel art patterns from tiny sample tiles. This example uses a minimal set of colored tiles with carefully designed edges to produce intricate, fabric-like patterns reminiscent of cross-stitch or mosaic art. The small tile size (4x4 pixels each) means thousands of tiles on screen, creating mesmerizing large-scale patterns from simple local rules.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const palettes=[
  ['#1a1a2e','#16213e','#0f3460','#533483','#e94560'],
  ['#2d132c','#801336','#c72c41','#ee4540','#f5b461'],
  ['#0b0c10','#1f6f8b','#99e1d9','#f0f7ee','#e6b89c'],
  ['#222831','#393e46','#00adb5','#eeeeee','#ff5722'],
];
let pal=palettes[0];
const GS=6;let cols,rows,grid,done,collapsed;
function mkTiles(){
  const T=[];
  for(let i=0;i<pal.length;i++){
    T.push({e:[i,i,i,i],color:pal[i],w:2});
    for(let j=0;j<pal.length;j++){
      if(i!==j&&Math.abs(i-j)<=1){
        T.push({e:[i,j,i,j],color:pal[i],color2:pal[j],w:1});
        T.push({e:[j,i,j,i],color:pal[j],color2:pal[i],w:1});
      }
    }
  }
  return T;
}
let T=mkTiles();
const DIRS=[[0,-1],[1,0],[0,1],[-1,0]],EP=[[2,0],[3,1],[0,2],[1,3]];
function canA(a,b,d){return T[a].e[EP[d][0]]===T[b].e[EP[d][1]]}
function init(){
  pal=palettes[Math.random()*palettes.length|0];T=mkTiles();
  cols=Math.floor((W-10)/GS);rows=Math.floor((H-40)/GS);
  grid=Array.from({length:cols*rows},()=>({opts:[...Array(T.length).keys()],tile:-1}));done=false;collapsed=0;
}
init();
function propagate(idx){
  const stack=[idx];const vis=new Set();
  while(stack.length){const cur=stack.pop();if(vis.has(cur))continue;vis.add(cur);const cx=cur%cols,cy=cur/cols|0;
  for(let d=0;d<4;d++){const nx=cx+DIRS[d][0],ny=cy+DIRS[d][1];if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
  const ni=ny*cols+nx,nc=grid[ni];if(nc.tile>=0)continue;const bf=nc.opts.length;
  nc.opts=nc.opts.filter(t=>grid[cur].opts.some(ct=>canA(ct,t,d)));
  if(!nc.opts.length)return false;if(nc.opts.length===1){nc.tile=nc.opts[0];collapsed++}
  if(nc.opts.length<bf)stack.push(ni)}}return true;
}
function step(){
  if(done)return;let mE=999,mI=-1;
  for(let i=0;i<grid.length;i++){if(grid[i].tile>=0)continue;const e=grid[i].opts.length+Math.random()*0.1;if(e<mE){mE=e;mI=i}}
  if(mI<0){done=true;return}const cell=grid[mI];
  const ws=cell.opts.map(t=>T[t].w),tot=ws.reduce((a,b)=>a+b);
  let r=Math.random()*tot;for(let i=0;i<cell.opts.length;i++){r-=ws[i];if(r<=0){cell.tile=cell.opts[i];cell.opts=[cell.opts[i]];collapsed++;break}}
  if(!propagate(mI))done=true;
}
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='14px monospace';
  x.fillText('WFC Pixel Art Patterns — Click for new palette + pattern',10,18);
  const ox=(W-cols*GS)/2,oy=30;
  for(let i=0;i<grid.length;i++){
    const gx=i%cols,gy=i/cols|0,px=ox+gx*GS,py=oy+gy*GS;
    if(grid[i].tile>=0){
      const t=T[grid[i].tile];
      x.fillStyle=t.color;x.fillRect(px,py,GS,GS);
      if(t.color2){
        x.fillStyle=t.color2;
        if(t.e[1]!==t.e[0])x.fillRect(px+GS/2,py,GS/2,GS);
        else x.fillRect(px,py+GS/2,GS,GS/2);
      }
    } else {x.fillStyle='#0a0a0a';x.fillRect(px,py,GS,GS)}
  }
  if(!done)for(let i=0;i<30;i++)step();
  requestAnimationFrame(draw);
}
c.addEventListener('click',init);draw();
</script></body></html>

8. Interactive WFC Editor

The ultimate WFC playground: paint your own tiles, define adjacency rules by drawing, and watch the algorithm fill the canvas. Left-click to cycle through tile types, right-click to lock a cell (forcing that tile), then press Space to run WFC and fill the rest. Press R to reset. This lets you experiment with constraint propagation in real time — place a few tiles and watch how they constrain the entire grid.

<!DOCTYPE html><html><body style="margin:0;background:#111;overflow:hidden">
<canvas id="c"></canvas>
<script>
const c=document.getElementById('c'),x=c.getContext('2d');
let W,H;function resize(){W=c.width=innerWidth;H=c.height=innerHeight}resize();
addEventListener('resize',resize);
const PALETTE=['#2d5a1e','#1a5276','#d4b96a','#c44','#666','#8a5ac4','#e8a030','#e8e8e8'];
const NAMES=['Grass','Water','Sand','Lava','Stone','Crystal','Gold','Snow'];
const GS=28;let cols,rows,placed,grid,running=false,done=false,collapsed=0;
const DIRS=[[0,-1],[1,0],[0,1],[-1,0]],EP=[[2,0],[3,1],[0,2],[1,3]];
function init(){
  cols=Math.floor((W-20)/GS);rows=Math.floor((H-80)/GS);
  placed=new Int8Array(cols*rows).fill(-1);
  grid=null;running=false;done=false;collapsed=0;
}
init();
function buildTilesFromPlaced(){
  const adj=new Map();
  for(let y=0;y<rows;y++)for(let xp=0;xp<cols;xp++){
    const i=y*cols+xp;const t=placed[i];if(t<0)continue;
    if(!adj.has(t))adj.set(t,[[],[],[],[]]);
    for(let d=0;d<4;d++){
      const nx=xp+DIRS[d][0],ny=y+DIRS[d][1];
      if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
      const nt=placed[ny*cols+nx];if(nt<0)continue;
      if(!adj.get(t)[d].includes(nt))adj.get(t)[d].push(nt);
    }
  }
  if(adj.size<2){
    for(let i=0;i<PALETTE.length;i++){
      if(!adj.has(i))adj.set(i,[[],[],[],[]]);
      for(let d=0;d<4;d++){
        for(let j=0;j<PALETTE.length;j++){
          if(Math.abs(i-j)<=2&&!adj.get(i)[d].includes(j))adj.get(i)[d].push(j);
        }
      }
    }
  }
  return adj;
}
function startWFC(){
  const adj=buildTilesFromPlaced();
  const types=[...adj.keys()];
  grid=Array.from({length:cols*rows},(_,i)=>{
    if(placed[i]>=0)return{opts:[placed[i]],tile:placed[i]};
    return{opts:[...types],tile:-1};
  });
  collapsed=grid.filter(g=>g.tile>=0).length;running=true;done=false;
  for(let i=0;i<grid.length;i++){if(grid[i].tile>=0)propagateWFC(i,adj,types)}
  window._adj=adj;window._types=types;
}
function propagateWFC(idx,adj,types){
  const stack=[idx];const vis=new Set();
  while(stack.length){
    const cur=stack.pop();if(vis.has(cur))continue;vis.add(cur);const cx=cur%cols,cy=cur/cols|0;
    for(let d=0;d<4;d++){
      const nx=cx+DIRS[d][0],ny=cy+DIRS[d][1];if(nx<0||nx>=cols||ny<0||ny>=rows)continue;
      const ni=ny*cols+nx,nc=grid[ni];if(nc.tile>=0)continue;const bf=nc.opts.length;
      nc.opts=nc.opts.filter(t=>{
        return grid[cur].opts.some(ct=>{
          const a=adj.get(ct);return a&&a[d]&&a[d].includes(t);
        });
      });
      if(!nc.opts.length){done=true;return}
      if(nc.opts.length===1){nc.tile=nc.opts[0];collapsed++}
      if(nc.opts.length<bf)stack.push(ni);
    }
  }
}
function stepWFC(){
  if(!running||done)return;
  const adj=window._adj;let mE=999,mI=-1;
  for(let i=0;i<grid.length;i++){if(grid[i].tile>=0)continue;const e=grid[i].opts.length+Math.random()*0.1;if(e<mE){mE=e;mI=i}}
  if(mI<0){done=true;return}
  const cell=grid[mI];const pick=cell.opts[Math.random()*cell.opts.length|0];
  cell.tile=pick;cell.opts=[pick];collapsed++;
  propagateWFC(mI,adj,window._types);
}
c.addEventListener('mousedown',e=>{
  if(running)return;
  const r=c.getBoundingClientRect();const mx=e.clientX-r.left,my=e.clientY-r.top;
  const ox=(W-cols*GS)/2,oy=50;
  const gx=Math.floor((mx-ox)/GS),gy=Math.floor((my-oy)/GS);
  if(gx<0||gx>=cols||gy<0||gy>=rows)return;
  const i=gy*cols+gx;
  if(e.button===2){placed[i]=placed[i]>=0?-1:0;e.preventDefault();return}
  placed[i]=(placed[i]+2)%(PALETTE.length+1)-1;
});
c.addEventListener('contextmenu',e=>e.preventDefault());
addEventListener('keydown',e=>{
  if(e.code==='Space'&&!running){e.preventDefault();startWFC()}
  if(e.code==='KeyR'){init()}
});
function draw(){
  x.fillStyle='#111';x.fillRect(0,0,W,H);
  x.fillStyle='#eee';x.font='14px monospace';
  x.fillText('WFC Editor — Click: place tiles | Space: run WFC | R: reset'+(running?' | '+collapsed+'/'+(cols*rows):''),10,18);
  x.font='11px monospace';x.fillStyle='#888';
  x.fillText('Paint a few tiles to define adjacency rules, then press Space to fill the grid',10,36);
  const ox=(W-cols*GS)/2,oy=50;
  for(let i=0;i<grid?.length||i<cols*rows;i++){
    const gx=i%cols,gy=i/cols|0,px=ox+gx*GS,py=oy+gy*GS;
    if(running&&grid){
      if(grid[i].tile>=0){x.fillStyle=PALETTE[grid[i].tile];x.fillRect(px,py,GS-1,GS-1)}
      else{const n=grid[i].opts.length;x.fillStyle=`hsl(240,30%,${10+n*3}%)`;x.fillRect(px,py,GS-1,GS-1)}
    } else {
      if(placed[i]>=0){x.fillStyle=PALETTE[placed[i]];x.fillRect(px,py,GS-1,GS-1);
        x.strokeStyle='#fff3';x.strokeRect(px,py,GS-1,GS-1)}
      else{x.fillStyle='#1a1a2e';x.fillRect(px,py,GS-1,GS-1)}
    }
  }
  if(!running){
    const py=oy+rows*GS+10;x.fillStyle='#eee';x.font='11px monospace';x.fillText('Palette:',10,py+12);
    for(let i=0;i<PALETTE.length;i++){x.fillStyle=PALETTE[i];x.fillRect(70+i*30,py,24,18);
      x.fillStyle='#eee';x.font='9px monospace';x.fillText(NAMES[i],70+i*30,py+28)}
  }
  if(running&&!done)for(let i=0;i<4;i++)stepWFC();
  requestAnimationFrame(draw);
}
draw();
</script></body></html>

The WFC Algorithm in Depth

Let's formalize what's happening across all these examples. The Wave Function Collapse algorithm has three core operations:

Observation (Collapse)

Find the uncollapsed cell with the lowest Shannon entropy: H = -Σ(wᵢ·log(wᵢ)) where wᵢ are the normalized weights of remaining options. In practice, counting remaining options with a small random tiebreaker works nearly as well and is much faster. Collapse this cell to a single tile chosen by weighted random selection.

Propagation

After collapsing a cell, propagate constraints outward. For each neighbor, remove any tile options that are incompatible with the collapsed cell. If a neighbor loses options, propagate from it too. This cascade can resolve large portions of the grid from a single collapse. Use a stack (not recursion) to avoid stack overflow on large grids.

Contradiction Handling

When propagation empties a cell's option set, we have a contradiction. Three strategies: (1) Restart — simple but wasteful. (2) Backtracking — undo the last collapse and try a different tile. (3) Weighted initialization — bias tile weights to reduce contradiction probability. For creative coding, restart is usually fine since generation is fast.

From Tiles to Textures: Overlapping WFC

The examples above use the "simple tiled" variant of WFC, where you define tiles and adjacency rules explicitly. The original WFC algorithm by Maxim Gumin (2016) also includes an "overlapping" variant that learns constraints from a sample image. It extracts NxN patches, records their overlap frequencies, and generates new images that locally look like the sample. This is essentially texture synthesis — and it's remarkably effective at capturing the "style" of a source image.

Performance Considerations

WFC's performance depends on grid size, tile count, and constraint density. Key optimizations:

  • Arc consistency (AC-3) — The propagation step is essentially an AC-3 algorithm from constraint satisfaction. Use efficient data structures (bitsets for option sets, indexed adjacency lookups).
  • Priority queue — Instead of scanning all cells for minimum entropy, use a min-heap. This reduces observation from O(n) to O(log n).
  • Incremental entropy — Recalculate entropy only for cells that changed during propagation, not the entire grid.
  • WebWorker — For large grids (100x100+), run WFC in a Web Worker to avoid blocking the main thread.

When to Use WFC

WFC excels at generating locally coherent, globally diverse content from hand-authored rules. It's ideal for tile-based games, texture synthesis, architectural layouts, and any domain where you can express constraints as adjacency rules. It's less suitable for generation with global structure requirements (like "exactly one boss room" or "a river from north to south") — for those, combine WFC with higher-level planning algorithms.

The algorithm's beauty is in its simplicity: define local rules, get global coherence for free. That's the core insight of Wave Function Collapse, and it's why it's become one of the most popular procedural generation techniques in game development and creative coding.

Related articles

Procedural Generation: How to Create Infinite Worlds With Code
A complete guide to procedural generation — the algorithms behind infinite game worlds, generative art, and adaptive content. Covers noise-based terrain, wave function collapse, cellular automata, BSP dungeons, L-systems, Poisson disc sampling, random walks, and marching squares. 8 working code examples.
Tessellation Art: How to Create Mesmerizing Tiling Patterns With Code
Learn to create tessellation art with JavaScript and Canvas. 8 interactive examples: regular tilings, Escher-style transformations, Penrose tilings, hyperbolic tessellations, Voronoi cells, Islamic star patterns, aperiodic monotiles, and animated morphing tiles.
Maze Generation: How to Create Perfect Labyrinths With Code
Learn to generate mazes algorithmically with JavaScript and Canvas. 8 interactive examples: recursive backtracker, Kruskal's algorithm, Prim's algorithm, Eller's row-by-row method, recursive division, growing tree, Wilson's uniform spanning tree, and animated maze solver with A* pathfinding.
Cellular Automata: How to Create Emergent Art From Simple Rules With Code
Learn how cellular automata like Conway's Game of Life, Rule 30, and Langton's Ant create stunning emergent patterns from minimal rules. 8 interactive code examples using HTML Canvas.