2a:null 2b:["$","title",null,{"children":"Pachinko Tree | Job van der Zwan | Observable"}] 30:Tb46,function* pachinkoTreeVisual(visibility, width = 1000, nodeSize = 40) { const height = (nodeSize * 1.5 + Math.sqrt(16) * nodeSize * 3) | 0; const { ctx } = getCtx(width, height, Math.min(width, 800)); ctx.canvas.style.imageRendering = "auto"; const initTree = () => { const array = [1]; for (let i = 1; i < 16; i++) { array[i] = i + 1; } const buffer = [-Infinity]; const depth = Math.ceil(Math.log2(array.length)); const length = 2 ** (depth + 1); for (let i = 0; i < length / 2; i++) buffer[i] = 0; for (let i = length / 2; i < length; i++) buffer[i] = -Infinity; return [array, buffer, depth]; }; let [array, buffer, depth] = initTree(); const drawTree = async () => { await visibility(); ctx.fillStyle = "#EEE"; ctx.fillRect(0, 0, width, height); ctx.fillStyle = "#000"; ctx.lineJoin = "round"; ctx.font = `${(nodeSize * 0.8) | 0}px serif`; ctx.textAlign = "center"; let k = 1; ctx.beginPath(); const pos = (i) => { const y = Math.sqrt(2 ** (i + 0.5)) * nodeSize * 3 - 2 * nodeSize; const y2 = Math.sqrt(2 ** (i + 1.5)) * nodeSize * 3 - 2 * nodeSize; const x = width * 0.5 - 2 ** (i - 1) * nodeSize * 1.5 + nodeSize * 0.75; const x2 = width * 0.5 - 2 ** i * nodeSize * 1.5 + nodeSize * 0.75; return [x, y, x2, y2]; }; // draw connections ctx.strokeStyle = "#444"; ctx.lineWidth = nodeSize >> 3; for (let i = 0; i < depth; i++) { let [x, y, x2, y2] = pos(i); const kEnd = k + (1 << i); while (k++ < kEnd) { ctx.moveTo(x, y); ctx.lineTo(x2, y2); ctx.moveTo(x, y); ctx.lineTo(x2 + nodeSize * 1.5, y2); x += nodeSize * 1.5; x2 += nodeSize * 3; } ctx.stroke(); } // draw nodes/leaves ctx.strokeStyle = "#FFF"; ctx.lineWidth = nodeSize >> 1; k = 1; for (let i = 0; i <= depth; i++) { let [x, y] = pos(i); const kEnd = k + (1 << i); while (k < kEnd) { const val = buffer[k++]; const text = Number.isFinite(val) ? val : "."; ctx.strokeText(text, x, y); ctx.fillText(text, x, y); x += nodeSize * 1.5; } } return ctx.canvas; }; while (true) { [array, buffer, depth] = initTree(); yield drawTree(); yield Promises.tick(2000, drawTree()); const { random } = Math; for (let n = 0; n < array.length; n++) { const v = array[n]; let k = 1; for (let i = 0; i < depth; i++) { ++buffer[k]; yield Promises.tick(400, drawTree()); const l = buffer[k + k]; const r = buffer[k + k + 1]; k += k; if (l > r) k++; else if (l === r) k += (random() * 2) | 0; } buffer[k] = v; yield Promises.tick(400, drawTree()); } yield Promises.tick(4000, drawTree()); } }31:T60d,The [pseudo-blue noise algorithm](https://observablehq.com/@jobleonard/pseudo-blue-noise) works by repeatedly splitting an array of values in two and recursing on each array. That means it can be rewritten as a tree that does the shuffling as part of inserting values (with the caveat that the maximum number of values being inserted needs to be known at the time of creating the tree). Here is how it works: 1. Given an array of indices to shuffle, we initiate a perfect binary tree the size of `2 ** (1 + Math.ceil(Math.log2(indices.length)))`. Or in other words: the next power of two, rounded up. 2. The leaves of the tree either are empty (represented by `-Infinity` in the implementation below) or store an index. This is also why we needed a tree this size: because we need to be able to store all indices in the leaves. 3. The nodes of the tree store the count of indices that passed through them (in other words, how many non-empty leaves they have) 4. When inserting an index, we start at the root, then repeatedly pick the lowest-valued child. In case of a tie we choose a child at random 5. To extract our shuffled sequence, we read the leaves from left to right and skip the empty leaves The idea of indices tumbling down the tree, picking child nodes at random reminded me of the metal balls falling down a vintage [pachinko machine](https://en.wikipedia.org/wiki/Pachinko), so I decided to call this a pachinko tree. Plus, the name wasn't taken yet and I liked the sound of it, so I figured I'd better claim it before it's too late.32:T6ce,## TODO (Some notes-to-self with ideas of how I might refine the data structure in the future) - if we have leaves or nodes that should always stay empty, they can be marked with `Infinity`, since all (finite) values will be lower than them and `toIndices()` ignores non-finite values. - left and right nodes will never differ by more than one, because in that case the next time an index passes through their parent it will always pick the other side. If we wish to optimize for space we can use this reduce the size of the nodes to two bits: the parent node will store -1 if left is ahead, 1 if right is ahead, and zero if they are tied. We can represent this as `0b11`, `0b01` and `0b00`. We can use `0b10` to mark a node as "never pick this" (so, per the previous point, "infinity"). Note that this approach requires storing the leaves in a separate array, since the indices we wish to store in them are probably larger than two bits. - encode 2D rectangle sizes in nodes/leaves, with randomized rounding directions upon splitting (like with the pbn noise algorithm). This should be done when initiating the tree. - use a four-way tree instead of a binary tree for 2D representations. This has the bonus advantage of spontaneously representing a quad tree in Z-order traversal (tangent: I just discovered this on my own and am slightly upset that nobody told me in the decade and a half that I have been playing around with quad trees). - come up with ways of biasing the coin flips in ways that improve noise quality. For example, try taking into account presence of indices in surrounding nodes/leaves (see also best-candidate approaches based on nearest neighbors in other blue noise algorithms) ## Extra Indices projected into 2D:33:[] 2e:{"id":"16b2aff98f75afef","slug":"pachinko-tree","title":"Pachinko Tree","thumbnail":"e9106196a6b22df94fcab163a9e132fb7c9a6806227516d11350cf5e6bb8202f","access_level":"public","create_time":"$D2021-11-28T20:03:05.456Z","update_time":"$D2026-07-28T08:21:59.450Z","view_time":null,"first_public_time":"$D2021-11-29T10:58:48.716Z","has_unpublished_edits":null,"fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":"starter_2024"},"version":606,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}],"members":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Pachinko Tree","cells":[{"id":95,"value":"# Pachinko Tree\n\n*Pseudo-blue noise as a data structure*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":451,"value":"pachinkoTreeVisual(visibility, 1000, 40)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":124,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"class PachinkoTree {\n constructor(array) {\n const buffer = [-Infinity];\n const depth = Math.ceil(Math.log2(array.length));\n const length = 2 ** (depth + 1);\n for (let i = 0; i < length / 2; i++) buffer[i] = 0;\n for (let i = length / 2; i < length; i++) buffer[i] = -Infinity;\n\n const { random } = Math;\n for (const v of array) {\n let k = 1;\n for (let i = 0; i < depth; i++) {\n ++buffer[k];\n const l = buffer[k + k];\n const r = buffer[k + k + 1];\n k += k;\n if (l > r) k++;\n else if (l === r) k += (random() * 2) | 0;\n }\n buffer[k] = v;\n }\n\n this.buffer = buffer;\n this.depth = depth;\n }\n\n toIndices() {\n const output = [];\n const { buffer } = this;\n for (let i = buffer.length / 2; i < buffer.length; i++) {\n if (Number.isFinite(buffer[i])) output.push(buffer[i]);\n }\n return output;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":343,"value":"Let's compare the output to a [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle), which produces uniform distributions:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":80,"value":"{\n const w = 2 ** (Math.log2(width) | 0);\n const h = w >> 3;\n await visibility();\n const range = [0];\n for (let i = 1; i < w; i++) {\n const j = (Math.random() * (i + 1)) | 0;\n range[i] = range[j];\n range[j] = i;\n }\n yield label(\n \"Range of indices shuffled with a Fisher-Yates shuffle (uniform distribution)\",\n render(w, h, (x, y) => toU32Gray((y * w) / h < range[x] ? 255 : 0)),\n Math.min(800, width)\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"{\n const w = 2 ** (Math.log2(width) | 0);\n const h = w >> 3;\n await visibility();\n const range = [0];\n for (let i = 1; i < w; i++) range[i] = i;\n const indices = new PachinkoTree(range).toIndices();\n return label(\n \"Range of indices shuffled with a pachinko tree\",\n render(\n w,\n h,\n (x, y) => toU32Gray((y * w) / h < indices[x] ? 255 : 0),\n Math.min(800, width)\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":475,"value":"{\n const w = width;\n const h = 100;\n const indices = Uint32Array.from({ length: w * h }, (_, i) => i);\n\n for (let i = 0; i < w * h; i++) {\n const j = (Math.random() * (i + 1)) | 0;\n const t = indices[i];\n indices[i] = indices[j];\n indices[j] = t;\n }\n const len = indices.length;\n\n return label(\n \"Range of indices shuffled with Fisher-Yates, projected into 2D in left-to-right, top-to-bottom order\",\n render(\n w,\n h,\n (x, y) => {\n const n = indices[x + y * w];\n return toU32Gray((n / len) * 255);\n },\n Math.min(400, width)\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":477,"value":"{\n const w = width;\n const h = 100;\n const indices = new PachinkoTree(\n Uint32Array.from({ length: w * h }, (_, i) => i)\n ).toIndices();\n const len = indices.length;\n\n return label(\n \"Range of indices shuffled with a pachinko tree, projected into 2D in left-to-right, top-to-bottom order\",\n render(\n w,\n h,\n (x, y) => {\n const n = indices[x + y * w];\n return toU32Gray((n / len) * 255);\n },\n Math.min(400, width)\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":586,"value":"{\n const w = width;\n const h = 100;\n const indices1D = new PachinkoTree(\n Uint32Array.from({ length: w * h }, (_, i) => i)\n ).toIndices();\n const len = indices1D.length;\n\n const hIndices = hcurve(w, h).toIndices();\n\n const indices2D = Uint32Array.from(\n { length: w * h },\n (_, i) => indices1D[hIndices.gridToLine[i]]\n );\n return label(\n \"Range of indices shuffled with a pachinko tree, projected into 2D with H-curve\",\n render(\n w,\n h,\n (x, y) => {\n const n = indices2D[x + y * w];\n return toU32Gray((n / len) * 255);\n },\n Math.min(400, width)\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":604,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":319,"value":"## Dependencies\n\nNot needed for the data structure, but used for the visualizations","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":550,"value":"import {render, label, getCtx, toU32Gray} from \"@jobleonard/canvas-tools\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":508,"value":"import {hcurve} from \"@jobleonard/curve-tools\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 2f:"$2e:body"