30:T15c4,{ if (navigator.userAgent.match('HeadlessChrome')) return html``; return md`Forked from Tom MacWright's [Diffusion-limited aggregation](https://beta.observablehq.com/@tmcw/diffusion-limited-aggregation), with speedup to the rendering from Fabian Iwand's [fork](https://beta.observablehq.com/d/6476797a385e8d05). *Tom MacWright's original description:* Based heavily on [Michael Drzal’s bl.ock](https://bl.ocks.org/xmichaelx/39fa023f9ce1fb82d5c0). I made it because [Michael Fogleman](https://github.com/fogleman/dlaf) wrote an implementation recently that’s probably 1,000 times faster than this one. And Michael Fogleman also pointed to [dla-nd](https://github.com/markstock/dla-nd) by [Mark Stock](http://markjstock.org/dla-nd/) which is also so cool. Anyway, I made it kind of pretty and fast but otherwise didn’t invent anything. Tweak those sliders. *New stuff:* The large-scale structure of DLA clusters is known to be quite sensitive to anisotropy in the system. For instance, if the particles are constrained to a grid, there's a bias towards the grid directions in large DLA clusters (see e.g. [this paper of Meakin's](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.33.3371)). [Fogleman's very pretty images in [his twitter thread](https://twitter.com/FogleBird/status/1093352480950439936) are made with an "off-lattice" DLA which is immune to this effect.] If you're trying to use DLA to model some serious physics like dust bunny formation then this kind of thing can make your life hard, but in this notebook we **exploit** this sensitivity by varying the attachment rules to generate different flavors of DLA. To be more precise, recall that in the original notebook, each particle in the system undergoes a random walk and becomes "stuck" and joins the cluster when it sits next to a stuck particle. Visually, the particle becomes stuck if there are any stuck particles in the black boxes in this diagram: (the green square is the position of the wandering particle). To go beyond this, we can keep track of the **number** of stuck particles that are "nearest-neighbors" on the grid: (\`#NN\`) and the number of stuck particles that are "next-nearest-neighbors" on the grid: (\`#NNN\`). Using this data, we can explore different attachment rules which depend on the values of \`#NN\` and \`#NNN\` (e.g. we can have particles get stuck only if \`#NN\` is 1 or 3). To make things even more interesting, we can tune the importance of various rules by making the rules probabilistic (that is, particles satisfying the conditions only get stuck with some fixed frequency). [So the "CA" in the title stands for "[cellular automata](https://en.wikipedia.org/wiki/Cellular_automaton)", as rules depending on \`#NN\` and \`#NNN\` are common in those systems.] I've included a few preset rules below; try switching them while the cluster is growing and watching the different geometries build off each other! If you're feeling really adventurous you can also try tweaking them or creating your own (more detailed instructions [below](#rulesFormat)). I've also [implemented](#updateSingleParticleFast) an algorithm inspired by Fogleman's ["dlaf"](https://github.com/fogleman/dlaf), where particles are added **one at a time** by repeatedly jumping ${tex`d_{stuck}`} in a random direction until stuck, where ${tex`d_{stuck}`} is the distance to the closest stuck particle (for this, I use [d3-quadtree](https://github.com/d3/d3-quadtree)). For larger box sizes, the dlaf-inspired algorithm seems to finish more quickly, however the clusters that grow seem to be different from those created by the original algorithm. One visual change is that particles are colored differently depending on the (even-odd) parity of their coordinate sums *x+y*. In the original algorithm, particles make steps of ${tex`(\pm1,\pm1)`}, which preserves this parity, so there are effectively two distinct populations of particles (they move like black and white bishops on a chessboard). In the dlaf-inspired algorithm, particles make bigger jumps, so they change their parities frequently. However, with either algorithm, one can design growth rules where the two colors segregate by varying the rules carefully (see e.g. the "two-color moss").` }31:T753,viewof clusterSize = { const {run, passes, dark, hue, contrast} = object; const ctx = DOM.context2d(width, height, 1); ctx.canvas.style.imageRendering = "pixelated"; ctx.canvas.style.width = "100%"; ctx.fillStyle = "#000"; const imageData = ctx.createImageData(width, height); const values = new Uint32Array(imageData.data.buffer); const vEmpty = hsl2Value(0, 0, 0); const vFloat = hsl2Value(hue, 1, dark ? .2 : contrast); const vStuck = hsl2Value(hue, 1, dark ? contrast : .2); const vFloat2 = hsl2Value((hue - 120) % 360, 1, dark ? .2 : contrast); const vStuck2 = hsl2Value((hue - 120) % 360, 1, dark ? contrast : .2); let j = 0; while (particles.stuck.some(d => d===0) && run) { if (fast.fast) { for (let i = 0; i < count; i++) { while (particles.stuck[i] === 0) { j++; updateSingleParticleFast(i); if (j % (250*passes) === 0) { render(ctx,particles, {imageData, values, vEmpty, vStuck, vFloat, vStuck2, vFloat2}); ctx.canvas.value = particles.stuck.reduce((a,b) => a+b, 0); yield ctx.canvas; j = 0; } } if (!run) break; } } else { for (let pass = 0; pass < passes; pass++) { for (let i = 0; i < count; i++) { if (particles.stuck[i] === 0) { updateSingleParticle(i); } if (!run) break; } if (!run) break; } } if (!run) break; render(ctx,particles, {imageData, values, vEmpty, vStuck, vFloat, vStuck2, vFloat2}); ctx.canvas.value = particles.stuck.reduce((a,b) => a+b,0); yield ctx.canvas; } render(ctx,particles, {imageData, values, vEmpty, vStuck, vFloat, vStuck2, vFloat2}); ctx.canvas.value = particles.stuck.reduce((a,b) => a+b,0); yield ctx.canvas; }32:Ta69,viewof object = { let edited = false; const f = form(html`

Run (uncheck to stop)

step(s) per frame (speed)

Hue

Contrast

Cluster is bright (uncheck to make free particles bright)

${ruleArr.map(({name},i) => ` ${name}
`)} custom

<i>custom rule</i></label></div>
</form>`);
  const updatePasses = () => f.passes.nextSibling.nextSibling.innerHTML = `<code>${f.passes.value}</code> <a href="#passNote">step(s)</a> per frame`;
  f.passes.oninput = updatePasses;
  const updateHue = () => f.hue.nextSibling.nextSibling.innerHTML = `<code>${f.hue.value}</code> Hue`;
  f.hue.oninput = updateHue;
  const updateContrast = () => f.contrast.nextSibling.nextSibling.innerHTML = `<code>${f.contrast.value}</code> Contrast`;
  f.contrast.oninput = updateContrast;
  
  function ruleText(rule) {
    let rA;
    if (rule < ruleArr.length) rA = ruleArr[+rule].rule;
    else if (testCustom(f.custom.value)) rA = JSON.parse(f.custom.value);
    else
      return '<span style="color:red">invalid custom rule</span>';
    return rA.map(
      ({numNN,numNNN,p}) => 
      `(${[numNN !== undefined ? `#NN ∈ {${numNN}}` : '',
           numNNN !== undefined ? `#NNN ∈ {${numNNN}}` : '',
           p !== undefined ? `probability ${p}` : '']
      .filter(s => s.length>0).join(' && ')})`
    ).join(' || ');
  }
  
  const currRules = f.querySelector('#currRules');
  const updateRules = () => {
    currRules.innerHTML = `Current ruleset:<br> <code>${ruleText(f.value.rules)}</code>`;
    if (f.value.rules < ruleArr.length) {
      if (!edited)
        f.custom.value = JSON.stringify(ruleArr[+f.value.rules].rule);
      f.custom.disabled = true;
    } else {
      edited = true;
      f.custom.disabled = false;
    }
  };
  f.addEventListener('input', updateRules);
  
  updatePasses(); updateHue(); updateContrast(); updateRules();
  
  return f;
}33:T5e0,rulesFormat = md` ## Rule format
Rules are encoded in JSON as follows. A rule consists of an array of clause objects. Each clause object may have the keys \`"numNN"\`, \`"numNNN"\` or \`"p"\` and represents a logical condition:
- \`"numNN"\` (if it exists) must be an array of numbers. This part of the clause will hold true if the number of stuck nearest neighbors (\`#NN\`) lies in \`"numNN"\` (if it exists).
- \`"numNNN"\` (if it exists) must be an array of numbers. This part of the clause will hold true if the number of stuck next-nearest neighbors (\`#NNN\`) lies in \`"numNNN"\` (if it exists).
- \`"p"\` (if it exists) should be a probability between 0 and 1. Each time the clause is checked, a random number is generated and if it is less than \`"p"\`, this part of the clause will hold true.

These conditions are logical-AND'd together to give a boolean result for the clause. Finally, the results for all the clauses are logical-OR'd together to give a result for the rule. If the final result is \`true\`, the particle is attached, otherwise, the particle will not be attached.

For example, if the rule array is \`[{"numNN":[1],"numNNN":[0]}]\`, particles can only attach themselves if they have exactly one stuck nearest-neighbor and zero stuck next-nearest-neighbors. A moment's thought should convince you that the cluster will be a single straight line. Another example is \`[{"p":0.05}]\`. In this case, particles will become stuck 5% of the time without regard for their neighbors.`34:[{"id":"496aa34d00b91c96cd341a19aa836b4c5381c4e8ced843ec0ddf7be368e56bc6b88a42b67853b604af0e80b94f576af1e0693ba8ef14ca6116a9eed7c2eb1d91","href":"https://static.observableusercontent.com/files/496aa34d00b91c96cd341a19aa836b4c5381c4e8ced843ec0ddf7be368e56bc6b88a42b67853b604af0e80b94f576af1e0693ba8ef14ca6116a9eed7c2eb1d91","name":"hsl-rgb-1.0.0.js","type":"application/javascript","lastModified":1588417259827.906,"size":1130}]
2e:{"title":"DLA + CA rules!","cells":[{"id":1067,"value":"md`# DLA + CA rules!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":0,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1195,"value":"{\n  return (object.run && clusterSize < fast.count) ? md`[Uncheck \"Run\"](#object) to enable Save button.` : DOM.download(await new Promise(resolve => viewof clusterSize.toBlob(resolve)), 'cluster.png', 'Save PNG');\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":341,"value":"md`${clusterSize} particles in the cluster (max ${fast.count}) and ${fast.count-clusterSize} free particles.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":179,"value":"viewof reset = html`<button>Reset</button>`","pinned":false,"hidden":false,"mode":"ojs"},{"id":590,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1247,"value":"passNote = md`If using dlaf, each step is 250 single-particle updates, if not, each step is an update pass through all particles.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":641,"value":"viewof fast = {\n  const f = form(html`<form>\n  ⚠️ Changing these options will trigger a reset ⚠️\n  <div><label><input name=\"fast\" type=\"checkbox\" checked> <b>use <a href=\"https://github.com/fogleman/dlaf\">dlaf</a>-inspired algorithm</b></label></div>\n  <div><label><input name=\"size\" type=\"range\" value=\"${navigator.userAgent.match('HeadlessChrome') ? 0.1 : 0.5}\" min=\"0.1\" max=\"1\" step=\"0.1\"> <i>size factor</i>  (smaller means lower resolution, more zoomed graphic)</label></div>\n  <div><label><input name=\"count\" type=\"range\" value=\"60000\" min=\"1000\" max=\"1000000\" step=\"1\"> <i>total particles</i> (values above 100k or so will be slow unless using dlaf)</label></div>\n</form>`);\n  const updateSize = () => f.size.nextSibling.nextSibling.innerHTML = `<code>${f.size.value}</code> size factor`;\n  f.size.oninput = updateSize;\n  const updateCount = () => f.count.nextSibling.nextSibling.innerHTML = `<code>${f.count.value}</code> total particles`;\n  f.count.oninput = updateCount;\n  updateSize(); updateCount();\nreturn f;}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1129,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":806,"value":"// Feel free to edit this to add more options in the form above\n// Did you find something really cool? Let me know!\nruleArr = \n[\n  {name:\"original\", \n   rule:[{numNN:[1,2,3,4]}, \n         {numNNN:[1,2,3,4]}]},\n  {name:\"tangle\", \n   rule:[{numNN:[1], numNNN:[0]}, \n         {numNN:[0], numNNN:[1]}]},\n  {name:\"two-color moss\", \n   rule:[{numNN:[0], numNNN:[1]}, \n         {numNN:[2], p:0.01}]},\n  {name:\"horizontal & vertical fuzz\", \n   rule:[{numNN:[1], numNNN:[0]}, \n         {numNN:[1], numNNN:[2], p:0.5}]},\n  {name:\"diamond flakes\", \n   rule:[{numNN:[2,3,4], numNNN:[2,3,4]}, \n         {numNN:[1], numNNN:[2]}, \n         {numNN:[1], numNNN:[0], p:0.1}]}\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":1170,"value":"md`## Code\n\nI'm not too happy with the user interface for adding rules. Is there a more intuitive approach? Maybe something which allows for inputting and editing time-varying rules? (I've set up [something crude to generate a semi-interesting thumbnail](#multipleRulesGenerator).) I'd be happy to hear what you think [on twitter](https://twitter.com/blockspins).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":884,"value":"function testCustom(custom) {\n  function isBadNumArr(arr) {\n    return (arr !== undefined && \n            (!Array.isArray(arr) || arr.some(d => typeof d !== \"number\")))\n  }\n  try {\n    const r = JSON.parse(custom);\n    if (r.some(\n      ({numNN,numNNN,p}) => \n      isBadNumArr(numNN) || isBadNumArr(numNNN) ||\n      (p !== undefined && typeof p !== \"number\")\n    ))\n      throw new Error('invalid custom rule');\n    return true;\n  } catch(e) {\n    return false; // invalid rule \n  }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":876,"value":"customRule = testCustom(object.custom) ?\n  JSON.parse(object.custom) :\n  [{numNN:[5]}] // a do-nothing rule to (kind-of) stop execution","pinned":true,"hidden":false,"mode":"ojs"},{"id":703,"value":"rules = (object.rules === \"custom\" ? customRule : ruleArr[+object.rules].rule).map(\n  ({numNN, numNNN, p}) => \n  ({nn,nnn}) => \n  (numNN === undefined || numNN.some(d => d === nn)) && \n  (numNNN === undefined || numNNN.some(d => d === nnn)) && \n  (p === undefined || Math.random() < p)\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":695,"value":"function funcRules(nn,nnn) {\n  // rules should encode something in DNF https://en.wikipedia.org/wiki/Disjunctive_normal_form\n  return !rules.reduce((a2,v2) => a2 || v2({nn,nnn}), false);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":323,"value":"function render(ctx, particles, {imageData, values, vEmpty, vStuck, vFloat, vStuck2, vFloat2}) {\n    for (let i = 0; i < values.length; i++) {\n      values[i] = vEmpty;\n    }\n    for (var i = 0; i < count; i++) {\n      const x = particles.x[i];\n      const y = particles.y[i];\n      const stuck = particles.stuck[i];\n      if ((x+y) % 2)\n        values[y * width + x] = stuck ? vStuck : vFloat;\n      else\n        values[y * width + x] = stuck ? vStuck2 : vFloat2;\n    }\n    ctx.putImageData(imageData, 0, 0);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":6,"value":"field = {\n  reset;\n  const field = new Uint8Array(width * height);\n  const fcenterX = Math.floor(width / 2);\n  const fcenterY = Math.floor(height / 2);\n  qt.add([fcenterX,fcenterY]);\n  field[fcenterX + fcenterY * width] = 1;\n  return field;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":8,"value":"particles = {\n  reset;\n  const particles = {\n    x: new Uint16Array(count),\n    y: new Uint16Array(count),\n    stuck: new Uint8Array(count)\n  };\n  for (let i = 0; i < count; i++) {\n    if (fast.fast)\n      // resetSingleParticle2(particles, i);\n      resetSingleParticle3(particles, i);\n    else\n      resetSingleParticle(particles, i);\n  }\n  return particles;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"resetSingleParticle = (particles, i) => {\n  let x = Math.floor(Math.random() * width);\n  let y = Math.floor(Math.random() * height);\n\n  while (field[y * width + x]) {\n    x = Math.floor(Math.random() * width);\n    y = Math.floor(Math.random() * height);\n  }\n\n  particles.x[i] = x;\n  particles.y[i] = y;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":461,"value":"// particles come in from further out\nresetSingleParticle2 = (particles, i) => {\n  let x = Math.floor(4*(Math.random()-0.5) * width);\n  let y = Math.floor(4*(Math.random()-0.5) * height);\n\n  while (field[y * width + x]) {\n    x = Math.floor(Math.random() * width);\n    y = Math.floor(Math.random() * height);\n  }\n\n  particles.x[i] = x;\n  particles.y[i] = y;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":504,"value":"// particles arrive from boundary\nresetSingleParticle3 = (particles, i) => {\n  let x,\n      y;\n  switch (Math.floor(Math.random()*4)) {\n    case 0: {\n      y=0;\n      x = Math.floor(width*Math.random());\n      break;\n    }\n    case 1: {\n      y = height - 1;\n      x = Math.floor(width*Math.random());\n      break;\n    }\n    case 2: {\n      x=0;\n      y = Math.floor(height*Math.random());\n      break;\n    }\n    case 3: {\n      x=width - 1;\n      y = Math.floor(height*Math.random());\n      break;\n    }\n  }\n  particles.x[i] = x;\n  particles.y[i] = y;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":477,"value":"function alone(i) {\n  let cx = particles.x[i];\n  let cy = particles.y[i];\n\n  let lx = cx - 1;\n  let rx = cx + 1;\n  let ty = cy - 1;\n  let by = cy + 1;\n\n  if (\n    cx <= 0 ||\n    cx >= width-1 ||\n    lx <= 0 ||\n    lx >= width-1 ||\n    rx <= 0 ||\n    rx >= width-1 ||\n    cy <= 0 ||\n    cy >= height-1 ||\n    ty <= 0 ||\n    ty >= height-1 ||\n    by <= 0 ||\n    by >= height-1\n  ) {\n    return true;\n  }\n\n  cy *= width;\n  by *= width;\n  ty *= width;\n\n  const nn = field[cx + ty] + field[lx + cy] + field[rx + cy] + field[cx + by];\n  const nnn = field[lx + ty] + field[lx + by] + field[rx + ty] + field[rx + by];\n  if (navigator.userAgent.match('HeadlessChrome')) \n    return multipleRules(nn,nnn);\n  return funcRules(nn,nnn);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":956,"value":"multipleRules = {\n  reset;\n  return multipleRulesGenerator();\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":973,"value":"function multipleRulesGenerator() {\n  let t = 0;\n  return (nn,nnn) => {\n    const rules = ruleArr[t < 5000 ? 0 : (t < 30000 ? 4 : 3)].rule.map(\n      ({numNN, numNNN, p}) => \n      ({nn,nnn}) => \n      (numNN === undefined || numNN.some(d => d === nn)) && \n      (numNNN === undefined || numNNN.some(d => d === nnn)) && \n      (p === undefined || Math.random() < p)\n    )\n    ++t;\n    // rules should encode something in DNF https://en.wikipedia.org/wiki/Disjunctive_normal_form\n    return !rules.reduce((a2,v2) => a2 || v2({nn,nnn}), false);\n  }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":16,"value":"updateSingleParticle = i => {\n  let x = particles.x[i];\n  let y = particles.y[i];\n\n  x += Math.random() > 0.5 ? 1 : -1;\n  y += Math.random() > 0.5 ? 1 : -1;\n\n  if (x < 0 || y < 0 || x >= width || y >= height) {\n    resetSingleParticle(particles, i);\n  } else {\n    particles.x[i] = x;\n    particles.y[i] = y;\n  }\n\n  if (!alone(i)) {\n    particles.stuck[i] = 1;\n    field[y * width + x] = 1;\n  }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":348,"value":"updateSingleParticleFast = i => {\n  let x = particles.x[i];\n  let y = particles.y[i];\n\n  const [closex, closey] = qt.find(x,y);\n  const dx = x-closex,\n        dy = y-closey;\n  const rsq = dx*dx + dy*dy;\n  // const rsq = Math.abs(dx) + Math.abs(dy);\n  if (rsq > 2) {\n    const [dx,dy] = getPointFromCircle(rsq);\n    x += dx;\n    y += dy;\n  } else {\n    x += Math.random() > 0.5 ? 1 : -1;\n    y += Math.random() > 0.5 ? 1 : -1;\n  }\n  \n  if (x < 0 || y < 0 || x >= width || y >= height) {\n    resetSingleParticle3(particles, i);\n    x = particles.x[i];\n    y = particles.y[i];\n  } else {\n    particles.x[i] = x;\n    particles.y[i] = y;\n  }\n\n  if (!alone(i)) {\n    particles.stuck[i] = 1;\n    field[y * width + x] = 1;\n    qt.add([x,y]);\n  }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":352,"value":"qt = {\n  fast;\n  reset;\n  return d3.quadtree().extent([[0,0],[width,height]]);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":422,"value":"function getPointFromCircle(rsq) {\n  let x = (Math.random()-0.5);\n  let y = (Math.random()-0.5);\n  let r0sq = x*x + y*y;\n  while (r0sq > 1) {\n    x = (Math.random()-0.5);\n    y = (Math.random()-0.5);\n    r0sq = x*x + y*y;\n  }\n  const r0 = Math.sqrt(0.5*rsq/r0sq);\n  return [Math.round(x*r0), Math.round(y*r0)];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":20,"value":"count = fast.count","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"height = Math.floor(width * 0.75)","pinned":true,"hidden":false,"mode":"ojs"},{"id":188,"value":"width = Math.floor(window.innerWidth * fast.size)","pinned":true,"hidden":false,"mode":"ojs"},{"id":208,"value":"hsl2rgb = require(await FileAttachment(\"hsl-rgb-1.0.0.js\").url())","pinned":false,"hidden":false,"mode":"ojs"},{"id":1230,"value":"function hsl2Value(h, s, l) {\n  const [r, g, b] = hsl2rgb(h, s, l);\n  return new Uint32Array(new Uint8ClampedArray([r, g, b, 255]).buffer)[0];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":581,"value":"import {form} from '@mbostock/form-input@151'","pinned":false,"hidden":false,"mode":"ojs"},{"id":276,"value":"d3 = require('d3-quadtree')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}
</article></body></html>